How to design a Post-Quantum Information System
Jean-Louis Olié, Alain Fernando-Santana ; November 2022
This article introduces the concept of Post Quantum Information Systems (PQIS), a new concept aimed at defining Information Systems designed to resist to any attack, whether from classical or quantum computers. In this article, CyferAll proposes a definition for PQIS and its approach to design such systems and to identify the essential building blocks.
Background
In our previous article, we discussed why and how information systems and the digital data that transit through them remain exposed to cyber-criminality, despite the cryptosystems currently deployed to protect digital data. We also reviewed the new threats that quantum computing will generate as the technology matures and why these new threats create an immediate threat requiring governments and businesses to replace their current cryptosystems. But how could we design information systems to make them resistant to quantum computing threats and provide digital data with a level of protection akin to “perfect secrecy”, a concept originally defined by Claude Shannon in 1949?[1] The aim of this article is to propose various paths the pursuit of which can bring us closer to Shannon’s vision while providing the preliminary building blocks for a Post-Quantum Information System.
Defining a Post-Quantum Information System
For purposes of this article, a post-quantum information system is defined as an application-level information system, running on one or several computers linked by a network and expected to provide system users with total protection:
(i) of processed digital data, in all its possible states: “in use”, “at rest” and “in transit”, from creation to restitution, against any threat, whether from classical or quantum computers;
(ii) from viruses and malware that could be resident on the computers processing the digital data; and
(iii) during user on-boarding and user login services supported by the system.
Total Data Protection
Let’s first clarify what “total data protection” really means and what are the real-world limits to the protection that an information system can provide to digital data. Indeed, for various reasons, an information system can never provide “total” protection as such since there are practical realities that will make this impossible. For example:
User Behaviour
Users are individuals and, as such, they are the ultimate holder of the actual information or the access to the information to be protected. However, these individuals always have the option to disclose the information, whether intentionally (with or without authorization) or unintentionally through simple or gross negligence. No matter how sophisticated the information system, it can never prevent the unauthorized intentional or negligent unintentional disclosure by a user of data or access credentials. This can be mitigated by security clearance procedures, information compartmentalization with “need to know” criteria, as well as personnel training to raise awareness on security.
In addition, the software instructions underlying any information system are coded by individuals who may have ulterior motives. A back-door placed intentionally during solution development by a coder that will then result in zero-day attacks cannot be identified ahead of time and protected against by an information system. This can be mitigated by code reviews and external certification procedures.
Facility-based surveillance
Moreover, users and peripherals are in physical facilities (a corporate or home office) and these facilities could be the object of unauthorized surveillance equipment able to capture access credentials / exchanged data and an information system cannot protect against such a scenario. This can be mitigated by systems that detect the presence of undesirable devices.
Therefore, the definition of “Total Protection” is understood to describe measures that are within the technological scope of an information system and its management of digital data.
Initial considerations regarding a Post Quantum Information System (PQIS)
Equipment/ Firmware
Ideally, a PQIS should be readily accessible and, as such, not require the use of specific, tailored, or customized computer hardware. Moreover:
i. the components within the computer hardware and their firmware must not be compromised and a process to ensure this “clean” state must precede their connection to the PQIS;
ii. the processor, CPU board and RAM must operate securely; and
iii. the capturing / rendering peripherals must be secure and not capable of surreptitious access to or the leaking of data to unauthorized recipients.
Operating Systems
The operating system plays a fundamental role in the operation of a computer, but it is a software component and, therefore, potentially modifiable by viruses or malware. Making an operating system less susceptible to viruses and malware is fundamental to the creation of a secure PQIS. One option to protect the operating system is to run it as a virtual machine and have it reside entirely in RAM in order to protect it against any malicious modifications.
Access Rights
Vinton G. Cerf, one of the designers of the key blocks of the Internet said that on creating the new network “We didn’t focus on how you could wreck the system intentionally.” This remains the challenge today. Information Systems grant access rights to approved users then no longer doubt their intentions. This logic has revealed itself to be fundamentally flawed as there seem to be as many users with bad intentions on the outside as on the inside of a private network. The American National Institute of Standards and Technology (NIST) addressed this concern in its special publication of 2020[2] relating to models for Zero Trust information systems. In such a model, the rights to access data in-the-clear are only granted to computers whose users are proven to be trustworthy to access the data. Until this prerequisite is met, the computer is not trusted, and a policy enforcement component of the system prevents data to be provided in-the-clear for the user of the computer. The policy enforcement component acts under the control of a policy decision point, managing all users’ rights to access each category of data. However, this model must be further refined. Indeed, as we have seen, considered as a whole, a computer cannot be considered trustworthy as it could have been infected by viruses or malware or the user’s access information could have been stolen using the techniques described earlier in this article. To protect against a computer that has been infected by a virus or malware the implementation of the zero-trust model must create an unbreakable chain of data custody between protected enclaves. In such a model, end-to-end encryption is in fact implemented as secure enclave to secure enclave, with much better guarantees of protection for not only data “in transit” but also data “in use” and data “at rest”.
To protect against a user whose access information has been stolen the information system can regularly undertake identity verifications, biometric or otherwise, depending on the information system’s analysis of the user’s behaviour, previous access to this same information, time of day, location from which the access request is made etc. etc. The assumption should no longer be that the user has any right to be in the network and much less access the requested information.
The role of the Browser
As its name would suggest, the internet browser was invented to facilitate navigating the internet and retrieving information from sites or other internet locations. The browser is also the program that sets up video conferencing connections, Internet voice connections, webmail and chat in specific web-applications. Most all information transiting through the browser is in-the clear since this browser is the end point of “end to end encryption“ in these web-applications. Indeed, although the TLS protocol provides for the symmetrical encryption of data and the asymmetrical exchange of keys with authentication, it cannot resist quantum attacks. Furthermore, the TLS protocol only protects data during transport between browsers. Before encryption and after decryption, data resides “in the clear” in the browsers’ cache and can be data mined or compromised by viruses and malware. The advent of cookies and their ability to track, collect and store the data resulting from a user’s browsing activity (data mining) created a revenue opportunity of such proportion that the browser became as much a surveillance tool as a facilitator of internet surfing/ internet services. But to undertake data mining activities on the information that transits through the browser, this information must be in-the-clear. Since browsers are at the core of any internet browsing and user communication activity and since their browser publisher’s primary focus is data mining and data monetization, in a PQIS, where exposing / compromising data must be absolutely avoided, the browser cannot play a role when it comes to data protection. In a PQIS, the components of the computer should be reviewed to identify any protected enclaves that can shelter data in-the-clear, and it is these enclaves that should be directly managed by the policy enforcement component. It is only in these enclaves that data can be in-the-clear and where changes in data state can safely occur when authentication of the user is performed during a transition from one of the three states, “in use”, “at rest” or “in transit” to another of these three states. These protected enclaves are also the places where hardware peripherals necessary to create or to render information, such as a keyboard, a microphone, a camera, a loudspeaker, or a screen display, should capture and render data.
The Protected Enclaves
In all modern computers, without any specific hardware component, the three possible locations for storing data are the processors’ registers, the volatile random-access memory, also called main memory, and the mass storage devices[3]. The processors’ registers have a very limited capacity and can only store data being processed. The mass storage devices can be accessed by any application running on the computer and an application can be a malware, therefore sensitive data must not be in the clear on mass storage devices. In the end, the only location to create protected enclaves is the volatile random-access memory (RAM).
Indeed, slices of RAM are allocated to each running process in an exclusive manner by the processor. If a slice of memory is allocated to an application, none of the other simultaneously running processes, including viruses and malware, will be able to access the data stored within the allocated slice.
The RAM-based software architecture described above helps to address the weaknesses of the application layer of most current information systems, without requiring any specific hardware component, but the cryptosystem it must rely on remains to be discussed.
The Cryptosystem
As seen previously, the first component that this cryptosystem must include is a symmetrical encryption algorithm to encrypt/ decrypt data needing protection within the above defined secure enclaves. As seen in the previous article, this algorithm will require a 512-bit key to resist quantum computing attacks, but it must also: (i) resist side channel attacks, (ii) provide integrity verification without creating weaknesses or operational limitations in its use and, (iii) as data will be processed directly in RAM, the algorithm must have a very high throughput and ultra-low latency. This latency is defined as the number of clock cycles necessary to encrypt, decrypt and verify integrity of each byte of data. To achieve the highest standard in terms of resistance to cryptanalysis, the symmetrical encryption algorithm must be indistinguishable under adaptative chosen cipher attack (IND-CCA2)[4]. An encryption algorithm is said to have such a property if an attacker, being given two plaintexts and the ciphertext of one of these two plaintexts, cannot determine which one of the plaintexts corresponds to the ciphertext with a probability higher than ½. Even more, this property must be established if the attacker also has access to a decryption oracle that can provide any number of decrypted forms of encrypted messages chosen by the attacker, with the exception, of course, of the encrypted message itself. In addition, all these requirements must be met by the symmetrical encryption algorithm without requiring any specific hardware component.
The second component of the cryptosystem is an asymmetrical encryption algorithm that will allow the exchange of the symmetrical encryption algorithm key described above, between two distant users of the PQIS, when these users are cleared by a Policy Decision Point to exchange messages or real time streams of data encrypted with this symmetrical algorithm. The asymmetrical algorithm must be post-quantum, more precisely, able to resist to quantum computing with a level of security of at least 256 bits. In July 2022[5], the NIST announced that after a five-year selection process they choose to standardize the Crystals-Kyber algorithm. This algorithm is IND-CCA2 and has a version with a level of security of 256 bits.
The last component needed by the cryptosystem is another post-quantum asymmetrical algorithm. This asymmetrical algorithm will allow the authentication of users in the exchange of keys encrypted with the first asymmetrical algorithm, by providing these users with the means to sign this exchange and verify their counterparts’ signature. In their July 2022 announcement, the NIST also gave a list of three Digital Signature algorithms to be standardized: Crystals-Dilithium, Falcon and Sphincs+.
The Proof of Concept
A Post-Quantum Information System built on such principles, with a software architecture based on a Zero-Trust model with RAM-to-RAM[6] encryption and a cryptosystem including symmetrical and asymmetrical encryption as outlined above, will be able to provide users with “total protection” of digital data. To prove the feasibility of the concept, CyferAll, a France-based start-up implemented the concept in its SaaS platform supporting a wide range of encryption, messaging, and communication services. The RAM-to-RAM software architecture and the symmetrical encryption algorithms have been the subject of two patent filings. The software architecture adheres to Privacy-By-Design principles to ensure GDPR / HIPPA compliance. The CyferAll platform also complies with French and European regulations aimed at preventing the utilisation of cryptographic means for malevolence and acts of terrorism. The first innovation relates to the software architecture and the associated protocols for users’ on-boarding and users’ login, allowing to safely support the RAM-to-RAM software concept, while respecting the regulatory constraints.
The second innovation relates to the definition of a symmetrical encryption algorithm that addresses all weaknesses listed in our previous article, related to insufficient key length and indirect attacks. The symmetrical encryption algorithm is derived from the “One Time Pad” (OTP) algorithm that was proposed by an American engineer, Joseph Mauborgne, as an improved version of the Vernam cipher[7], invented in 1917 by Gilbert Vernam.
This algorithm is said to be semantically secure since it has the interesting, mathematically proven, characteristic to be totally unbreakable, whatever the computing power utilised. Unfortunately, it requires a key of the same length as the data to be encrypted and requires this key to be different for each data transmission. This made the algorithm impossible to use in practice in modern information systems, as the keys, each time different, are as difficult to exchange as the messages themselves, but this OTP algorithm is IND-CCA2 with an infinite level of security. It is also resistant to side channels attacks, since there is no fixed key to be retrieved by statistical analysis, and it has by very far the lowest encryption latency of any existing encryption algorithm. Within CyferAll’s cryptosystem technology, this algorithm has been transformed so that it is able to produce streams of random pads, of any length and different for each message, from a fixed key, 512 bits long and it also has an integrity verification capability. It can be proven that it remains IND-CCA2 but with a level of security reduced to 512 bits, which is sufficient to resist quantum computing. This transformation of the algorithm is also designed to preserve its resistance to side channel attacks. The integrity verification capability increases latency, but performance remains much better than with any other existing standard algorithm. When this development was completed, NIST had not yet published the list of post-quantum asymmetrical algorithms selected for standardization, so the post-quantum algorithms used in the CyferAll proof of concept were RLCE[8] and XMSS-MT[9].
The results
A comparison of symmetrical encryption algorithm technologies is provided below.
Security
Performance
These results confirm that with significantly lower latency, the proposed symmetrical encryption algorithm can provide the required 512 bits level of security, with integrity verification and resistance to side channel attacks
In conclusion, it is feasible to build Post-Quantum Information Systems that offer what we have defined as “total protection”, a level of protection as close as possible to Perfect Secrecy, while considering the need to ensure excellent application perform
[1] Shannon, Claude, Communication Theory of Secrecy Systems, Bell System Technical Journal, 28(4): 656–715, 1949
[2] Rose Scott, Borchert Oliver, Mitchell Stu and Connelly Sean Zero Trust Architecture, NIST Special Publication 800–207, 2020
[3] John L. Hennessy and David Patterson (2006). Computer Architecture: A Quantitative Approach (Fourth ed.). Morgan Kaufmann. ISBN 978–0–12–370490–0
[4] Bellare, Mihir; Rogaway, Phillip (May 11, 2005). Introduction to Modern Cryptography, Chapter 5: Symmetric Encryption
[5] https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
[6] CyferAll registered the mark RAM2RAM to describe its software architecture
[7] Vernam, Gilbert S., Secret signaling System patent, Google.com, Archived from the original on 11 March 2016
[8] Yongee Wang, Quantum Resistant Random Linear Code Based Public Key Encryption Scheme RLCE, eprint arXiv:1512.08454, 2016
[9] A. Huelsing, D. Butin, S. Gazdag, J. Rijneveld, A. Mohaisen. XMSS: eXtended Merkle Signature Scheme, https://datatracker.ietf.org/doc/html/rfc8391
