CRYPTOGRAPHIC MIGRATIONS: A story of failure and an approach to transform modern cryptography

Arqit

03-11-2023

BEWARE THE WOLF: Hidden danger in familiar places

The field of cryptography is dynamic, and history has shown us that the timeline of cryptographic security is underestimated. Algorithms are predicted to be able to maintain certain security levels for much longer than the reality. Cryptographic algorithms can become deprecated (or considered weak) over time due to advances in computation, development of more efficient attack methods, or discovery of a vulnerability.

Cryptographic hash functions are essential components in many security systems and can be used to construct efficient digital signature schemes and for integrity verification in various applications and protocols. Hash serves as a building block for many security applications, such as validating websites — so that when you load a webpage, you can trust that its purported source is genuine. It secures information by performing a complex math operation on the characters of a message, producing a short string of characters called a hash. It is impossible to reconstruct the original message from the hash alone, but knowing the hash provides an easy way for a recipient to check whether the original message has been compromised, as even a slight change to the message alters the resulting hash dramatically.

MD5 (Message Digest Method 5) is a message digest algorithm designed by Ronald Rivest of MIT in 1991. It was conceptualized as a means for digital signature verification and standardized by the Internet Engineering Task Force. Initially, it was thought MD5 might provide security for decades. And then...

  • In 2005, Arjen Lenstra, Xiaoyun Wang, and Benne de Weger demonstrated a practical collision by constructing two public key X.509 certificates with different public keys and the same MD5 hash value.
  • In 2008, another group of researchers announced how they had used MD5 collisions to create an intermediate certificate authority certificate that appeared legitimate when checked by its MD5 hash.
  • In 2008, the CMU Software Engineering Institute concluded that MD5 was essentially "cryptographically broken and unsuitable for further use".

The weaknesses of MD5 continued to be exploited and found a nefarious niche within the realm of malware, most infamously by the Flame malware which was discovered running on Microsoft Windows operating systems in 2012.

  • Flame was signed with a fraudulent public key certificate purportedly from the Microsoft Enforced Licensing Intermediate PCA certificate authority. Flame victims included governmental organizations, educational institutions, and private individuals.
  • MD5 remained the de facto standard for fingerprinting malware samples and even in 2015, it was still used, most notably by security research and antivirus companies to identify malware despite being known to be broken for more than a decade.
  • As of 2019, one quarter of content management systems were still used MD5 for password hashing.
  • In 2023, Generative AI is creating educational content to explain how MD5 may be used to protect passwords and generate checksums.

SHA-1 (Secure Hash Algorithm 1) is another hash function with an all too similar story. Designed by NSA, SHA-1 became a NIST FIPS 180-1 standard in 1993. The algorithm was repeatedly shown to be cryptographically weak since 2005, yet it was still widely used. NIST formally deprecated SHA-1 in 2011 and disallowed its use for digital signatures after 2013. Still, it wasn’t until 2020, that Microsoft discontinued SHA-1 code signing.

In 2016, malware was able to use SHA-1 to masquerade as valid code. In the same year, researchers demonstrated real-world collision attacks, showing the hash was completely unsafe. Urgent pleas to migrate away from SHA-1 as quickly as possible, were unheeded and SHA-1 continued to validate credit card transactions, email PGP/GPG signatures, open-source repos, and more.

It wasn’t until 2017 that all major web browser vendors ceased acceptance of SHA-1 SSL certificates. Due to the migration time needed to update complex systems, NIST set a phased-out path for SHA-1 by 2030.

“MODULES THAT STILL USE SHA-1 AFTER 2030 WILL NOT BE PERMITTED FOR PURCHASE BY THE FEDERAL GOVERNMENT. COMPANIES HAVE EIGHT YEARS TO SUBMIT MODULES THAT NO LONGER USE SHA-1.”

NIST 2022: HTTPS://WWW.NIST.GOV/NEWS-EVENTS/NEWS/2022/12/NIST-RETIRES-SHA-1-CRYPTOGRAPHIC-ALGORITHM

This is a too familiar nearly 30-year history of the rise and very slow fall of two cryptographic algorithms. Cryptography persists, even long after weaknesses are discovered, well-documented, and deprecated by security experts. In some cases, organizations might be slow to update cryptographic systems due to concerns about compatibility, disruption, or simply lack of awareness. Even when organizations decide to migrate, migration is very complex. Sluggish. timelines often are associated with legacy systems, interoperability concerns, operational disruptions, risk of errors, and cost.

VIGILANCE REQUIRED: Covert perils of public key

A hash function is primarily used for data integrity. These algorithms are based primarily on bitwise operations and logical functions and designed to be fast and efficient to compute yet computationally infeasible to reverse or find collisions. Hash functions are typically a few hundred lines of code. On the other hand, public key algorithms are used for confidentiality (through encryption) and authenticity (through signatures). Public key schemes are rooted in hard math problems, where hard math problems are defined as computationally inefficient to solve. These algorithms are resource intensive, especially for key generation and decryption, and the computational complexity grows as the key size increases. Algorithms like RSA and Elliptic Curve Cryptography require big-number arithmetic and are typically thousands of lines of code. Public key systems are intrinsically fragile, containing countless opportunities for deadly mistakes which even the cryptographic engineer cannot be expected to avoid.

If it took 15 years to migrate away from old hash functions, what is the realistic outlook to migrate extensive public key infrastructures? Discovery tools are being written today to detect and report the presence and use of quantum vulnerable cryptography, and these tools will be imperfect. Emerging post-quantum algorithms will be more resource intensive and will not be possible for all use cases. Many are championing hybrid public key systems which will present a whole of challenges and added complexity. While migrating from one public key algorithm to another is feasible, the complexity of the migration will very likely bring about costly errors, security gaps and unforeseen down-stream consequences.

UNRAVELING THE GREAT MYTH OF PUBLIC KEY CRYPTOGRAPHY

Public key cryptography was not originally conceived to secure today’s internet at scale. The concept of public key cryptography emerged as a solution to the key distribution problem – to securely exchange cryptographic keys between parties who wish to communicate securely without having to share a common secret key in advance. It wasn't developed for the internet, yet it has played a pivotal role in securing online communications as the internet has expanded and evolved to secure online transactions. It was just happenstance that public key cryptography has become the backbone tool for securing online communications at large.

A NEW ERA: The pivotal role of symmetric key

With the realization that public key cryptography is no longer appropriate as a broad, long-term, scalable security option, Arqit developed a light weight, crypto-agile approach leveraging the power of symmetric key agreement (SKA). SKA is an existing standard that has endured over 20 years of scrutiny. It is quantum-safe, computationally performant, simple to code, and generally applicable to a broad set of use cases.

SYMMETRIC KEY AGREEMENT

  • SIMPLICITY
  • SPEED AND EFFICIENCY
  • PROVEN TRACK RECORD
  • ESTABLISHED STANDARDS
  • HARDWARE IMPLEMENTATIONS
  • LESS OVERHEAD

There are numerous established standards for symmetric key agreement including AES and Ascon. AES has been extensively analyzed and vetted by the global cryptographic community.

Symmetric key agreement can also work in hybrid settings with PKI, and as a defense-in-depth approach. Instead of relying on a single PKI security measure, SKA aligned with PKI can provide a layered defense approach to thwart vulnerabilities and create redundancy with a diversity of defensive security measures, and very low overhead.

Arqit has reinvented a security approach for data-in-transit. Our solution has solved the challenges historically related to SKA, namely key distribution, and management. Our modernized approach and unique protocol offer leverages mature, symmetric ciphers. This is incredibly effective for a defense-in-depth approach for the future of cybersecurity.

QuantumCloudTM - A simple, effective, quantum-safe solution