[LinkSec] Re: CWC
I've gone back and reviewed the entire thread on algorithm choices.
As one of the CWC designers, let me register my thoughts.
CWC is, much like CCM, currently under consideration for NIST
standardization. At the time that 802.11i was standardizing on CCM,
CWC did not exist, thus Russ' comment that there was nothing else
interesting on track within NIST than the options considered.
Note that Doug Whiting was involved in the development of both CWC and
CCM. CCM came first. The mail goal of CWC was to be able to break
the speed limit that CCM implicitly has (my understanding is that
there's about a 3Gb/sec limit in commodity hardware).
Comparing CWC to CCM, there are some advantages each way. The primary
advantage for CCM mode is that it's already part of the 802.11i
standard, and there are already vendors who support this algorithm in
hardware. Otherwise, I think that CWC is better suited for what
you're trying to do. Let me try to do a comparison that is as fair as
possible:
- CCM uses 2 AES operations for each 128 bits of message. CWC uses just
1, plus two additional AES operations per message.
- On the other hand, if you're using an unoptimized version of CWC,
then the cost of the universal hash function is about on par with the
extra AES operations in CCM.
- Of course, there's plenty of room for optimizing CWC implementations
(particularly, the underlying universal hash function). Bernstein has
done a lot of work optimizing an almost identical hash function. His
implementation processes data at under 3 cycles per byte on most
modern x86 machines, which is astounding. However, his methods are
actually quite complex and can be hard to reproduce to the same level
of performance. I've seen some work in the graphics world that
indicates that one might even be able to improve on Bernstein's
techniques by using both the fpu and the integer unit on the x86,
effectively in parallel. Such things give me high confidence that CWC
will eventually run very fast in software compared to CCM. Right now,
there isn't much of a difference.
- CWC clearly scales much farther than CCM does in hardware. Doug is
more capable of discussing specifics there, though.
- While both modes have security proofs attached to them, CWC seems to
be better regarded from a provable security standpoint. First, the
security bounds are better. Second, the proof is a whole lot simpler,
particularly since CWC is just an instantiation of the
"encrypt-then-authenticate" paradigm.
- CWC does not have the complexity CCM has. This seems to be a big
deal to some people. I remember it was one of the more important
criticisms in the Rogaway/Wagner critique of CCM.
Personally, I think that in environments that aren't trying to reach
10Gigabits/sec, the differences between the two modes are fairly
minor. There's also EAX, which is similar to CCM in its properties,
except that, like CWC, it uses the encrypt-then-authenticate paradigm
(and is advertised as less complex than CCM in many ways). Unlike
CWC, EAX does not scale in hardware the way CWC and OCB do.
When looking at high speed environments, CWC currently seems to be the
best choice all around. First, we can compare it to patented modes,
particularly OCB, since it stands out amongst those modes.
In software, OCB performs better in the general case. It should take
up slightly less space in hardware implementations. Its security
proof is fairly simple, but the algorithm itself is often hard for
people to understand (a minor point in favor of CWC). The security
bounds are not quite as good as for CWC, but that is also a minor
issue.
All things considered, if there were no patent restrictions on OCB,
one would probably choose it as slightly preferable to CWC. Perhaps
with the advent of CWC, Rogaway will be willing to license OCB rights
to anyone for free, except that there is still an IBM patent that will
hold domain that one would also have to license. I think that one
would be a bigger hurdle.
The other interesting modes from this perspective are all covered by
IBM patents, except for David McGrew's work in combining mmh-style
universal hashes with CTR mode (CWC combines a hash with CTR mode as
well). The McGrew work is at least as appealing as CWC on many
fronts. The big problem is that it has significantly larger key sizes
that probably makes it a bit less appealing overall. Plus, McGrew's
work isn't currently under consideration for NIST standardization as
an AES mode (though that is probably easy to change).
The other alternative that someone suggested is to use generic
composition with something like HMAC-SHA-256 as the MAC. That
solution won't scale much farther than CCM in hardware, since HMAC is
not parallelizable. One would have to go to an XOR mac to solve that
problem, and XOR macs are also covered by patent. I'd also say that
AES has received far more scrutiny than has SHA-256 as to its merits
as a pseudo-random function. Plus, the use of a universal hash
function instead of a cryptographic one brings you more speed and also
brings you well defined collision probabilities, meaning that, short
of an attack that renders AES useless in general, a solution based on
a universal hash function has far higher assurance (on the message
authentication piece).
John