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

From: Alfonso De Gregorio <[email-masked]>
Date: Thu, 26 Oct 2006 13:23:06 -0400

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>

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

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: "Weger, B.M.M. de" <[email-masked]>
Date: Thu, 26 Oct 2006 21:20:59 +0200

Hi Steven,

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

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

---

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,

---

From: Christian Rechberger <[email-masked]>
Date: Fri, 27 Oct 2006 16:33:31 +0200

> the real-world security of some protocols.
Hi everyone,

agreed to all you've said, still there are special examples where 
bridging this gap seems closer. Consider a special type of preimage 
resistance, CTFP (Chosen Target Forced Prefix), which was introduced by
John Kelsey and Tadayoshi Kohno in their paper "Herding Hash Functions 
and the Nostradamus Attack" at Eurocrypt 2006.

If new methods like the one developed by Marc Stevens for MD5 are 
sufficiently fast (just being faster than a birthday attack is not 
enough in this setting), then also herding attacks can be faster.
Hence finding a preimage for MD5 in this special setting would be faster 
than for a good MD-style hash function with the given output size.

Collision search for full SHA-1 (especially in this setting) does not 
seem to be fast enough to allow this speed-up of herding attacks. 
However, according to our experiments, with some new methods and 
reducing SHA-1 to e.g. 75% of its steps, this changes.

Note that the effort for finding a preimage by looking for lots of 
collisions in this setting would still be prohibitive in practice. For 
MD5 and even more so for SHA-1.

Note also that this does not allow to draw conclusions on the standard 
preimage or 2nd-preimage resistance of the mentioned algorithms. This 
seems a different and challenging problem.

Best regards,
  Christian Rechberger

-- 
Christian Rechberger <[email-masked]>
Krypto Group - IAIK - TU Graz, Inffeldgasse 16a, A-8010 Graz, Austria
http://www.iaik.tugraz.at/research/krypto/
phone: +43 (0)316 873 5534  ---  fax: +43 (0)316 873 5594