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 majord...@metzdowd.com
