Re: Counter Mode Security: Analysis and Recommendations

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

On Wed, Nov 20, 2002 at 04:37:57PM -0800, Bob Doud wrote:
> > >>>>> "David" == David A Mcgrew <mcgrew@cisco.com> writes:
> <snip>
> > 
> >  David> 4) is it acceptable to implement AES-192 or AES-256 and use
> >  David> those ciphers for counter mode?  Or is it desirable to use
> >  David> AES-128 for both CBC and counter mode?
> > 
> > I would hate to depend on AES-192 or above, since it's not clear to me
> > how widely those will initialy be implemented in high speed silicon.
> > 
> And let's keep in mind that a fundamental reason that we're pursuing 
> counter mode in the first place is for high-performance as systems 
> move into the multi-Gigabit range.  (Parallelizing the crypto operations
> across multiple engines with staggered counters.) It's safe to say that 
> all hardware and software implementations will be noticably slower with 
> AES-256 than with AES-128.

The speed hit to go from AES-128 to AES-192 is about 20% (12 rounds
versus 10 rounds).  But that's assuming that folks feel this is
actually necessary.  

I want to make sure that everyone in the IPSEC working group
understands that the TMTO attack requires only O(2**85) in time, but
it also requires O(2**85) in space.  That means that in order to carry
out this attack, the attacker needs to have access to order of
magnitude 512 yottabytes of storage.  (For those who aren't familiar
with the SI prefixes, that's kilo-, mega-, giga-, tera-, peta-, exa-,
zetta-, yotta-).

It's hard to describe how much space this is.  Currently, the biggest
single system commercially available from IBM and EMC (the Shark and
Symmetrix products, respectively) is 60-70 terabytes.  The ASCI
Purple, which is an incredibly large system for simulating atomic bomb
explosions at close to the atomic level, and which will probably end
up costing at least tens of billions of dollars, calls for 1.2
petabytes.  CERN estimates that by 2007, they will hopefully have 2.4
petabytes of disk storage.  Now, 512 yottabytes is 400,000,000 times
bigger.

Now, I'm willing to believe that the NSA has a much bigger budget than
the Atomic Bomb folks --- but I'm not sure they have a budget which is
a factor of four hundred million times bigger.

Speaking of budgets, using an estimate of $2,500/terrabyte, the
storage required to carry out this attack would cost approximately
$1,000,000,000,000,000,000 US dollars.  That's approximately 200
hundred thousand times the current US National Debt, and a million
times the current U.S. Federal budget.  So when it was stated that
this would require a "well funded" attacker, this was rather somewhat
of an understatement.  Even if the prices declined to a penny a
terrabyte (which might happen by 2023, according to some estimates, if
storage breakthroughs can continue to happen at current spaces), it
would still cost $5,000,000,000,000,000, which is still approximately
a thousand times the current U.S. National Debt.  (Of course, by 2023,
the U.S. National Debt will no doubt be much larger!)

Of course, this estimate completely ignores the overhead in indexing
this much data for fast access, and the amount of time it would take
to *write* 512 yottabytes worth of data.  (At today's rates of 100
megabytes/second, it would take quite a while.)  

The bottom line is that it's not at all clear to me (with my working
group chair off) the TMTO attack against AES-128 counter mode is
really realistic.  Furthermore, as I pointed out at the IPSEC working
group, the recommendation of 75 bits worth of keyspace in the ad-hoc
key-length paper assumed brute-force attacks using large numbers of
fast, specialized FPGA's with relatively insignificant amounts of
storage --- hundreds of bytes, not 512 yottabytes of storage.  So the
claim that the strength of AES Counter mode with a 128-bit key has
fallen below the cipher strength of as recommended by the ad-hoc
keylength paper seems to involve an apples vs oranges comparison.

That being said, there has been a number of hallway discussions about
some other ways in which we could add some additional bits of
unpredictability with minimal disruptions to the drafts, regardless of
whether it is not necessary.  It might not add as many bits as you had
suggested, but (again with my working group chair hat off), I'm still
not convinced that this attack, and thus the requirement to defend
against it, is really realistic.  Personally speaking, requiring an
additional 20% overhead for those people who are worried about what
seems like a largely theoretical concern doesn't seem like a horrible
thing.

							- Ted