Comments: Cryptographers have a Responsibility to Explain Results

Well I think bad guys like the Gambinos study crypto and will put people on finding a means to form an economic attack but not today. The legal users and designers of crypto have been fair and honest. The FUD folks will always be there selling worthless FUD snakeoil draining the resources from the real issues or developments. So in a sense the Gambinos like the FUD folks and may have joined their ranks to acquire a fast monetary gain. As the FUD folks and the Mafia move away from real and legal usage they take away from the purity of crypto for commercial purposes, but oddly enough enhance the secret spy usage by increasing the size of misdirectional information pool. The legal commerce users and the spy community have found a point from which they differ spys like FUD, Mafia, and misdirectional snakeoil good folks do not. Examine if you will the references to the MD5 almost attack
The Authors state
""How to verify
The certificates are valid in the sense that they comply with the relevant standards (RFC
3280, ASN.1 DER encoding), and also in the sense that their digital signature can be verified
against the issuing Certification Authority’s certificate. For manual verification of our claims
we have provided the above byte dumps, as well as further technical data (such as the prime
factors of the moduli and the CA public key) at the mentioned website. We would like to
advise the interested reader about more convenient ways of verifying our claims. Tools that
can be used are e.g. Peter Gutmann’s dumpasn14, and Microsoft’s standard Certificate Viewer
as it comes with e.g. Windows XP. Unfortunately Microsoft’s Certificate Viewer does not show
the certificate’s signature, but dumpasn1 does, as the final byte string of length 257. Note that
when the CA certificate is installed in the standard Windows (Internet Explorer) Certificate
Store, the Certificate Viewer will automatically validate the certificate signatures against the
CA certificate.
4 See

What they state clearly is that the standards for the verification of certificates is flawed and that additional modification need to be developed for the certificate viewers like Microsofts.

In Valerys blog,date,2005-03-02.aspx
She states
""Two certificates with the same signature has been published on ePrint

Wang, Lenstra and de Weger have published article on Cryptology ePrint with announcement of construction of two different X.509 certificates with the same MD5 hash:

Certificates differ only in subject’s public key (the rest is exactly the same). The paper provides algorithm describing how to use Wang et al. MD5 hash collision algorithm together with a clever way of constructing two distinct RSA 2048 bit keys pairs with modulus that differ only in their high 1024 bits, but gives MD5 hash collision (taking result of MD5 compression function on starting “common” part of certificates as IV).

Great work!

By the way: certificate signing is an example of chosen message attack and does require collision resistance. This opens new revenue for attacks…, however my point is that if you started to trust certificate of malicious party it will always be dangerous decision for you, regardless of them having duplicate certificates or not… and here we are talking about two certificates that has everything equal except for subject public key – I don’t quite recall the last time I’ve memorized and checked subject public keys on certificates I have stored on my box ;-)

So the question is one of usage and selection of applications. This makes the certificate a questionable feature for security to use exclusively. The FUD folks will ask ""Do you want additional functionality added to your browsers?"" well lets sell you some. The spys will test the attack construction using the Mafia as their test bed and the financial rewards will be split between the two. So does that mean that an attack scenario can not be developed for this construction? Well it probably has been done already and the corporations that aggregate consumer information will use this as a method to side step their lack of responsible behavior in guarding consumer transactions. The spys and the mafia have had a tough time of it of late with all the cut backs in spending due to the peace dividend and a real war in the middle east going on. This lack of funding provided the spy and mafia community has forced them into a commercial space to obtain funds illegally. These are not people that ask twice for their money if it can be stolen they steal it. So the spys and the mafia work hand in hand making money scamming us all gathering information and playing the world like a harmonica. The disclosure of this almost attack was probably funded by some legal defense fund for CA folks and their clients that have sold or misplaced consumer information and allowed theft to go on. Lets see at one time Mutual Funds corrupting the process of common investors funds for their own personal benefit was considered beyond understanding. Now that the myth has been dashed against the rocks of reality lets look at the carefully constructed release of the MD5 collision and assume that there is an evil purpose behind its disclosure. Perhaps something has already happened and the linkage between the two events has not been established. I suggest that the liability to a wide array of clients of CAs and applications used in conjuncttion with the ceritifcates is being defused. After all why should they be held responsible its all an academic excercise ask the financial crypto conference your only guilty of product liability if you loose you professorship. The published report should be examined with a microscope and angles of corruption determined. The academic forum should be held to tough standards of ethical review because the appearance of objectivity has become questionable and the funding of the research in this case suspect. Even if nothing happens because of this attack the FUDs win they wasted our time and resources in their efforts to drain us for the eventual attack from our as yet unknown evil enemies.

Posted by Jimbo at March 13, 2005 11:16 AM

I have to admit that I did not read the paper before today. Your comments motivated me to take a look at it.

Some of what you say here is not quite right. The colliding keys they construct are valid RSA keys for which they know the private components. On page 2 of the paper they generate p1, p2, q1, q2 which are the factorizations. They say, "It is reasonable to expect, based on the Prime Number Theorem, that this algorithm will produce in a feasible amount of computation time, two RSA moduli n1=p1q1 and n2=p2q2, that will form an MD5-collision with the specified IV."

So these certs can in fact be used in normal signature protocols. However, it is still not an attack!

This does not let you create a key/cert that matches someone else's key. That would require reversing MD5, while these attacks merely let you generate collisions. This lets you create two RSA keys, get one signed (certified), and then substitute the other RSA key while keeping the certificate signature valid. (And this requires that the CA use MD5, which none of them do any more, and that you predict the precise certificate serial number and creation/expiration date/times.) Even if you satisfy these requirements, you don't accomplish anything, security-wise, by being able to swap one RSA key you control for another.

What would be a legitimate attack would be if you could change out the naming information in the cert, rather than the RSA key. You could get your key/name certified legitimately, and then change the name, giving you a cert on a name you weren't supposed to have. But the problem with this is that the Wang technique produces random-looking binary data for the collisions, so it would not be suitable for a name field.

Posted by Cypherpunk at March 14, 2005 01:00 AM

Good explanation! We need more of that. I agree your explanation looks better than mine.

Posted by Iang at March 14, 2005 01:33 PM
Post a comment

Remember personal info?

Hit Preview to see your comment.
MT::App::Comments=HASH(0x55f72a14d568) Subroutine MT::Blog::SUPER::site_url redefined at /home/iang/www/fc/cgi-bin/mt/lib/MT/ line 125.