Quantum Computers -  A threat for PKI?

Photo Credit: IBM quantum computer. An IBM Q cryostat used to keep IBM’s 50-qubit quantum computer cold in the IBM Q lab in Yorktown Heights, New York.

What are the prerequisites for a secure PKI today? Will quantum computers make PKIs obsolete in the future? Could blockchain provide a solution? The speakers attended such questions at a SIGS event. Another question also discussed was when quantum computers would be ready for production at all.

PKI IN THE FOCUS

The Special Event of Security Interest Group Switzerland (SIGS) on February 9, 2017 at Mobiliar in Bern was titled „About and beyond PKI“. The speakers were:

• Dr. François Weissbaum, Scientist for cryptography, Swiss department of defense (FUB)
• Marcel Suter, Principal Consultant, IibC Technologies Sàrl
• Marcel Dasen, Vice President Engineering, Securosys SA
• André Clerc, Expert IT Security Consultant, TEMET AG 

The Event focused on four presentations with the following topics:

• François Weissbaum: What is a quantum computer? What is the threat to the PKI and what approaches are there to protect against attacks? 

• Marcel Suter: Which tasks must be addressed in key management for  PKI? How do you go about it? What aids and systems are available?

• Marcel Dasen: How do I protect my PKI keys efficiently? Which obstacles must be overcome? 

• André Clerc: Can the PKI be protected in the future using Blockchain? What are the implementation approaches? What are the pros and cons of blockchain? What should I do?

THE QUANTUM COMPUTER IS THREATENING - WHAT TO DO?

How can quantum computers influence the world of cryptography? The scientist François Weissbaum tried to answer this question. First though, the question is, what is a quantum computer what can it do. In contrast to conventional computers, quantum computers are based on Qubits instead of bits as the smallest memory unit. A Qubit can take on a multitude of states - different than a bit. According to theoretical studies, quantum computers will be able to solve certain problems in much less time than conventional computers.

SHOR’S: THREAT FOR ASYMMETRIC ALGORITHMS

Weissbaum asked the question: Suppose, in the foreseeable future, quantum computers with at least 64 qubits will be available: What problems will they solve? He argued that there are two quantum algorithms: Grover's and Shor's. With the latter, a non-trivial divisor of a compound number can be found in a much faster time via a quantum computer than on a conventional computer. However, because of technical limitations Shor's can hardly be used practically. However, should the universal quantum computer come, all asymmetric standard algorithms will become breakable: Diffie-Hellman, RSA, Elliptic curve, ElGamal etc.

GROVER’S: 128-BIT ALGORITHMS IN DANGER

Using Grover's algorithm, on the other hand, a certain value can be found from a set of possible values. The above quantum computer could break with it a symmetric key with 128 bits in about 2⁶⁴ iterations.

What to do?

"In order to maintain the previous security level, the key length should be doubled because an attack with an exhaustive search from a conventional computer against a symmetric cipher with 128 bits corresponds to a 256-bit symmetric cipher from a quantum computer. The Advanced Encryption Standard AES would therefore have to be increased to 256 bits", explained Weissbaum.

Grover's algorithm can also be used against hash functions. However, a hash function starting from 384 bits is theoretically quantum-proof. "Also practicable attacks against SHA-256 as well as SHA3-256 are unimaginable in the foreseeable future," explained Weissbaum.

STRATEGIES FOR PROTECTING PKIS

He proposes the following options to secure PKIs in the future:

1. Replace PKI by a central key infrastructure that only works symmetrically
2. Find a new, asymmetric algorithm that is quantum-proof.

For the latter approach, there are so far four hopeful approaches:

1. Hash-based cryptography
2. Codebased cryptography
3. Grid-based cryptography
4. Cryptography based on multivariate polynomial equations

Weissbaum puts the greatest hope on the fourth approach: "This is close to a solution."

It is also worth mentioning that the US National Institute for Standards and Technology (NIST) has launched a project to find quantum-resistant cryptography algorithms for public keys.

Weissbaum does not see any threats to the authentication process, nor to standard signatures, nor to the encryption of information that does not have to be protected for tens of years. However, signatures and information that must be protected over a period of more than ten years are threatened. Weissbaum argued that even the most optimistic physicists do not expect universal quantum computers in a ten, fifteen year timeframe. "Quantum computers with three to four qubits can be produced now. But they are neither scalable nor stable. In addition, the operation of a single universal quantum computer would require the performance of a whole nuclear power plant. The advantage would be that you can easily determine who really has a quantum computer. "

Presentation „The Quantum Apocalypse von Dr. François Weissbaum“ 

THE CUMBERSOME WAY TO OPTIMAL KEY MANAGEMENT

Key management within a PKI is a challenging task. Marcel Suter showed that many aspects must be considered. These include governance, availability, security, training, and key distribution. "The difficulty is," says Suter, "that you have to combine a lot of aspects and form a framework."

NIST list as planning aid

Suter proposes to plan key management according to the recommendations of the US National Institute of Standards and Technology (NIST). On  NIST's website are many documents such as recommendations and best practices. Basically, a five-step plan is required:

1. Service definition: What should the service do?
2. Security: Are confidentiality, data integrity, authentication integrity, source authentication, authorization, recognition, support services, and combined services guaranteed?
3. Planning: Have you thought of everything, for example, which cryptographic algorithms to use, how big key lengths are, responsibilities, protection requirements and mechanisms, key usage and types, etc.?
4. Specification: aspects of cryptographic application, key management, access control, key recovery and distribution, etc.
5. Implementation

Suter recommends to write a document about with detailed specification. Every aspects splits into a lot of sub-aspects, which must be meticulously defined. For example, it is paramount to use longer key lengths for data that needs to be protected in the long term. That also requires that you know which data must be protected in the long term.

IMPORTANT: WHERE DO THE KEYS COME FROM?

An important aspect in key management is the question of where the keys come from. A good solution is the purchase of a hardware security module. "The manufacturer, however, should be closely scrutinized. After all, the system will be in operation for about a decade, because the keys can not be extracted from the HSM", warns Suter. "If you get your HSM, for example, from a US manufacturer you may have a problem." Not only the trustworthiness of the HSM manufacturer should be checked. But also how the keys are generated. A safe possibility of key generation is the measurement of random physical phenomena. One of the things to check here is that this measurement can not be tracked or spied out.

Another option for key management is to keep the keys in the cloud. But even here, Suter warns against US-American vendors: "As non-Americans, you may not have good data protection there."

In short, setting up  suitable key management is a lengthy process, with many details to be considered. Suter advises: "Make a good mix and look to meet the needs of your business."

Presentation „Key Management Tasks“ by Marcel Suter.

HOW TO EFFICIENTLY PROTECT YOUR ENCRYPTION KEYS

In his presentation, Marcel Dasen showed how to build a secure infrastructure that is prepared for tomorrow's challenges. It is a fact that cryptographic keys are indispensable in the digital world. Today, they are used in a wide range of domains, including payment traffic, "regulated" digital signatures, web server authentication, infrastructure services, e.g. DNSSEC or SMTP or for data storage.

WHAT KEY TYPES ARE THERE AT ALL?

Within the PKI infrastructure there are encryption, signature and certificate keys. These keys are typically organized hierarchically. Even for a simple PKI, several key pairs are already required. Moreover, for different applications, different principles for key handling are needed. This means that different types of certificates are required. Because keys can also be revoked, a certification authority (CA) must issue and sign a revocation list (CRL).

Based on this complexity, it becomes obvious that keys need to be managed actively.

KEYS ANYWHERE, SOMEWHERE - A FATAL MISTAKE

Encryption is good. But when storing keys, often a fatal error is made because keys are typically stored in files. Often just in the home directory of users who are protected by access rights for the user or groups. Users with comprehensive permissions can access them. As a result, the keys are generally not adequately protected. Marcel Dasen: "It's like the house is closed, but the key is right underneath the doormat."

Help is provided by using a managed key store, a so-called hardware security module, which offers the best solution. The hardware security module is a dedicated device for encryption keys, which protects them from loss and theft, and serves as the central authority for the PKI infrastructure: "Private and secret keys are stored here. They can also be generated there and never leave the device." An HSM may also provide protection from quantum computers if it can be updated with appropriate cryptography as soon as these new algorithms become available.

However, post-quantum cryptography, as Weissbaum had shown, is still not available. But you can already build a secure infrastructure today by:

• using symmetric cryptography, for example with AES and Kerberos
• storing keys safely in a HSM
• using keys and signatures with longer bit length
• use updateable cryptographic hardware and software
• manage encryption keys
• work with trustworthy suppliers

This strategy also protects data in the cloud when the solutions are implemented correctly.

Presentation „Keep your fingers off my keys – today & tomorrow“ by Marcel Dasen 

BLOCKCHAIN AS A PROTECTION AGAINST QUANTUM COMPUTERS?

André Clerc wondered whether blockchain technology could replace a PKI in the longer term. In his analysys he assumed that today's PKIs could be broken with a quantum computer.

To start off, Clerc pointed out that PKIs already have shortcomings: Verification of the identity can be insufficient, for example, or a certification authority (CA) could work with an obsolete list, which would not detect faulty CA behavior for a very long time. And with regard to the future, the algorithms used with PKIs, as already shown several times, are not quantum-proof.

Could these inadequacies be compensated for with the blockchain technology?

THIS IS HOW BLOCKCHAIN WORKS

Blockchain is a distributed database of transactions (ledger) that maintains a growing list of records (blocks). Each entry in the list is linked to a previous entry (blockchain). This results in a so-called hash-tree or hash-calendar. As a rule, the list is distributed and publicly visible, ie neither confidential nor centralized. The entity is called Distributed Open Ledger (DOL). ECDSA (Elliptic Curve Digital Signature Algorithm) is used to sign the transactions. With a key length of 512 bits, a security margin of 256 bits results. The hashes used are SHA256 and RIPEM-160 as well as SHA3-256. Since these underlying algorithms are not quantum-proof, the blockchain is not quantum-proof either.

BLOCKCHAIN COMPENSATES FOR PKI INADEQUACIES

There are already some implementation approaches of blockchain in the PKI, which try to compensate for their weaknesses:

• IKP (Instant Karma PKI). The problem of possible misconduct of a certificate instance (CA) is addressed via blockchain.
• DPKI (decentralized PKI). In this approach, the control of the online identities is returned to the entities to which they belong.
• Support for detailed access data with a blockchain PKI. The revoked certificates are checked on the local copy of the blockchain.
• KSI (Keyless Signature Infrastructure). A worldwide distributed system that offers time stamps and digital signature services. This is not vulnerable to key compromises and is therefore suitable for long-term protection of digital signatures - but it is not suitable for encryption.

ARGUMENTS FOR BLOCKCHAIN:

• High availability
• Operation by a decentralized authority
• Anyone involved can check all modifications, the data or even the code are accessible

ARGUMENTS AGAINST BLOCKCHAIN:

• Scalability and throughput capacity are low
• If someone controls more than half of the administrators of the distributed database, then he also determines the new entries in the ledger
• The linking process would consume far too much power
• The algorithms used are not quantum-proof

Therefore blockchain does not provide long-term protection for the PKI.

HOW TO PROTECT ONESELF ANYWAY?

Before post-quantum cryptography is available, organizations can protect themselves by verifying the following:

• Do all critical applications work with certificates?
• Is there a process for updating cryptographic principles?
• Is the PKI strategy up-to-date?
• Do key and certificate management match the business?
• Is the key-up cycle up-to-date?
• Is certificate validation up-to-date?
• Do I know the current standards regarding quantum-secure algorithms?
• Etc.

In addition, one should create an inventory that lists all applications and communication channels that use asymmetric cryptography.

Assuming that post-quantum cryptology (PQC) is available, then you should

• Establish a process that verifies the maturity of the PQC algorithm
• Integrate the PQC algorithm on the affected communication channels and applications

"Does it make sense to invest in fixing a poorly implemented PKI if it can be hacked with the quantum computer anyway?" This question was asked by the audience. André Clerc confirmed this: "Investing in fixing your PKI is always worthwhile. Regarding making your PKI quantum-secure there is still time. Once this work has been done, only the algorithms have to be adapted."

Presentation „Blockchain and PKI“ by André Clerc 

CONCLUSION

In summary, the following procedure is recommended to be prepared for the future:

• Review your key management: Does your homework and build a clean, detailed, verified key management for the PKI. Document it together with the entire PKI process and you are well prepared for the future. This also requires:
• Increase key lengths: Symmetrical keys of 256 bits or longer can not be cracked based on existing knowledge on quantum computers. Likewise, the key lengths in asymmetric methods such as RSA should be increased to at least 3072 bits or even 4096 bits if data is protected for long-term storage.
• Protect keys: Encryption only works when the encryption keys are safely stored and well protected. This is only guaranteed in a trustworthy hardware security module.

• Blockchain offers interesting approaches, but it is not suitable for the protection of the PKI - especially not in a future with quantum computers, it requires quantum-resistant algorithms.
• Hardware Security Module (HSM) from a trusted manufacturer like Securosys protect keys from unwanted accesses, operate very efficiently with larger key lengths and support a reputable key management. In addition, HSM from Securosys can be upgraded with quantum-fast algorithms in the future. They offer the necessary protection for the PKI - even in a future with quantum computers.