The Flame virus contains some highly advanced code to fake a Microsoft certificate. In the first part of this mini series we explained the discovery of a completely unknown cryptographic attack. Now we want to focus on the mysteries surrounding this work of an unknown agency. Part 2 of a story by Max Huijgen, EuroTech, Spain
Yesterday, The Washington Post reported that Israel and the US worked together on creating Flame to target Iran, but without real sources their claim can’t be substantiated. Let’s focus on the cryptographic surprise in Flame to see if we can get closer to the ‘Who’ and the ‘How.’
We concluded part one with the shocking discovery of a completely unknown attack on a certificate. The unknown group obtained rights to sign code by using a falsified Microsoft certificate which gave the virus the chance to use Windows Update to introduce completely new virus modules to machines which were 100% up to date and considered secure.
How did the perpetrators pull this attack off? First, they used a weakness at Microsoft which still issues outdated MD5 based certificates which have the capability to say ‘this is valid code.’ Completely unnecessary and either a stupid mistake or as the inevitable conspiracy lovers think, part of Microsoft’s help to the unknown makers of the Flame virus. It would have been easier though if Microsoft would have just issued a certificate if they really wanted to help.
We spoke with Marc Stevens, who was leading the first group to successfully create a rogue certificate based on an MD5 hash. He was also the one who discovered last week that this falsified certificate was not based on any published method to pull off such an attack, causing a shock in the scientific world as there must be some group out there which is capable of developing a completely novel way of generating two different certificates with identical MD5 hashes.
Putting together the jigsaw of facts
Let’s see how a rogue group would approach this. To be able to pass the Windows Vista and 7 checks you need to present a valid signed certificate, meaning it has an identical hash to the original legitimate one. Basically you apply for a normal certificate: in this case you order a Terminal server license and you make sure that you have a slightly different forged certificate which has an identical hash. As browsers just check the hash of every certificate, it will pass if it generates the same value and you got entry into the system and can do whatever you want.
Marc Stevens and his group already published a so called ‘hashclash’ with a rogue certificate to show it can be done – so the initial discovery was just that Microsoft had been lax in updating its system. But what our unknown attackers didn’t know, was that Marc had done more than show the theoretical possibility and later a demonstration of a practical attack. Silently, he had been working on a tool that can detect whether a certificate contains the telltale signs of tampering with the explicit intent to create an almost identical twin.
As part of his dissertation he developed a general purpose identification tool which glows red when a collision-based certificate is tested. It does even more: it immediately dumps the complete structure and to his surprise, this Flame certificate was not only one of the few other examples of a falsified MD5 certificate, it was based on a very different method than was published in the academic world. There are cryptographic masterminds who had never revealed their method!
Now why would a secret group of very rare experts in this specific field in cryptography develop a completely different method? There was no need to do so as Stevens and his co-authors published not only a scientific paper, but also software to ‘do it yourself’ after they had given the industry half a year to fix the security holes. So everyone with sufficient knowledge could just use their software and generate a false certificate if they knew Microsoft still issued the broken versions.
Was it because they started development of their code before Stevens’ c.s. was published? To answer that, it is crucial to look at the issue date of the certificate: February 2010. That means this attack was done after the software was available (June 2009) – it’s kind of ridiculous to develop a completely new method when you could have used a ready-made kit.
Let’s assume the makers of Flame were working on this before they got their hands on the public code with the full scientific publication (August 2009). They knew it was theoretically feasible as that had been demonstrated by Stevens in 2007, so maybe they developed a practical method all by themselves in complete secret and in parallel to the open research world.
Why didn’t they use the published version to hide their knowledge and skills which so far were unknown? After all, this only points to a state agency and there are only a few candidates. It would point extremely large fingers into the direction of the NSA – while using a publicly known method would have kept them in hiding.
It would require leading cryptographers to comprehend the first 2007 paper and find a practical implementation. To understand how difficult it is you must realize that a collision is extremely hard to create. MD5 used to be considered completely safe regarding so called collisions: a different document with the same hash would require 2^64 or eighteen quintillion, four hundred forty-six quadrillion, seven hundred forty-four trillion, seventy-three billion, seven hundred nine million, five hundred fifty one thousand, six hundred and 16 attempts to find one, but of course you could be lucky and find one earlier 
The need for speed
Thanks to scientific breakthroughs it has been proven that MD5 has weaknesses which make it possible to generate these collisions in just 2^16 attempts – which can be done very rapidly on an ordinary PC. Ever since, MD5 should have been abandoned but unfortunately the commercial world chose to ignore the scientific findings.
To show how unsafe MD5 really was for certificates, Marc Stevens proved that it was practically possible to generate two certificates with an identical first part (the actual certificate text), a so called chosen prefix attack. To create these tailor-made certificates, it takes a little over 2^50 attempts. In 2008 that was achievable in a weekend on a cluster of 200 Playstations (a very competent supercomputer when running Linux) and the result was an officially signed certificate from Microsoft and a rogue certificate with an identical MD5 hash.
The reason you need to do this very fast is that you have to make sure that you get a certificate which exactly matches your design. Certificates have serial numbers so you need to make sure your rogue one has the same serial. The trick is to measure how many serial numbers are used during a certain time. To learn this, you request a few certificates and check on the changes over time.
When you know the pattern you ask for a certificate on a Friday afternoon to get the current serial, start number crunching over the weekend and try to get the expected one early Monday morning on exactly the second you predicted. You will never get it perfectly right, but by asking a few extra certificates you’ll end up with the certificate with the serial number you pre-computed. In 2008, five attempts were needed to get the right one on which the cluster had been number-crunching over the weekend.
Fast forward to the Flame certificate, for which security researcher Alex Sotirov has shown that there was only a 1 millisecond window for the attack due to the complexity of the serial number. This significantly increases the amount of retries of the entire attack before a successful attempt has been achieved and even the physical distance between your computer and the certificate issuer becomes important to avoid uncontrollable delay. The available computing power becomes even more important when you want to hit such a precise moment as you need to restart your full attack when you’re off by too wide a margin.
So assuming you have a group of top scientists who work in secret and you also have an extremely fast computer at your disposal you could take most of the uncertainties out of the method described above. If you do the needed calculations in a few hours because your method is even faster than the published one or you happen to have all the support of your state’s supercomputers you would be quite sure you only need to ask for a few certificates to get the one with the serial number you expected. The less requests, the less attention you draw and the easier to stay under the radar of the logs.
The role of forensic cryptography
So either this unknown secret little army of scientists had a need to come up with a much faster method tailor-made for their own supercomputer or they had another reason to use a different method. We spoke at length with Marc Stevens and there is no definite explanation. There is however an alternative theory: What if agency xxx was not aware that Marc had been working silently on his piece of forensic software?
The Flame authors didn’t want to be noticed and the moment the virus was discovered, it self-destructed without leaving any traces. All that was left was a false certificate which proved nothing until Stevens used his unknown software to analyze it. It was immediately identified as a rogue certificate and on top of that, Marc can see how it was done and which method is used. He tells me that he is confident that he will be capable of finding the exact method and will publish it when he is done.
It took his unknown software just 0.02 second to identify and analyze years of work of a group of secret cryptographers, but could they foresee this? By using their own method, they could have assumed to go even further below the radar and go completely unnoticed.
Of course we asked if we will ever be capable of reconstructing the original certificate as that could reveal whose name was on it, but unfortunately that can’t be done. Microsoft doesn’t keep them and all the logs will tell us is that it was issued as ‘Terminal Services LS.’ The attackers clearly knew what they were doing as most other certificates require a name of the organization requesting it.
On top of that, this specific certificate was ideal as it had code signing authorization, meaning every machine it was installed on could be manipulated in accepting new software. Completely unnecessary for a license to use Terminal Server, but a good find by our mysterious attackers.
We asked Marc Stevens if he could backtrack and find more information from analyzing the ‘evil cert.’ He could reverse a large part of the calculations that were being done and got the to the first hash before the subtle changes were made to get the final hash identical (the so called birthday bits). Just to show the attackers how close on their heels he got, the hash value is 8262d01365179fa09bd4c9cf1b76732e. Impractical knowledge at this time, but publishing it here is a clear warning to our mysterious crypto guys that open science is closing in on them!
Moving forward
We will never know if our attackers had to come up with their own method to make sure the attack would work under a restriction we don’t know. Normally no agency would ever use a secret method when a public one is available. Maybe they expected to escape scrutiny by using a different attack not knowing that in a university room in Amsterdam an expert in this field just came up with the ultimate forensic tool.
What we do know is that MD5-signed certificates are not secure and its successor SHA-1 is about to fall apart as well. The good news: this young scientist developed a tool which will just as easily spot a future rogue SHA-1 certificate. The secret cryptographers may have some advantages, but they were caught with their pants down and are more vulnerable than they expected.
We also know that the complete details of this cryptographic attack clearly point to the NSA, often referred to as ‘No Such Agency’ as they always operate below the radar. Seeing that this attack was only possible by a team which picked up the first paper by Marc Stevens and developed a completely new method, there must be a team of top-notch cryptographers at work.
The number of people worldwide who are as well-versed in MD5 attacks as Marc Stevens and his co-authors is less than ten – so it must have been created by a group which works in secret and has the computing power, the logical capabilities and most of all the human brain power to achieve this. From initial research to practical implementation, this must have been a concerted effort by the CIA and the NSA and our interviews underline the findings of the Washington Post that there can be no doubt that the US was highly involved in at least the cryptographic attack hidden in the Flame virus.
Is it reassuring that public cryptography is so close to the secret science or should we really worry now that it’s clear that every conceivable resource is used to create superspy viruses?
Marc Stevens is the first author on most of the cryptographic research in this area and works at the Cryptology Group of the CWI in Amsterdam. He is willing to answer specific questions you might have regarding this very complex subject.
WP with latest Flame news: http://www.washingtonpost.com/world/national-security/us-israel-developed-computer-virus-to-slow-iranian-nuclear-efforts-officials-say/2012/06/19/gJQA6xBPoV_story.html
Marc Stevens’s dissertation: http://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pd