I see signs of a wave of FUD spreading through the net as cryptoplumbers try and interpret the latest paper on MD5 collisions in certs from Lenstra, Wang, Weger. I didn't have time to read the paper at the time, and wasn't easily able to divine from the chit chat what the result meant. When the dust settled, this was not an attack, but many assumed it was.
Why? Because it wasn't explained, neither in the paper nor anywhere else that I read. Reading the paper, the closest I came to a limitation on damage in human language was this:
``The RSA moduli are secure in the sense that they are built up from two large primes. Due to our construction these primes have rather different sizes, but since the smallest still are around 512 bits in size while the moduli have 2048 bits, this does not constitute a realistic vulnerability, as far as we know.''
The last part (my emphasis) may seem pretty clear, but the reasoning behind it is inaccessible to non-cryptographers. Further, it is buried deep: the key phrase is not in the abstract or conclusion, nor on the more accessible HTML page.
Now, in all probability, the authors may be surprised to know that non-cryptographers read these papers. That's because normally most of the output from cryptology is not of importance to the outside world - small improvements and small suggestions. And, frankly, it's economic for us all to let the people doing to work get on and do it without the distraction of the real world.
This time is different however. The Wang, Yin, Yu results go beyond the limited world of cryptography as they have shifted the security statement of a large class of algorithms in which we previously trusted and relied upon. This time we are all effected, and those who understand have a responsibility to explain what the real significance of the results is.
Here is my own limited interpretation:
The paper describes how to create a false or forged certificate based on MD5. But what it does not seem to say is that the key within the certificate can be forged, neither in private key form nor in useful public key form (on this last point I am not sure).Without the private key, the certificate cannot take place in a normal signature protocol. That's the point of the public key: to prove that the other party has control of the private key.
Which means no attack, as yet, in general. Yes, we should with all due speed deprecate MD5 in the production of certificates, but we are a long way from seeing the situation turn into an economic attack.
Addendum:But it looks like I got it wrong in detail. See cypherpunk's comment below, which explains how it is. We do concur on results though - no attack.
So where's the danger? People on the net are drawing out the unexplained results and assuming that things are totally broken. And that crosses the line into FUD.
It may be that encouraging a sense of Fear, Uncertainty and Doubt will help the Internet run like scared lemmings away from the now weakened MD5 hash. It may help build emphasis towards what we need - a serious effort to construct a new theory of message digest functions along the lines of NIST's AES competition.
But, more than likely, FUD will do what it has always done: spread confusion and cause people to make bad decisions. And, as those bad decisions are often made in the direction of the spreaders of FUD, we must understand that there is a financial benefit to those spreading FUD. More sales, more exposure.
This is not responsible behaviour. Now, to be clear, the primary authors of this paper are focused on the result, and we understand that distractions of dotting the i's and crossing the t's will slow down the real work. But those of us who are not involved in the creation of the new result have a duty to explain and teach, rather than steal the limelight.
Cryptographers as scientists and wider security specialists as advisers have a duty to deliver value in terms of security, not sales. We all have to be on the watch for the tempation to use FUD as the easy way for sales. In the long run, spreading FUD and reaping easy sales results in a mess that we as the security community have to clean up.
Worse, it spreads the doubt that cryptography and security as a science and specialisation is not worth listening to, because whatever we say next time has to fight the failure of last time. Selling FUD now means we are damned for all time to sell snake oil forever.
Posted by iang at March 13, 2005 09:09 AM | TrackBackWell 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 http://eprint.iacr.org/2005/067.pdf
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 http://www.cs.auckland.ac.nz/pgut001/
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 http://www.harper.no/valery/default,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: http://eprint.iacr.org/2005/067.
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 AMI 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 AMGood explanation! We need more of that. I agree your explanation looks better than mine.
Posted by: Iang at March 14, 2005 01:33 PM