> -----Original Message-----
> From: Michael Wojcik [mailto:[EMAIL PROTECTED]]
> Sent: Thursday, December 06, 2001 10:46 PM
> To: [EMAIL PROTECTED]
> Subject: RE: Cryptology Questions
>
>
> > From: Neff Robert A [mailto:[EMAIL PROTECTED]]
> > Sent: Thursday, December 06, 2001 2:47 PM
> > Indeed, collisions of messages *must* exist. However, by it's
> > very nature, the other message(s) causing the collisions would,
> > with almost 100% certainty, not be valid within the context it
> > was used in.
> This is a dubious claim. Take a look at Gideon Yuval's
> protocol for using a birthday attack against a cryptographic
> hash, as described in AC2 (18.1, p 430): Alice creates two
> versions of a contract, one fair, the other favorable to her.
> She uses a cosmetic change - eg. an extra space is either
> present or not before the newline - on each of N/2 lines in
> each contract (where N is the size in bits of the hash). By
> toggling her change - adding or removing the unnecessary
> space character - on the N/2 lines independently, she
> obviously can create N/2 variations of each of her two
> documents. Thanks to the birthday paradox, the odds favor
> her finding a colliding pair. Then all she has to do is take
> the "fair" contract from the pair and convince Bob to sign
> just the hash (and not, say, make a cosmetic change to the
> contract, and then hash and sign that), and she can
> substitute the "unfair" contract at a later date and
> demonstrate that it hashes to the value the Bob signed.
It's even worst than that: Alice can agree with Bob to the original
contract, and have Bob sign it. THEN she have:
- The contract itself (which can be used to generate the MD5 digest)
- Bob's signed MD5 digest
Then applying the birthday attack she can fiddle with the "better-for-her"
contract till it generates the same MD5 digest. The mere fact the MD5 digest
is the same makes that Bob's signature "match" this contract.
The fact this can be done afterwards has several implications:
1) As time goes, machines are faster and faster, so the attack is simpler
and simpler. Just this should promotes avoiding short digests for long-lived
contracts.
2) Bob can decide, as an afterthought, that it may be beneficial for him to
"repudiate" a contract that he've signed, as he can play exactly the same
game :-)
The only solution to this, that will increase the difficulty of tampering
with a contract, is requesting both parts to sign exactly the same contract,
but with a mention of which is signing. For example you can have as
contract:
"This contract is between Bob and Alice and say that SO AND SO."
Then Bob will sign:
"This contract is between Bob and Alice and say that SO AND SO.
Signed by BOB"
And Alice will sign:
"This contract is between Bob and Alice and say that SO AND SO.
Signed by ALICE"
The final contract being:
"This contract is between Bob and Alice and say that SO AND SO."
Bob's signature
Alice signature
Note that "Signed by BOB" and "Signed by ALICE" could be replaced by their
certificates, expurged from the public key to avoid any risk of key
"interference" that coudl occur when signing with the private key something
that is dependant on the public key.
Then the birthday attack will need to find a tampered contract that
generates the same MD5 (or SHA1 or SHA-4096 if that ever exist) than the
original one for both to-be-signed messages. I'm not an expert but it looks
like it would be VERY difficult to find a double collision, perhaps
completely defeating the birthday paradox.
And anyway such a double signing is requested for a lot of contracts, as a
lot of these are mutually binding; if the contract will only bind me, I'd
probably arrange to get two certificates from two different CAs, with as
much different optional info on each one, and sign the contract twice.
Note that you must expect this kind of after-signing compromission to be
possible for as long as the CONTRACT is valid, as certificate
expiration/revokation is of no help here: once you've signed, you're bound
to what you've signed. Or else you have to expect having to sign again
regularly ;-(
> In short, there's a perfectly good algorithm for finding
> valid colliding documents, assuming you can and want to do
> the work required for the birthday attack (2 to the power of
> N/2 on average), and assuming you can make N/2 independent
> cosmetic changes to each of the documents. Of course, in
> actual applications those assumptions are often not met; but
> simply assuming that colliding pairs of valid documents are
> much harder to find than other collisions is a mistake.
Especially as this is simpler and simpler as computer are faster and faster;
and anyway every year there's people winning at the lottery...
Regards,
Bernard
--------------------------------------------
Bernard Dautrevaux
Microprocess Ingenierie
97 bis, rue de Colombes
92400 COURBEVOIE
FRANCE
Tel: +33 (0) 1 47 68 80 80
Fax: +33 (0) 1 47 88 97 85
e-mail: [EMAIL PROTECTED]
[EMAIL PROTECTED]
--------------------------------------------
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
