Re: How do embedded linux-rt systems fill their entropy/randomness pools?

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]


On Tue, 19 Jun 2012, Thomas Gleixner wrote:

<snip>
> 
> There are enough papers out there, which cover the inherent randomness
> of todays cpu systems, so go wild with finding the relevant points
> which can be abused to a stick some value into the pools fast
> path.
> 
> Thanks,
> 
> 	tglx

Here a quick shot of the current state of our ESRNG (Embarrasingly Simple Random Number Generator) - a trivial entropy extracter. There actually are not random number generators on this planet - they all just extract entropy from some poison process - but the name "generator" seems to be accepted.... this is unfortunately work stalled in progress - no more than prototype code and some early papers.

Here is a run on my current working box from this morning.

idle system:

hofrat@debian:/tmp$ time ./esrng -t 2 -c 4000 -r 5000 -j 9000 -q 0 -p 10000 -s 3 -l 1 -u 10000
min:1,max:22306,wsize:4216
r: 167347, d: 152621 N:7361 (data_int_10000_2t_jw10q0_c4000_r5000_N3000_j9000.3)
real    0m33.942s
user    0m8.141s
sys     0m7.708s
hofrat@debian:/tmp$ /home/hofrat/ESRNG/test_code/ent data_int_10000_2t_jw10q0_c4000_r5000_N3000_j9000.3
Entropy = 7.998823 bits per byte.

Optimum compression would reduce the size
of this 167347 byte file by 0 percent.

Chi square distribution for 167347 samples is 273.57, and randomly
would exceed this value 20.26 percent of the times.

Arithmetic mean value of data bytes is 127.2821 (127.5 = random).
Monte Carlo value for Pi is 3.136495644 (error 0.16 percent).
Serial correlation coefficient is 0.014924 (totally uncorrelated = 0.0).

so 5k/s on an idle system - note that the entropy extraction rate goes down on
loaded systems as the entropy extraction is proportional to the execution time
of the extratro so if it gets no CPU time then it extract little entropy - but
in general highly loaded systems have sufficient sources of entropy.

loaded system (io load)

hofrat@debian:/tmp$ time ./esrng -t 2 -c 4000 -r 5000 -j 9000 -q 0 -p 10000 -s 4 -l 1 -u 10000
min:1,max:39148,wsize:4218
r: 167931, d: 152037 N:7420 (data_int_10000_2t_jw10q0_c4000_r5000_N3000_j9000.4)real    0m34.505s
user    0m8.241s
sys     0m7.656s
hofrat@debian:/tmp$ uptime
 14:48:37 up 10 days, 15:17,  9 users,  load average: 8.46, 3.20, 1.17
hofrat@debian:/tmp$ /home/hofrat/ESRNG/test_code/ent data_int_10000_2t_jw10q0_c4000_r5000_N3000_j9000.4
Entropy = 7.998924 bits per byte.

Optimum compression would reduce the size
of this 167931 byte file by 0 percent.

Chi square distribution for 167931 samples is 250.41, and randomly
would exceed this value 56.93 percent of the times.

Arithmetic mean value of data bytes is 127.3719 (127.5 = random).
Monte Carlo value for Pi is 3.141346291 (error 0.01 percent).
Serial correlation coefficient is 0.019616 (totally uncorrelated = 0.0).

loaded system (CPU load of 16++ on a 8 core box)

hofrat@debian:/tmp$ time ./esrng -t 2 -c 4000 -r 5000 -j 9000 -q 0 -p 10000 -s 5 -l 1 -u 10000
wmove: 35870min:1,max:117000,wsize:63174
r: 28762, d: 291206 N:1 (data_int_10000_2t_jw10q0_c4000_r5000_N3000_j9000.5)
real    63m51.208s
user    43m53.533s
sys     81m43.550s
hofrat@debian:/tmp$ /home/hofrat/ESRNG/test_code/ent data_int_10000_2t_jw10q0_c4000_r5000_N3000_j9000.5
Entropy = 7.993978 bits per byte.

Optimum compression would reduce the size
of this 28762 byte file by 0 percent.

Chi square distribution for 28762 samples is 238.02, and randomly
would exceed this value 77.02 percent of the times.

Arithmetic mean value of data bytes is 127.2472 (127.5 = random).
Monte Carlo value for Pi is 3.129563947 (error 0.38 percent).
Serial correlation coefficient is 0.005237 (totally uncorrelated = 0.0).


Parameters:

the somewhat ugly list of arguments to esrng is due to the lack of 
autocalibration (a still unsolved issue really) and so this nees some manual
tuning. Keeping the extraction stable is done by the runtime control loop
(a windowing controler using the occurence of a race condition as the feedback
signal to adjust the loop length (statistical race "control") to race on)

Summary: on an idle MP system or io-loaded system a few kilobyte per second is
resonable - on UP this can be much less (on some embedded UP processors it can
go down to 100byte/s). for high CPU load it will fade more or less to 0 (it
is running with the lowest priority in the system in user-space at the moment)

If anybody has time to play with this and test it - I would be greatful for
input - works for me and if you have enough time (weeks...) to generate GB size
samples you can (provided the calibration was correct) pass the NIST test-suit
- atleast some of our data sets did pass - but at this point consider it 
insecure until proven otherwise. The test-outputs shown above are from ent
 (random.org test-suit). But if you have no RNG/entropy source at all I'm 
comfortable claiming this is better than nothing :) 

for those interested - just dumped the current state of ESRNG code (after
adding comments in the code) to http://www.opentech.at/papers/ESRNG.tar.bz2 

  have fun - get confused !

thx!
hofrat
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/


[Other Archives]     [Linux Kernel Newbies]     [Linux Driver Development]     [Fedora Kernel]     [Linux Kernel Testers]     [Linux SH]     [Linux Omap]     [Linux Kbuild]     [Linux Tape]     [Linux Input]     [Linux Kernel Janitors]     [Linux Kernel Packagers]     [Linux Doc]     [Linux Man Pages]     [Linux API]     [Linux Memory Management]     [Linux Modules]     [Linux Standards]     [Kernel Announce]     [Netdev]     [Git]     [Linux PCI]     Linux CAN Development     [Linux I2C]     [Linux RDMA]     [Linux NUMA]     [Netfilter]     [Netfilter Devel]     [SELinux]     [Bugtraq]     [FIO]     [Linux Perf Users]     [Linux Serial]     [Linux PPP]     [Linux ISDN]     [Linux Next]     [Kernel Stable Commits]     [Linux Tip Commits]     [Kernel MM Commits]     [Linux Security Module]     [AutoFS]     [Filesystem Development]     [Ext3 Filesystem]     [Linux bcache]     [Ext4 Filesystem]     [Linux BTRFS]     [Linux CEPH Filesystem]     [Linux XFS]     [XFS]     [Linux NFS]     [Linux CIFS]     [Ecryptfs]     [Linux NILFS]     [Linux Cachefs]     [Reiser FS]     [Initramfs]     [Linux FB Devel]     [Linux OpenGL]     [DRI Devel]     [Fastboot]     [Linux RT Users]     [Linux RT Stable]     [eCos]     [Corosync]     [Linux Clusters]     [LVS Devel]     [Hot Plug]     [Linux Virtualization]     [KVM]     [KVM PPC]     [KVM ia64]     [Linux Containers]     [Linux Hexagon]     [Linux Cgroups]     [Util Linux]     [Wireless]     [Linux Bluetooth]     [Bluez Devel]     [Ethernet Bridging]     [Embedded Linux]     [Barebox]     [Linux MMC]     [Linux IIO]     [Sparse]     [Smatch]     [Linux Arch]     [x86 Platform Driver]     [Linux ACPI]     [Linux IBM ACPI]     [LM Sensors]     [CPU Freq]     [Linux Power Management]     [Linmodems]     [Linux DCCP]     [Linux SCTP]     [ALSA Devel]     [Linux USB]     [Linux PA RISC]     [Linux Samsung SOC]     [MIPS Linux]     [IBM S/390 Linux]     [ARM Linux]     [ARM Kernel]     [ARM MSM]     [Tegra Devel]     [Sparc Linux]     [Linux Security]     [Linux Sound]     [Linux Media]     [Video 4 Linux]     [Linux IRDA Users]     [Linux for the blind]     [Linux RAID]     [Linux ATA RAID]     [Device Mapper]     [Linux SCSI]     [SCSI Target Devel]     [Linux SCSI Target Infrastructure]     [Linux IDE]     [Linux SMP]     [Linux AXP]     [Linux Alpha]     [Linux M68K]     [Linux ia64]     [Linux 8086]     [Linux x86_64]     [Linux Config]     [Linux Apps]     [Linux MSDOS]     [Linux X.25]     [Linux Crypto]     [DM Crypt]     [Linux Trace Users]     [Linux Btrace]     [Linux Watchdog]     [Utrace Devel]     [Linux C Programming]     [Linux Assembly]     [Dash]     [DWARVES]     [Hail Devel]     [Linux Kernel Debugger]     [Linux gcc]     [Gcc Help]     [X.Org]     [Wine]

Add to Google Powered by Linux

[Older Kernel Discussion]     [Yosemite National Park Forum]     [Large Format Photos]     [Gimp]     [Yosemite Photos]     [Stuff]