Counter Mode Security: Attacks, Storage & a Proposal

[Black_David@emc.com]

Ted observed that the O(2**85) attack requires O(2**85) storage for
the precomputation.  Actually it requires more, since each of those
O(2**85) records is at least 256 bits (2**5 bytes) in size, so the
need is at least O(2**90) bytes of storage.  Since I work for a storage
company that builds large storage infrastructures, I thought I'd offer
some observations on feasibility of that size of storage infrastructure
- the upshot is that I have no idea how to build anything within several
orders of magnitude of that scale in the near future ... but we'd love
to be paid to try :-).  Here are the details:

Next year, the disk drive industry should be producing disk drives of
about 300GB capacity.  The largest currently available disk array
holds 1024 drives, and that number's not likely to go up much.  The
result is 300TB with 300GB drives.  Three such arrays yield a petabyte
(2**50) and so 3000 arrays would yield about an exabyte (2**60) storage
infrastructure, and that's near the edge of what's feasible with current
storage networking technology.  The cost to build that sort of system
will be $5-10 billion or more - between that cost and the fact that
this is close to current technology scaling limits, 2**60 is probably
a decent approximation of what a very-well-funded adversary could put
together next year.  

Projecting into the future, areal bit density of disk media doubles
about annually, but drive capacities lag that because drive manufacturers
spend some of that density on reducing the number and size of platters.
In addition, about once every 5 years or so, a form factor reduction
occurs that results in no drive capacity increase for about a year.  We're
nearing the end of one now - about a year ago the largest commercially
available drive was a 180GB 3.5" HH (1.5" high) drive - that drive and
the HH form factor are being phased out, and the largest alternative
3.5" LP (1" high) drive currently available is 160GB.  Taking this into
consideration and allowing for some scaling improvements in storage
networking technology, another factor of 2**10 covers 8-10 years into
the future (i.e., 8-10 years from now, O(2**70) storage is what a
very-well-funded adversary could reasonably expect to put together).

Assuming that the attack scales uniformly in time vs. space (a serious
assumption that knowledgeable experts should check), O(2**70) storage is
O(2**20) short of the O(2**90) requirement for the O(2**85) attack - adding
that O(2**20) factor to the attack complexity yields a feasible attack of
O(2**105) rather than O(2**85).  In hallway discussions with several
interested parties, it was proposed that 24 unpredictable bits be used
instead of the truncated SPI in the counter block, and IKE nonces were
suggested as a good source for these unpredictable bits.  An additional
24 unpredictable bits increases the attack effort by O(2**16) [effort scales
as 2/3 of added unpredictable bits according to McGrew's paper] yielding
an O(2**121) attack in 8-10 years against 128-bit keys, and a current
situation in which the brute force attack is easier (2**128) than the
precomputation attack (2**131).  I think that should suffice ...  Further,
these attack effort estimates do not include the time necessary to search
the huge precomputed storage.

One caveat - this analysis is not as rigorous as David McGrew's -
I would apply a fudge factor of something like  O(2**3) to the size
and scale estimates to be safe, but I believe the conclusion that
24 additional unpredictable bits in the counter block are sufficient
still holds.

Thanks,
--David
----------------------------------------------------
David L. Black, Senior Technologist
EMC Corporation, 176 South St., Hopkinton, MA  01748
+1 (508) 293-7953 **NEW**     FAX: +1 (508) 293-7786
black_david@emc.com        Mobile: +1 (978) 394-7754
----------------------------------------------------