Breaking News
Blog

# How random is random?

NO RATINGS
View Comments: Newest First | Oldest First | Threaded View
Page 1 / 3   >   >>
User Rank
Author
re: How random is random?
1/8/2012 5:18:44 AM
NO RATINGS
And here is Intel digital implementation, based on presentation in last Hot Chips 23. Entropy source is from existing digital network of power supply and uses latch metastability which apparently dominated by thermal noise. CBC-AES-MAC used to get better entropy (2:1 compression 256 bit from 512 bit). Reseeds AES-CTR from external source every 512 bits. 11 Clocks per 128 bits @800Mhz gives: (128 bit * 800Mclks/s)* 1/(11 clks)* 1/2[for compression] ~ 4.5 Gbps (do you agree?) http://www.hotchips.org/archives/hc23/HC23-papers/HC23.18.2-security/HC23.18.210-Random-Numbers-Cox-Intel-e.pdf

User Rank
Author
re: How random is random?
1/7/2012 12:00:45 AM
NO RATINGS
Good Let's summarize and maintain big picture as we have more details and thanks for contribution to this discussion. So far, combining TRNG outputs can potentially have issue for 2 reasons: 1. TRNG sources and output of each source can be corelated or affected by environment. So accumulation of TRNG source or sources doesn't seem a good strategy. 2. Potentially combining distributions (like adding random numbers) also results in Normal distribution (as it is seen in nature and Central Limit Theorem confirms). One good solution offered: To get around TRNG source corelation, one can use TRNG seed to generate PRNG (like 1024 bits) and then use Hash function to make 128 bit of true entropy. From one of the links sent, it looks like PRNG (stream cipher) with a TRNG seed can pass FIPS and has performance of few Mbps (perhaps max 10 Mbps). To test RNG, we have FIPS standard, so if it passes then "it's enough". Hmm probably you noticed, we are giving up on TRNG and moving to hybrid TRNG/PRNG. Let's trigger more questions: What else you found from articles that doesn't work... What is highest performance a PRNG in market as there are increasing demand in number of sessions? Let's say we need continuous 1Gbps performance, and cannot use latency in our advantage. How would you do it? SW cannot be solution as they are not "secure enough". How long is the period of PRNG before it repeats, for example LFSR has period ...very difficult to calculate, how would you go about in calculation based on polynomial representation of LFSR for example! In cryptography, we assume algorithms are known, so we need irreversible function unfortunately PRNG Fucntion is predictable but may be "good enough" before intruder can use it. Have you thought of irreversible function?

User Rank
Author
re: How random is random?
1/6/2012 4:08:03 PM
NO RATINGS
The following link points to a few research papers describing techniques for that: http://www.odysci.com/search/?q=true+random+number+generator

User Rank
Author
re: How random is random?
1/6/2012 3:00:14 PM
NO RATINGS
Nice tip and nice to read, but be aware of the alinea right above figure2, saying: A third factor affecting the quality of the RNG is the random source itself. As both periodic and aperiodic elec- tromagnetic noise exists inside a computer system, there may be correlation in the output sequence as the result of coupling of periodic noise from the power supply, clocks, crosstalk, thermal effects and so on. This issue is not addressed in this work. This is a HUGE problem for FPGA RNG implementation and I would never advise this solution... Maybe it is better to use one of the old devices as shown on www.cryptomuseum.com ;-)

User Rank
Author
re: How random is random?
1/6/2012 9:18:48 AM
NO RATINGS
and here http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/prng_cdt07.pdf

User Rank
Author
re: How random is random?
1/6/2012 9:12:54 AM
NO RATINGS
the real question, imho, is how do you test for randomness ? a lfsr passes lots of the random tests, apart from the one about being predictable from past info. a noise source passes the predictable from the past issue, but does not have equal probability of all numbers occurring, they are typically gausian. can I recommend this as a starting place http://www.dspguide.com/ch2/6.htm

User Rank
Author
re: How random is random?
1/6/2012 8:57:13 AM
NO RATINGS
But if you use DPA attack method on your chip, I bet you can guess the "unique" serial number. I would approach with caution the word "Unclonable".

User Rank
Author
re: How random is random?
1/6/2012 8:44:01 AM
NO RATINGS
Like all "True" RNGs, these ones are not "true random" (and here I'm just talking about the seed generation phase - obviously the PRNG phase producing the bulk of the data is not "true"). They are simply random enough to pass a qualification test. But since no qualification test for true randomness could ever finish, it's obvious that we are just talking about "random enough". Of course, "good enough" is good enough. Once you have reached the stage that it's statistically more likely to be crushed by a meteor than for your security code to be broken, you don't really need to worry about making your RNG more random. The irony here is that it's easier to be sure you have reached this stage with PRNGs than with "true" RNGs. Part of the reason for that is your point here about correlation of the entropy sources - as they typically /are/ correlated. All "true" entropy sources rely on some external events or effects, such as measuring thermal noise or the aforementioned ring oscillators. Other popular choices are things like the timing of incoming data on networks, or keys on a keyboard. Typically you only take a few bits from each source. Each bit will have less than a bit's worth of entropy - clearly the more significant bits will be less "random" than the less significant bits (that's why you only use a few). And there will be some correlation between samples from the same noise source - the timing of consecutive keystrokes will be related, as will the samples based on thermal noise. So if you just collect together 128 bits from these sources, you do not have 128 bits of entropy. So what you do is collect something like 1024 bits - then you reduce it to 128 bits using a secure hash algorithm which will preserve most of the entropy. That way you can get very close to 128 bits of true entropy. But it is very hard to calculate (or even guesstimate) the entropy of the sources and their correlation, to know how many bits you need to hash together.

User Rank
Author
re: How random is random?
1/5/2012 8:34:36 PM
NO RATINGS
It *is* a fascinating subject.

User Rank
Author
re: How random is random?
1/5/2012 8:34:14 PM
NO RATINGS
I am waiting for lawyers to patent their own hairstyles... :-)

Page 1 / 3   >   >>
More Blogs
Foxconn is apparently considering smartphone manufacturing in the U.S., raising questions about what deals the Trump Administration is offering.
Hot Chips has a talk for every hot computing topic this year as well as great human networking with many of the most interesting people in the chip business.
Lauro Rizzatti, Nasr Ullah (Samsung), Bruce Cheng (Starblaze), and Robert Kaye (ARM) discuss emulation for data storage chips, system IP, and embedded software.
Suits and counter-suits make for good entertainment from the sidelines, but do they help consumers?
The Internet of Things needs an open standard for unlicensed band connectivity.
Like Us on Facebook
EE Times on Twitter