Subject: Re: [Cfrg] Applications of target collisions: Pre or post-dating MD5-based RFC 3161 time-stamp tokens

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 26 Oct 2006 13:13:14 -0400

So how close are we getting to first or second preimage attacks?

---

From: Russ Housley <[email-masked]>
Date: Thu, 26 Oct 2006 14:01:43 -0400

FYI.

>Date: Thu, 26 Oct 2006 13:23:06 -0400
>From: Alfonso De Gregorio <[email-masked]>
>To: "Weger, B.M.M. de" <[email-masked]>, [email-masked],
>         [email-masked], [email-masked], [email-masked]
>Subject: [Cfrg] Applications of target collisions: Pre or 
>post-dating MD5-based RFC 3161 time-stamp tokens
>
>Hi All,
>
>On 3rd march 2005, in a follow up to the announcement by Benne de Weger,
>Xiaoyun Wang and Arjen Lenstra [LWdW], I wrote a note explaining how it
>is possible to apply their method also for the construction of pairs of
>colliding RFC 3161 [3161] time-stamp  tokens - my original note is
>available at: <http://crypto.lo.gy/writings/CollidingTST.pdf>
>
>However that construction based on random collisions do not posed a
>significant  threat to RFC 3161 players, as all the opponent was able to
>do was to show that  the target Time Stamping Authority not complied
>with section 2.4.2 of the  standard.
>
>In the time-stamping setting, a severe attack is an attack that allows
>the opponent to obtain assertions of proof, signed by a target TSA, that
>a datum  - possibly never processed by the time-stamping unit - existed
>at a moment in time chosen at will.
>
>Using the recent method by Marc Stevens to construct MD5 target
>collisions  starting from two arbitrary IHVs [MS], and moving on the
>construction of colliding  X.509 certificates for different identities
>by by M. Stevens A. Lenstra and  B. de Weger [SLdW], it is possible to
>construct two MD5 based time-stamp tokens with  different genTime,
>serialNumber and messageImprint fields. These fields contain
>respectively the time at which the token has been created by the TSA,
>the  integer assigned by the TSA to each time-stamp token, the hash of
>the time-stamped datum. Hence this allows also the pre-dating and
>post-dating of  tokens and can have a severe negative impact on RFC 3161
>based applications  that need to build a strong evidence of temporal
>ordering of events  (e.g., RFC 3126, intellectual property protection).
>
>In this email I'll not provide the construction details and an actual
>pair of such colliding tokens, just a short outline.
>
>The scenario consist in an opponent trying to generate simultaneously
>two colliding time-stamp tokens, where the genTime field (or
>messageImprint, or serialNumber) is different. The opponent can interact
>with the target time-stamping unit, requesting it to issue time-stamps
>for selected  messages.
>
>In order to succeed in the attack, the following requirements need to be
>fulfilled:
>
>1. the opponent need to hide random looking data in the target tokens;
>2. the signed-data of time-stamp tokens need to have equal bitlength to
>accommodate the Merkle-Damgard strengthening;
>3. the opponent need to predict all fields appearing before the chosen
>random looking strings.
>
>Looking at the TSTInfo data structure (see the standard for more
>details [3161]) and to the current implementations of RFC3161, it is
>easy to see how all these  conditions can be dealt with by the opponent:
>
>TSTInfo ::= SEQUENCE  {
>    version                      INTEGER  { v1(1) },
>    policy                       TSAPolicyId,
>    messageImprint               MessageImprint,
>      -- MUST have the same value as the similar field in
>      -- TimeStampReq
>    serialNumber                 INTEGER,
>     -- Time-Stamping users MUST be ready to accommodate integers
>     -- up to 160 bits.
>    genTime                      GeneralizedTime,
>    accuracy                     Accuracy                 OPTIONAL,
>    ordering                     BOOLEAN             DEFAULT FALSE,
>    nonce                        INTEGER                  OPTIONAL,
>      -- MUST be present if the similar field was present
>      -- in TimeStampReq.  In that case it MUST have the same value.
>    tsa                          [0] GeneralName          OPTIONAL,
>    extensions                   [1] IMPLICIT Extensions   OPTIONAL  }
>
>
>(1) The opponent will use the nonce field to hide random looking data.
>It is worth to note how the ASN.1 SEQUENCE provides an ordered series of
>elements and the nonce field, if set, will appear in the DER encoded
>data always after the genTime and before the tsa general-name.
>
>More specifically, the opponent, using the method developed by M.
>Stevens [MS], will construct two bit-strings that, when appended to the
>two targeted messages, will turn them  into MD5 collisions. Here the
>target messages chosen by the attacker contain, among others, the
>genTime, serialNumber and messageImprint fields. This leads to the
>aforementioned abuse scenario.
>
>Though this may appear a bit overdone, the nonce field can contain huge
>integers. The standards do not specify any additional size constraint on
>nonces, hence  the maximum and minimum values for these ASN.1 integers
>are those imposed by  the specific encoding rules (i.e.; DER).
>
>(2) For any selected algorithm suite, the signed-data will have a
>bitlength known a priori by the opponent. The fields that precedes the
>nonce will have a bitlength known as well.
>
>(3) With regard to guessing the signed values:
>
>version: Constant value;
>
>policy: Known for any given time-stamping unit;
>
>messageImprint: Chosen by the attacker;
>
>serialNumber: In several implementations, the serial number is
>guessable, since it's a monotonically increasing number or a quantity
>derived from the system time;
>
>genTime: The value at which the genTime field will be set by the TSA
>can be guessed depending on the accuracy of the clock (i.e.,the time
>deviation around the UTC time contained in genTime) and the time
>required  to send and consume the time-stamping request message (e.g.,
>the half  round-trip latency plus the processing time);
>
>accuracy: The accuracy is a public information and is typically equal
>to  one second, or lesser values;
>
>ordering: Known for any given time-stamping unit.
>
>The detailed construction builds on the above considerations and the
>resulting  time-stamp tokens will be syntactically well-formed and
>obviously valid also  by a cryptographic standpoint, since their digital
>signature can be successfully  verified by the relying parties.
>
>Cheers,
>
>-- Alfonso    http://crypto.lo.gy
>
>
>[LWdW] A. Lenstra, X. Wang, B. de Weger, Colliding X.509 Certificates,
>        <http://eprint.iacr.org/2005/067>
>   [MS] M. Stevens, TU Eindhoven MSc thesis, in preparation
>[SLdW] M. Stevens, A. Lenstra, B. de Weger, Target Collisions for MD5
>        and Colliding X.509 Certificates for Different Identities,
>        <http://eprint.iacr.org/2006/360>
>[3161] C. Adams, P. Cain, D. Pinkas, R. Zuccherato, Internet X.509
>        Public Key Infrastructure Time-Stamp Protocol (TSP),
>        <http://www.ietf.org/rfc/rfc3161.txt>

---

From: Alfonso De Gregorio <[email-masked]>
Date: Fri, 27 Oct 2006 08:09:20 -0400

Hi Steven, hi Benne,

Yes, this is a sweet and sour truth. We are not getting closer to
preimage attacks. We are getting more far away from considering preimage
and second-preimage resistance sufficient hash-function requirements for
the real-world security of some protocols.

Cheers,

Weger, B.M.M. de wrote:
> As far as we know, not one bit closer. 
> Best known attack on MD5 preimage resistance still is brute force. 
>
> You may interpret our result as enlarging the applicability of 
> collision attacks. In that sense the gap to preimage attacks has 
> diminished. But we have no measure available to tell by how much.
>
> Grtz,
> Benne de Weger
>