Colliding RFC 3161 time-stamp tokens, via MD5-collisions

[Alfonso De Gregorio <alfonso.degregorio@xxxxxxxxxxxxxxxxxxx>]

Hi All, please accept my apologies if you have received this more than once.

First, 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.

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;
   ii) the genTime (the time at which the time-stamp token has been
       created) and the serial-number needs to be guessed;
  iii) the position where the nonce field ends should be an exact
       multiple of 64 octets;

  (ii) 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). The accuracy is a public information and
  is typically equal to one second, or lesser values.

  In several implementations, the serial number is also guessable,
  since its a monotonically increasing number or derived from the
  system time.

  (iii) The third condition can be dealt with by filling out the
  nonce field with random data up to an exact multiple of 64 octets.
  This is a first part of the nonce value. For future reference,
  the offset where the first part of the nonce ends is labeled
  Offset-1. A second bitstring will be appended to it (see the
  step number 4).

2. The MD5 algorithm get executed on the first portion of the
 "to be signed" part, truncated at the position Offset-1
 (i.e., where the first part of the nonce ends). The input
 to MD5 is an exact multiple of 512 bits. The padding normally
 used in MD5 needs to be suppressed. The output should to be
 taken as the IV used as input for the next step.

3. Perform the step number 3 described by Lenstra et al. in
 'Colliding X.509 Certificates' available at
 <http://eprint.iacr.org/2005/067>. Two different bitstring,
 b1 and b2, whose length is a multiple of 512 bits, get
 constructed, using the technique developed by Wang et al.,
 for which the MD5 compression function with the IV from the
 previous step produces a collision.

4. Append the bitstring b1 into the time-stamp token template
 after the Offset-1. This bitstring completes the nonce value.
 Now all the (to be) signed data are complete and a time-stamping
 transaction can start with the given TSA. In the time-stamp
 request the attacker will specify the nonce that contains the
 bitstring b1.

5. The TSA replies with the time-stamp response that contains
 (seemingly) the expected time-stamp token.

6. To obtain the second valid time-stamp token, replace b1 for b2
 in the nonce field. The signature remains valid.

The time-stamp tokens are syntactically well-formed and obviously
valid also by a cryptographic standpoint, since their digital signature
can be verified by relying parties.

The same method may be applied against other iterative hash functions,
if a technique is identified to produce collisions with prescribed IV
also with the target function.


Finally, it would be much more interesting if someone would be
able to construct pairs of colliding RFC 3161 time-stamp tokens
whose genTime field (and/or serial number field) can be arbitrary
chosen. This would allow the pre-dating and post-dating of
data and would have a severe negative impact on intellectual property
protection applications and notary services based on RFC 3161 digital
time-stamping - reaffirming the importance of a strong evidence of
temporal ordering of time-stamps.


Alfonso