headers
David A. McGrew | 2 Mar 2005 00:38
Picon
Favicon

Fwd: [saag] X.509 certificate collision, via MD5 collisions

FYI. Comments welcome.

David

Begin forwarded message:

> From: Russ Housley <housley <at> vigilsec.com>
> Date: March 1, 2005 3:24:00 PM PST
> To: saag <at> mit.edu, ietf-pkix <at> imc.org
> Subject: [saag] X.509 certificate collision, via MD5 collisions
>
> I have not had an opportunity to review this document yet, but the 
> findings need to be shared with the whole Internet security community.
>
>> We announce a method for the construction of pairs of valid X.509 
>> certificates in which the "to
>> be signed" parts form a collision for the MD5 hash function. As a 
>> result the issuer signatures
>> in the certificates will be the same when the issuer uses MD5 as its 
>> hash function.
>
> http://eprint.iacr.org/2005/067
>
>
>
> _______________________________________________
> saag mailing list
> saag <at> mit.edu
> https://jis.mit.edu/mailman/listinfo/saag
>
(Continue reading)

Permalink | Reply | 0 comments |
headers
Alfonso De Gregorio | 4 Mar 2005 12:30

Colliding RFC 3161 time-stamp tokens based on MD5-collisions

Hi All.

I would like to thank Arjen Lenstra, Xiaoyun Wang, and Benne de Weger
for announcing a method for the construction of pairs of colliding
X.509 certificates, and David McGrew for forwarding to the list.

I would like also to point out that it is possible, in a similar way,
to construct pairs of valid, but different, RFC 3161 time-stamp tokens
in which the signed data form a collision for the MD5 hash function.
This yields to the generation of the same signature by the
Time Stamping Authority when it uses MD5 as its hash function.

With this construction the attacker can easily craft MD5 collisions
in such a way that he or she constructs RFC 3161 time-stamp tokens
in which all fields, except the nonces, are equal (i.e., including
the TSA name and serial number). Hence, producing an evidence of the
apparent violation, by a given TSA, of an absolute requirement -
according to RFC 2119 - of the specifications. In fact, the RFC 3161
requires (see section 2.4.2) the uniqueness of the serial number that,
with the TSA name, must identify a unique time-stamp token.

The construction is straightforward.

1. First construct a template for the time-stamp token.
  All the fields must be completely filled in, with the exception
  of the nonce and the signature. The following requirements
  needs to be met:

     i) the data structure should be compliant to the RFC 3161 standard
        and the ASN.1 DER encoding rules;
(Continue reading)

Permalink | Reply | 0 comments |
headers
Hallam-Baker, Phillip | 16 Mar 2005 22:29
Picon
Favicon

Interim MAC function

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.
Permalink | Reply | 9 comments |
headers
David Wagner | 16 Mar 2005 22:58
Picon

Re: Interim MAC function

Hallam-Baker, Phillip wrote:
>What I came up with was the MASH digest, (MAC and SHA) as follows:
>	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.
Permalink | Reply | 7 comments |
headers
Michael Silk | 16 Mar 2005 23:29
Picon

RE: Interim MAC function

isn't the suggestion to prepend m and the output of SHA(m) such that if
your collision is for sha(m) only, it won't collide in hmac(m +
collision) ?

sort of like the proposal:

hash(m) = hashFunc1(m + hashFunc2(m))

I don't see how it could be less secure then HMAC as all it does is
provide more input to it; instead of just M you get SHA(m) too. Are you
able to explain a little bit how it makes it less secure?

-- Michael

> -----Original Message-----
> From: David Wagner [mailto:daw <at> taverner.cs.berkeley.edu] 
> Sent: Thursday, 17 March 2005 8:59 AM
> To: cfrg <at> ietf.org
> Subject: Re: [Cfrg] Interim MAC function
> 
> Hallam-Baker, Phillip wrote:
> >What I came up with was the MASH digest, (MAC and SHA) as follows:
> >	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.
>
(Continue reading)

Permalink | Reply | 1 comment |
headers
csjutla | 16 Mar 2005 23:39
Picon
Favicon

RE: Interim MAC function


I dont think MASH is breakable by just finding collisions in SHA-1.
On the other hand, it is like adding more rounds to MD5/SHA-1, but with a
shuffle. Interesting idea, though I am sure there are many such ideas.

Charanjit Jutla

Michael Silk writes:
 > isn't the suggestion to prepend m and the output of SHA(m) such that if
 > your collision is for sha(m) only, it won't collide in hmac(m +
 > collision) ?
 > 
 > sort of like the proposal:
 > 
 > hash(m) = hashFunc1(m + hashFunc2(m))
 > 
 > I don't see how it could be less secure then HMAC as all it does is
 > provide more input to it; instead of just M you get SHA(m) too. Are you
 > able to explain a little bit how it makes it less secure?
 > 
 > -- Michael
 > 
 >  
 > 
 > > -----Original Message-----
 > > From: David Wagner [mailto:daw <at> taverner.cs.berkeley.edu] 
 > > Sent: Thursday, 17 March 2005 8:59 AM
 > > To: cfrg <at> ietf.org
 > > Subject: Re: [Cfrg] Interim MAC function
 > >
(Continue reading)

Permalink | Reply | 0 comments |
headers
Scott Fluhrer | 16 Mar 2005 23:42
Picon
Favicon

Re: Interim MAC function


On Wed, 16 Mar 2005, David Wagner wrote:

> Hallam-Baker, Phillip wrote:
> >What I came up with was the MASH digest, (MAC and SHA) as follows:
> >	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.

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.
(Continue reading)

Permalink | Reply | 4 comments |
headers
csjutla | 17 Mar 2005 00:06
Picon
Favicon

Re: Interim MAC function


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).

Scott Fluhrer writes:
 > 
 > 
 > On Wed, 16 Mar 2005, David Wagner wrote:
 > 
 > > Hallam-Baker, Phillip wrote:
 > > >What I came up with was the MASH digest, (MAC and SHA) as follows:
 > > >	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.
 > 
 > 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):
(Continue reading)

Permalink | Reply | 0 comments |
headers
csjutla | 17 Mar 2005 00:15
Picon
Favicon

SHA-1: No post whitening


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)
Permalink | Reply | 2 comments |
headers
Daniel Brown | 17 Mar 2005 00:22

Re: Interim MAC function

David Wagner wrote on 03/16/2005 04:58:49 PM:

> Hallam-Baker, Phillip wrote:
> >What I came up with was the MASH digest, (MAC and SHA) as follows:
> >   MASH (m) = HMAC (m, (SHA (m))
> 
> 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.

> can find a collision in SHA1, they can break MASH.  This permits offline
> 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

> 
> _______________________________________________
> Cfrg mailing list
> Cfrg <at> ietf.org
> https://www1.ietf.org/mailman/listinfo/cfrg
Permalink | Reply | 0 comments |

Gmane