Subject: Re: [Cfrg] VMAC Internet-Draft Available

From: David McGrew <[email-masked]>
Date: Wed, 2 May 2007 13:46:49 -0700

Hi Ted,

thanks for posting.  I have not had a chance to read over it in  
detail yet, but I look forward to that.

I do have a quick question, though.  What would change if the high  
level structure were modified to something like Tag = F_K2(H_K1(M))?   
As you probably guessed, the reason that I ask is that I believe that  
there are applications that would be interested in alternatives to  
HMAC, but which would prefer to use a MAC that does not require a  
sequence number.

David

On Apr 24, 2007, at 10:32 AM, Ted Krovetz wrote:

> A new Internet-Draft is available for VMAC. The draft and reference  
> code are available at
>
>   http://fastcrypto.org/vmac
>
> VMAC is a message authentication code that is extremely fast on 64- 
> bit little-endian machines, and pretty fast on other architectures.  
> The primary goals of VMAC are:
>
> * High speed on 64-bit architectures. The table below gives sample  
> performance on several architectures. The code that generated these  
> numbers is written in C with a small amount of inline assembly.  
> Optimizing for other architectures requires as little as writing  
> efficient 64-bit multiplication, 128-bit addition and 64-bit byte- 
> swapping routines.
>
>                                           64-bit Tags     128-bit Tags
>         Bits/Endian/Architecture         64  512   4K     64  512   4K
>     ---------------------------------+-----+----+-----+-----+----+----
>     64/LE/AMD Athlon 64 "Manchester" |  6.0  1.1  0.5 |  7.0  1.6  0.9
>     64/LE/Intel Core 2 "Merom"       |  5.9  1.2  0.6 |  6.9  1.7  1.1
>     64/BE/IBM PowerPC 970FX          | 10.1  2.5  1.6 | 11.4  3.8  3.0
>     32/LE/Intel Core 2 "Merom"       |  8.3  2.2  1.4 | 11.1  3.6  2.8
>     32/LE/Intel NetBurst "Nocona"    | 15.0  4.4  3.1 | 18.9  7.1  5.8
>     32/BE/Freescale PowerPC 7457     | 15.3  6.4  5.3 | 22.1 11.2 10.0
>     32/LE/Embedded ARM v5te core     | 39.9 13.1 10.1 | 53.6 22.9 19.8
>     ---------------------------------+-----+----+-----+-----+----+----
>     Table: Tag generation speed measured in CPU cycles per message
>     byte, for cache-resident messages of length 64, 512 and 4K bytes.
>     Architectures are listed as register-size/endianness/model.
>
> * Reduction of per-session memory requirement over UMAC (A VMAC  
> predecessor). Whereas UMAC required 1080 bytes of internal key to  
> produce 64-bit authentication tags, VMAC uses 160 bytes. (If one  
> were to increase VMAC's internal key to the same as UMAC's, peak  
> speeds would be as low as 0.3 CPU cycles per byte.)
>
> * Retention of the virtues of UMAC: no intellectual-property  
> claims, provable security, flexibility between normal-security tags  
> (64-bit) and high-security tags (128-bit).
>
> VMAC was introduced at the Selected Areas of Cryptography 2006  
> conference. Special thanks go to Wei Dai, a very talented crypto  
> programmer. He read the SAC paper and then made significant  
> contributions to the VMAC design (increasing speed and security)  
> and code (resulting in the speeds reported here).
>
> A security note is being written and will be available on eCrypt  
> and the VMAC website later this summer. Any comments you may have  
> would be most welcome.
>
> Thank you,
> Ted Krovetz
> Computer Science Department
> California State University, Sacramento
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Ted Krovetz <[email-masked]>
Date: Thu, 3 May 2007 09:12:26 -0700

Hi David,

> level structure were modified to something like Tag = F_K2(H_K1 
> (M))?  As you probably guessed, the reason that I ask is that I  
> believe that there are applications that would be interested in  
> alternatives to HMAC, but which would prefer to use a MAC that does  
> not require a sequence number.

Two things, really only affecting short-tag macs:

1) Speed on short messages. Because I use only half an AES output per  
VMAC-64 mac tag, VMAC can save a hundred or so cycles on average by  
caching AES outputs on sequential nonces. Your suggestion wouldn't  
allow this kind of caching.

2) Birthday bound. F_K2(H_K1(M)) gives away knowledge of hash  
collisions when they happen. If we define this as failure, then over  
q tags, failure occurs with probability around (q(q-1)/2) \epsilon  
for an \epsilon-AU hash family.

These issues are really only relevant for VMAC-64 and UMAC-32/64/96.  
For VMAC/UMAC-128, \epsilon is low enough to tolerate the birthday  
bound and AES caching is not possible. So, my next project is to look  
at constructing a universal-hash-based incarnation of Phil's SIV mode  
(which is essentially F_K2(H_K1(M)) on steroids).

Something should come out this summer.

-Ted

---

From: "Wei Dai" <[email-masked]>
Date: Tue, 8 May 2007 11:24:02 -0700

Another implementation of VMAC is now available as part of the recently 
released Crypto++ 5.5 (http://www.cryptopp.com). It further improves VMAC 
performance on 32-bit CPUs with SSE2 instructions, and reaches a peak 
performance of 3.7 cycles per byte for VMAC-128 on the Pentium 4, making its 
speed almost competitive with UMAC on that CPU (and at a much smaller memory 
footprint).

I'd also like to point out that VMAC is very easy to parallelize, and should 
be very suitable for future generations of CPUs that may have hundreds or 
thousands of ALUs. I think this should be part of future algorithm design 
considerations (but fortunately I think I just missed the NIST hash 
algorithm requirements comment period).