Re: [Cryptography] Techniques for malevolent crypto hardware
On Sun, 8 Sep 2013 15:22:32 -0400 "Perry E. Metzger" wrote: > Ah, now *this* is potentially interesting. Imagine if you have a > crypto accelerator that generates its IVs by encrypting information > about keys in use using a key an observer might have or could guess > from a small search space. Oh, and of course, if you're doing a DSA style algorithm, you can leak information in your choice of random nonce. This is yet more reason to force protocols to use nonces that are deterministic based on context, and to enforce that. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On Sep 9, 2013, at 9:17 AM, Kent Borg wrote: >> Which brings into the light the question: Just *why* have so many random >> number generators proved to be so weak. > > Your three cases left off an important one: Not bothering to seed the PRNG at > all. I think the Java/Android cryptographic (!) library bug that just came > up was an instance of that. > > I think the root of the problem is that programs are written, and bugs > squashed, until the program works. Maybe throw some additional testing at it > if we are being thorough, but then business pressures and boredom says ship > it. > > That won't catch a PRNG that wasn't seeded, nor a hashed password that wasn't > salted, the unprotected URL, the SQL injection path, buffer overflow, etc. Good observations, but I think you're being too pessimistic. All the examples you give *could* be tested - but not by "ignorant black box testing" - testing that ignores not just what's inside the box, but the actual requirements on what the box is supposed to produce. A non-seeded PRNG, and even one seeded with a very small amount of entropy, will be caught by a test that runs multiple instances of the PRNG from the system starting state and ensures that the ensemble of first outputs (and, for good measure, the first *couple* of outputs) has the right statistics. Similarly, a test that inserts the same password into multiple instances of the same system in the same state can check that the hashed versions have the right statistics. No, these can't catch deliberate attack code which produces random-looking values that the attacker can predict - no test can. But it will catch a broad class of common errors. The others aren't cryptographic issues and require different approaches. The fact that there are bad testing practices - and that those bad practices are used all too often - doesn't mean there aren't good practices, and that they could not be applied. Where the testing is bad because of ignorance of what is actually important and how to test for it, learning from the failures of the past is the way forward - which was exactly the point of "PRMG failures" classification. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On 09/08/2013 11:56 PM, Jerry Leichter wrote: Which brings into the light the question: Just *why* have so many random number generators proved to be so weak. Your three cases left off an important one: Not bothering to seed the PRNG at all. I think the Java/Android cryptographic (!) library bug that just came up was an instance of that. I think the root of the problem is that programs are written, and bugs squashed, until the program works. Maybe throw some additional testing at it if we are being thorough, but then business pressures and boredom says ship it. That won't catch a PRNG that wasn't seeded, nor a hashed password that wasn't salted, the unprotected URL, the SQL injection path, buffer overflow, etc. Computer security is design, implementation, and skepticism. But unless you can sell it with a buzzword... -kb ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On 9/09/13 06:42 AM, James A. Donald wrote: On 2013-09-09 11:15 AM, Perry E. Metzger wrote: Lenstra, Heninger and others have both shown mass breaks of keys based on random number generator flaws in the field. Random number generators have been the source of a huge number of breaks over time. Perhaps you don't see the big worry, but real world experience says it is something everyone else should worry about anyway. Real world experience is that there is nothing to worry about /if you do it right/. And that it is frequently not done right. When you screw up AES or such, your test vectors fail, your unit test fails, so you fix it, whereas if you screw up entropy, everything appears to work fine. Precisely. It is hard, perhaps impossible, to have test suite that makes sure that your entropy collection works. One can, however, have a test suite that ascertains that on any two runs of the program, most items collected for entropy are different except for those that are expected to be the same, and that on any run, any item collected for entropy does make a difference. Does your unit test check your entropy collection? When I audited the process for root key ceremony for CAcert, I worried a fair bit about randomness. I decided the entropy was untestable (therefore unauditable). So I wrote a process such that several people would bring their own entropy source. E.g., in the one event, 3 sources were used, by independent people on independent machines: * I used a sha-stream of laptop camera on dark paper [0] * Teus used sound card driver [1] * OpenSSL's RNG. The logic was that as long as one person was honest and had a good source, and as long as our mixing was verifiable, the result would be good. Then, I wrote a small C program to mix it [2]; as small as possible so a room full of techies could spend no more than 10 minutes checking it on the day [3]. The output of this was then fed into the OpenSSL script to do the root key. (I'm interested if anyone can spot a flaw in this concept.) iang [0] This idea from Jon Callas from memory, the idea is that the lack of light and lack of discrimination between pixels drives the photocells into a quantam uncertainty state. [1] John Denker's sound card driver. [2] As an amusing sidenote, I accidentally used | to mix the bytes not ^. My eyeball tests passed at 2 sources but at 3 sources it was starting to look decidedly wonky. [3] It was discussed on the group at this time, it was advised that the output of the mix should be sha'd, which I eventually agreed with, but I don't think I did in the event. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On Sep 8, 2013, at 9:15 PM, Perry E. Metzger wrote: >> I don't see the big worry about how hard it is to generate random >> numbers unless: > > Lenstra, Heninger and others have both shown mass breaks of keys based > on random number generator flaws in the field. Random number > generators have been the source of a huge number of breaks over time. > > Perhaps you don't see the big worry, but real world experience says > it is something everyone else should worry about anyway. Which brings into the light the question: Just *why* have so many random number generators proved to be so weak. If we knew the past trouble spots, we could try to avoid them, or at least pay special care to them during reviews, in the future. I'm going entirely off of memory here and a better, more data-driven approach, might be worth doing, but I can think of three broad classes of root causes of past breaks: 1. The designers just plain didn't understand the problem and used some obvious - and, in retrospect, obviously wrong - technique. (For example, they didn't understand the concept of entropy and simply fed a low-entropy source into a whitener of some kind - often MD5 or SHA-1. The result can *look* impressively random, but is cryptographically worthless.) 2. The entropy available from the sources used was much less, at least in some circumstances (e.g., at startup) than the designers assumed. 3. The code used in good random sources can look "strange" to programmers not familiar with it, and may even look buggy. Sometimes good generators get ruined by later programmers who "clean up the code". -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On 09/08/2013 09:15 PM, Perry E. Metzger wrote: Perhaps you don't see the big worry, but real world experience says it is something everyone else should worry about anyway. I overstated it. Good random numbers are crucial, and like any cryptography, exact details matter. Programmers are constantly making embarrassing mistakes. (The recent Android RNG bug, was that Sun, Oracle, or Google?) But there is no special reason to worry about corrupted HW RNGs because one should not be using them as-is, there are better ways to get good random data, ways not obvious to a naive civilian, but still well known. Snowden reassured us when he said that good cryptography is still good cryptography. If that includes both hashes and cyphers, then the fundamental components of sensible hybrid RNGs are sound. Much more worrisome is whether Manchurian Circuits have been added to any hardware, no matter its admitted purpose, just waiting to be activated. -kb ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On 2013-09-09 11:15 AM, Perry E. Metzger wrote: Lenstra, Heninger and others have both shown mass breaks of keys based on random number generator flaws in the field. Random number generators have been the source of a huge number of breaks over time. Perhaps you don't see the big worry, but real world experience says it is something everyone else should worry about anyway. Real world experience is that there is nothing to worry about /if you do it right/. And that it is frequently not done right. When you screw up AES or such, your test vectors fail, your unit test fails, so you fix it, whereas if you screw up entropy, everything appears to work fine. It is hard, perhaps impossible, to have test suite that makes sure that your entropy collection works. One can, however, have a test suite that ascertains that on any two runs of the program, most items collected for entropy are different except for those that are expected to be the same, and that on any run, any item collected for entropy does make a difference. Does your unit test check your entropy collection? ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On Sun, 08 Sep 2013 20:34:55 -0400 Kent Borg wrote: > On 09/08/2013 06:16 PM, John Kelsey wrote: > > I don't think you can do anything useful in crypto without some > > good source of random bits. > > I don't see the big worry about how hard it is to generate random > numbers unless: Lenstra, Heninger and others have both shown mass breaks of keys based on random number generator flaws in the field. Random number generators have been the source of a huge number of breaks over time. Perhaps you don't see the big worry, but real world experience says it is something everyone else should worry about anyway. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On 09/08/2013 06:16 PM, John Kelsey wrote: I don't think you can do anything useful in crypto without some good source of random bits. I don't see the big worry about how hard it is to generate random numbers unless: a) You need them super fast (because you are Google, trying to secure your very high-speed long lines), or b) You are some embedded device that is impoverished for both sources of entropy and non-volatile storage, and you need good random bits the moment you boot. On everything in between, there are sources of entropy. Collect them, hash then together and use them to feed some good cryptography. If you seem short of entropy, look for more in your hardware manual. Hash in any local unique information. Hash in everything you can find! (If the NSA knows every single bit you are hashing in, no harm, hash them in anyway, but...if the NSA has misunderestimated any one of your bits...then you scored a bit! Repeat as necessary.) I am thinking pure HW RNGs are more sinful than pure SW RNGs, because real world entropy is colored and hardware is the wrong place to fix that. So don't buy HW RNGs, buy HW entropy sources (or find them in your current HW) and feed them into a good hybrid RNG. On a modern multi-GHz CPU the exact LSB of your highspeed system counters, when the interrupt hits your service routine, has uncertainty that is quite real once the you push the NSA a few centimeters from your CPU or SoC. Just sit around until you have a few network packets and you can have some real entropy. Wait longer for more entropy. In case you did notice, I am a fan of hybrid HW/SW RNGs. -kb P.S. Entropy pools that are only saved on orderly shutdowns are risking crash-and-playback attacks. Save regularly, or something like that. P.P.S. Don't try to estimate entropy, it is a fool's errand, get as much as you can (within reason) and feed it into some good cryptography. P.P.P.S. Have an independent RNG? If it *is* independent, no harm in XORing it in. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On Sun, Sep 08, 2013 at 06:16:45PM -0400, John Kelsey wrote: > I don't think you can do anything useful in crypto without some > good source of random bits. If there is a private key somewhere > (say, used for signing, or the public DH key used alongside the > ephemeral one), you can combine the hash of that private key into > your PRNG state. The result is that if your entropy source is bad, > you get security to someone who doesn't compromise your private > key in the future, and if your entropy source is good, you get > security even against someone who compromises your private key in > the future (that is, you get perfect forward secrecy). Nice in theory of course, but in practice applications don't write their own PRNGS. They use whatever the SSL library provides, OpenSSL, GnuTLS, ... If we assume weak PRNGS in the toolkit (or crypto chip, ...) then EDH could be weaker than RSA key exchange (provided the server's key is strong enough). The other concern is that in practice many EDH servers offer 1024-bit primes, even after upgrading the certificate strength to 2048-bits. Knee-jerk reactions to very murky information may be counter-productive. Until there are more specific details, it is far from clear which is better: - RSA key exchange with a 2048-bit modulus. - EDH with (typically) 1024-bit per-site strong prime modulus - EDH with RFC-5114 2048-bit modulus and 256-bit "q" subgroup. - EECDH using secp256r1 Until there is credible information one way or the other, it may be best to focus on things we already know make sense: - keep up with end-point software security patches - avoid already known weak crypto (RC4?) - Make sure VM provisioning includes initial PRNG seeding. - Save entropy across reboots. - ... Yes PFS addresses after the fact server private key compromise, but there is some risk that we don't know which if any of the PFS mechanisms to trust, and implementations are not always well engineered (see my post about GnuTLS and interoperability). -- Viktor. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On Sep 8, 2013, at 3:55 PM, Thor Lancelot Simon wrote: ... > I also wonder -- again, not entirely my own idea, my whiteboard partner > can speak up for himself if he wants to -- about whether we're going > to make ourselves better or worse off by rushing to the "safety" of > PFS ciphersuites, which, with their reliance on DH, in the absence of > good RNGs may make it *easier* for the adversary to recover our eventual > symmetric-cipher keys, rather than harder! I don't think you can do anything useful in crypto without some good source of random bits. If there is a private key somewhere (say, used for signing, or the public DH key used alongside the ephemeral one), you can combine the hash of that private key into your PRNG state. The result is that if your entropy source is bad, you get security to someone who doesn't compromise your private key in the future, and if your entropy source is good, you get security even against someone who compromises your private key in the future (that is, you get perfect forward secrecy). > Thor --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On Sun, 8 Sep 2013 15:55:52 -0400 Thor Lancelot Simon wrote: > On Sun, Sep 08, 2013 at 03:22:32PM -0400, Perry E. Metzger wrote: > > > > Ah, now *this* is potentially interesting. Imagine if you have a > > crypto accelerator that generates its IVs by encrypting > > information about keys in use using a key an observer might have > > or could guess from a small search space. > > > > Hadn't even occurred to me since it seems way more blatant than > > the other sort of leaks I was thinking of, but of course the mere > > fact that it is blatant doesn't mean that it would never be > > tried... > > Well, I guess it depends what your definition of "blatant" is. > Treating the crypto hardware as a black box, it would be freaking > hard to detect, no? Ah, but it only needs to be found once to destroy the reputation of a company. Inserting bugs into chips (say, random number generators that won't work well in the face of fabrication processes that alter analog characteristics of circuits slightly) results in a "could be an accident" sort of mistake. Altering a chip to insert an encrypted form of a key into the initialization vectors in use cannot be explained away that way. You may say "but how would you find that?". However, I've worked in recent years with people who decap chips, photograph the surface and reconstruct the circuits on a pretty routine basis -- tearing apart secure hardware for fun and profit is their specialty. Even when this process destructively eliminates in-RAM programming, usually weaknesses such as power glitching attacks are discovered by the examination of the "dead" system on the autopsy table and can then be used with live hardware. Now that it has been revealed that the NSA has either found or arranged for bugs in several chips, I would presume that some of these people are gearing up for major teardowns. Not all such teardowns will happen in the open community, of course -- I'd expect that even now there are folks in government labs around the world readying their samples, their probe stations and their etchant baths. Hopefully the guys in the open community will let us know what's bad before the other folks start exploiting our hardware silently, as I suspect the NSA is not going to send out a warning. > I also wonder -- again, not entirely my own idea, my whiteboard > partner can speak up for himself if he wants to -- about whether > we're going to make ourselves better or worse off by rushing to the > "safety" of PFS ciphersuites, which, with their reliance on DH, in > the absence of good RNGs may make it *easier* for the adversary to > recover our eventual symmetric-cipher keys, rather than harder! I'll repeat the same observation I've made a lot: Dorothy Denning's description of the Clipper chip key insertion ceremony described the keys as being generated deterministically using an iterated block cipher. I can't find the reference, but I'm pretty sure that when she was asked why, the rationale was that an iterated block cipher can be audited, and a hardware randomness source cannot. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On Sun, Sep 08, 2013 at 03:22:32PM -0400, Perry E. Metzger wrote: > > Ah, now *this* is potentially interesting. Imagine if you have a > crypto accelerator that generates its IVs by encrypting information > about keys in use using a key an observer might have or could guess > from a small search space. > > Hadn't even occurred to me since it seems way more blatant than > the other sort of leaks I was thinking of, but of course the mere > fact that it is blatant doesn't mean that it would never be tried... Well, I guess it depends what your definition of "blatant" is. Treating the crypto hardware as a black box, it would be freaking hard to detect, no? And not so easy even if you're willing to go at the thing at the gate level. You could end up forced to examine everything attached to any of your crypto chip's I/Os, too, and it goes rapidly downhill from there... When we build protocols that have data elements we *expect* to be random, and rely on cryptographic primitives whose outputs we expect to be indistinguishable from random, we kind of set ourselves up for this type of attack. Not that I see an easy way not to. I also wonder -- again, not entirely my own idea, my whiteboard partner can speak up for himself if he wants to -- about whether we're going to make ourselves better or worse off by rushing to the "safety" of PFS ciphersuites, which, with their reliance on DH, in the absence of good RNGs may make it *easier* for the adversary to recover our eventual symmetric-cipher keys, rather than harder! Thor ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
In principle, the malevolent crypto accellerator could flip into weak mode (however that happens) only upon receiving a message for decryption with some specific value or property. That would defeat any testing other than constant observation. This is more or less the attack that keeps parallel testing of electronic voting machines from being a good answer to the security concerns about them. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware
On Sun, 8 Sep 2013 15:10:45 -0400 Thor Lancelot Simon wrote: > On Sun, Sep 08, 2013 at 02:34:26PM -0400, Perry E. Metzger wrote: > > > > Any other thoughts on how one could sabotage hardware? An > > exhaustive list is interesting, if only because it gives us > > information on what to look for in hardware that may have been > > tweaked at NSA request. > > I'd go for leaking symmetric cipher key bits into exposed RNG > output: nonces, explicit IVs, and the like. Crypto hardware with > "macro" or "record" operations (ESP or TLS record/packet handling > as a single operation; TLS or IKE handshake, etc.) offers ample > opportunities for this, but surely it could be arranged even with > simpler hardware that just happens to accellerate both, let's say, > AES and random number generation. Ah, now *this* is potentially interesting. Imagine if you have a crypto accelerator that generates its IVs by encrypting information about keys in use using a key an observer might have or could guess from a small search space. Hadn't even occurred to me since it seems way more blatant than the other sort of leaks I was thinking of, but of course the mere fact that it is blatant doesn't mean that it would never be tried... Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Techniques for malevolent crypto hardware (Re: Suite B after today's news)
On Sun, Sep 08, 2013 at 02:34:26PM -0400, Perry E. Metzger wrote: > > Any other thoughts on how one could sabotage hardware? An exhaustive > list is interesting, if only because it gives us information on what > to look for in hardware that may have been tweaked at NSA request. I'd go for leaking symmetric cipher key bits into exposed RNG output: nonces, explicit IVs, and the like. Crypto hardware with "macro" or "record" operations (ESP or TLS record/packet handling as a single operation; TLS or IKE handshake, etc.) offers ample opportunities for this, but surely it could be arranged even with simpler hardware that just happens to accellerate both, let's say, AES and random number generation. Thor ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
