[17021] in cryptography@c2.net mail archive
[Fwd: [Cfrg] Colliding RFC 3161 time-stamp tokens based on MD5-collisions]
daemon@ATHENA.MIT.EDU (Alfonso De Gregorio)
Sun Mar 6 14:41:25 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sat, 05 Mar 2005 19:55:58 +0100
From: Alfonso De Gregorio <adg@Com-And.COM>
Reply-To: adg@Com-And.COM
To: cryptography@metzdowd.com
This is a multi-part message in MIME format.
--------------090906090502060403090708
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
I hope this might be of interest.
Alfonso
--------------090906090502060403090708
Content-Type: message/rfc822;
name="[Cfrg] Colliding RFC 3161 time-stamp tokens based on MD5-collisions"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="[Cfrg] Colliding RFC 3161 time-stamp tokens based on MD5-collisions"
Return-Path: <cfrg-bounces@ietf.org>
Received: (qmail 71271 invoked by uid 89); 4 Mar 2005 11:47:34 -0000
Received: (qmail 71262 invoked from network); 4 Mar 2005 11:47:32 -0000
Received: from unknown (HELO megatron.ietf.org) (132.151.6.71)
by com-and.com with SMTP; 4 Mar 2005 11:47:32 -0000
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
by megatron.ietf.org with esmtp (Exim 4.32)
id 1D7BGM-0005hI-Tj; Fri, 04 Mar 2005 06:46:34 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
by megatron.ietf.org with esmtp (Exim 4.32) id 1D7BGL-0005h0-Aa
for cfrg@megatron.ietf.org; Fri, 04 Mar 2005 06:46:33 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
by ietf.org (8.9.1a/8.9.1a) with ESMTP id GAA04552
for <cfrg@ietf.org>; Fri, 4 Mar 2005 06:46:30 -0500 (EST)
Received: from relay.andxor.it ([195.223.2.3] helo=com-and.com)
by ietf-mx.ietf.org with smtp (Exim 4.33) id 1D7BHt-00083j-Cg
for cfrg@ietf.org; Fri, 04 Mar 2005 06:48:10 -0500
Received: (qmail 71221 invoked from network); 4 Mar 2005 11:46:22 -0000
Received: from unknown (HELO ?192.168.2.12?)
(a.degregorio@com-and.com@192.168.2.12)
by com-and.com with SMTP; 4 Mar 2005 11:46:22 -0000
Message-ID: <422846C7.4070503@Com-And.COM>
Date: Fri, 04 Mar 2005 12:30:15 +0100
From: Alfonso De Gregorio <adg@Com-And.COM>
Organization: C&A S.r.l.
User-Agent: Mozilla Thunderbird 1.0 (X11/20041206)
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: cfrg@ietf.org
X-Enigmail-Version: 0.90.0.0
X-Enigmail-Supports: pgp-inline, pgp-mime
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Scan-Signature: a7d2e37451f7f22841e3b6f40c67db0f
Content-Transfer-Encoding: 7bit
Subject: [Cfrg] Colliding RFC 3161 time-stamp tokens based on MD5-collisions
X-BeenThere: cfrg@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
Reply-To: Alfonso.DeGregorio@acm.org
List-Id: Crypto Forum Research Group <cfrg.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@ietf.org?subject=unsubscribe>
List-Post: <mailto:cfrg@ietf.org>
List-Help: <mailto:cfrg-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@ietf.org?subject=subscribe>
Sender: cfrg-bounces@ietf.org
Errors-To: cfrg-bounces@ietf.org
X-Spam-Checker-Version: C&A Anti-Spam 1.2 by Alex Dupre
X-Spam-Level:
X-Spam-Status: No, hits=-2.6 required=4.5 tests=BAYES_00 autolearn=ham
Hi All.
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, and David McGrew for forwarding to the list.
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.
Best regards,
Alfonso
_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg
--------------090906090502060403090708--
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
