Applications of target collisions: Pre or post-dating MD5-based RFC 3161 time-stamp tokens

[Alfonso De Gregorio]

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>




---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com