Fast MAC algorithms?

[Nicolas Williams]

I've an application that is performance sensitive, which can re-key very
often (say, every 15 minutes, or more often still), and where no MAC is
accepted after 2 key changes.  In one case the entity generating a MAC
is also the only entity validating the MAC (but the MAC does go on the
wire).  I'm interested in any MAC algorithms which are fast, and it
doesn't matter how strong they are, as long as they meet some reasonable
lower bound on work factor to forge a MAC or recover the key, say 2^64,
given current cryptanalysis, plus a comfort factor.

On the other hand, practical MAC forgery / key recovery attacks would
completely break the security of this application.  So stronger MACs
would have to be available as well, as a performance vs. security
trade-off.

Key length is not an issue.  Having to confound the MAC by adding a
nonce is an acceptable and desirable requirement.  MAC and nonce length
are also not an issue (128-bits is acceptable).  Implementation of any
MAC algorithms for this application must be in software; parallelization
is not really an option.  Algorithm agility is also not a problem, and
certainly desirable.

I see many MAC algorithms out there: HMAC, NMAC, OMAC, PMAC, CBC-MAC,
UMAC, ...  And, of course, AEAD ciphers that can be used for
authentication only, (AES-GCM, AES-CCM, Helix/Phelix, ...).  What I'm
interested in is a comprehensive table showing relative strength under
current cryptanalysis and relative performance.  I suspect there's no
such thing, sadly.  UMAC and HMAC-SHA-1 seem like obvious default
candidates.

I also see papers like "Differential-Linear Attacks against the Stream
Cipher Phelix", by Wu and Preneel.  Wu and Preneel declare Phelix to be
insecure because if you violate the requirement that nonces not be
reused then the key can be recovered rather easily.  Helix seems to be
stronger than Phelix in this regard, even though the opposite was
intended.  That makes Phelix and Helix seem likely to be in for further
weakening.  For uses such as mine (see above), such weaknesses are fine
-- nonces will not be reused, and keys will be changed very often.  So
I'm willing to consider algorithms, for this particular use, that I'd
not consider for general use cases, though these sorts of weaknesses
make me feel uneasy.

Which MAC algorithms would you recommend?  (Off-list replies will be
summarized to the list with attribution if you'll allow me to.)

Nico
-- 

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