The title reads like the name of a lecture in cryptography 101 or the first rule of Crypto Club. ‘DUHK‘ is in fact neither of those but the name of a recently disclosed vulnerability in a pseudorandom number generating algorithm (PNRG) that was until recently part of the federal standard X9.31.
Random numbers are essential to viable cryptography. They are also hard to obtain leading to solutions like using the physical properties of semiconductors or decaying matter, that are governed by quantum effects. The next best solution is to log events that are hard to predict like the timing of strokes on a keyboard. The weakest source of randomness is math, which makes sense, because one of maths most popular features is its predictability. Mathematical solutions have the one redeeming quality of being able to produce a lot of numbers that look random to a human in a short time.
PNRGs require a starting point from which they begin to produce their output. Once this seed is known the produced sequence becomes predictable.
The X9.31 PNRG is an algorithm that is used in various cryptographic algorithms and has been certified in the Federal Information Processing Standards for decades until it was dropped from the list of approved standards in 2016. The researchers behind DUHK found out that the standard allowed the seed to be stored in the source code of its implementation. The next step was to look for software that did this and they found X9.31 in an older version of FortiOS running on VPN gateways.
Should I be Worried?
Probably, maybe not. The analysis (PDF) published by the team behind DUHK notes that the vulnerability is limited to legacy implementations and doesn’t allow to takeover the device running them, only to eavesdrop on ‘secure’ connections. The scope of this is much more limited than exploits like remote code execution via bluetooth. It is on the other hand providing a strong case for handling standards and technical certifications with extreme scrutiny. The teams conduct also gives insight into the best practises for white-hat hacking which are frequently discussed around here. And they have a great theme song.
*PRNG
*GPRN
How to properly seed a PRNG is not a trivial problem at all. Either using a fixed value or an easily predictable value (like the time) are insecure. I faced this in my Orthrus v2 design and actually included an avalanche transistor entropy source to it to solve the problem. Fortunately the v3 design includes a controller that has a hardware RNG in it that’s trustworthy.
TIL about avalanche transistors….many thanks.
>controller that has a hardware RNG in it that’s trustworthy
or so you think
my fav is using boot time, while broadcasting that boot time in the cleartext ;-)
Well, ATMel/Microchip has a datasheet that shows their design testing methodology. The bad news is that you can only get a copy by request.
Duh! ‘K
There are two alternative technical terms for people who hardcode keys or seeds: (1) noobs, (2) dip-shits.
When I find someone making a mistake, I usually try the gentle approach so they understand but are not embarrassed. One of the few exceptions is when I find someone relatively senior has done or proposes to do this. Then I figure they don’t grok the subtle approach, and I make a big noise. It stuns me how often it happens.
Three:
You left out “forced to do this by management to save time/money/whatever” DAMHIKT
This matches my experience, these things usually play out like this:
Management: We need crypto!
Devs: Good crypto is hard. And expensive.
Management: Just do something simple, we can improve it later.
…
Also crypto often is an afterthought that is poorly bolted onto a system that should have been designed around security from the beginning.
When hard coding keys to read your encrypted software licence files, at least use an asymmetric algorithm, so the hard coded key can’t be used to generate new files. (even better use a digital signature) It’s still a broken DRM system because the the hard-coded public keys can be replaced with a different public key, but it doesn’t look as dumb as hard coded private keys.
https://xkcd.com/221/
http://dilbert.com/strip/2001-10-25
I Agree. We should definitely have some kind of limits on that.
BTW, Christian Trapp only has 6 posts- all from October 11, 2017 forward.
I third the motion.
I changed my name to Afroman and my comment is being moderated,
Perhaps let thing be as they are and just require an extra step when the association between and email address and screen name changes.
I don’t think it’s a big issue that net that is probably because no one else uses my screen name (so far). HAD staff should be able to get a better idea because of the use of cookies.
That’s because you have to guess the e-mail: or in the case of Afroman, visit the linked site (The reason his name is yellow) and find an about-person somewhere… there shall be an email address if supplied.
Then right-click the yellow link and copy-link-location in the menu, paste that into the URL… As long as everything matches, all good.
Example:
His email is displayed here [link]
He is called Afroman
his name links to: http://www.afrotechmods.com/
It redirects to the sub page: /tutorials/
Oh and as for some of the ones without yellow name handles: try to guess the E-mail, if their name looks like it should have @email-server.com or equivalent on the end… try G-Mail first and then try a few other sites… failing that, then skip onto the next victim… ;)
Sir, I’d suggest changing your writing style because it makes a good cloak. It reveals a lot about an individual!
So easy, even a new born can do it!
notes about padding here and at the end as the content is below:
That’s because you have to guess the e-mail: or in the case of Afroman, visit the linked site (The reason his name is yellow) and find an about-person somewhere… there shall be an email address if supplied.
Then right-click the yellow link and copy-link-location in the menu, paste that into the URL… As long as everything matches, all good.
Example:
His email is displayed <a href="http://www.afrotechmods.com/"here [link]
He is called Afroman
his name links to: http://www.afrotechmods.com/
It redirects to the sub page: /tutorials/
Oh and as for some of the ones without yellow name handles: try to guess the E-mail, if their name looks like it could be an email compatable name… try G-Mail first and then try a few other sites… failing that, then skip onto the next victim… ;)
Sir, I’d suggest changing your writing style because it makes a good cloak. It reveals a lot about an individual!
So easy, even a new born can do it!
EOF regarding padding
I started programming with BASIC as a young kid. I was writing games for a TRS-80 at school.
I soon got bored with BASIC and moved to machine code,
One of the first challenges in machine code was “how do I generate random numbers”. I had previously noted that the BASIC random function often produced predictable sequences when used to generate a game play field.
I was stumped for a while and then reverted to getting the player to enter a long sequence of key strokes before the game play starts and counting clock cycles between each press (truncating the higher significant bits).
Now there’s lots of tools. In VHDL I use a Linear Feedback Shift Register (LFSR) but that wouldn’t be useful for encryption.
It’s still the case that the best sources for random are far away from code and logic.
The term pseudo-random has always irked me because the definition of random is “unpredictable” and that is a binary status. So pseudo-random means like unpredictable but actually predictable or in more binary terms it means “not random” while suggesting some association with random. It’s kind of like “politically correct” which is another oxymoron.
“pseudo” means “not genuine” so “pseudo-random” means “not actually random” which seems quite appropriate, no?
Yes, but random is a binary state. Either something *is* random or it *is not* random. There is no grey area. It would be like saying a number is *like* an integer.
I disagree, some routines generate an easily predictable pattern (eg 1,2,3…) and others are quite difficult to predict, i.e. it is difficult to reverse engineer the algorithm. A pseudo random generator has quality, some more than others. In the end though the best random numbers come from analogue chaotic creatures and devices.
I’m afraid I don’t understand your quibble. The term “pseudo-random” doesn’t mean “like random”, it means “not random”.
Pseudo in this case means “seeded”.
Well, it’s not hard to find simple PRNGs that are adequate for low impact situations. I faced this with my Crazy Clock project, where because of the low Clock speed the Arduino one was just too slow. I wound up finding one on the Internet that works fine, but this is not a security context – it’s just making behavior patterns for a clock.
To make random cryptographic keys you seriously need to step up your game from that.
It’s funny. At the Hack A Day-NYC event, one individual mentioned using a random number routine for the Arduino(!)! to accomplish the usual things. I promptly commented that the typical ones, including the ones for that thing, are broken. About all I can report is a few moments of dead air. I strongly suspect that no one believed me. And this is before hearing about this one. The only places where the random number routines are not broken is probably Linux, as it would be appropriately wired.
PRNG, not PNRG. One’s a PseudoRandom Number Generator, the other is a either a random generator of pseudo-numbers, or a pseudo-numeric generator of randomness. Neither of which is what we want.
“Because a PRNG’s raw output is never used directly for cipher generation, the PRNG itself does not need to possess the property of unpredictability.
It is the key-stream that needs to exhibit unpredictability rather than the generator’s own stream of bits. Put another way, the requirement for unpredictability is shifted from the bit- to the byte-level.
Given a string of bytes, an adversary must not be able to guess what the next byte-value in the sequence will be or to deduce previous values from subsequent ones. This is the essence of cryptographic security.” – Conrad Kayne
If your using the PRNG for a non security application (Monte Carlo Etc.) hard coded seeds are often fine.
Philosophical aside: Monte Carlo “random” numbers don’t really need to be random — in fact for any given problem, there’s probably an optimal set of non-random points that will give a best answer.
Analogy: think of doing numerical integration, which is basically what a Monte Carlo experiment is. You can just find the value of the function at a bunch of points, multiply by the step size, and sum them up. Or you can pick the points cleverly and get significantly better results (Gaussian quadrature and all it’s variants).
The point is, for any given problem there is a (at least one) optimal location for the points in the parameter space — such that averaging the function’s value at those points gives the best approximation to the integral/average.
When you do a Monte Carlo sim, you’re just saying “hell if I know what the best choice of points is! I’ll just pick ’em randomly.” Which is cool for a general-purpose integration method, but it’s sub-optimal for any given problem.
And _none_ of this uses any actual properties of random numbers at all — except that a well-chosen (uniform?) distribution is likely to span all of the relevant parameter space.
(Something here about importance sampling should go here.)
So, yeah. What @James Lawson said. (I feel better having gotten that off my chest.)
Indeed, I always hard-code MC seeds for repeatability. Trying again with the same / different seeds is super helpful when debugging.