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

[thayes@xxxxxxxxxxxx (Terry Hayes)]

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.

Paul Halliden wrote:

> 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:pkoning@xedia.com]
> >Sent: 19 June 2000 16:00
> >To: seidel@timeproof.de
> >Cc: FRousseau@chrysalis-its.com; Denis.Pinkas@bull.net;
> >ietf-pkix@imc.org
> >Subject: Re: I-D ACTION:draft-ietf-pkix-time-stamp-08.txt
> >
> >
> >>>>>> "Joerg" == Joerg Seidel <seidel@timeproof.de> 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
> >