Fast MAC algorithms?

mheyman at gmail.com mheyman at gmail.com
Wed Jul 22 14:46:19 EDT 2009


On Wed, Jul 22, 2009 at 1:43 AM, Nicolas
Williams<Nicolas.Williams at sun.com> wrote:
>
> But that's not what I'm looking for here.  I'm looking for the fastest
> MACs, with extreme security considerations...In the crypto world
> one never designs weak-but-fast algorithms on purpose, only
> strong-and-preferably-fast ones.  And when an algorithm is
> successfully attacked it's usually deprecated, put in the ash heap of
> history.  But there is a place for weak-but-fast algos, as long as
> they're not too weak.
>
It just so happens that I worked on a DARPA funded project about 10
years ago looking at the effects of any possible strength vs speed
trade off available for different MACing algorithms. We built the
capability into FreeS/Wan's IPSec. Some of our MACs were so weak we
called them Partial MACs (PMACs). PMACs authenticated only randomly
selected pieces of the packet. We figured PMACs were good enough for
video - who cares if Eve can feed you a frame or two of partially
spoofed video as long as you can't get enough to notice.

<http://www.isso.sparta.com/documents/acsa_final_report.pdf>

The major take aways include:

1) HMAC-SHA1-96 can typically triple the amount of CPU required to
move IP packets through the kernel over a no-crypto option.
HMAC-MD5-96 can double it.

2) If you throw TCP processing in there, unless you are consistantly
going to have packets on the order of at least 1000 bytes, your crypto
algorithm is almost _irrelevant_. TCP costs up to ~1000 cycles per
byte on 10 byte packets, 100 cycles per byte on 100 byte packets, and
only gets down to ~15 cycles per byte at 1000 byte packets. For
reference, HMAC-SHA1-96 takes about 25 cycles per byte for ~1000 byte
packets. These are PentiumII numbers for a Linux 2.2.14 kernel,
remember, this was 10 years ago.

3) If your host is actually going to do something with the data you
receive, it is really really hard to find something that the crypto
algorithm will affect. A coworker of mine struggled for to find a real
world desktop application in which you could actually see a result
(other then some numbers in a log file). Finally he found that viewing
a video remotely in an X-window (thats uncompressed video) would have
occasional drops that becomes noticeable if you pick your video well.
Our video was of a circular radar screen with a rotating update line
(I think it came from a screen saver). With this contrived
application, we could change the MAC algorithm and see more or less
disturbance in the video.

I'd like to emphasize points 2 and 3. You need an application that
either doesn't use TCP or that only uses TCP with MTU sized packets to
even want to care about crypto performance. I don't think the paper
points it out, but all are testing was done with two machines
connected directly to each other. Any out of order processing TCP
needs to do will only decrease the effect a MAC algorithm has. Also if
you want to do _anything_ with the data other than ignore it, it will
only further decrease the effect the MAC algorithm has. We tried
timing FTP transfers, streaming an MPEG, and numerous other things
that I don't remember but all these things had too much overhead to
allow the choice of MAC algorithm to be noticed. 10 years of kernel
network stack development and CPU improvements may have changed the
numbers slightly but I believe you need a really specialized case,
probably including real time requirements on marginal CPUs, before you
need to look at faster MAC algorithms.

Thanks for letting me reminisce about a really fun project (sprinkling
rdtsc around the Linux kernel and getting Steve Kent upset (not
really) at our attempted subversion of IPSec intent - we ended up
doing it the way he wanted even though my way would have been cleaner
<grin/>).

-Michael Heyman

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list