The CRYSTALS-Kyber public-key encryption and key encapsulation mechanism recommended by NIST for post-quantum cryptography has been broken using AI combined with side channel attacks.
The post AI Helps Crack NIST-Recommended Post-Quantum Encryption Algorithm appeared first on SecurityWeek.
About SecurityWeek Cyber Insights | At the end of 2022, SecurityWeek liaised with more than 300 cybersecurity experts from over 100 different organizations to gain insight into the security issues of today – and how these issues might evolve during 2023 and beyond. The result is more than a dozen features on subjects ranging from AI, quantum encryption, and attack surface management to venture capital, regulations, and criminal gangs.
SecurityWeek Cyber Insights 2023 | Quantum Computing and the Coming Cryptopocalypse – The waiting time for general purpose quantum computers is getting shorter, but they are still probably decades away. The arrival of cryptanalytically-relevant quantum computers (CRQCs) that will herald the cryptopocalypse will be much sooner – possibly less than a decade.
At that point our existing PKI-protected data will become accessible as plaintext to anybody; and the ‘harvest now, decrypt later’ process will be complete. This is known as the cryptopocalypse. It is important to note that all PKI-encrypted data that has already been harvested by adversaries is already lost. We can do nothing about the past; we can only attempt to protect the future.
Here we are going to examine the why, what, and how we need to prepare for that cryptopocalypse – but first we need a few definitions to ensure we’re all singing the same song.
The cryptopocalypse is the point at which quantum computing becomes powerful enough to use Shor’s algorithm to crack PKI encryption. Since public key encryption is used to secure almost all data in transit, both between separate IT infrastructures and even within individual infrastructures, that data will become accessible by anyone with a sufficiently powerful quantum computer.
“That means that all secrets are at risk,” explains Bryan Ware, CEO at LookingGlass; “nuclear weapons, banks, business IP, intelligence agencies, among other things, are at risk of losing their confidentiality and integrity.”
But this is not a threat for the future – the threat exists today. Adversaries are known to be stealing and storing encrypted data with the knowledge that within a few years they will be able to access the raw data. This is known as the ‘harvest now, decrypt later’ threat. Intellectual property and commercial plans – not to mention military secrets – will still be valuable to adversaries when the cryptopocalypse happens.
“Even if a cryptographically relevant quantum computer is still years away, the time to start preparing is now,” warns Rebecca Krauthamer, co-founder and CPO at QuSecure.
The one thing we can say with certainty is that it definitely won’t happen in 2023 – probably. That probably comes from not knowing for certain what stage in the journey to quantum computing has been achieved by foreign nations or their intelligence agencies – and they’re not likely to tell us. Nevertheless, it is assumed that nobody yet has a quantum computer powerful enough to run Shor’s algorithm and crack PKI encryption in a meaningful timeframe.
It is likely that such computers may become available as soon as three to five years. Most predictions suggest ten years. Note that a specialized quantum computer designed specifically for Shor does not need to be as powerful as a general-purpose quantum computer – which is more likely to be 20 to 30 years away.
It is difficult to make precise predictions because the power of a quantum computer comes from the number of qubits that can be used. This is further complicated by the instability of qubits that require a high number of additional qubits used solely for error correction. Consequently, the number of qubits that can be ‘used’ (logical qubits) is much less than the total number needed (physical qubits).
It has been suggested that as many as 1,000 physical qubits may be required for each logical qubit. This will depend on the quality of the error correction in use – and this is an area of intense research. So, at some time in the next few years, as the number of physical qubits increases, and the number of required physical qubits per logical qubit decreases, quantum developers will have a quantum computer able to crack PKI. It has been estimated that this will require between approximately 1,000 and 2,000 logical qubits.
To put some flesh on this skeleton, we can look at an announcement made by IBM on November 9, 2022: a new 433 qubit Osprey processor. This was accompanied by a roadmap that that shows a progression toward a 4,000 plus qubit quantum computer, codenamed Kookaburra, due in 2025.
Error correction is being approached by a new version of IBM’s Qskit Runtime software that allows ‘a user to trade speed for reduced error count with a simple option in the API’. This is supported by a new modular IBM Quantum System Two able to combine multiple processors into a single system with communication links. System Two is expected to go live in 2023, around the same time that IBM expects to have a 1k+ qubit processor codenamed Condor.
System Two will be a building block in what IBM calls quantum-centric supercomputing. Scott Crowder, the VP of IBM quantum adoption and business, explains in more detail: “Quantum-centric supercomputing (which describes a modular architecture and quantum communication designed to increase computational capacity, and which employs hybrid cloud middleware to seamlessly integrate quantum and classical workflows) is the blueprint for how quantum computing will be used in the years to come.”
He added, “This approach to scaling quantum systems alongside the recent, dramatic improvements in techniques to deal with quantum processor errors is how we envision a path to near-term, practical quantum advantage – the point when quantum processors will be capable of performing a useful computation, faster, more accurately, or cheaper than using exclusively classical computing.”
Navigating such projections doesn’t tell us precisely when to expect the cryptopocalypse, but they clearly show it is getting perilously close. “Quantum computing is not, yet, to the point of rendering conventional encryption useless, at least that we know of, but it is heading that way,” comments Mike Parkin, senior technical engineer at Vulcan Cyber.
Skip Sanzeri, co-founder and COO at QuSecure, warns that the threat to current encryption is not limited to quantum decryption. “New approaches are being developed promising the same post-quantum cybersecurity threats as a cryptographically relevant quantum computer, only much sooner,” he said. “It is also believed that quantum advancements don’t have to directly decrypt today’s encryption. If they weaken it by suggesting or probabilistically finding some better seeds for a classical algorithm (like the sieve) and make that more efficient, that can result in a successful attack. And it’s no stretch to predict, speaking of predictions, that people are going to find ways to hack our encryption that we don’t even know about yet.”
Steve Weston, co-founder and CTO at Incrypteon, offers a possible illustration. “Where is the threat in 2023 and beyond?” he asks. “Is it the threat from quantum computers, or is the bigger threat from AI? An analysis of cryptoanalysis and code breaking over the last 40 years shows how AI is used now, and will be more so in the future.”
Quantum key distribution (QKD) is a method of securely exchanging encryption keys using quantum properties transmitted via fiber. While in this quantum state, the nature of quantum mechanics ensures that any attempt to access the transmission will disturb the content. It does not prevent attacks, but ensures that an attempted attack is immediately visible, and the key can be discarded. Successful QKD paves the way for data to be transmitted using the latest and best symmetrical encryption. Current symmetrical algorithms are considered safe against quantum decryption.
“Symmetric encryption, like AES-256, is theorized to be quantum aafe, but one can speculate that key sizes will soon double,” comments Silvio Pappalardo, chief revenue officer at Quintessence Labs.
“Quantum cryptography is a method of encryption that uses the principles of quantum physics in securing and transmitting data,” says Ganesh Subramanya, head of data protection CoE cybersecurity at TCS. “It creates security so strong that data coded in quantum state cannot be compromised without the sender being notified. Traditional cryptography uses technologies like SSL and TLS to secure data over the internet, but they have been vulnerable to a variety of attacks, as an attacker can change the communication between two parties (like user’s browser and the webpage / application) and make them believe they’re still communicating with each other. With quantum cryptography, such an alteration of data is not possible, thereby strengthening the security of online transactions.”
John Prisco, Toshiba partner and president/CEO of Safe Quantum, applies these principles to QKD. “Quantum key distribution contains a key security aspect that cannot be overstated,” he says, “especially if it is being utilized in tandem with the NIST post-quantum encryption standards (PQC). The gold standard in cybersecurity is considered to be defense in-depth, as this leverages two totally different technologies with diverse failure mechanisms, working for protection. With harvest now decrypt later attacks becoming more frequent, there is no delay time that is safe to defend against quantum attacks. QKD authenticated with PQC signature algorithms is the only defense that can be deployed immediately and guarantee a successful defense against harvest now, decrypt later.”
Terry Cronin, the VP at Toshiba who oversees the QKD Division, agrees with this assessment. “The use of QKD as part of a hybrid solution to quantum resistance can offer the security needed ensuring that a harvest and decrypt attack cannot succeed in accessing the data.”
The practical difficulties in introducing wide-scale fiber based QKD means that it cannot be implemented everywhere. Its immediate use will likely be limited to point-to-point communications between high value sites – such as some government agencies and between major bank offices.
NIST began a competition to select and standardize post quantum encryption algorithms in 2016. “We’re looking to replace three NIST cryptographic standards and guidelines that would be the most vulnerable to quantum computers,” said NIST mathematician Dustin Moody at the time. “They deal with encryption, key establishment and digital signatures, all of which use forms of public key cryptography.”
In July 2022, NIST announced its first four finalists. However, it emerged in August 2022 that a different finalist, the Supersingular Isogeny Key Encapsulation (SIKE) algorithm had already been broken. SIKE is designed to deliver keys securely from source to destination across an untrusted network. Researchers had demonstrated, however, the algorithm could be cracked on a single classical PC in little over an hour.
This illustrates a problem that all security professionals need to confront. Any encryption algorithm is secure only until it is cracked. Whitehat researchers will tell you if they can crack an algorithm — foreign governments will not. In effect, this means that the ‘later’ part of ‘harvest now, decrypt later’ is an optimistic view. We believe that encrypted IP being stolen today cannot yet be decrypted — but we cannot be certain.
We do, however, know that current PKI encryption will certainly be broken by quantum computers in the relatively near future. The solution from NIST is to replace current vulnerable PKI algorithms with more complex algorithms — that is to solve more powerful computing by using more powerful algorithms.
Ultimately, we will be in the same position we are in today. We will believe our IP protected by NIST’s post quantum algorithms will be safe — but we cannot be certain. Remember that at least one proposed post-quantum algorithm has been broken on a PC. So, even if we switch to a NIST-approved post quantum encryption standard tomorrow, we cannot be certain that the harvest now decrypt later philosophy has been beaten.
NIST’s PQC algorithms are ‘quantum safe’, they are not ‘quantum secure’. The former is thought to be safe against quantum decryption but cannot be proven to be so (since they are mathematical in nature and susceptible to mathematical decryption). Cryptography that can be proven to be safe is known as ‘quantum secure’ — and the only way to achieve this is to remove mathematics from the equation.
The only quantum secure cryptography known is the one-time pad because it relies on information security rather than mathematical security. Technically, QKD could be described in similarly secure terms since any attempt to obtain the keys for mathematical decryption could result in the immediate destruction of the keys (preventing them from being usefully decrypted). We have already seen that QKD has problems for widespread use — but it remains an open question whether modern technology is able to deliver usable one-time pads.
Historically, OTP has been considered unworkable for the internet age because it requires keys of the same length or longer than the message being encrypted. Nevertheless, several companies have been exploring the possibilities becoming available with new technology.
Qrypt started from the basis that the quantum threat comes from the communication of encryption keys from source to destination. If you can avoid the necessity to communicate the keys, you can eliminate the threat. It consequently developed a process that allows the generation of the same quantum random numbers simultaneously at both source and destination. A quantum random number is a genuinely random number generated with quantum mechanics principles. These numbers can then be used to generate identical keys without them needing to be transmitted across the internet.
However, since the generation of the numbers can be performed and stored until use, there remains the potential to chain the process to provide genuine OTP for the keys without requiring them to be transmitted across the internet. Solutions based on this process are quantum secure.
Incrypteon, a British startup, has taken a different route by applying Shannon’s information theories to the one-time pad. The science is a bit mind-numbing but is based on Shannon’s equivocation from his Communication Theory of Secrecy Systems published in 1949. “The definition of perfect secrecy is based on statistics and probabilities,” says Incrypteon. “A ciphertext maintains perfect secrecy if the attacker’s knowledge of the contents of the message is the same both before and after the adversary inspects the ciphertext, attacking it with unlimited resources.”
Using its own patented software and ‘Perpetual Equivocation’, Incrypteon “ensures that conditional entropy never equals zero, therefore achieving Perfect Secrecy.” The result is something that is automatically quantum secure (not just quantum safe) — and is available today.
Co-founder Helder Figueira had been an electronic warfare signals officer commanding a cryptanalysis unit in the South African Army. The concepts of Shannon’s equivocation are well-understood by the military, and he has long-been concerned that the commercial market is forced to accept encryption that is, by definition, ‘insecure’ — if something cannot be proven to be secure, it must be insecure.
A third and potentially future approach to the one-time pad could evolve from current advances in tokenization – more specifically cloud-based vaultless tokenization protected by immutable servers.
Rixon, another startup, is involved in this area. Its primary purpose is to protect PII stored by organizations with a web presence – but the principles could easily be extended. Plaintext is immediately tokenized in the cloud, and no plaintext is held onsite. Nor is the plaintext held at the tokenization engine in the cloud – all that is stored is the tokenization route for each tokenized character (for the purpose of comparison, this tokenization route is equivalent to the cryptographic key, but is random for each character).
This provides the primary parallel with the OTP – the ‘key’ is the same length as the message. Currently, Rixon concentrates on tokenizing PII; but the same concept could be extended to secure high value files at rest such as intellectual property and commercial plans.
The coming cryptopocalypse requires organizations to transition from known quantum-vulnerable encryption (such as current PKI standards) to something that is at least quantum safe if not quantum secure. This will be a long process, and in 2023 businesses will need to start planning their route in greater detail.
Most companies will start from the viewpoint that NIST post-quantum algorithms is the only way forward. We have discussed OTP developments in some depth to show that the NIST route is not the only available route – and we expect further OTP developments during 2023.
The full transition to post quantum readiness will take many years, and will not be achieved by throwing a switch from classical to PQC. This has led to the concept of ‘crypto agility’. “It will be essential that quantum ready algorithms (QRAs) are able to coexist with existing cryptographic capabilities, in a hybrid manner, while the complete transition to quantum safe occurs,” explains Silvio Pappalardo, chief revenue officer at Quintessence Labs.
“Crypto agility enables applications to migrate between key types and cryptographic algorithms without the need to update the application software — transitioning from homogenous towards micro-service architecture,” he said. “With encryption ciphers changing due to the threat of quantum, decreasing longevity, increasing key sizes, and the expanding requirements to protect more data, more effectively, crypto agility becomes a business enabler and defender to keep pace with constant innovations and enable greater flexibility into the future.” Such agility also allows companies to switch from one quantum safe algorithm to another if the one in use gets broken.
For now, government agencies will have little choice but to follow NIST. On November 18, 2022, the White House issued a memorandum to the heads of executive departments and agencies requiring that CRQC readiness begins with taking an inventory of vulnerable assets. “By May 4, 2023, and annually thereafter until 2035”, states the memo, “agencies are directed to submit a prioritized inventory of information systems and assets, excluding national security systems, that contain CRQC-vulnerable cryptographic systems to ONCD and the Department of Homeland Security Cybersecurity and Infrastructure Security Agency (CISA).”
(This confirmed earlier details announced in the National Security Memorandum NSM/10 published on May 4, 2022.)
On December 21, 2022, Biden signed the Quantum Computing Cybersecurity Preparedness Act into law. “Quantum computers are under development globally with some adversarial nation states putting tens of billions of dollars into programs to create these very powerful machines that will break the encryption we use today,” comments Sanzeri. “While not here yet, quantum computers will be online in coming years, but it will take more than a few years for our federal agencies and commercial enterprises to upgrade their systems to post quantum cybersecurity.”
This Act, he continued, “requires federal agencies to migrate systems to post quantum cryptography which is resilient against attacks from quantum computers. And the Office of Management and Budget is further required to send an annual report to Congress depicting a strategy on how to assess post-quantum cryptography risks across the federal government.”
The government is clearly wedded to the NIST proposals. This may be because NIST is correct in its assertion that OTP is not realistic. NIST computer security mathematician Dustin Moody told SecurityWeek in October 2022, “The one-time pad must be generated by a source of true randomness, and not a pseudo-random process.” But there are numerous sources for the generation of genuinely random numbers using quantum mechanics.
“The one-time pad must be as long as the message which is to be encrypted,” added Moody. “If you wish to encrypt a long message, the size of the one-time pad will be much larger than key sizes of the algorithms we [NIST] selected.” This is also being challenged as a problem by both Qrypt and Incrypteon, and potentially tokenization firms like Rixon.
Nevertheless, most companies will follow the incremental process of NIST rather than the more revolutionary process of OTP, if only because of NIST’s reputation and government support. 2023 will see more companies beginning their move to CRQC readiness – but there are more options than are immediately obvious.
Related: Quantum Computing’s Threat to Public-key Cryptosystems
Related: Quantum Computing Is for Tomorrow, But Quantum-Related Risk Is Here Today
Related: Solving the Quantum Decryption ‘Harvest Now, Decrypt Later’ Problem
Related: Is OTP a Viable Alternative to NIST’s Post-Quantum Algorithms?
The post Cyber Insights 2023: Quantum Computing and the Coming Cryptopocalypse appeared first on SecurityWeek.
