The quantum threat to RSA-based encryption is deemed to be so pressing that NIST is seeking a quantum safe alternative

The cracking of the SIKE encryption algorithm (deemed to be on its way to NIST standardization) on a single classical PC should make us evaluate our preconceptions on what is necessary for the post-quantum era. SecurityWeek has spoken to several cryptography experts to discuss the implications of the SIKE crack.

The issue

NIST, through the vehicle of a competition, is in the process of developing new cryptographic algorithms for the post quantum era. Shor’s algorithm has already shown that the existing RSA encryption, underlying modern internet communication, will be broken probably within the next decade.

IBM currently has quantum processors with 127 qubits. Mike Osborne, CTO of IBM Quantum Safe, added, “and a roadmap essentially, more or less, up to 4000 cubits [with] an idea how we get to a million cubits… the era of what we call cryptographically, relevant quantum machines is getting closer all the time.”

The threat to RSA-based communication has become known as the ‘harvest now, decrypt later’ problem. Adversarial nations can steal and copy currently encrypted data now, knowing that in a relatively few years’ time, they will be able to decrypt it.

Many secrets have a lifetime of decades – at the personal level, for example, social security numbers and family secrets; while at the nation level this can include state secrets, international policies, and the truth behind covert activity. The quantum threat to RSA is deemed to be so pressing that NIST is seeking a quantum safe alternative.

But the SIKE crack should remind us that the threat to encryption already exists – encryption, even post quantum encryption – can be defeated by classical computing.

Some cryptographic theory

The new algorithms being considered by NIST are designed to be ‘quantum safe’. This is not the same as ‘quantum secure’. ‘Safe’ means there is no known way to decrypt the algorithm. ‘Secure’ means that it can be mathematically or otherwise proven that the algorithm cannot be decrypted. Existing algorithms, and those in the current NIST competition, are thought to be quantum safe, not quantum secure.

As the SIKE crack shows us, any quantum safe encryption will be safe only until it is cracked.

There is only one quantum secure possibility – a one-time pad (OTP). A one-time pad is an encryption method that cannot be cracked. It requires a single-use (one-time) pre-shared key that is not smaller than the message being sent. The result is information-theoretically secure – that is, it provides perfect secrecy that is provably secure against mathematical decryption, whether by classical or quantum computers.

But there are difficulties – generating keys of that length with true randomness and delivering the key to the destination have so far proven impractical by electronic means. 

Scott Bledsoe, CEO at Theon Technology, summarized the current status: “The only encryption method guaranteeing survivorship even at the creation of the quantum computer is one-time pad encryption.” But he told SecurityWeek there is an issue with randomness and the uniformity of the distribution in the keys – any issue at this top level can allow you to predict all future keys.  

“Secondly,” he added, “the size of the key needs to be equal or larger than the message, and this requires more compute time and is slower than other classical algorithms.” The third problem is, “Key distribution and how the initial keys can be transmitted. This was handled in the past by person-to-person exchange, guaranteeing secrecy.”

This is the nub of the issue. NIST’s algorithms can only be ‘safe’. OTPs can be ‘secure’ but have been impractical to use. But the need for ‘secure’ rather than ‘safe’ is highlighted by the SIKE crack. Any algorithm can be considered safe until it is cracked, or until new methods of decryption suggest it is unsafe. During the time it is used before it is unsafe, it remains susceptible to harvest now, decrypt later.

This can happen at any time to any mathematical algorithm. The original RSA had a key length of 128 bits with a projected lifetime of millions of years before it could be cracked. As computers got better, the lifetime was progressively reduced requiring the key length to be increased. RSA now requires a key length in excess of 2,000 bits to be considered safe against classical computers, but cannot be secure against Shor’s quantum algorithm.

So, since no mathematical encryption can be proven secure, any communication using that algorithm can be decrypted if the algorithm can be broken – and SIKE demonstrates that it doesn’t always require quantum power to do so. So, at the very best, NIST’s quantum safe algorithms provide no guarantee of long-lasting security.

“There are multiple research organizations and companies working on these problems,” says Bledsoe. “In the future we will see algorithms based on OTP concepts that have answers to the current shortcomings. They will leverage information theory and become viable options as an alternative to NIST-approved algorithms.”

The pros and cons of OTP

The NIST competition is solely focused on developing new encryption algorithms that should, theoretically, survive quantum decryption. In other words, it is an incremental advance on the current status quo. This will produce quantum safe encryption. But quantum safe is not the same as quantum secure; that is, encrypted communications will only remain encrypted until the encryption is broken.

History and mathematical theory suggest this will inevitably, eventually, happen. When that does happen, we will be back to the same situation as today, and all data harvested during the use of the broken algorithm will be decrypted by the adversary. Since there is an alternative approach – the one-time pad – that is secure against quantum decryption, we should consider why this approach isn’t also being pursued.

SecurityWeek spoke to senior advocates on both sides: NIST’s computer security mathematician Dustin Moody, and Qrypt’s cofounder and CTO Denis Mandich.

Moody accepts that one-time pads provide theoretically perfect security, but suggests their use has several drawbacks that make them impractical. “The one-time pad,” he said, “must be generated by a source of true randomness, and not a pseudo-random process.  This is not as trivial as it sounds at first glance.”

Mandich agrees with this, but comments, “[This is] why Qrypt uses quantum random number generators (QRNGs) licensed from the Oak Ridge National Laboratory and the Los Alamos National Laboratory.” These are quantum entropy sources that are the only known source of genuine randomness in science. (See Mitigating Threats to Encryption From Quantum and Bad Random for more information on QRNGs.)

Moody also suggests that OTP size is a problem. “The one-time pad must be as long as the message which is to be encrypted,” he said. “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.”

Again, Mandich agrees, saying the trade-off for higher security is longer keys. “This is true for 100% of all crypto systems,” he says: “the smaller the keys, the less security is a general statement.” But he adds, “One of the other [NIST] finalists is ‘Classic McEliece’ which also has enormous key sizes but will likely be standardized. In many common use cases, like messaging and small files, McEliece keys will be much larger than OTPs.”

Moody’s next concern is authentication. “There is no way to provide authentication using one-time pads,” he said.

Here, Mandich simply disagrees. “Authentication can be provided for any type of data or endpoint.” He thinks the idea may stem from the NSA’s objection to QKD. The NSA has said, “QKD does not provide a means to authenticate the QKD transmission source.”

But Mandich adds, “A simple counter example is that the OTP of an arbitrary length may be hashed and sent in the clear between parties to authenticate that they have the same OTP. This could be appended to the encrypted data.”

“As the name implies,” said Moody, “one-time pads can only be used once. This makes them very impractical.”

But Mandich responds, “This is the trade-off to achieve higher security. Re-use of encryption keys means that breaking or getting access to the key facilitates decryption of all the previously encrypted data. OTPs are only used once, so if someone gets access to one OTP, it does not help in any other decryption.”

For Moody, the biggest problem for OTPs is the exchange of ‘keys’. “Probably the most major drawback,” he told SecurityWeek, “is that to use a one-time pad with another party, you must have securely exchanged the secret one time pad itself with the other party.”

He believes this distribution at scale is impossible and doesn’t work where the requirement is to communicate with another party that hasn’t been communicated with before. “You could send the one-time pad through the mail or via a courier, but not electronically,” he continued. “And if you could securely send the one-time pad, why didn’t you just send the message you wanted to share with the other party? Which makes the one-time pad not needed.” 

Mandich points out that the difficulty in key transfer and distribution at scale apply equally to all the public key encryption keys currently being considered by NIST. “There is nothing unique about OTPs other than size,” he said. “OTPs can be generated continuously and consumed when the messages are created at a later date. There is no reason to do it simultaneously unless it is a realtime communications channel.” He adds that combining keys for decryption with the encrypted data makes it easy to attack. “Decoupling these two mechanisms [as with OTPs] makes it almost impossible.”

Finally, comments Moody, “Modern cryptosystems overcome these obstacles and are very efficient.”

Mandich concedes this point but refers to the distinction between NIST’s quantum safe approach, and the OTP’s ability to be quantum secure. “Modern systems are very efficient and a one-size-fits-all solution – but at the cost of less security. Obstacles to using OTPs have long been overcome by the cloud, high bandwidth networks, and distributed and decentralized data centers. The PQC evolution from RSA is just changing an algorithm based on a 1970s pre-internet architecture, when Alice and Bob were connected by a single copper wire channel and a few network switches.”

Current examples

Some companies are already using OTP concepts in their technology. Two examples include startups Rixon and Qrypt. The first borrows OTP ideas to secure data, while the second can enable genuine OTP communication.

Rixon

Rixon delivers a cloud-based vaultless tokenization system. Information received from a customer is immediately sent to the cloud and tokenized. What is returned to the client is data where each character has been randomly tokenized, and detokenization is under the control of the client’s customer; that is, the original end user.

No encryption algorithm nor encryption key is directly used in the tokenization, just a large set of random steps. The purpose is not to provide secure communications nor to provide a one-time pad. The purpose is to remove clear text data from a customer’s computers so that it cannot be stolen.

Nevertheless, the process borrows many of the concepts of the OTP. There is no algorithm that can be decrypted to provide widescale adversarial access to the data. Each character is independently tokenized, so that even if the tokenization process for that character is broken or discovered, it will only provide access to the single character.

The effect is that no two sets of customer data have the same ‘cryptographic’ process, making it similar to the OTP approach. 

“Everyone starts with a robust key management system, with key rotation, and key retirement being a keystone of every encryption management model,” Dave Johnson, CEO and cofounder of Rixon, told SecurityWeek. “After a time, all systems become looser in the sense that the processes and procedures become lax. Paperwork is easily adjusted to reflect compliance, but the reality is that key management systems become outdated and useless. Keys are stolen, compromised, and become known – organizations end up over time with an illusion of security.”

This will get worse in the quantum era. He continued, “With the advent of quantum processors – not that they’re really necessary to compromise encryption –with the implementation of these extremely fast processors the faults and the frailties of encryption will become blatantly apparent.”

Qrypt

Qrypt generates genuinely random numbers through a quantum process. This is the only known approach able to produce true randomness. The company has also developed a method able to provide the same random numbers simultaneously with both the sender and receiver. Both ends of the communication channel can use these numbers to generate the encryption keys without requiring the keys to be sent across the untrusted internet.

The initial purpose was primarily to provide true random numbers for any key generation, since poor or bad random numbers are the primary encryption attack vector. The second purpose was to eliminate the need to send keys across an untrusted network by having the same key independently built at both ends of the communications channel.

This process can be used to improve the safety of both current classical algorithms and NIST’s PQC algorithms, or to facilitate a move toward the security of one-time pads – the same process can be harnessed as a one-time pad.

The future for encryption

There is no doubt that current encryption algorithms need to be replaced before the quantum era. NIST is focused on staying with the existing approach – by using more complex algorithms to counter more powerful computers. If one-time pads were still impractical (NIST believes that to be true), then this is the only valid way forward.

But startups are already demonstrating that the problems that have prevented electronic OTPs in the past are being circumvented by new cloud technology. This throws into stark relief that there is now a genuine choice between NIST’s quantum safe solutions, and OTP’s quantum secure solution.

By Kevin Townsend on Tue, 04 Oct 2022 16:06:49 +0000
Original link