Subject: RE: [RPSEC] Minutes and Presentations from Paris are now Posted...

From: "Vishwas Manral" <[email-masked]>
Date: Tue, 16 Aug 2005 21:08:13 -0700

Hi Steve B.,

Thanks for the link. I agree. Regarding the HMAC part, when applying the
HMAC construct to MD5 or SHA-1, I agree the collision attacks can be
mitigated. This is exactly what we have put in our draft. 

However the packets are not just arbitrary bit streams. We actually
check for the packet fields for validity and we also have the checksum
field, so probabilities of the packet being used after collisions are
even lesser.

I think the collision attacks that you talk about are the same as
"Birthday Attacks" where we use brute force to actually find another
stream with the same message digest, right?
http://mathworld.wolfram.com/BirthdayAttack.html

Thanks,
Vishwas
-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Tuesday, August 16, 2005 8:41 PM
To: Vishwas Manral
Cc: Stephen Kent; [email-masked]
Subject: Re: [RPSEC] Minutes and Presentations from Paris are now
Posted... 

In message
<[email-masked]>, "Vis
hwas Manral" writes:
>Hi Steve,
>
>> Steve Kent: The keyed MD5 and HMAC constructs in current use are 
>> not vulnerable to the sort of hash function attacks that Russ cited
>> in his presentation. These attacks allow someone to construct
distinct
>> bit strings that yield the same hash value, but do not allow someone 
>> to create a distinct bit string that maps to a has value chosen by 
>> someone else, much less a hash value that is chosen by someone else 
>> and that is a function of a secret key.
>What you are saying is that although "Birthday attacks" are possible,
>they may not be such a problem in the case described in the draft?
>
>I guess your concern is regarding: -
>
>"While there are no openly published attacks on that mechanism, some
>reports [Dobb96a, Dobb96b] create concern about the ultimate strength
of
>the MD5 cryptographic hash function", 
>which we have taken from the
>http://www.ietf.org/internet-drafts/draft-rja-ripv2-auth-01.txt draft.

He's referring to Wang's attacks -- she has found 
collisions in MD5 and shown how to do so for SHA1.  See
http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions/
for an explanation.  *But* -- the attacks don't apply to these hash 
functions when used as part of HMAC.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

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

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 17 Aug 2005 00:19:38 -0400

In message <[email-masked]>, "Vis
>http://mathworld.wolfram.com/BirthdayAttack.html

A collision attack is where you produce two messages, A!=B, such that 
H(A) = H(B).  For an n-bit hash function, that should require work 
factor 2^(n/2).  The attacks on current hash functions -- MD5 is dead 
from that perspective; the latest word, from CRYPTO, is that there is 
now a 2^63 attack on SHA-1, as compared to its design strength of 2^80 
-- are quite serious.  These are much better than brute force.

I would not take comfort from the structure of the packets.  There was 
a lovely talk at CRYPTO on how to find useful collisions in quite a 
variety of file formats.  There's even been a demonstration of how to 
produce a certificate with two different public keys that have a 
collision.

The bottom line is simple: if your use of a hash function is vulnerable 
if a collision is found, you need to replace it.  If you're using MD5, 
you need to replace it *soon*.  You *probably* have a few years for 
SHA1, but I have no confidence in that number.

---

From: Paul Jakma <[email-masked]>
Date: Wed, 17 Aug 2005 07:49:53 +0100 (IST)

On Wed, 17 Aug 2005, Steven M. Bellovin wrote:

> I would not take comfort from the structure of the packets.  There 
> was a lovely talk at CRYPTO on how to find useful collisions in 
> quite a variety of file formats.  There's even been a demonstration 
> of how to produce a certificate with two different public keys that 
> have a collision.

These attacks are all with fully known/controllable input (TTBOMK). 
The attacker constructs /both/.

Further, in HMAC code, you have a secret you have to guess too. In 
OSPF it's 32 bits but only 28bit effectively due to how some (most?) 
systems allow the secret to be configured (ASCII). So you have 
another 28 bits you need to brute-force before you can apply your MD5 
collision methods (which, to date, are /not/ for arbitrary input 
IIRC. you must be able to 'mould' the input to make it suit).

For the likes of OSPF it would be more fruitful today to examine and 
revise how the 'secret' is configured and used so as to make full use 
of those last 4 bits of the secret.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
Some people can tell what time it is by looking at the sun. But I have never
been able to make out the numbers.

---

From: Tony Tauber <[email-masked]>
Date: Thu, 18 Aug 2005 11:13:41 -0700 (PDT)

On Wed, 17 Aug 2005, Steven M. Bellovin wrote:

> A collision attack is where you produce two messages, A!=B, such
> that H(A) = H(B).  For an n-bit hash function, that should require
> work factor 2^(n/2).  The attacks on current hash functions -- MD5
> is dead from that perspective; the latest word, from CRYPTO, is that
> there is now a 2^63 attack on SHA-1, as compared to its design
> strength of 2^80 -- are quite serious.  These are much better than
> brute force.

Given that this list is composed of people with varying levels of
familiarity with cryptography and its application; and because this
topic appears to be a frequent source of confusion, perhaps more
clarification is warranted.

Steve, below you mention "useful collsions".  What I take that to mean
is a collsion where message B has semantics which will match the
situation in a way that is useful to an attacker.  In the context of a
routing protocol, I'd guess this to be a packet which is semantically
valid within the protocol and but changes the outcome in a way that's
adventageous to the attacker.

Can you comment on how that improves the profile (or not) of these
functions?  For instance, I'd expect that if a PDF of my credit card
bill comes every month and I'm used to the format of it (e.g.
layout and logo graphics) it'd be very hard to produce a file with the
same format but just some of the numbers changed. 
(Perhaps the analogy isn't valid, but hopefully I'm being clear in
what I'm asking.)

Tony

> The bottom line is simple: if your use of a hash function is
> vulnerable if a collision is found, you need to replace it.  If
> you're using MD5, you need to replace it *soon*.  You *probably*
> have a few years for SHA1, but I have no confidence in that number.
>

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 18 Aug 2005 14:29:16 -0400

In message <[email-masked]>, Tony Tauber write
>(Perhaps the analogy isn't valid, but hopefully I'm being clear in

Your definition of "useful" is almost correct, but leave room for 
changes to other fields in a way that isn't harmful.  Your example of a 
PDF document is a good one, because that was one of the examples used 
in the talk at CRYPTO.  You can generate two different versions of the 
PDF file, where there's text that can vary -- but its font color is set 
to white, so it's effectively invisible.

For BGP, this is easy to do: add an attribute, with the  Optional bit 
set to 1, and the rest of the type code set to something you're pretty 
sure the other side doesn't understand, and hence will ignore.  (Set 
Transitive, Partial, and Extended Length according to taste.)  The 
value field is then an opaque field that can be changed at will to 
produce the desired collision.

Now -- I'm not saying this is a useful thing to do.  Remember that 
we're talking about a collision attack, not a pre-image or second 
pre-image attack.  (See draft-hoffman-hash-attacks-04.txt for an 
explanation of what these mean.)  What I am saying is that you can't 
assume there are no problems, just because of the structured nature of 
the data.

---

From: Paul Jakma <[email-masked]>
Date: Thu, 18 Aug 2005 19:45:07 +0100 (IST)

On Thu, 18 Aug 2005, Tony Tauber wrote:

> functions?  For instance, I'd expect that if a PDF of my credit 
> card bill comes every month and I'm used to the format of it (e.g. 
> layout and logo graphics) it'd be very hard to produce a file with 
> the same format but just some of the numbers changed. (Perhaps the 
> analogy isn't valid, but hopefully I'm being clear in what I'm 
> asking.)

 	http://www.cits.rub.de/MD5Collisions/

Note however that the deviant actor must prepare /both/ inputs, and 
further must make use of some tricks in the format of the input to 
hide some of the differences from cursory inspection. In this case 
it's in the details of the postscript, but you could theoretically 
exploit similarity of glyphs in UTF-8, or, in the below example, 
special terminal control characters (on linux console):

 	http://www.derkeiler.com/Mailing-Lists/securityfocus/bugtraq/2004-12/0067.html

MD5 does not /yet/ appear to be vulnerable to finding a collision for 
a /specific/ (fixed, eg cause it's someone else's packet) message.. 
And even if MD5 were, you still have about 28 bits of protection due 
to the HMAC usage mode (the secret key which is not included in the 
message), which is typically the case in routing protocols (OSPF).

As someone pointed out in Paris, if someone guesses your key as part 
of trying to attack the MD5 HMAC, then you're out of luck anyway - 
the attacker no longer needs to find MD5 collisions ;).

IANAC, i'm just rehashing information I gleaned from others.

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
It appears that PL/I (and its dialects) is, or will be, the most widely
used higher level language for systems programming.
 		-- J. Sammet