Subject: Re: [Cfrg] Re: [saag] Bad day at the hash function factory

From: der Mouse <[email-masked]>
Date: Wed, 27 Oct 2004 21:37:46 -0400 (EDT)

> A note to everyone using HMAC: Modern polynomial-evaluation MACs
> (such as GCM MAC) offer strong security guarantees (they're provably
> as secure as AES)

I'm not sure what this statement even _means_.  Block ciphers and MACs
have such drastically different security desires that it's not clear
how to perform the sort of comparison "as secure as" implies.  In
particular, each has some ways of being broken the other doesn't.

For that matter, what's "GCM MAC"?  Googling for it finds exactly two
hits: one is the message I'm responding to, the other is something in
some Latin tongue (Portugese? it's a .br host) and it looks like a
false positive to me - I for one find it hard to implement something
without any reference on it.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       [email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

---

From: Ken Raeburn <[email-masked]>
Date: Wed, 27 Oct 2004 22:33:36 -0400

On Oct 27, 2004, at 21:37, der Mouse wrote:
> For that matter, what's "GCM MAC"?

I assumed it was Galois/Counter Mode, used as a MAC (i.e., no data to 
encrypt).
http://www.cryptobarn.com/papers/gcm-spec.pdf

Ken

---

From: "D. J. Bernstein" <[email-masked]>
Date: 28 Oct 2004 02:57:55 -0000

der Mouse writes:
> I'm not sure what this statement even _means_.

Any message-forgery attack against a polynomial-evaluation MAC using AES
can be turned into a comparably fast algorithm to predict AES, i.e., to
distinguish AES from a uniform random permutation. AES was explicitly
designed to be indistinguishable from a uniform random permutation.

See, e.g., Rogaway, ``Bucket hashing and its application to fast message
authentication,'' J. Cryptology 12 (1999), 91-115, Proposition 14; or my
new paper http://cr.yp.to/papers.html#securitywcs, particularly Theorem
5.4; or http://www.google.com/search?as_q=wegman+carter+authentication.

Are MACs, message-encryption functions, etc. different objects from
block ciphers? Of course. Are there separate definitions of breaking a
MAC, breaking a message-encryption function, and breaking AES? Yes. But
that doesn't stop us from proving that breaking various AES-based MACs
implies breaking AES, that breaking counter-mode AES implies breaking
AES, etc.

> For that matter, what's "GCM MAC"?

http://eprint.iacr.org/2004/193/

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago

---

From: "David A. McGrew" <[email-masked]>
Date: Thu, 28 Oct 2004 04:51:27 -0700

Dan,

On Sep 26, 2004, at 12:50 PM, D. J. Bernstein wrote:

> A note to everyone using HMAC: Modern polynomial-evaluation MACs (such
> as GCM MAC) offer strong security guarantees (they're provably as 
> secure
> as AES) and are faster than HMAC-SHA1.

yes, thanks for pointing this out.  It would be worth having a 
discussion on universal hash based message authentication on the CFRG 
list.  (We should probably start a new thread for it too, so I've done 
that.)  I know that several others in CFRG are interested in this sort 
of work.  They'd probably also be interested in your recent 
announcement on `Stronger security bounds for Wegman-Carter-Shoup 
authenticators'', http://cr.yp.to/papers.html#securitywcs.

> Some of them (not GCM MAC) are
> even faster than HMAC-MD5.

Do you mean "in software" here?  As you know, the design target for GCM 
was high-speed authenticated encryption.  Unlike much of the work that 
uses universal hashing, GCM aims to be implementable in hardware as 
well as software.

Some other hashes, like UMAC and hash127, are better in software.  It 
would be great if CFRG could produce a specification for one or more of 
these functions.  It should not be hard to get some others to verify 
the test vectors.    I suspect that the group preference would be 
towards hash functions that are portable (e.g. fast on a wide variety 
of CPUs) and that require minimal per-key state.  There may be other 
points of view; others please chime in if you have other priorities.

David

> saag mailing list
> [email-masked]
> https://jis.mit.edu/mailman/listinfo/saag
>

---

From: RJ Atkinson <[email-masked]>
Date: Thu, 28 Oct 2004 08:49:21 -0400

David,

My protocol preference in an IETF context is for algorithm-independent 
protocols,
so that one does not need to change the protocol to add support for 
additional
algorithms in future.  This property holds for at least OSPFv2 
authentication and
RIPv2 authentication (and yes, I am working on documentation updates to 
each
of those specifications to document how SHA-1 and its relatives are 
implemented).

My algorithm preference in an IETF context is for algorithms that are 
acceptable
to the largest number of end users.  Right now, many governments (from 
multiple
governments, including several in Europe and several in Asia, NOT just 
the US)
and many non-governmental customers are insisting upon the same 
algorithm set,
which is the set of currently NIST-approved algorithms and modes.  This 
set of
algorithms appears to be the preferred set of algorithms and modes 
right now --
by a VERY wide margin.

In practice, that means there is a strong buyer preference from many 
countries
for SHA-1 (and its NIST-documented relatives) and for AES (in 
NIST-acceptable
modes).  Several countries, including several in Europe and several in 
Asia, are
also insisting that cryptographic products they buy have NIST FIPS 
140-2 approvals.
This also tends to reinforce the selection of algorithms and modes 
since only the
NIST-approved algorithms and modes can get a FIPS 140-2 approval.

I would even suggest that for the moment, any new security protocols 
developed
in an IETF context ought to include documentation on how NIST-approved 
algorithms
and modes are used with those protocols -- even if the IETF were to 
decide that
it preferred some non-NIST algorithm or mode for a particular security 
protocol
as the "default" algorithm/mode choice.

Yours,

Ran Atkinson
[email-masked]

PS:  Nitpickers should please note well that all of my comments above 
are about
the end-user/marketplace desires, and there is no comment above about 
the quality
of any particular algorithm or mode.

On Oct 28, 2004, at 07:51, David A. McGrew wrote:
>     I suspect that the group preference would be towards hash 
> functions that are portable (e.g. fast on a wide variety of CPUs) and 
> that require minimal per-key state.  There may be other points of 
> view; others please chime in if you have other priorities.
>
> David

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 27 Oct 2004 19:33:34 -0700

> particular, each has some ways of being broken the other doesn't.

How convenient you asked. 

Basically, you build a hash algorithm (or MAC) out of an encryption
algorithm. You can then demonstrate that the MAC/Hash is secure if the
encryption algorithm has a bunch of (somewhat idealized) properties.
Typically this is done by a reduction--showing that if you could break
the construction you could break the underlying encryption algorithm.

You might check out Tom Shrimpton's presentation on building
digests out of block ciphers from the recent DIMACS workshop. 

http://dimacs.rutgers.edu/Workshops/Practice/slides/shrimpton.ppt

As a side note, Tom makes the interesting point that the core of 
modern hash functions is basically a block cipher.

-Ekr