Almost 20 years ago, I wrote a paper that pointed to a potential flaw in the ANSI X9.17 RNG standard. Now, new research has found that the flaw exists in some implementations of the RNG standard.
Here’s the research paper, the website—complete with cute logo—for the attack, and Matthew Green’s excellent blog post on the research.
Martin • October 31, 2017 11:13 AM
Just to be clear… there are two kinds of random number generators.
The first (as described) is first seeded, the iterative output used is a stream of other numbers. The longer a stream that cannot be reversed to determine what the seed was, the better the generator.
The second type of generator does not use a seed, and outputs a sequence of numbers that do not repeat. The best generators output a succession of numbers that are physically impossible to predict.
Both types are needed.
That the first type is used to produce keys AT ALL, is itself a problem. Period.
It’s funny, what some people call SNAKE OIL but other people do not.
handle_x • October 31, 2017 11:43 AM
Are there ANY types of RNG’s? Are they not all PRNG’s?
(observes snowball fight from snow fort)
Clive Robinson • October 31, 2017 1:33 PM
@ handle_x,
Are there ANY types of RNG’s? Are they not all PRNG’s?
There are TRNGs that use the entropy from physical sources that are –currently– believed to be non determanistic in nature.
You have to be carefull though, there is usually a lot of noise much of which is predictable in physical sources and the “true entropy” you are looking for can be very small. In between you have what you might call “faux entropy” where the noise appears to an external observer to be nondetermanistic, however to an observer inside the system the determanism is apparent. Such a source might be the noise from a Switching Power Supply getting in past the line filtering to the “noise source” device.
Most TRNGs “raw signal” from the “noise source device” will fail the modern statistical tests such as “Die Harder”. One of the worst offenders are “on chip” based ring oscilators that are gated together. To cover up the failings the chip designers put the raw output through a crypto function such as a hash. However this DOES NOT INCREASE ENTROPY it just sprinkles it with magic pixie dust that will get the result through the likes of “Die Harder”.
The “Care and feeding of TRNGs” is an indepth subject and makes the breeding of rare orchids or even panders look easy.
blablablaginger • October 31, 2017 1:59 PM
@Tatütata, good quality true RNGs are quite economical to implement in hardware. Effects like thermal noise or shot noise or phase noise between uncorrelated oscillators is relatively easy to exploit once you have some control of the hardware. RNGs are only really a hard challenge in software where things are constrained to be deterministic.
Clive Robinson • October 31, 2017 2:22 PM
@ Tatütata,
Now, how do you provide guaranteed good seeds on an IoT node?
That is both easy and very very hard…
The easy way is when programing the NV memory in the device at the factory you use an “electronic serial number” and use that as an initial seed for a RAM based “entropy pool” or “state array”. That’s about it for “easy”.
How you update the pool/array is not as easy as it might first appear as it requires a nondetermanistic physical source of “noise” to be debiased and filtered to give you a true entropy source, “to stir the pool/array”…
How you stop the NV memory serial number being reused or being predictable to a level three (state level) attacker like a SigInt agency of a superpower or major country is another hard part of the problem.
Hidden away behind that is the hardest problem of all which is “Initial KeyGen” that will often end up being either the only or master KeyMat in the device.
As an example when you plug the device in and turn it on it will these days require a Public Key be produced. In modern systems that would be an RSA Cert around 4,096-16,384 bits in length… If the physical sources ib the IoT node only generate one or two bits of entropy a second or longer you could be waiting more than four and a half hours to get sufficient entropy… Most users will not wait even a small fraction of this time…
neill • October 31, 2017 3:11 PM
@Clive
i guess when you have an IoT with a camera builtin you could just use a superfast readout of the ccd to get ‘some random noise’ e.g. you use only 3×3 bits from the 24 per pixel = 2MP camera would get you 2.3 Mbyte ‘noise’, that you can flip & mix alike AES
now of course after many years the ccd could be ‘burnt in’ from a strong lightsource …
wumpus • October 31, 2017 6:36 PM
@Neill:
Assuming you get the image in JPEG, the least significant digits will be much more random (hopefully you can crank the quality factor much higher than sensor/lens can justify). Also a quick hash and subsample would likely be better, if you have a sufficiently fast hash.
JG4 • October 31, 2017 7:14 PM
@Neill and Clive – the use of a camera as a noise source is clever. because of the large number of channels, it is a good noise source. we could assume that you wrap it in tinfoil (or the much less expensive modern equivalent) to block out light (so as to start with mostly dark noise) and any thought-control beams (which might taint the randomness). the problem of detrending otherwise random data and removing any other elements of non-randomness is Kalman’s bailiwick. his contributions aren’t many standard deviations from Shannon’s. they could have given him a Nobel prize in physics. btw, I hope that the usual suspects noticed that Judyth Vary Baker is another of the Hungarians who had an outsized influence in science.
The Seminal Kalman Filter Paper (1960)
http://www.cs.unc.edu/~welch/kalman/kalmanPaper.html
In 1960, R.E. Kalman published his famous paper describing a recursive solution to the discrete-data linear filtering problem. Since that time, due in large part to advances in digital computing, the Kalman filter has been the subject of extensive research and application, particularly in the area of autonomous or assisted navigation.
Thanks to John Lukesh, who diligently transcribed the paper into electronic form, we are able to make available a PDF version of this seminal paper. (480KB). This PDF is best viewed with Acrobat Reader.
http://www.cs.unc.edu/~welch/kalman/media/pdf/Kalman1960.pdf
Please see John’s explanation and notes about the transcription.
http://www.cs.unc.edu/~welch/kalman/kalmanPaperTranscription.html
…
@Clive – when they shot the Brazilian electrician in the head, it appears that they got it wrong. can’t recall if anyone ever answered for that. maybe they erroneously ID’d him as Carlos or some other outlaw designated as “shoot on sight.” apparently the safeguards are light-years from what is appropriate.
@225 – we could think of science as being an adaptive system, where models are constructed, tested and converged for accuracy and precision. I think that Clive pointed out that even though cosmology cannot be replicated, cosmological models can be tested against publicly available data sets. and tested again any time that new data become available. given enough iterations of model testing and convergence, science will produce an arbitrarily accurate model of reality. or an arbitrarily accurate fit to experimental data, including any systematic errors.
the origins of psychology were pseudoscience with all kinds of crazy ideas (otherwise known as models) that were not particularly testable, nor accurate. the discipline, such as it is, has come a long way. methods like fMRI are science fiction from the perspective of the 1950’s. a lot more science fiction is in the pipeline.
for auld lang syne
https://www.nakedcapitalism.com/2017/10/links-103117.html
…
Big Brother is Watching You Watch
BlackBerry CEO Promises To Try To Break Customers’ Encryption If The US Gov’t Asks Him To TechDirt
Calgary police cellphone surveillance device must remain top secret, judge rules CBC
whatever • October 31, 2017 10:18 PM
Are there ANY types of RNG’s? Are they not all PRNG’s?
“Hardware” or “True” random number generators derive their bytestream from physical sources of entropy. There are lots of sources of usually unwanted noise, some of them are better suited for harvesting of entropy. Such sources include Zener diodes, certain kinds of gas discharge tubes, vacuum valves, Geiger tubes coupled to weak sources of radioactivity. Even a carbon film resistor in the megaohm range can generate practical levels of noise.
The signal from a noise source is analog in nature, so it is conditioned (amplified, filtered, limited) in hardware, sampled by an ADC, a comparator or a timer-counter and processed in the digital domain, including whitening and sanity checks. In modern implementations, a physical RNG output is used to feed a PRNG for whitening and stretching, especially when the required bandwidth exceeds the capability of a noise source. Entropy quantity management may be implemented. Tamper detection and prevention circuits, logic and other measures (shielding) may be present.
Coin flips, dice throws, card shuffles and lotto machine operation can also be considered hardware RNGs.
There are two big classes of entropy sources. One, such as coin flips and dice rolls, derives its unpredictability from a sheer amount of minute factors that affect the outcome of each sample. The second class is based on processes that are non-deterministic in nature, such as radioactive decay.
handle_x • November 1, 2017 1:42 AM
“Coin flips, dice throws, card shuffles and lotto machine operation can also be considered hardware RNGs.”
But all of those you mentioned are also approximations, you know. 🙂
Real random is so good you can’t measure it.
Bob Paddock • November 1, 2017 7:48 AM
@JG4, @Clive, @blablablaginger
@JG4:
Not a lot of people understand how to use a Kalman ‘Filter’ correctly.
Someone from the avionics industry that does wrote an tutorial on the subject:
http://www.avrfreaks.net/forum/tut-theory-what-kalman-filter.
@Clive:
“The “Care and feeding of TRNGs” is an indepth subject … ”
Are there any actual books, texts etc. that deal with this, beyond what you write here about Magic Pixie Dust (that I’ve been collecting form the archives)?
@blablablaginger
“… noise between uncorrelated oscillators … ”
Keeping devices in proximity from producing correlation is harder than it appears, for reasons that are not clearly understood.
Martin • November 1, 2017 12:10 PM
Just to be clear… there’s no such thing as a random number.
There are only sources of random numbers. Given a number, it is impossible to determine if it was extracted from a source of random numbers. Numbers do not have entropy. A succession of digits extracted from calculation of the number π satisfy criteria for randomness, but they are not random.
handle_x • November 1, 2017 5:03 PM
good point.
Grauhut • November 1, 2017 5:32 PM
For Linux the ChaosKey is trendy.
AJWM • November 1, 2017 5:49 PM
The second class is based on processes that are non-deterministic in nature, such as radioactive decay.
There is some possibility that radioactive decay is affected by neutrino flux (both depend on the weak nuclear force). Minute annual variations observed in lab is more likely experimental error due to other environmental effects than the slight variation in distance from the Sun in Earth’s elliptical orbit, but if a star were to go supernova within a couple of light years the neutrino flux would be immense, and likely cause a very observable difference in radioactive decay rates.
If there were anyone left around to observe them, that is.
handle_x • November 1, 2017 9:48 PM
If you have all data, is there such a thing as random?
Wael • November 2, 2017 4:44 AM
Hard-coded keys is a dumb idea, and I’ve seen my share of it. Once upon a time I was “told” to embed a key in the binary, which I refused to do. Got in trouble for it, but I still did not do it! I did something a bit more secure. Something not vulnerable to static analysis or binary dump and search.
The second is that government crypto certifications are largely worthless.
A lot of certification programs fall in that category.
Wael • November 2, 2017 5:10 AM
I’m curious to know how it was patched. Did they just use one of the remaining three standards and left it at that?
so the actually guessing space is typically only about 2^20 at most.
Off by 48,576. Oh, changing logarithm base 🙂 Strange! 45678, rearranged.
@CallmeLateForSupper,
I actually did the math. My turn this time (October 13)
PS: Anyone knows how to get iOS to use a proper “? href not working with the new “ they introduced! How annoying! It used to work in the past.
225 • November 2, 2017 6:44 AM
@JG4 the criticism I have of the Alison’s interrogation guide is that it claims to be based on science but it’s hypotheses are not falsifiable. Probably because they are psychologists and not scientists.
Ratio • November 2, 2017 6:55 AM
@Wael,
Anyone knows how to get iOS to use a proper “?
You could disable “Smart Punctuation” under Settings → General → Keyboards.
(Or use " every time you need an ” in HTML. Whatever works for you. :P)
225 • November 2, 2017 7:04 AM
@Martin that’s a weird way of talking, what do random number generators generate?
I agree that for a TRNG you test the method not the output, but you can still call the output a random number.
Wael • November 2, 2017 8:23 AM
@Ratio,
Thanks. I knew about &xxx; as I used it with other characters. For some reason it didn’t click with me in this situation.
As for the “Smart quote” thing… I didn’t know or look at settings. Smart, eh? Obviously not smart enough to deduce my intentions from <a href=”…
One of reasons I didn’t look at settings is my expectations that my settings wouldn’t change when I update the OS. Another new “feature” is if I have BT disabled, as I usually do, then cycle plane mode, BT is turned on again. I don’t like that either.
Bob Paddock • November 2, 2017 12:13 PM
“This article [Psychokinesis Research October 2017] describes the evolution of experimental studies of mind-matter interaction, commonly referred to as psychokinesis (PK). It ranges from early dice studies through to effects on random number generators (RNGs), both in the lab and in the field. It concludes with a description of recent investigations of the role of consciousness on quantum processes such as photon entanglement. Meta-analytic evidence is given to understand the strength of the findings. Theoretical considerations are also covered.”
handle_x • November 2, 2017 1:28 PM
“what do random number generators generate?”
The output. But calling it random is where folks go wrong. It’s “randomesque”
225 • November 3, 2017 3:39 AM
@handle_x
If I had a measurement generator (like a digital thermometer) what would I call the output? The measurement.
I don’t get why people feel like they have to treat a random number like Lord Voldemort.
RichardH • November 3, 2017 8:32 AM
@225
that’s a weird way of talking, what do random number generators generate?
Random sequences.
[insert appropriate qualifiers for “random” in both cases]
How could you quantify the “randomness” of a single number?
hmm • November 3, 2017 2:12 PM
“I don’t get why people feel like they have to treat a random number like Lord Voldemort.”
By acknowledging each exist only rhetorically? :0
Per your analogy, you can measure anything you want but you’re still approximating.
“Random” is probably impossible. “Random enough for x” is the significance I think.
A Nonny Bunny • November 3, 2017 4:54 PM
@Martin
Just to be clear… there’s no such thing as a random number.
There are only sources of random numbers.
That sounds contradictory.
And in any case, it’s a matter of definition/interpretation. A random number is a number generated by a random process/source. A random number is not in and of itself “random”, is probably what you’re getting at. But “randomly-generated number” is unnecessarily long when everyone, pedantics included, know what you mean if you say “random number”.
@225
@Martin that’s a weird way of talking, what do random number generators generate?
That’s another thing. Who says it’s a generator of random numbers, and not a random generator of numbers?
Clive Robinson • November 4, 2017 7:21 AM
@ hmm,
Per your analogy, you can measure anything you want but you’re still approximating.
Err be careful, there will be howls from some quaters, but many now accept the fact that when you get down small enough the world is not continuous. That said you have the issue of measurment, which gets progressively harder and for various reasons less accurate[1].
@ handle_x,
The output. But calling it random is where folks go wrong. It’s “randomesque”
There is no reliably quantafiable definition for either word. Saying “Random is something that looks random or is ranndomesque” whilst not entirely usless –in that it refrences an observer– is what it boils down to. From that people have made indications about things being determanistic or non determanistic process but again only as far as the observer of the output is concerned. Thus it is entirely possible that there is absolutly no such thing as “random” just determanism an observer can not see. It’s from this that we get the notion of CS-PRNGs. One such that is fairly easy to contemplate is AES in CTR mode, where at some point you change the key to prevent certain typs of theoretical attack.
Thus you can pull back to the mathmatical notion of a map that is arranged in an unknown way to an observer, also not visable to the observer is the selection mechanism by which the map is addressed to read out from the map the value the observer gets presented with. In effect you have atleast two unknown quantaties to the observer, the only question thus arising is how do you keep the observer from determaning one or both or all of the unknown quantities. One way is the notion of bounded and unbounded maps. If a map is bounded in theory the observed sequence will be repeated at some point etc.
[1] See for instanse the coastal mapping issue of an islands coast, it’s length gets longer the shorter your ruler is. Then ask yourself the implication of not being able to make the ruler shorter… It’s a problem not to dissimilar to tinking about infinity which drove a number of quite promising mathematicians quite mad (and probably still does).
Subscribe to comments on this entry
Sidebar photo of Bruce Schneier by Joe MacInnis.
Tatütata • October 31, 2017 11:06 AM
This work was supported by the National Science Foundation under grants CNS-1651344, CNS-1505799, CNS-1408734, CNS-1010928, CNS-1228443, and EFMA-1441209; The Office of Naval Research under contract N00014-14-1-0333; the Mozilla Foundation; and a gift from Cisco.
It’s interesting that two government departments (NSF, ONR) supports research that helps prevent potential (?) excesses by another one (NSA).
Are you a government with a desire for large scale decryption capabilities?
Weakening, sabotaging, backdooring, or frontdooring encryption standards may harm both the overall security of your country as well as your reputation!
Cute!
Now, how do you provide guaranteed good seeds on an IoT node?