deterministic random numbers in crypto protocols -- Re: Possibly questionable security decisions in DNS root management

Zooko Wilcox-O'Hearn zooko at zooko.com
Thu Oct 29 15:15:05 EDT 2009


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:

http://allmydata.org/trac/cryptopp/browser/c5/pubkey.h?rev=324#L1036

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?

Regards,

Zooko

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 majordomo at metzdowd.com



More information about the cryptography mailing list