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

[Paul Halliden <PHalliden@xxxxxxxxxxxxx>]

Terry, Michael

I agree that finding "meaningful" collisions *can* be substantially harder
than simply finding two arbitrary strings with the same hash.  How much
harder, depends on the application.  For instance, if a strictly formatted
message has provision for a 64-bit randomly allocated nonce, the task is no
more difficult.  The point is that, as security system designers, we should
not make any assumptions about the message and it is therefore safest to
assume that creating a set of meaningful messages is not significantly more
difficult than creating un-meaningful ones. Ok, there are many cases where
that will not be valid, but...

Certainly, as Terry argues, collisions in the TSA's own process will always
be a concern. Whether or not end entity collisions are a concern to the TSA
is application dependent.  As a minimum, collisions deliberately created by
the end entity would be an embarrassment to the TSA and affect the
perception of it in a public dispute.  Again, I would argue that it is
safest not to make assumptions about the application.

As regards the possibility of actually mounting a "brute force" attack on
MD5 today, I originally said that "this task is far from trivial".  That is
British understatement for "very difficult".  As far as I am aware,  the
largest exhaustive search was for 56-bits in 1997 - and that required
massive distributed processing.  Searching for a collision would also
require large amount of memory / storage (one has to store the variable part
of 2^64 [meaningful] messages and their hash in order to have about 50%
probability of having two identical hashes).  So I do not expect to read of
a successful brute force attack on MD5 this year - but I would not express
great surprise if it happened.

Regards
Paul Halliden

>-----Original Message-----
>From: thayes@netscape.com [mailto:thayes@netscape.com]
>Sent: 22 June 2000 19:13
>To: Paul Halliden
>Cc: 'Paul Koning'; seidel@timeproof.de; FRousseau@chrysalis-its.com;
>Denis.Pinkas@bull.net; ietf-pkix@imc.org
>Subject: Re: I-D ACTION:draft-ietf-pkix-time-stamp-08.txt
>
>
>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
>> >
>