Dan Kaminsky on the RSA key-vulnerability

Dan Kaminsky sez,

There's been a lot of talk about some portion of the RSA keys on the Internet being insecure, with "2 out of every 1000 keys being bad". This is incorrect, as the problem is not equally likely to exist in every class of key on the Internet. In fact, the problem seems to only show up on keys that were already insecure to begin with -- those that pop errors in browsers for either being unsigned or expired. Such keys are simply not found on any production website on the web, but they are found in high numbers in devices such as firewalls, network gateways, and voice over IP phones.

It's tempting to discount the research entirely. That would be a mistake. Certainly, what we generally refer to as "the web" is unambiguously safe, and no, there's nothing particularly special about RSA that makes it uniquely vulnerable to a faulty random number generator. But it is extraordinarily clear now that a massive number of devices, even those purportedly deployed to make our networks safer, are operating completely without key management. It doesn't matter how good your key is if nobody can recognize it as yours. DNSSEC will do a lot to fix that. It is also clear that random number generation on devices is extremely suspect, and that this generic attack that works across all devices is likely to be followed up by fairly devastating attacks against individual makes and models. This is good and important research, and it should compel us to push for new and interesting mechanisms for better randomness. Hardware random number generators are the gold standard, but perhaps we can exploit the very small differences between clocks in devices and PCs to approximate what they offer.

Primal Fear: Demuddling The Broken Moduli Bug (Thanks, Dan!)


  1. Forgive me if this is a dumb question, but is TrueCrypt a decent system on windows-based computers, or am I kidding myself?

    1.  It’s probably as good as you’re going to get.

      And it has the advantage of being open source so, unlike most commercial products, the code can be reviewed/inspected for security holes.

  2. Maybe we could look into the chaotic dynamics of many-body systems based on nonlinear equations of motion that that make the logistic map look like a kindergarten exercise. Just sayin’.

  3. The problem with the vast majority of today’s chaotic pseudorandom number generators is that they are based on maps that only have one future-facing translation vector per position (ie. x_1 = r x_0 (1 – x_0) gives a constant vector of (x_1 – x_0). That’s the epitome of a pattern. If you use many-body dynamics constrained to an n-sphere, then the number of future-facing translation vectors per position becomes infinite (ie. the number of possible positions on an n-sphere is infinite). These so-called old school “dynamical” maps have static backgrounds. That’s a bad thing, people.

    Forget clocks, they do not all behave the same and do not guarantee the same kind of “randomness” on various computer platforms. Either go chaotic, go full-blown quantum mechanical, or go home.

    1. P.S. In the event that the notion of switching from a chaotic system with one future-facing translation vector per position to a chaotic system with infinite future-facing translation vectors per position is novel, don’t bother trying to scoop me. I already put up the fully-developed cross-platform template-based C++ public domain source on Google Code (yes it successfully passes NIST testing), and I am writing the paper in your annoying English+Mathlish at my leisure, just in case the 4th International Interdisciplinary Chaos Symposium on “Chaos and Complex Systems” is interested.

    2. To be honest, this is so beyond me i can’t tell if it is Star Trek techno-babble or the genuine article.

      1. It’s not babble. I found one other PRNG called Trident (circa 2010) that relies on the idea of a future-directed per-position translation vector set of size larger than one. They implement this by incrementing their map’s auxiliary parameters by some constant value at each time step.

        The Trident system is nothing like mine under the hood. They use a single particle system evolved by linear equations of motion (it’s not even nonlinear like the logistic map, and so I’m still confused by their choice). I use a three+ particle system evolved by nonlinear equations of motion. In terms of quality of pseudo-unpredictability, it’s like apples and oranges.

        Plus, they explictly claim that Trident is unpredictable, which is total utter nonsense. The only unpredictable system is a quantum mechanical system. All PRNGs (ie. softwares) are only pseudo-unpredictable. Yes, they may be difficult to predict, but they are **NEVER** unpredictable. Anyone claiming otherwise is either high on crack, or high on themselves.

        If we want to “whip it out and compare”, all I have to do is increase the number of particles in my system to 101 and implement it on the GPU to keep it “fast”. At that point, my orange becomes a steak dinner with caviar and Dom Perignon. In other words, my system does not suffer from bounds on its complexity. It can be made arbitrarily close to random by changing one variable, depending on one’s computation resources and patience. Still, I would never be so stunned as to ever claim that it’s fully random (ie. fully unpredictable).

        The reason that I am so aggravated is because this confusion between pseudo-random and random is precisely what gets people who generate keys into messes in the first place (the point of this blog post).

        Still, I have to give them priority for seeing that a future-directed per-position translation vector set of size one is so obviously silly that it’s dumbfounding how no one else could have seen this in the 30+ years that these maps have been popular. I scratch my head in utter confusion.

        1. P.S. I made it out of high school without my Algebra (they basically gave me a diploma and kicked me out after my third try), and I did not go to university. So, don’t sell yourself short. This isn’t rocket science. This is also why I’m totally dumbfounded as to how armies of PhD-wielding mathematicians didn’t see this far sooner.

          1. Oh this is so rich… some of the authors of Trident — the groundbreaking chaotic pseudo-random number generator — have published in Chaos, Solitons & Fractals. I guess the “real” mathematicians were just too busy bashing everyone who published in CS&F to even bother reading the papers. LULZ!! Irony.

  4. ” Such keys are simply not found on any production website on the web,”

    I have seen web sites with pop-up warnings that they were expired or inaccurate (certificates for, say, http://www.domain.com instead of domain.com) that absolutely were “production” web sites and were legit.  Obviously they weren’t perfectly administered websites, but to say they “are simply not found” isn’t accurate.

    1. Yeah, I literally laughed out loud at that one.

      I deal with supposedly secure systems at dozens of hospitals.  The majority of them are using keys that are expired and/or inaccurate.  I have filed  many a trouble ticket, and never has one been fixed.  Ever!  They invariably tell me “just tell your browser to make an exception and don’t worry about it.”

      The only way that Dan’s comment would make any sense is if you changed it to say “such keys are rarely found at successful on-line payment sites.”  Most shopping cart sites use valid certs because otherwise some small fraction of their customers would go elsewhere.

Comments are closed.