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

["Theodore Ts'o" <tytso@mit.edu>]

On Thu, Nov 21, 2002 at 08:18:58PM -0500, Paul Koning 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.

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

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

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

> 1. As I recall, the historical rate of capacity growth has not been
> all that constant (unlike, say, the Moore's Law analog in processing
> power).  Not all that many years ago the rate increased dramatically,
> I believe.

The risk actually is probably in the opposite direction; there are
strong indications that Moore's law will not be able to continue going
forward.  This is also true for disk drives; the size of a magnetic
domain on a disk platter has been getting smaller and smaller, and
it's not clear this can continue.

> 2. The analysis assumes that hard drives are and continue to be the
> most cost effective (YB/$) technology.  I'm not sure that's true now
> (consider tape libraries) and it may not be true later.

Tape libraries aren't particularly useful because you need to do
O(2**85) lookups.  If you need to mount and unmount tapes between
lookups, this will rather slow down the time to perform the attack....

Finally, a further issue which will likely make the TMTO attack remain
completely intractable is the (lack of) rates of improvement in disk
read/write speeds.  While it is true that disk capacities have been
growing very rapidly, the speed at which disk blocks can read or
written have not increased nearly as quickly.

							- Ted