## 3 Flame
### The MD5 Hash Collision Attack  
As mentioned before, Flame can masquerade as a proxy for Windows Update, and by doing that, it can spread on a local network as if it was a signed update for the Windows operating system. In order to be able to generate digital signatures on the malware, the attackers created a public key--private key pair, and they managed to obtain a certificate for the public key that can be used for the verification of signed code and that chains up to the Microsoft root Certification Authority (CA). In this subsection, we give a brief overview on how the attackers obtained this fake certificate. This overview is based on the research of other researchers, and in particular, on the presentation of [PERSON] [15]. The attackers used the Microsoft Terminal Services Licensing infrastructure to obtain their fake certificate. This infrastructure allows licensing servers to obtain a certificate from a Microsoft activation server in a fully automated process. For this purpose, the licensing server generates a key pair, and sends the public key to the activation server together with other user-supplied parameters in a certificate request message. The activation server then issues the certificate for the public key and sends it back to the licensing server. The licensing server can then use the private key to sign licenses for clients, which they can use to access different terminal services. The validity of the licenses can be verified by checking the licensing server's signature and the certificate obtained from the activation server. The signature on the certificate issued by the activation server is generated on the MD5 hash of the content of the certificate. In addition, the certificate does not contain any extensions for restricting key usage, which means that the certificate can be used for code signing applications. However, the certificate contains some MS Hydra extensions, flagged as critical, which are not supported by Windows Vista and Windows 7. Thus, in effect, the certificate can be used as it is for code signing only on Windows XP (or earlier) systems. The attackers needed to get around the problem of the Hydra extensions, and they took advantage of the weaknesses of the MD5 hash algorithm to achieve their goal. More specifically, they mounted a chosen-prefix MD5 hash collision attack by which they obtained a valid signature from the Microsoft activation server on a crafted certificate that contained a public key whose private pair was known to the attackers, and in which the Hydra extensions were covered by an unusually longIssuerUniqueID field. Thus, the verifier of this fake certificate did not detect the presence of the Hydra extensions, and hence, the certificate could be used for code signing even on Windows Vista and Windows 7. The objective of any hash collision attack is to generate two inputs to the hash function that map to the same output hash value. In case of a chosen-prefix hash collision attack, the attacker starts with two chosen inputs that have some known difference, and then appends the so-called near collision blocks to both until the resulting extended inputs yield the same hash value. Optionally, the two colliding inputs can be further extended with the same additional data. MD5 was known to be vulnerable to this type of attack, and the feasibility of such an attack in practice was demonstrated as early as in 2008 [18]. Yet, Microsoft still used MD5 in its Terminal Services Licensing infrastructure. In case of Flame, the two colliding inputs were two certificates. One of them contained a certificate serial number, a validity period, the string \"MS\" as the certificate subject name, and the attackers' public key in the chosen prefix part, while the unstructured and long IssuerUniqueID field was used to hold the near collision blocks.