Subject: RE: I-D ACTION:draft-ietf-pkix-time-stamp-08.txt

From: Paul Halliden <[email-masked]>
Date: Thu, 22 Jun 2000 18:16:18 +0100

There were two potential issues with MD5.  The first one was an indication
that, at the time MD4 was "broken", MD5 was expected to fall to a similar
attack "in the near future".  That has not happened so far.  We do not know
if that is because the task was too hard or if it was simply that no-one has
got round to trying.  But it was the reason that many stopped using MD5 at
that time.

The second potential issue concerns the size of an MD5 hash, which is
shorter than an SHA-1 hash.  If an end entity is able to create two messages
that have the same value of hash, he can submit the hash to the TSA and then
subsequently claim that either of the messages existed. When challenged, the
end entity presents whichever version of the message best suits his argument
- an adjudicator would not be able to tell which was the genuine one. Whilst
this task is far from trivial for a 128-bit hash such as MD5, I believe it
is the same order of magnitude as finding a 64-bit symmetric key by
exhaustive search. (IANAC - so any cryptographer / mathematician please feel
free to correct me).

This potential attack is, IMHO, more significant for a TSA where one entity
chooses the message and generates the hash and a second entity signs it (as
part of the timestamp).  

Regards
Paul Halliden

>-----Original Message-----
>From: Paul Koning [mailto:[email-masked]]
>Sent: 19 June 2000 16:00
>To: [email-masked]
>Cc: [email-masked]; [email-masked];
>[email-masked]
>Subject: Re: I-D ACTION:draft-ietf-pkix-time-stamp-08.txt
>
>
>>>>>> "Joerg" == Joerg Seidel <[email-masked]> writes:
>
> Joerg> Comments inline.
> >> TSA implementations MUST support SHA-1.  TSA implementations
> >> SHOULD support MD5.
>
> Joerg> I think there are good reasons not to use MD5 in time
> Joerg> stamps. They should use a strong hash function in order to
> Joerg> achive long validity periods. MD5 is likely to be unsafe (=not
> Joerg> collision free) soon and is already discuraged by german
> Joerg> authorities.
>
> Joerg> IF we add a section about algorithms, it should maybe read:
> Joerg> "TSA implementations MUST support SHA-1.  TSA implementations
> Joerg> SHOULD NOT support MD5.". But I think such a section is not
> Joerg> very necessary.
>
>IANAC, but from what I understand the currently known attacks on MD5
>are nowhere near strong enough to justify that.  
>
>I don't have a problem with the current text (SHA-1 required, MD5
>recommended).  I do have a problem with text that implies that MD5 is
>bad, because I don't know of data that supports such an assertion.
>
>Also, it doesn't seem like a good idea for the timestamp spec to give
>very different signals from the other security specs.  If there really
>is good reason to say these kinds of things about MD5, let's have them
>identified.  (German authorities are not a good reason.  Cryptanalysis
>that shows weaknesses of interesting size would be.)  If the issues
>are real, changes to MD5 text should be applied across the board.
>
>      paul
>

---

From: Michael Sierchio <[email-masked]>
Date: Thu, 22 Jun 2000 10:43:18 -0700

Paul Halliden wrote:
> 
> There were two potential issues with MD5. 

A potential issue is not an issue...

> ...If an end entity is able to create two messages
> subsequently claim that either of the messages existed. 
> ...(IANAC - so any cryptographer / mathematician please feel
> free to correct me).

The difficulty of finding any two messages that have the same MD5
hash is enormous.  But consider that if both such messages are to
be meaningful it is quite another order of difficulty (greater,
if it isn't obvious).  

There is still no mechanism for creating a message which has
a given MD5 hash value...

---

From: [email-masked] (Terry Hayes)
Date: Thu, 22 Jun 2000 11:12:54 -0700

Paul,

Addressing the first point in your message (a client submitting a "cooked" MD5
hash for timestamping), there are two points to make:

1.  Finding collisions in MD5 is still hard, and finding meaningful ones much
harder.
2.  It is not the concern of the TSA whether the client has chosen a form of
message imprint that will hold up under a challenge.  The TSA's function is to
associate a timestamp with the message imprint, no more.  Whether that message
imprint can be used later to convince a third party that a particular document
was reference is more important to the client.  The client should choose an
imprint algorithm that will meet their requirements.

Addressing the second point (getting the TSA to generate a colliding time stamp
token):

1.  Again, it is difficult to find meaningful collisions.
2.  The TSA is concern in this case, since a collision could result it a token
that indicates a different timestamp (probably an earlier one).
3.  The TSA should choose a strong signature algorithm that will provide the
appropriate level of assurance for the required time period.  I suspect that
many TSAs will choose a signature based on SHA for this reason.  They will also
choose key lengths depending on the desired security level.
4.  Since a large part of the timestamp token is fixed or guessable, t is
probably worth including a "nonce" value in the generated signature to make it
difficult to force the TSA into generating a colliding signature.  This value
can easily be incorporated into the CMS SignedData object as a signed attribute.

Terry Hayes
Netscape Communications Corp.