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: <htt
p://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.iac
r.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.iac
r.org/2006/360>
[3161] C. Adams, P. Cain, D. Pinkas, R. Zuccherato, Internet
X.509
Public Key Infrastructure Time-Stamp Protocol (TSP),
<http://www.ie
tf.org/rfc/rfc3161.txt>
------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomo metzdowd.com
|