Friday, 18 March 2016

Was Flame Really State Sponsored?

Flame was a big story at the time it was discovered, although it has quickly faded from the collective memory.  At the time there was a lot of speculation as to who had produced the malware: the consensus appeared to be that it was a nation state.  Some of the evidence pointed to was the attack that was mounted on certain forms of encryption in order for Flame to operate.

The attack concerned the MD5 message digest algorithm.  MD5 has had a chequered history with some early implementations leading to problems for many but the effect of the Flame attack was for many to consider MD5 as effectively cryptographically broken.

I have never seen this done before (using so little data), but a team of researchers have managed to reverse engineer the cryptanalytic attack mounted by Flame.  This is of interest not just because it is the first time that a cryptanalytic attack has been reconstructed from a single output example, specifically, a single example half of a collision pair, but it has revealed some interesting features of the capabilities of those who constructed and used Flame. [This work was first presented at ASIACRYPT 2015.]

The analysis of the collision behind the attack revealed four interesting features of the Flame construction.  If you look at the chaining values shown in Appendix A of the paper you can confirm that:

  1. Where the near-collision blocks were hidden in the certificate there was limited space and so only four near-collision blocks could be used.
  2. Blocks 1 and 3 of the Flame collision attack use the message block differences from the first differential path of Wang et al.’s identical-prefix attack.  Blocks 2 and 4 use the differences from the second differential path of the identical prefix attack.
  3. The "working state differences" are maximal in all four near-collision blocks. It is the same for Blocks 1 and 3 are equal, likewise for Blocks 2 and 4.
  4. The four blocks all have a common structure.

[A detailed discussion of Differential Cryptanalysis, even limited to hash functions, is beyond the scope of a blog like this.  If you'd like to learn more I would suggest the book by Xie and Liu.]

These observation meant that it was possible to compare and contrast which, previously documented, attack techniques were probably used.  It was also possible to construct the "tunnel strengths" of the near-collision blocks

Using this the researchers were able to reconstruct the attack which was a "chosen prefix collision attack".

Assuming this is all correct, it is possible to then move on the calculate the cost (in computer terms) of mounting the attack.  The closest fit for these attack parameters is equivalent to 2^^49.5 MD5 compressions which takes roughly 40,000 CPUcore hours. Lets suppose you wanted to take 3 days to mount the attack you would need approximately 560 CPUcores.

You can tweak timescales for attacks but the essential maths tells you that the physical computing power required to mount this attack is well within the means of many academic groups working in this field, or relatively cheap to hire in a cloud based system, as well as being the sort of facility that a nation state might have.

True the attack is non-trivial but the required knowledge is in the public domain, and most of those in, say, academia who possess the expertise outside government probably do not work for a government (directly or indirectly).

As neither the required knowledge nor the computing power appear to be unique to what one might find in government organisations, there is nothing to suggest that the attack on the crypto that enabled Flame was in fact state sponsored malware.

This kind of research is difficult and very detailed (probably requiring more skill than the original attack)  but it does show that just because malware is thought to contain a complex attack it does not automatically mean that it is state sponsored.  It is well within the capabilities of organised crime. 

Of course, this is not the only piece of evidence.  There has been much analysis done by various security companies, some of which you might think still points to a government agency behind the attack.  However, at best the assertion that this was a state sponsored attack is unproven based solely on this element of the attack.

[NOTE: A lot of this work was initially investigated in the MSc dissertation (yes MSc!) of one of the authors back in 2013.]