Re: Counter Mode Security: Attacks, Storage & a Proposal

[Paul Koning <pkoning@equallogic.com>]

>>>>> "Theodore" == Theodore Ts'o <tytso@mit.edu> writes:

 Theodore> On Thu, Nov 21, 2002 at 08:18:58PM -0500, Paul Koning
 Theodore> wrote:
 >> I continue to prefer a design where the transform strength is
 >> equal to the cipher strength unconditionally, because that's (as
 >> far as I know) the normal design rule.

 Theodore> The problem I have with this imputed design rule is that it
 Theodore> appears to completely ignore the storage requirements of
 Theodore> attacks, and that doesn't seem right.  For example, if you
 Theodore> create a lookup table that enumerates the encryption of a
 Theodore> known plaintext for every single possible key, you can
 Theodore> carry out the attack in O(1) time.  This ignores the cost
 Theodore> of the storage, and the time it takes to create the table
 Theodore> in the first place, but if you posit the existence of this
 Theodore> table, the strength of any cipher (by what I believe is a
 Theodore> very flawed definition) is 0 bits.

But I never said to ignore the cost of storage.  What I meant (perhaps
I didn't say this explicitly) is that, given an attack requiring O(x)
storage and O(y) time, I judge the cipher strength to be O(max(x,y)).

 Theodore> This is why I don't believe that claim that the fact that
 Theodore> there exists an attack which takes O(2**85) time but
 Theodore> requires O(2**85) storage means that the cipher is only 85
 Theodore> bits strong.  That just doesn't seem to be an appropriate
 Theodore> way of judging the strength of a cipher.

The alternative is to apply a scale factor to storage cost different
from computation cost.  But the problem with doing this is that the
process for arriving at such a scale factor involves a lot of
guessword, especially when you're trying to secure data for 30 years.
(We are, right?  Clearly we should be.)

 Theodore> (As another example, triple DES is succeptible to attacks
 Theodore> that require O(2**56) in time and O(2**56) in space.  Does
 Theodore> this mean that if both can be attacked in O(2**56) time,
 Theodore> completely ignoring the storage requirements, both ciphers
 Theodore> are identically strong with 56 bits of strength?  I don't
 Theodore> think so.)

No, it's double DES that is subject to that attack ("meet in the
middle") which is precisely why double DES is never used.  

(Note that the incremental cost in SA state of 3DES -- in the form
used in IPsec -- compared to 2DES is essentially the same as the
incremental cost of the 64-bit random seed as proposed by David
McGrew.)

	 paul