Encryption: We Lost
Secrecy was good, whilst it lasted, but I can now confirm that the game is over.
I am being deliberately melodramatic, but I was drawn to two topics discussed at Blackhat 2013, the security conference held in Las Vegas last month. The ramifications of these topics could, in the worst case, destroy online commerce and much of the Internet itself; completely! It really is that serious.
Over the past 40 years we have developed cyphers based on mathematical one-way "trap-door" functions to encrypt information and perform public key-exchange functions. This is typically attributed to RSA, Diffie and Hellman, though the techniques were also developed several years earlier in secret, at GCHQ in the UK. Prime numbers are at the core, today, of these electronic encryption schemes which we use to protect our information - and the mechanisms for attacking them involve the factorisation of very large numbers that are the product of two of those primes – we call those resulting large numbers "semiprimes". That's where techniques like the General Number Field Sieve, Fermat's Little Theorem and the Sieve of Eratosthenes help us (or the bad guys) test for primality; breaking the semiprimes back down into their constituent prime numbers and in that way break the code.
These techniques have been around for several years (about 2300 years in the case of the Sieve of Eratosthenes!) Much more recently, this year, new approaches have been developed - Discrete Logarithm Algorithms; the Function Field Sieve and the Quasi-polynominal algorithm for discrete logs. And these are making fast progress in improving factoring performance; this is resulting in the RSA and DH protocols being put under increased threat – to such an extent that it won’t be long before we can’t trust them anymore. This problem was the topic of the talk "The factoring dead: preparing for the cryptopocalypse" by Samos, Ritter, Ptacek and Samuel.
The second briefing at the conference by Prado, Harris and Gluck was titled: "SSL, Gone in 30 Seconds" and it included a practical demonstration of how SSL encryption can be broken because of vulnerabilities as a result of the use of compression algorithms. They have developed a tool called BREACH which attacks constant secrets embedded in webpages; these are tokens which applications use to track sessions or maintain data.The attack is done with a clever incremental test, guessing additional characters and determining the impact by examining the compressed response from the server. Hundreds of such tests can be performed very rapidly, compromising the encryption in under a minute … hence the title of the talk.
All of the mitigations here are painful – either turn off compression or redevelop all applications. So this one sounds like we need improvements in the compression algorithms on web servers to help mitigate this new attack vector. The scary part here is that they are going to release the tool, so anyone will be able to use it.
I choose these two presentations partly because they’re interesting, and indeed frightening developments, but also because the technology media has also picked up on them and is raising their profile too. This combination of mathematical theory and practical attacks is giving us quite a worrying time. So how do we address the situation?
There are other, newer, encryption technologies like Elliptic Curve Crypography (ECC) that may save us. But can we move quickly enough, as an industry, to adopt ECC? Or are we going to sit back and wait for a disaster? We also watched the exhaustion of the IPv4 address space come racing towards us for several years, but have we moved to IPv6 yet?
There is also an interesting twist … several Elliptic Curve Cryptography patents are owned by Blackberry, through their acquisition of Certicom in 2009. So with commercial implications (who might buy Blackberry and how will that influence the usage of ECC?) there could be more challenges here to overcome before we see widespread adoption of ECC and save ourselves from impending doom.
There’s more information here: https://www.blackhat.com/us-13/briefings.html
and here for the BREACH attack in the second talk: http://breachattack.com/