On Wed, Jul 22, 2009 at 1:43 AM, Nicolas Williams<nicolas.willi...@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 majord...@metzdowd.com