On 2009 Oct 19, at 9:15 , Jack Lloyd wrote:

On Sat, Oct 17, 2009 at 02:23:25AM -0700, John Gilmore wrote:

DSA was (designed to be) full of covert channels.

one can make DSA deterministic by choosing the k values to be HMAC- SHA256(key, H(m))

I've noticed people tinkering with (EC) DSA by constraining that number k. For example, Wei Dai's Crypto++ library generates k by hashing in the message itself as well as a timestamp into an RNG:


Wei Dai's motivation for this is to deal with the case that there is a rollback of the random number generator, which has always been possible and nowadays seems increasingly likely because of the rise of virtualization. See also Scott Yilek: http://eprint.iacr.org/ 2009/474 which appears to be a formal argument that this technique is secure (but I suspect that Scott Yilek and Wei Dai are unaware of one another's work). Yilek's work is motivated by virtual machines, but one should note that the same issues have bedeviled normal old physical machines for years.

Since the Dai/Yilek approach also uses an RNG it is still a covert channel, but one could easily remove the RNG part and just use the hash-of-the-message part.

I'm beginning to think that *in general* when I see a random number required for a crypto protocol then I want to either deterministically generate it from other data which is already present or to have it explicitly provided by the higher-layer protocol. In other words, I want to constrain the crypto protocol implementation by forbidding it to read the clock or to read from a globally-available RNG, thus making that layer deterministic.

This facilitates testing, which would help to detect implementation flaws like the OpenSSL/Debian fiasco. It also avoids covert channels and can avoid relying on an RNG for security. If the random numbers are generated fully deterministically then it can also provide engineering advantages because of "convergence" of the output -- that two computations of the same protocol with the same inputs yield the same output.

Now, Yilek's paper argues for the security of generating the needed random number by hashing together *both* an input random number (e.g. from the system RNG) *and* the message. This is exactly the technique that Wei Dai has implemented. I'm not sure how hard it would be to write a similar argument for the security of my proposed technique of generating the needed random number by hashing just the message. (Here's a crack at it: Yilek proves that the Dai technique is secure even when the system RNG fails and gives you the same number more than once, right? So then let's hardcode the system RNG to always give you the random number "4". QED :-))

Okay, aside from the theoretical proofs, the engineering question facing me is "What's more likely: RNG failure or novel cryptanalysis that exploits the fact that the random number isn't truly random but is instead generated, e.g. by a KDF from other secrets?". No contest! The former is common in practice and the latter is probably impossible.

Minimizing the risk of the latter is one reason why I am so interested in KDF's nowadays, such as the recently proposed HKDF: http://webee.technion.ac.il/~hugo/kdf/kdf.pdf .

On Tuesday,2009-10-20, at 15:45 , Greg Rose wrote:

Ah, but this doesn't solve the problem; a compliant implementation would be deterministic and free of covert channels, but you can't reveal enough information to convince someone *else* that the implementation is compliant (short of using zero-knowledge proofs, let's not go there). So a hardware nubbin could still leak information.

Good point! But can't the one who verifies the signature also verify that the k was generated according to the prescribed technique?



P.S. If you read this letter all the way to the end then please let me know. I try to make them short, but sometimes I think they are too long and make too many assumptions about what the reader already knows. Did this message make sense?

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Reply via email to