[cryptography] philosophical question about strengths and attacks at impossible levels

Steven Bellovin smb at cs.columbia.edu
Fri Oct 15 10:56:17 EDT 2010

There are many possible answers to your query -- including, of course, "you're right" -- but maybe we should be a little bit more charitable.  Maybe, in fact, they're right.

The real goal is a certain degree of security -- an enemy cannot usefully attack it.  By "useful" I mean "in time to cause harm to someone".  Unfortunately, the cryptographic community -- at least the open sector community -- has no such metrics.  At best, resistance can be demonstrated to certain classes of attacks.  Against unknown attacks -- or against attacks unknown in the open community -- not very much can be said.  Think of all of the proposals in the 1980s about replacing the S-boxes in DES with something that would be more random -- it was known, after all, that they were not what one would expect if they'd been populated from a uniform distribution, but no one knew why.  Most of the guessing suggested back doors by NSA -- but of course we now know that they were picked to resist differential cryptanalysis, which IBM and the NSA knew about much earlier.

What if there is a new attack lurking, perhaps to be discovered (or released) 10 years from now?  Remember that no one has ever deployed a crypto mechanism that they knew was vulnerable; the fact that you or I don't know of an attack doesn't mean that one doesn't or can't exist.

Key size or hash function size are useful proxies here.  We do know that most attacks have work factors related to the key size, if only because some attacks recover M of the N key bits, leaving a brute force search of 2^(N-M) operations. Alternatively, think of all of the attacks on weakened versions of systems, attacks that have often led to later, practical attacks.  Today's certificational weaknesses can lead to tomorrow's cracks.  (Do you think that, were the AES competition to be held today, Rijndael would win?  I don't, even though the weaknesses in the 256-bit version are very far from being exploitable.)

A 512-bit requirement on hash functions, then, is two things: it is a rough metric of strength, and it is a safety margin.  We can argue endlessly about whether 512 bits is right, compared with 384 bits or even 768 bits.  We can even argue if it's the best metric or the best way to measure safety margin.  But I think it is indisputable that we need something.  (Aside: for most other areas of security, we're in even more desperate need of such things, and I don't think we can get them.  Here, though, we have something that isn't preposterous.)

More information about the cryptography mailing list