[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: Counter Mode Security: Analysis and Recommendations



Ted,

thanks for your comments and the good data about big-storage systems.  Your
point that the attacks that I'm describing are not practical given current
technology (and reasonable bounds on budgets) is certainly correct.  A couple of
comments inline:

> -----Original Message-----
> From: Theodore Ts'o [mailto:tytso@mit.edu]
> Sent: Wednesday, November 20, 2002 6:49 PM
> To: Bob Doud
> Cc: 'Paul Koning'; mcgrew@cisco.com; paul.hoffman@vpnc.org;
> ipsec@lists.tislabs.com
> Subject: Re: Counter Mode Security: Analysis and Recommendations
>
>
> 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-).

You're right that Hellman's TMTO requires 2^85 in order to ensure that it can
break a session with probability close to one.  However, there is also the
key-collision attack which should be considered, and that attack does not
require as much memory as does the TMTO.

Also, the TMTO can be implemented so that it requires less memory but has a
lower probability of success.  With (2^85 / A) storage, the probability of
success when attacking any particular key will be about (1 / A), so that one out
of every A keys can be broken.   This trick is pretty much equivalent to
hybridizing the KC and TMTO attacks.

>
> 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.

Granted.  We're discussing appropriate levels of paranoia to protect us into the
future.

> 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.

I disagree here.  From http://www.counterpane.com/keylength.pdf:

<quote>
A cryptographic algorithm is considered strong if:

   1. There is no shortcut that allows the opponent to recover the plain text
without using brute force to test keys until the correct one is found; and

   2. The number of possible keys is sufficiently large to make such an attack
infeasible.
</quote>

So while this analysis didn't explicitly consider the use precomputation, it
clearly states that there should be no shortcut whose cost would be cheaper than
an exhaustive search.  Precomputation attacks can provide such a shortcut, so I
believe that my recommendations are consistent with those of the ad-hoc work
cited above.

>
> 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

Every bit counts :-)

thanks,

David