Crypto Agility through Hybrid Cryptography

by Annegret Henninger / September 7, 2018

Contributors: Brian Goncalves

Cryptography allows digital communication to remain private and confidential through the use of encryption, and still have trust and authenticity by way of digital signatures, hash functions, and message authentication codes (MACs). These primitives act as some of the building blocks that the digital world is built upon, and are based on resource intensive and difficult to solve math problems in order to make them safe to use. When the security of a cryptographic primitive is guaranteed by the computational difficulty of an underlying mathematical problem, we refer to it as a computationally secure primitive. The alternative is an unconditionally secure primitive which is proven to be secure regardless of the computational power of the attackers.

As we have seen in the past, computational assumptions surrounding an attacker’s capabilities may have expiry dates. Indeed the attackers, like the rest of us, will have access to more powerful computing infrastructure as time passes. Moreover, there may be more efficient ways of solving an encryption scheme’s underlying mathematical problem that have not been discovered yet. As a result, there is no guarantee that the cryptographic primitives we use today will remain secure. As such, it is imperative to transition to new algorithms that are more secure. When an exploitable flaw in the algorithm or code is found, such as the KRACK attack for WPA2 WIFI protocol (Vanhoef and Piessens 2017), the algorithms can no longer be used.

However, abandoning the algorithms in use is not a simple task and can, in fact, be a complicated, costly, and time-consuming process. In a large organization there may be numerous upstream and downstream dependencies on a single cryptographic function. Hence, changing a cryptographic primitive may dictate a wide variety of other changes in hardware, software and networking infrastructure of an organization that deals with a lot of legacy hardware and applications. Vendor dependencies can add another layer of complexity to this transition so it is imperative for any organization anticipating a cryptographic transition to plan ahead and dedicate adequate resources to this change.

Cryptographic agility is therefore the ease with which organizations can carry-out cryptographic transitions (Mehmood 2018). Importantly, it is not a singular end state, but rather and ongoing process of planning and preparing. Most organizations are not currently agile enough to carry out cryptographic transitions within a reasonable timeframe. This has been demonstrated in several major recent cryptographic transitions the industry has gone through. For example with symmetric encryption algorithms DES and 3DES to AES (NIST 2004, 2017), and with hash functions SHA-1 to SHA-2 (NIST 2011). Although these algorithms are no longer thought to be secure or part of acceptable standards set by regulatory agencies such as the National Institute of Standards and Technology (NIST), or European Telecommunications Standards Institute (ETSI), they lingered long after new standards were introduced. In fact, many organizations are still not completely free of SHA-1 certificates. In 2017, a study found that of 33 million websites analyzed, 21% of websites were still using SHA-1 certificates (Venafi Research 2017), years after destandardization.

There is another major cryptographic transition that the industry is anticipating in the horizon. It is one that is perceived to be much bigger than the recent cryptographic transitions, creating a lot of discussions with some comparing it with the Y2K and the chaos that came with it. It has been aptly named as Y2Q, Years to Quantum (Hutchinson 2018).

Quantum computers pose a serious and significant threat to much of public key cryptography as they are able to quickly solve the mathematical problems which public key cryptography is based on, thanks to Shor’s algorithm (Shor 1994). The post about the Quantum Threat provides some insight on how the developments in quantum computing will impact the world of information security.

As part of their efforts in helping the industry become resilient against the quantum threat, NIST put forth a request for post-quantum cryptographic algorithms for standardization in 2016 (NIST 2016). The standardization process is expected to be completed between 2022-2024 (NIST 2019). However, as previously discussed fully transitioning away from insecure algorithms is a difficult and slow process, and can leave a significant gap in security. By 2031, for instance, there is a 50% chance that “some of the fundamental public-key cryptography tools upon which we rely today will be broken” (Mosca 2015), leaving a relatively small window in which it will still be secure to use. It is then still an important question as to what can ease this transition and what can be done now that prepares us for this upcoming industry wide change. In other words, what can increase our cryptographic agility and ensure security both during and after the transition to protect against quantum computers?

Hybrid Cryptography is an approach that addresses all these challenges through the use of hybrid cryptosystems. A hybrid cryptosystem is a cryptographic system which uses both traditionally secure and quantum-resistant components. Importantly, hybrid cryptosystems are able maintain security against either traditional or quantum attacks. This dual resistance means that hybrid cryptosystems are well suited for the challenges presented by quantum computers transitioning to newer algorithms (Bindel et al. 2018).

By developing hybrid cryptosystems that work with generic algorithms, both older and newer algorithms can be replaced more efficiently to help cryptographic agility. Equally important, the systems also solve the gap in security presented as dual resistance ensures that even if older, less secure algorithms remain in use after destandardization the risk of them being exploited is marginal. Consequently, this also means that transitioning can be done on a longer time frame offsetting the cost and other factors delaying more immediate action. Both cryptographic agility and hybrid cryptography are active areas of research. Research into cryptographic agility is motivated by real world constraints faced in industry settings and seeks to address these constraints in a practical and effective manner. Research into hybrid cryptography seeks to develop new hybrid cryptosystems with provable security that are computationally efficient, and easily adoptable on top of current cryptographic infrastructure.