EuroTech spoke with leading experts who claim this specific method has never been published and must have been developed independently and in total secrecy.
by Max Huijgen, EuroTech
By using a newly developed tool which analyzes rogue certificates (which allows malicious users to impersonate any website secured through the HTTPS protocol), Marc Stevens not only found that the Flame virus used a hitherto unknown method, but the researchers think they will be able to find the exact attack method by analyzing the data.
The news here is not that this certificate was falsified, but that the attackers clearly had world class cryptographic knowledge which they deliberately chose to withhold from the academic world.
To understand what the makers of the Flame virus did, we need to do some investigative work and reconstruct what happened here. EuroTech spoke with cryptographers to see how much we now know about the possible scenarios and sources to zoom in on the unknown attackers.
The recently found Flame virus was already known as the most advanced virus ever found. Its sheer size (in excess of 20MB), its capabilities (eavesdropping by enabling Bluetooth on mobile phones), the way it targeted only specific goals in the Middle East, the so called zero-day exploits to get into fully protected Windows 7 computers, all go to show Flame is definitely the most complex virus ever.
Now cryptographic experts from the Netherlands have established that the way Flame falsified a security certificate from Microsoft is not based on any known method in the academic cryptographic world. Ways to produce rogue certificates already exist, but here a completely novel approach was independently conceived by an unknown group with world class cryptographic knowledge.
We all know that the U.S. National Security Agency is not publishing all their findings and we can safely assume the same holds true for some other government agencies, but there is a limited list of candidates. The needed mathematical skill levels and deep insight in the exact MD5 encryption that was used in falsifying this certificate, are so rare that it would be easy to make a list of ten to twenty people in the world capable of doing this. However within state sponsored secret research there will be many more who never publish their findings.
The known theoretical MD5 attack
What happened here? An organization obtained an innocent MD5 based SSL certificate from Microsoft. A shame in itself, as it was already known to be unsafe: The provider of a certificate gives you a so called hash which should be unique for the specific text in the certificate. The next step is to produce a rogue certificate, a different text, with the same hash code.
When that is done, you can use the rogue certificate instead of the real one and every browser in the world will accept this. The difference between the original certificate and the falsified one will be the domain that is declared trustworthy. This certificate was issued as authorization for Remote Desktop services. Suddenly every Windows computer will accept this domain as a trusted source and happily follow instructions from the virus command and control center.
Now that’s all fine and dandy, but it has been known since 2004 that for a given text (or general: input) there will be some other text which produces the same hash code when MD5 encryption is used. However if you can’t control the text, this knowledge won’t help you as you can’t manipulate the new text to match the existing hash of the old one, nor does it necessarily fit into the SSL format. Nice, but so far it is just an academic observation.
In 2007, Marc Stevens and colleagues published a groundbreaking article showing that in theory you could use a chosen prefix text and append it so that the end result matches the original hash. In other words, you could make a rogue certificate which contained the text you wanted and some made up information to create a hash which was identical to the official one. Complete end of safety for MD5; in theory that is.
A year later, Marc and co-researchers managed to find a practical implementation of their theory. They demonstrated their proof of concept and notified all stakeholders in the industry. As a result, MD5 was declared unsafe for certificates and yes even Microsoft issued a security warning that certificates based on this now unsafe cryptographic method were no longer to be trusted. After giving the industry half a year to stop issuing unsafe certificates, their “chosen prefix text” paper was met with wide acclaim at Crypto2009.
Virus makers introduce mysterious cryptographic attack
Now fast forward to the discovery of the Flame virus just over a week ago. Marc Stevens and his original co-author Benne de Weger picked up a copy of the falsified Microsoft certificate and ran their own analysis on it. Marc is on the brink of publishing his thesis and as part of his work developed an analytical tool to test a certificate on possible collision detections (meaning there could be another certificate with the same hash value). Out of curiosity, he ran the Flame certificate through it and made a stunning discovery.
The method used to construct a false certificate is completely different from all known methods. We are not talking about a different way to code an algorithm but a completely different approach. It’s still based on the chosen prefix collisions but it doesn’t follow the approach of the published paper in 2009 nor any other later paper in circulation. There are high hopes that, based on the findings, the used method can be reconstructed, but until then this is an unknown technique created by world-class cryptographic experts.
For this article, I spoke with Dr. Benne de Weger of the Technical University of Eindhoven, co-author of the groundbreaking 2007 article, and with Professor Ronald Cramer, head of the Cryptology Research Group, at the Mathematical Institute in Leiden, both academic mentors of Marc Steven. Marc himself enjoyed a long weekend off pondering over the implications of his unexpected finding.
What needs to be stressed is that this is not “new science” although some people chose this unfortunate word. It’s no alien knowledge and the small community of people who are engaged in this research could probably have come up with a different method themselves. The point is: they didn’t and some other, unknown group did.
This is part 1 of this article. In part 2 we will start investigating how it’s possible that a completely unknown cryptographic method could turn up in a virus and why the unknown authors chose to do so.