Real World Crypto 2021 - Session 6: Post-Quantum Cryptography
RWC2021 · Real World Crypto
Session video
Daniel Apon (NIST) / James Howe (PQShield) / Attacks on NIST PQC 3rd Round Candidates / paper video / slides
The full study attempted all of:
- classical cryptanalysis
- static timing analysis
- fault attacks (try to drive the algorithm into revealing internal details by pushing it into a fault state)
- simple power attacks
- advanced (differential/correlation) power analysis
- electromagnetic attacks
- template attacks
- cold-boot attacks
- whether countermeasures exist
For lattice-based approaches, do any of the attacks enable lattice reduction to be made possible/easier?
Some finalists in the 3rd round are so similar that success will probably depend on their resistance to particular side-channels.
There’s a ‘QuantumHammer’ attack which sounds cool.
They expect implementation complexity to be considerably greater than non-PQ algorithms which will make weaknesses more likely to occur. Some algos will just not be small/light enough for small devices such as smartcards.
Another call for businesses to start considering their transition to PQC and consider the possible impact of the types of attacks being studied.
Hannah Davis (UCSD) / Separate Your Domains: NIST PQC KEMs and Pitfalls in Implementing Random Oracles / paper video
KEM = Key Encapsulation Mechanism
One KEM algo, ‘DAGS’, leaked half of its session key into ciphertext! Half the key bits were directly present in the c/t. DAGS didn’t pass round 1, but this particular attack was not the reason, and was not spotted
This was a common mistake on behalf of developers: An algo calls for 3 –distinct– hash functions H1, H2, H3 – but the developer set all three to be SHA3. Then, their outputs were correlated and so not independent as required.
This gives rise to a problem called ‘Oracle Cloning’ It’s reasonable to only want to use a single hash function, but you want to use it to derive three hash functions that are indeed independent of each other. That can be done by domain separation, where Hi(X) = H(i || X), and separate ‘i’ for each. It’s enough for i to be a single byte.
They analysed the various NIST KEMs to identify the different ways that designers end up oracle cloning. They classified the various methods, to define safe ways of oracle cloning.
When finalized PQC algos are standardized, there’s the likelihood of lots of impls in different crypto libraries, and if inexperienced devs do that then guidance on safe ways to do oracle cloning is important.
Toolbox of good oracle cloning methods:
- Output splitting - take non-overlapping bit ranges from the parent H for H1, H2, H3
- Prefix with domain separators - as shown above
- Identity/Length separation - do use the same H func for H1,2,3 but ensure it is never called on identical input
Joppe Bos (NXP) / Post-Quantum Crypto: The Embedded Challenge / video slides
You must prepare yourself for coming PQC standards, whether you happen to believe that Quantum Computers will be a thing or not.
There are many embedded devices:
- 70% cars will be connected by ‘25
- 6B IoT units in 2021, 12B expected 2025
- 60B mobile devices by 2025
Use cases:
- Digital Sigs for industrial and IoT applications
- it’d be a good idea for these to be Q-resistant for secure boot
- for automative it’d be good for OTA updates to be Q-resistant
- Key Exchange - for Industrial / IoT - the “secure element” better be Q-resistant
He studied performance of various lattice algs on Cortex M4 and found it largely as fast as X25519 classical. However : memory usage much higher (ca 20kB vs 1or2kB for 25519); also key sizes much higher. This is problematic for embedded devices, where needing >4kB stack can present challenges
How can industry prepare?
- move to stateful-hash signature schemes - can be done now
- track NIST’s standardization for KEM and digital signatures - in the longer term