NIST reduced the number of candidates for post-quantum cryptography

Post-quantum cryptography encompasses the algorithms that are allegedly immune against quantum computing. There are five categories that seem suitable for post-quantum cryptography. See previous post.
In 2017, NIST initiated the process to select and standardize a set of post-quantum cryptosystems. In 2019, the second round selected 26 candidates. The third round started in 2020. Last month, NIST published an intermediary analysis of these candidates. As a result, NIST selected seven serious candidates and eight potential but unlikely contenders. The draft standards should be available by 2024. Table 1 lists the nine candidates for encryption. The predominance of lattice-based and code-based solutions is visible. Table 2 lists the six selected candidates for digital signatures. The more likely candidates are highlighted.

Classic McElieceX
NTRU primeX
Table 1: NIST candidates for encryption
Table 2: NIST candidates for digital signature

Lattice seems to be the big runner for post-quantum. A future post will attempt to give a hint on lattice-based cryptography.

The report is available at

Quantum what?

Quantum what?

Quantum computing, quantum cryptography, and post-quantum cryptography: these terms are confusing.  This post attempts to clarify them and draws the relationship between them.

Quantum computing is the set of technologies that use quantum-mechanical phenomena to perform computing.  Quantum computing uses qubits rather than bits.  Where one bit of conventional computing has one of the two possible states “0” or “1”, a qubit has a set of independent states simultaneously via superposition.  Furthermore, entangled qubits behave together in non-conventional ways (for instance, immediate synchronization independent from the distance separating the two qubits).

These properties allow solving some classes of problems, many orders faster than conventional computing.  In 1994, Peter Shor published “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” [1].  His algorithm solves the prime factorization and discrete logarithm hard problems.  Prime factorization is the foundation of cryptosystems such as Diffie Hellman (DH) and RSA.  Discrete logarithms are the foundation of elliptic curve cryptosystems (ECC). In 1996, Lov Grover published “A fast quantum mechanical algorithm for database search” [2].  His algorithm inverts one-way functions in  time.  It applies to symmetric ciphers and cryptographic hashes.

Whenever quantum computing is operational, accurate, and with enough qubits, these algorithms and their enhancements will impact traditional cryptography.  To mitigate Grover’s algorithm, the size of symmetric keys and hashes has to increase.  For instance, AES will need at least 256-bit keys. Shor’s algorithm annihilates the security of prime factorization or discrete logarithm-based cryptosystems.  In other words, DH, RSA, and ECC will not be secure anymore.

Post-quantum cryptography encompasses the algorithms that are allegedly immune against quantum computing.   There are mainly four categories of algorithms.

  • Hash-based signatures; It uses the current hash algorithms, and its security is well understood. The size of the public key is far larger and usable only once. 
  • Code-based encryption;  It uses sophisticated error-correcting codes.  The McEliece’s scheme was first proposed in 1978 [3] and has not been broken since. 
  • Lattice-based encryption is the most efficient and promising solution.  It allows encryption, digital signatures, and fully homomorphic encryption.
  • Multi-variate Quadratic Equations seem the less promising path.  All proposed schemes are currently broken. 

It is wise to strengthen post-quantum cryptography to be ready whenever this threat is active.  NIST estimates that a 1 billion $ quantum computer may break RSA 2048 keys in a matter of hours.   A future post will explore more in detail post-quantum cryptography.

Quantum cryptography or Quantum Key Distribution (QKD) sends over information, including a secret key, using photons over a line between Alice and Bob.  Once Bob received the secret key, Alice and Bob use it to encrypt and decrypt via traditional symmetric cryptosystems their messages.  This key distribution is very similar to many current systems.  Nevertheless, due to the Heisenberg’s principle, if Eve eavesdrops the QKD, she alters the secret key.  Thus, Alice and Bob know they are eavesdropped, offering higher security.  The obvious limitation is that it can only be used in point to point communications.  The first QKDs were designed in the 80s.

Hoping that this post shed some light, I wish you a happy new year.


[1]          P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Comput., vol. 26, no. 5, pp. 1484–1509, Oct. 1997, doi: 10.1137/S0097539795293172.

[2]          L. K. Grover, “A fast quantum mechanical algorithm for database search,” ArXivquant-Ph9605043, Nov. 1996.

[3]          R. McEliece, “A public-key cryptosystem based on algebraic coding theory,” NASA, DSN 42-44, 1978.

My preferred papers at Black Hat 2019

I attended the briefings at Black Hat 2019.  All the presentations I attended were engaging.  Nevertheless, here is the feedback on my preferred ones.  The link gives access to the corresponding slid decks.

A Decade After Bleichenbacher ’06, RSA Signature Forgery Still Works (Sze Yiu Chau)

One of the mitigations to Bleichenbacher’s attack is that the exponent d should be large. Unfortunately, in some standards d is still small, typically 3.  But even with larger exponents, forgery is possible due to vulnerable software.

Forgery uses the fact that many verifiers do not check garbage, parameter lengths, and padding.

He provides a list of vulnerable libraries (that are now fixed).


  • Check everything. No corner cutting.
  • Parsing in security should be bulletproof.  The complexity of the structures and syntax may become an issue.  Complexity is the enemy of security.

Lessons from 3 years of crypto and blockchain audit (Jean-Philippe Aumasson)

Jean Philippe is a Kudelski Security expert. 

He provides a view of most deployed mistakes.  Most are well known.  A few ones that I liked:

  • Weak key derivation from a password. Use a real derivation function.
  • Avoid using panic if the error is not unrecoverable, else it may become a potential DoS.
  • No way to erase securely sensitive memory with garbage collection (for Instance, go)

His preferred language for crypto is Rust.

The slide deck is an excellent refresher of what not to do.  Practitioners should have a look.

Breaking Encrypted Databases: Generic Attacks on Range Queries (Marie-Sarah Lacharite)

She presented how to use access pattern leakage and volume attack leakage to guess the content of the database even if encrypted.

Independently of the provided attacks, the researcher reminded that if using a common encryption key (and same IV) with server-side encryption, it is still possible to perform a range query because the same cleartext generates the same ciphertext.  This may be a PII issue. 

There are some partial solutions to this problem:

  • Order preserving encryption solves the issue
  • Order revealing encryption is even better

Pattern leakages measure the number of returned records per request. She used PQ trees to rebuild the order of the observed answer of access pattern. For N values in the database, N log N queries were needed.

Volume leakage is easier because the attacker may just monitor the communication. For N values in the database, N2 log N of observed queries are needed.

Some possible mitigations:

  • Restricting query types
  • Dummy records
  • Dummy values

The two last solutions may introduce some accuracy issues if not filtered out.

Everybody be Cool, This is a Robbery! (Gabriel CampanaJean-Baptiste Bédrune)

The studied the actual security of Hardware Security Modules (HSM).  HSMs are rarely studied because they are expensive and if attacked they will erase secret.

They used the PKCS11 API.

The targeted HSM used an old version of LINUX (10-year-old). Furthermore, every process runs as root, and there was NO secure boot.  Attackers used fuzzing to find 14 vulnerabilities.  Exploiting a few of them, they could get access to the private root key!


Hardware Tamper Resistance and controlled API are not enough.  The software should assume that the enclave has been breached and be protected correspondingly. 

Breaking Samsung’s ARM TrustZone (Maxime PeterlinAlexandre AdamskiJoffrey Guilbon)

Samsung’s Trustzone works only on Samsung chip Exonis and not Qualcomm’s Snapdragon

The secure OS is Kinibi by Trustonics.

Once more, adversaries used a fuzzier (AFL-based)

Currently, the trustlet has no ASLR and PIE (Position Independent Executable). They used buffer overflow on the trustlet and a trusted vulnerable driver to go inside the Trustzone. From there,  they attacked mmap for accessing Kinibi.

They were able to read and write memory arbitrarily. For instance, they accessed the master key both from EL3 and from EL1.  With the master key, the attacker has access to all the secrets in the Trustzone.


Once more, protect code within the secure enclave.  Defense in depth is critical.

Apple’s Find My

Apple disclosed at the WWDC an interesting feature: “Find My.”   It will be possible to track the GPS location of your device if it is stolen or lost.  And Apple will not know this location.  Here is how it works. 

The prerequisite is that you have at least two Apple devices.   All your devices share a private key.  The trick is that instead of having one unique public key, the devices have a multitude of public keys linked to this private key.  This is possible, and there are numerous known cryptographic solutions that may fulfill this part.

The device broadcasts via Bluetooth its current public key.   The device broadcasts this beacon even while turned out.  Any Apple device nearby may catch the beacon.  Then the receiving device encrypts its current GPS location with the broadcast public key.  It sends the encrypted location as well as the cryptographic hash of the public key to Apple’s server.  Of course, the public key changes periodically.  The rotating period has not been disclosed.

If you want to locate one of your devices, you trigger the request on one of your devices.  It sends the hash of the public key to the Apple server, which returns the encrypted location.  The device has the private key and thus can decrypt the location. Et voila.

Of course, under the assumption that Apple does not have the private key, only your devices can decrypt the location.  Normally, Apple can neither get the location nor link different related public keys together.

Many questions that were not answered in the presentation.  The frequency of key rotation, is there a limited number of public keys, how to know which hash to send?  Waiting for some publications to deep dive.

The idea is interesting.  It is complex, thus subject to failures and vulnerabilities.   What would the system do if, from many locations, there is a beacon broadcasting the same public key?  Will the collection of multiple related public keys not reveal some partial information, for instance one of the exponents?

Biometric Vein Recognition Hacked

Biometric vein recognition is considered with iris recognition as the most secure biometrics system. Vein recognition is used in highly secure areas. Automatic Telling Machines starts to use this technology with, for instance in Japan. This statement was valid until December 2018. At the famous German Chaos Communication Congress (35c3), Krissler Ian, also known as Starbug, and Albrecht Julian demonstrated a method (German video) to create a lure hand that defeats commercial systems.

Starbug is a well known hacker in the field of biometrics. For instance, in 2016, he faked successfully the fingerprints of a German minister using high resolution captured photos.

For about 20 years, vein recognition is mainly a Japanese technology. Fujitsu and Hitachi are the two leaders. The network of veins is captured either by reflection from the palm or through transparency with Infra Red (IR) light for fingers. The captured network is turned into minutiae like a typical fingerprint.

The capture phase seems rather simple. The researchers removed the IR filter of a traditional high-end DSLR camera (in that case, Nikon D600) with good lenses. They were able to get a proper capture up to 6 meters with a flash. They also built a raspberry-based system that could be hidden into a device, for instance, a hand-dry-blower. The captured image is processed via a python script to generate a skeleton of the network of veins (as illustrated by the figure below).

Once the skeleton available, they build a fake hand (or finger) using bee wax. The fake hand covers the printed picture. They tried many different materials, but the wax presented the best performance concerning transparency and diffraction of IR light, in other words, it better emulated skin.

Once the fake hand available, the attacker has to use it on the detector. They performed a live demonstration. The demonstration highlighted that the lighting conditions were critical. The strong lighting of the scene spoiled the demonstration, and they had to shade the detector to success. On the other hand, the fake finger detection went on smoothly. The detector was a kind of tunnel. At the time of the presentation, Hitachi and Fujitsu did not have yet reacted.

The attacked detectors had no liveliness detection. As I highlighted in section 7.4.2 of “Ten Laws for Security,” detecting the presence of a real living being behind the captured biometrics is necessarily for robust systems. Unfortunately, such detection increases the complexity and cost of detectors.

Conclusion: Once more, Law 1: Attackers will always find their way
was demonstrated.

Deep Learning: A Critical Appraisal (paper review)

Deep learning is becoming extremely popular. It is one of the fields of Machine Learning that is the most explored and exploited. AlphaGo, Natural Language Processing, image recognition, and many more topics are iconic examples of the success of deep learning. It is so successful that it seems to become the golden answer to all our problems.

Gary Marcus, a respected ML/AI researcher, published an excellent critical appraisal of this technique. For instance, he listed ten challenges that deep learning faces. He concludes that deep learning is only one of the tools needed and not necessarily a silver bullet for all problems.

From the security point of view, here are the challenges that seem relevant:

“Deep Learning thus far works well as an approximation, but its answers often cannot be fully trusted.”

Indeed, the approach is probabilistic rather than heuristic. Thus, we must be cautious. Currently, the systems are too easily fooled. This blog reported several such attacks. The Generative Adversarial Networks are promising attack tools.

“Deep learning presumes a largely stable world, in ways that may be problematic.”

Stability is not necessarily the prime characteristics of our environments.

“Deep learning thus far cannot inherently distinguish causation from correlation.”

This challenge is not related to security. Nevertheless, it is imperative to understand it. Deep learning detects a correlation. Too often, people assume that there is causation when seeing the correlation. This assertion is often false. Causation may be real if the parameters are independent. If they are linked/triggered by an undisclosed parameter, it is instead this undisclosed parameter that produces the causation.

In any case, this paper is fascinating to read to keep an open, sane view of this field.

Marcus, Gary. “Deep Learning: A Critical Appraisal.” ArXiv:1801.00631 [Cs, Stat], January 2, 2018.



Blockchain: a “supply chain” attack

A hacker, by the handle Right9ctrl, has injected malicious code that steals Bitcoin and Bitcoin Cash funds stored inside BitPay’s Copay wallet apps. The hacker injected the malicious code in the JavaScript library Event_Stream. This malicious code lays dormant until used inside the source code of Copay, a Bitcoin wallet. There, it steals much information such as the private key.

Right9ctrl inherited the access to the Event_Stream library because the initial author passed him/her the control. The initial author did not want to maintain anymore the open source library.

In other words, this is an example of a software supply chain attack. One element in the supply chain (here a library) has been compromised. Such an attack is not a surprise. Nevertheless, it raises a question about the security of open source components.

Many years ago, the motto was “Open source is more secure than proprietary solutions.” The primary rationale was that many eyes reviewed the code and we all know that code review is key for secure software. In the early days of open source, this motto may have been mostly true, under some specific trust models ( see, Chapter 12 of Securing Digital Video…). Is it still true in our days?

Currently, there are a plethora of available open source libraries. With the advent of many new programming languages, the number of libraries is exploding. Many projects have a few contributors, sometimes even only one individual. How many users of these libraries review the code before using it? I would guess very very few. Thus, the motto is becoming weaker. It is probably true for large, well-established projects, such as OpenSSL, but what for projects with one contributor? The success of the library is most probably not a valid indicator of trustfulness.

In this case, a warning signal would have been that the malicious code was heavily obfuscated. There is no legitimate reason why a JavaScript open source should be obfuscated. Open source is about transparency. Obfuscation is about obscurity.

Conclusion: be very careful when selecting an open source library, you may not necessarily trust it.

Conclusion2: if you are using a copy wallet, Sophos provides some advices.