[Cryptography] Should the demarcation point for a viable cryptographic attack really be more efficient than brute force?

[Jerry Leichter]

> Should the demarcation point for a viable cryptographic attack really be more efficient than brute force? It could be argued that the birthday bound is the point when a cipher should be rekeyed due to the risk of collisions or a distinguishing attack....
You've jumped between two different kinds of attacks:  A "viable" attack and a "distinguishing" attack.

It's reasonably clear what a "distinguishing" attack is - it can readily be formalized as the ability of a machine of some sort gaining an epsilon advantage at guessing which of a pair of oracles - one implementing a random permutation, one implementing the encryption - is the random one.  Fill in details as you like; they don't change things by very much.  This is the weakest possible criterion for judging an encryption algorithm as vulnerable:  Any other attack that succeeds in and of itself provides a distinguishing attack.

A "viable" attack, on the other hand, has no clear meaning.  Is an attack that reduces the complexity of AES to 126 bits "viable"?  It would certainly be very interesting, but if "viable" has something to do with "of practical significance", it's hard to come up with situations where there's any practical difference between 128 and 126 bits.  It's not even clear where to draw the line.  How about 120 bits?  Hard to say. A factor of 256 is real - and if we're talking about a difference between 1 year and 256 years, it can be very significant.  But how about a difference between 1 hour and 256 hours?  That hardly seems worth discussing.

Saying "anything better then brute force is a viable attack - regardless of how *little* better" is likely to eliminate every algorithm out there.  I'm not sure we actually use that as the demarcation line.  Oh, we great attacks that achieve it with interest - but we need more detail about *how much better* before we really worry about the system.

There's tons of mathematics behind cryptography, but there are also ultimately practical tradeoffs to make.  "Viability" seems to get at those tradeoffs.

As for birthday bounds and rekeying ... now we're off into something entirely different.  We're no longer even talking about attacks on the crypto algorithm as such.  All that matters is the block size.  A random permutation on the same size blocks would reveal as much, or as little, about the cleartext.

It's really not clear where you are trying to go with this.

                                                        -- Jerry