Re: [Cryptography] The hypothetical random number generator backdoor
On 23 September 2013 01:09, Phillip Hallam-Baker hal...@gmail.com wrote: So we think there is 'some kind' of backdoor in a random number generator. One question is how the EC math might make that possible. Another is how might the door be opened. Are you talking about http://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy or hypothetical RNGs in general, maybe not even EC based? I was thinking about this and it occurred to me that it is fairly easy to get a public SSL server to provide a client with a session key - just ask to start a session. For an RSA key exchange without ephemeral DH, the _client_ generates the premaster secret from which the session key is derived. However, ClientHello and ServerHello both contain random numbers sent before key exchange. If you are intercepting traffic, you have a nonce generated shortly before the session key generation for every key exchange, even without starting sessions of your own. Possibly you can use the client nonces to reduce the search space for the session keys (and if it's an RC4 session key, maybe the biases in RC4 help?). (Or, if using DHE, maybe it helps find DH private keys.) And possibly if you have server nonces based on the same PRNG seed as was used when the RSA key was generated, you can search for the RSA key. -- alan.bragg...@gmail.com http://www.chiark.greenend.org.uk/~armb/ ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] The hypothetical random number generator backdoor
On Sep 22, 2013, at 8:09 PM, Phillip Hallam-Baker hal...@gmail.com wrote: I was thinking about this and it occurred to me that it is fairly easy to get a public SSL server to provide a client with a session key - just ask to start a session. Which suggests that maybe the backdoor [for an NSA-spiked random number generator] is of the form that ... you get a lot of nonces [maybe just one] from the random number generator ... and that allows the [next one to be predicted more easily or even the] seed to be unearthed. One simple way [to stop this] would be to encrypt the nonces from the RNG under a secret key generated in some other fashion. nonce = E (R, k) Or hashing the RNG output and XORing with it nonce = R XOR H(R) You shifted from random value to nonce. Given the severe effects on security that using a nonce - a value that is simply never repeated in a given cryptographic context; it may be predictable, even fixed - to a random value, one needs to be careful about the language. (There's another layer as well, partly captured by unpredictable value but not really: Is it a value that we must plan on the adversary learning at some point, even though he couldn't predict it up front, or must it remain secret? The random values in PFS are only effective in providing forward security if they remain secret forever.) Anyway, everything you are talking about here is *supposed* to be a random value. Using E(R,k) is a slightly complicated way of using a standard PRNG: The output of a block cipher in counter mode. Given (a) the security of the encryption under standard assumptions; (b) the secrecy and randomness of k; the result is a good PRNG. (In fact, this is pretty much exactly one of the Indistinguishability assumptions. There are subtly different forms of those around, but typically the randomness of input is irrelevant - these are semantic security assumptions so knowing something about the input can't help you.) Putting R in there can't hurt, and if the way you got R really is random then even if k leaks or E turns out to be weak, you're still safe. However ... where does k come from? To be able to use any of the properties of E, k itself must be chosen at random. If you use the same generator as way use to find R, it's not clear that this is much stronger than R itself. If you have some assured way of getting a random k - why not use it for R itself? (This might be worth it if you can generate a k you believe in but only at a much lower rate than you can generate an R directly. Then you can stretch k over a number of R values. But I'd really think long and hard about what you're assuming about the various components.) BTW, one thing you *must not* do is have k and the session key relate to each other in any simple way. For hash and XOR ... no standard property of any hash function tells you anything about the properties of R XOR H(R). Granted, for the hash functions we generally use, it probably has about the same properties; but it won't have any more than that. (If you look at the structure of classic iterated hashes, the last thing H did was compute S = S + R(S), where S was the internal state and R was the round function. Since R is usually invertible, this is the only step that actually makes the whole thing non-invertible. Your more-or-less repetition of the same operation probably neither helps more hinders.) At least if we assume the standard properties, it's hard to get R from H(R) - but an attacker in a position to try a large but (to him) tractable number of guesses for R can readily check them all. Using R XOR H(R) makes it no harder for him to try that brute force search. I much prefer the encryption approach. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] The hypothetical random number generator backdoor
On Tue, Sep 24, 2013 at 10:59 AM, Jerry Leichter leich...@lrw.com wrote: On Sep 22, 2013, at 8:09 PM, Phillip Hallam-Baker hal...@gmail.com wrote: I was thinking about this and it occurred to me that it is fairly easy to get a public SSL server to provide a client with a session key - just ask to start a session. Which suggests that maybe the backdoor [for an NSA-spiked random number generator] is of the form that ... you get a lot of nonces [maybe just one] from the random number generator ... and that allows the [next one to be predicted more easily or even the] seed to be unearthed. One simple way [to stop this] would be to encrypt the nonces from the RNG under a secret key generated in some other fashion. nonce = E (R, k) Or hashing the RNG output and XORing with it nonce = R XOR H(R) You shifted from random value to nonce. Given the severe effects on security that using a nonce - a value that is simply never repeated in a given cryptographic context; it may be predictable, even fixed - to a random value, one needs to be careful about the language. (There's another layer as well, partly captured by unpredictable value but not really: Is it a value that we must plan on the adversary learning at some point, even though he couldn't predict it up front, or must it remain secret? The random values in PFS are only effective in providing forward security if they remain secret forever.) Anyway, everything you are talking about here is *supposed* to be a random value. Using E(R,k) is a slightly complicated way of using a standard PRNG: The output of a block cipher in counter mode. Given (a) the security of the encryption under standard assumptions; (b) the secrecy and randomness of k; the result is a good PRNG. (In fact, this is pretty much exactly one of the Indistinguishability assumptions. There are subtly different forms of those around, but typically the randomness of input is irrelevant - these are semantic security assumptions so knowing something about the input can't help you.) Putting R in there can't hurt, and if the way you got R really is random then even if k leaks or E turns out to be weak, you're still safe. However ... where does k come from? To be able to use any of the properties of E, k itself must be chosen at random. If you use the same generator as way use to find R, it's not clear that this is much stronger than R itself. If you have some assured way of getting a random k - why not use it for R itself? (This might be worth it if you can generate a k you believe in but only at a much lower rate than you can generate an R directly. Then you can stretch k over a number of R values. But I'd really think long and hard about what you're assuming about the various components.) BTW, one thing you *must not* do is have k and the session key relate to each other in any simple way. For hash and XOR ... no standard property of any hash function tells you anything about the properties of R XOR H(R). Granted, for the hash functions we generally use, it probably has about the same properties; but it won't have any more than that. (If you look at the structure of classic iterated hashes, the last thing H did was compute S = S + R(S), where S was the internal state and R was the round function. Since R is usually invertible, this is the only step that actually makes the whole thing non-invertible. Your more-or-less repetition of the same operation probably neither helps more hinders.) At least if we assume the standard properties, it's hard to get R from H(R) - but an attacker in a position to try a large but (to him) tractable number of guesses for R can readily check them all. Using R XOR H(R) makes it no harder for him to try that brute force search. I much prefer the encryption approach. There are three ways a RNG can fail 1) Insufficient randomness in the input 2) Losing randomness as a result of the random transformation 3) Leaking bits through an intentional or unintentional side channel What I was concerned about in the above was (3). I prefer the hashing approaches. While it is possible that there is a matched set of weaknesses, I find that implausible. -- Website: http://hallambaker.com/ ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] The hypothetical random number generator backdoor
So we think there is 'some kind' of backdoor in a random number generator. One question is how the EC math might make that possible. Another is how might the door be opened. I'm assuming you're talking about DUAL_EC_DBRG. Where the backdoor is and how it can be exploited is pretty simple to explain – if you know your way around the elliptic curve discrete logarithm problem, which I really don't. See [0]. Please allow me to stumble up an explanation in an attempt to learn how this shit works. In any case, in the algorithm as the NIST specifies it [1], two constants are used: the generator P of the curve and a specific point on that curve Q. It hasn't been explained why point Q has been chosen. The potential backdoor lies in the existence of a constant e so that Q^e = P. Calculating e, knowing only P and Q, would require solving the discrete logarithm problem. It is however trivial to generate Q and e together, just like in any other public-key cryptosystem (with e being the private key). According to the researchers from Microsoft, exploiting this would require at most 32 bytes of the PRNG output to reveal the internal state, thus revealing all random numbers generated with the same instantiation of the PRNG from that moment on. If the NSA in fact specially crafted point Q, it would have been the perfect backdoor for them. Only they had the keys to the kingdom. As long as the private key remained secret, other attackers wouldn't have any advantage from the existence of the backdoor. Would I be correct to say that backdoors with such properties cannot exist in PRNGs based on symmetric crypto or hashing functions? Either way, the question is how to stop this side channel attack. One simple way would be to encrypt the nonces from the RNG under a secret key generated in some other fashion. That seems silly. You are just shifting the responsibility from the PRNG to the cipher and its (random) key/seed. In any case, the result is just a new, needlessly complex PRNG, since you might just as well encrypt zeroes. You also seem to think that evoking random numbers from a system somehow constitutes a side channel attack. It does not. Pretending that it does will only lead to security by obscurity (hiding the algorithm). If you really doubt implementations, instantiate multiple algorithms with independent seeds and XOR the output together. The combination will be at least as strong as the strongest individual PRNG (assuming good seeds). That seems silly as well. Regards, Gerard [0] http://rump2007.cr.yp.to/15-shumow.pdf [1] http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] The hypothetical random number generator backdoor
On Sep 24, 2013, at 7:53 PM, Phillip Hallam-Baker wrote: There are three ways a RNG can fail 1) Insufficient randomness in the input 2) Losing randomness as a result of the random transformation 3) Leaking bits through an intentional or unintentional side channel What I was concerned about in the above was (3). I prefer the hashing approaches. While it is possible that there is a matched set of weaknesses, I find that implausible. Then I'm mystified by your proposal. If enough bits are leaked to make it possible to feed all possible values of the generated value R into whatever algorithm uses them (and, of course, recognize when you've hit the right one), then the extra cost of instead replacing each such value R with R XOR H(R) is trivial. No fixed transformation can help here - it's no different from using an RNG with problem 1 and whitening its output: It now looks strong, but isn't. (In fact, in terms of black box behavior to someone who doesn't know about the limited randomness/internal loss/side channel, these three weaknesses are functionally equivalent - and are subject to exactly the same attacks.) The encryption approach - replacing R by E(k,R) - helps exactly because the key it uses is unknown to the attacker. As I said before, this approach is fine, but: Where does this magic random key come from; and given that you have a way to generate it, why not use that way to generate R directly rather than playing games with code you don't trust? -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] The hypothetical random number generator backdoor
On Sep 24, 2013, at 6:11 PM, Gerardus Hendricks konfku...@riseup.net wrote: I'm assuming you're talking about DUAL_EC_DBRG. ... According to the researchers from Microsoft, exploiting this would require at most 32 bytes of the PRNG output to reveal the internal state, thus revealing all random numbers generated with the same instantiation of the PRNG from that moment on. Would I be correct to say that backdoors with such properties cannot exist in PRNGs based on symmetric crypto or hashing functions? Well, that depends on how they are used and what you believe about the primitives. If you use encryption in counter mode - E(k,counter), where k is random - then the assumption that the generated values are random is, as I remarked in another comment, pretty much equivalent to the indistinguishability assumptions that are commonly made about symmetric cryptographic algorithms. If you don't think you have an appropriately secure symmetric cipher to work with ... it's not clear just what you're going to *do* with your random numbers anyway. It's harder to know what to make of hashing approaches because it depends on the hash algorithm and what you believe about *it*. For most uses, a cryptographic hash function just has to prevent first- and second-preimage attacks. If that's all you are willing to assume your hash function provides, it's enough for the standard, intended uses of such hashes, but not enough to prove much more. (For example, nothing in these two assumptions, on its own, says that the hash function can't always produce an output whose first bit is 0.) People generally do assume more, but you really have to be explicit. Either way, the question is how to stop this side channel attack. One simple way would be to encrypt the nonces from the RNG under a secret key generated in some other fashion. That seems silly. You are just shifting the responsibility from the PRNG to the cipher and its (random) key/seed. In any case, the result is just a new, needlessly complex PRNG, since you might just as well encrypt zeroes. Indeed - though you could safely reuse the random key in counter mode up to some limit determined by the security guarantees of the cipher, and if the encryption function lives up to its guarantees, you'll still be secure. Stretching a short random key into a long effectively random sequence is exactly what symmetric encryption functions *do*! -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] The hypothetical random number generator backdoor
On Sep 25, 2013 8:06 AM, John Kelsey crypto@gmail.com wrote: On Sep 22, 2013, at 8:09 PM, Phillip Hallam-Baker hal...@gmail.com wrote: Either way, the question is how to stop this side channel attack. One simple way would be to encrypt the nonces from the RNG under a secret key generated in some other fashion. nonce = E (R, k) This would work if you had a secure key I couldn't guess for k. If the entropy is really low, though, I would still see duplicate outputs from time to time. If the RNG has short cycles, this would also show up. Note that Kerberos confounds: it encrypts it's nonces for AES in CTS mode (similar to CBC). Confounding makes it harder to exploit a backdoored RNG if the exploit is made easier by the ability to see RNG outputs as nonces. I'm not sure how much harder though: presumably in the worst case the attacker has the victim's device's seed somehow (e.g., from a MAC address, purchase records, ...), and can search its output via boot and iteration counter searches (the details depend on the PRNG construction, obviously). Seeing an RNG output in the clear probably helps, but the attacker could design the PRNG such that they don't need to. Now, there's a proposal to drop confounding for new cipher suites in Kerberos. Among other things doing so would improve performance. It would also make analysis of the new cipher suites easier, as they'd match what other standard protocols do. Of course, I'd rather implementations have a strong enough RNG and SRNG -- I'd rather not have to care if some RNG outputs are trivially available to attackers. But if confounding is a net security improvement for PRNG-only use cases (is it? it might depend on the PRNG construction and boot-time seed handling), maybe we should keep it. Thoughts? Nico -- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
