Subject: [Cfrg] Interim MAC function

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Wed, 16 Mar 2005 13:29:27 -0800

All I had a thought on a means of constructing a digest function for cases
where we have a serious need for a high assurance digest.

A part of the MD4/SHA design I find somewhat unsatisfactory is the chain
construction. It seems to me that by the time we have got to the end of the
message the influence of the initial bits is somewhat dispersed. It would be
nice to have a digest such that the complexity of attack increased with the
size of the message rather than just the key space.

What I came up with was the MASH digest, (MAC and SHA) as follows:

	MASH (m) = HMAC (m, (SHA (m))

This is clearly much more costly to compute on a long message because the
entire message has to be fed in twice, but it does provide a means of
signing certificates etc. that uses the deployed cryptographic primitives to
achieve greater security which is similar to what 3DES did with DES. 3DES is
not an ideal cipher but it is better than any of the alternatives that were
likely to be chosen when the need for it appeared.

I am not convinced that I want to go to SHA-256 until the cryptographers
have given it some serious attention. At the moment everyone appears to be
too busy stomping on the little pieces of SHA-1 to do that. I would much
rather hear a paper giving a credible estimate of the strength of SHA-256
than yet another paper arguing whether SHA-1 is a really, really bad idea or
a really, really, really bad idea.

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

---

From: [email-masked] (David Wagner)
Date: Wed, 16 Mar 2005 21:58:49 +0000 (UTC)

>	MASH (m) = HMAC (m, (SHA (m))

I think this is likely to be less secure than SHA1-HMAC.  If an attacker
can find a collision in SHA1, they can break MASH.  This permits offline
collision attacks on MASH, where the attacker prepares a collision before
he even knows the key and without interacting with the legitimate parties.

In contrast, SHA1-HMAC does not permit such offline collision attacks.
This was an explicit design goal of SHA1-HMAC.

So I view MASH as a step backwards.

---

From: Scott Fluhrer <[email-masked]>
Date: Wed, 16 Mar 2005 14:42:51 -0800 (PST)

> This was an explicit design goal of SHA1-HMAC.

I believe you're misunderstanding the proposal -- it's not a MAC.
Instead, it's a hash function.  As such, it doesn't have a key.

On the other hand, it appears that your conclusion may be correct -- an
attacker that can find a collision in SHA1 can find a collision in MASH.
If HMAC is given a key larger than the hash function's block size, it
uses the hash of the key.  So, a more explicit definition of MASH
would be (assuming that |m| > 64 bytes):

 MASH(m) = SHA( opad^SHA(m) | SHA( ipad^SHA(m) | SHA(m) ) )

^ is bitwise xor, | is string concatination

>From this definition, it is clear that a collision in SHA implies a
collision with MASH.

---

From: csjutla <[email-masked]>
Date: Wed, 16 Mar 2005 18:06:47 -0500 (EST)

The definition that Hallam-Baker gives, if I understood correctly, is
to first compute SHA(m), then feed that as  IV to another computation
of SHA(m).

---

From: csjutla <[email-masked]>
Date: Wed, 16 Mar 2005 18:15:43 -0500 (EST)

While we are on this topic, it will be an intersting
challenge to break SHA-1 without the IV chained forward.
It definitely seems to have helped in these multi block attacks.
I wonder, if that is removed it causes some other weakness.

To be precise, the way SHA-1 and MD5 are defined right is:
There is a compression function Compress(IV,M) which is a feistel network,
and then the actual hash = Compress(IV,M) xor IV.

It would be an interesting challenge to break SHA-1 (or even MD5)
with the xor IV removed.

Charanjit Jutla
(IBM T.J. Watson REsearch Center)

---

From: Daniel Brown <[email-masked]>
Date: Wed, 16 Mar 2005 18:22:14 -0500

> I think this is likely to be less secure than SHA1-HMAC.  If an attacker

Wasn't MASH a HASH not a MAC?  If so it shouldn't be compared to a HMAC - 
unless SHA1-HMAC is some other hash construction I failed to learn about.

> collision attacks on MASH, where the attacker prepares a collision 
before

Because for long messages, the HMAC key is computed as SHA-1(m), is that 
you what you're referring to?  Maybe the original intention was to modify 
HMAC to expand out the key the somehow.  Anyway, I agree with you that 
MASH - with a compacted key - is no more secure that SHA1 as a HASH, for 
the reason above. 

        Dan

---

From: Scott Fluhrer <[email-masked]>
Date: Wed, 16 Mar 2005 15:53:29 -0800 (PST)

> It would be an interesting challenge to break SHA-1 (or even MD5)

One thing that would do would be to reduce the effort to compute preimages
from O(2^160) (for SHA-1) down to O(2^80).  This happens because, without
that xor, the compression function is invertable (that is, given hash and
M, you can compute Compress^-1(hash,M)=IV such that Compress(IV,M)=hash).

-- 
scott

---

From: csjutla <[email-masked]>
Date: Wed, 16 Mar 2005 19:06:38 -0500 (EST)

Yeah, thats true. Meet in the middle!

---

From: Ken Raeburn <[email-masked]>
Date: Wed, 16 Mar 2005 17:54:35 -0500

> 	MASH (m) = HMAC (m, (SHA (m))

Seems like it does make it a bit more challenging; even if you find m 
and m' colliding under plain SHA, in this case you've got two different 
sets of internal state you'd have to produce collisions for with one 
pair of messages, one starting with nothing, and one starting with 
SHA(m) XOR 0x3636....  Without knowing how the current 
collision-finding algorithm works, I couldn't begin to guess how much 
harder that makes it.  (Well, other approaches might be possible, but 
that's the obvious one building on a simple break of SHA.)

I was under the impression that a lot of the strength of HMAC came from 
the secrecy of the key, in combination with the double-hash, but maybe 
I'm wrong.  Haven't actually looked at the papers.

> too busy stomping on the little pieces of SHA-1 to do that.

They're not that little yet, there's still more stomping to be done. :-)

>  I would much

I'd be interested in hearing the opinions specifically of the team 
that's been breaking all our other hash functions....

Ken

---

From: [email-masked] (David Wagner)
Date: Thu, 17 Mar 2005 06:43:39 +0000 (UTC)

I want to retract my comments.  I misunderstood the proposal (I read too
quickly, I guess), and my remarks were totally bogus.  I apologize.

I have no idea whether MASH is any better than SHA1, but I don't have any
reason to think MASH is broken or is worse than SHA1.

Again, my apologies for my egregious error.