DUHK: Don’t Use Hard-Coded Keys

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.

31 thoughts on “DUHK: Don’t Use Hard-Coded Keys

  1. 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.

  2. 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.

      1. 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.

    1. 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.

  3. 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.

        1. 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.

    1. 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.

  4. 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.

  5. 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.

  6. “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

    1. 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.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s