Written by [James Sellwood] An article reporting on one of the briefings given at Black Hat 2013 came to our attention recently and triggered an interesting discussion amongst our numerous security minded staff. The briefing, “The Factoring Dead: Preparing for the Cryptopocalypse”, discussed recent work into mathematical problems which are relied upon as being 'difficult' by cryptographic algorithms such as RSA and the Diffie-Hellman Key Exchange Protocol. The security of RSA is provided for by the difficulty in factoring large integers, specifically the product of two large primes, whilst Diffie-Hellman makes use of the difficulty of the Discrete Logarithm Problem (DLP).
As the briefing and article both point out, the means by which we solve these two problems is similar enough that advancements in the methods used to solve one problem have historically led to advancements in the methods used to solve the other. The briefing's authors believe that recent work indicates that in the "next two to five years" we may find ourselves in the situation where these problems can no longer be relied upon as the foundation for security systems. They recommend that we begin a concerted effort to move to Elliptical Curve Cryptography (ECC) as a wide spread replacement. Whilst ECC is reliant on similar problems it would be far less significantly affected by the advancements they believe may come.
It was the potential timeframe associated with this "Cryptopocalypse" that initially triggered our discussion. In particular, staff discussed the number of times such prophecies had been heard before and the ongoing use of other cryptographic algorithms, such as DES, which are no longer considered 'secure' in the general case.
Algorithms such as DES and 3DES haven’t yet been completely replaced because they haven't yet had their underlying security foundations ripped away. Whilst DES is no longer secure for most applications, due to the ability to brute force keys in a relatively short period of time, the algorithm itself is still believed to be strong. 3DES is equally considered a strong algorithm although it has been shown that the effective strength of 3-key and 2-key configurations is not what was intended, with 3-key configurations currently taking a greater hit proportional to key size. Such attacks do not, as yet, reduce the cover time to a point where the algorithm is worthless.
If factoring became possible in a polynomial time complexity (in other words, if the advancements result in it being ‘easy’ to do) then RSA would likely be completely crushed. It would be like finding a crack in DES that has not yet, and may not be there to, be found. The repercussions of this are potentially monumental if it happened sometime soon and whilst I have no opinion of the time frame in which this might happen, in my mind it seems to be more plausible than that an algorithm like DES may succumb to a serious flaw in its ability to secure data (without brute force of the now far too small key space).
As I see it the difference between the advancements discussed by the briefing and the expiration of algorithms like DES is precisely the cause of why we don’t know when such a break in RSA might occur. Determining when DES would need replacing due to too small a key space was a straightforward assessment of computing power. It was no surprise when there was a continual incremental improvement in the speed of brute force of DES keys year on year; the computing power used to perform the search was increasing in step. DES only offered a single key size to the user and so there was no way to increase the challenge as the computational power increased. Whilst RSA can be performed with varying key sizes depending on security requirements, the advancements we are discussing may easily neutralise even this protection. With the advancements in factoring we are actually changing the algorithmic mechanism with which we attempt to search for the solution, rather than just performing the same algorithm on faster hardware. Such changes to the algorithm can therefore have dramatic affect by reducing the complexity of the task rather than just working that bit faster. If factoring in general does become ‘easy’ in the near future, then the size of RSA key which would likely be required to provide a reasonable level of security would be so great that the computational cost of performing RSA calculations would make it worthless. The issue and the driving point of the briefing is that for those of us not working in this field we have no idea when such jumps may occur or how great they will be.
Whether you believe that algorithms such as RSA will fall in the next few years or not there is good reason to work on alternatives. The research time so far spent on looking at the problems relied upon by RSA and Diffie-Hellman is significant and far in excess of that which has so far been levied at alternatives like ECC. As with all replacement technologies, it is only when the technology being replaced is finally unavailable that the real test begins. That said it is not advisable to just wait for that time to come when the potential repercussions of a new technology's teething issues could be significant in the modern world of information security. Systems should be designed with appropriate mitigations in place depending on their requirements. Systems that must secure data for more than a few years and systems that must secure highly confidential information should likely be designed with mechanisms for key and algorithm roll-over in place.
Whilst it is not the case that everyone is ignoring this issue, there is a significant dependency on RSA which continues to grow as more and more systems are developed without support for alternatives. In essence the problem is one that needs consideration whether discussing RSA or any other cryptographic algorithm which is relied upon to such a degree. Whether the briefing’s “Cryptopocalypse” happens before wide adoption of alternatives will have to wait to be seen. For now, continued work on alternatives is worthy of our attention.
