Subject: [Cfrg] Patent-free, parallelizable MACing

From: John Viega <[email-masked]>
Date: Wed, 11 Dec 2002 15:27:55 -0500

Yoshi Kohno, Russ Housley and I have been working on the issue of 
patent-free parallelizable MACs for a little while, now. We've come up 
with a construct that we are confident is patent-free, which we call a 
"split MAC".

I've attached a document for CFRG feedback that describes the generic 
concept, and an instantiation based on HMAC-SHA1.  We're also working 
on an instantiation based on XCBC-MAC-AES, as well as dual-use modes 
that combine with counter mode in a way similar to CCM.  We're also 
looking to see if a slight variation that takes a tree-based approach 
is more useful, particularly to hardware designers.

We're interested in any feedback you might provide.  For example, we're 
particularly interested in feedback on whether the interleaving 
parameter should be lowered (hardware people would like it to be one 
byte instead of 20, but this may lead to significantly worse software 
performance).

John

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Wed, 11 Dec 2002 17:23:56 -0800

Some comments on the patent issue.

1) The problem is not a problem for a sufficiently large community for
the patent to be paradigmatic.

	In other words folk hoping to get rich off the patent rights
here should understand that the performance problem only affects a tiny
proportion of the user community. So callibrate your expectations
accordingly.

2) The solution need not be pretty and need not allow an infinite degree
of fine grained parallelization.

	So if I need 4 parallel pipes to give me 100 Gb/s of data I
might simply divide the stream up into 4 separate streams and MAC each
one independently.

	If I was doing IPSEC I might simply build 4 independent packet
construction pipelines and simply round robin the packets to the
pipelines in turn.

	If I was doing multimedia I might interleave the streams at the
block level.

Throughput is a serious issue in many applications, latency is a serious
issue in many applications. Very few applications are constrained both
ways at the same time - applications that generate 10Gb/s are rarely so
constrained that they cannot tolerate a latency of 1000 bytes or so.

		Phill

> -----Original Message-----
> From: John Viega [mailto:[email-masked]]
> Sent: Wednesday, December 11, 2002 12:28 PM
> To: [email-masked]
> Subject: [Cfrg] Patent-free, parallelizable MACing
> 
>