POST-QUANTUM CRYPTOGRAPHY AND THE FUTURE OF IOT IN QUANTUM COMPUTING ERA
Cothan <[email protected]>
ABOUT ME
- 4th-year Ph.D. Student in Applied Post-Quantum Cryptography
-
CTF Player, NSUCrypto winner
-
Hardware Engineer
-
Code Reverser, Crypto Engineer
-
Highly proficient Hardware Architecture: ARM, Intel
-
Enjoy writing high performance SIMD code
-
Enjoy watching people trial by combat
The Threat of Quantum Computing
Superposition In Quantum Computing
- As you may know, there are 2 states |1> and |0> happen at the same time
- For short, 10 classical bits are approximately equivalent to 5 qubits.
- We can think of it on a large scale: 64 qubits is equivalent to 128 classical bits.
Entanglement In Quantum Computing
An effect over a single in quantum bit can propagate through entire array.
Threat of Quantum Algorithm over RSA, ECC cryptography
- Integer factorization
- Discrete log in finite field
- Discrete log on elliptic field
Quantum Computer can solve in polynomial time:
Threat of Quantum Algorithm over RSA, ECC cryptography
- Integer factorization
- Discrete log in finite field
- Discrete log on elliptic field
Quantum Computer can solve in polynomial time:
Threat of Quantum Algorithm over RSA, ECC cryptography
- Integer factorization
- Discrete log in finite field
- Discrete log on elliptic field
Quantum Computer can solve in polynomial time:
=> RSA is dead
=> DSA, Elgamal are dead
=> ECC is dead
- Frankly, algorithm for factorization and discrete logarithm can be solved in a similar fashion.
Both can be solved in polynomial time on a quantum computer.
Threat of Quantum Algorithm over Symmetric Cryptography
Grover's algorithm can thwart classical security bit by a half
-
AES-128 is only 64 security bits in quantum computer. Thus, AES-192 is only 96 quantum security bit.
-
SHA0, SHA1 are dead, SHA2 suffer length extension attack due to its Merkle–Damgård structure, SHA3-224 is insecure in quantum era.
-
SHA3-256, SHA3-384, SHA3-512 (published in 2015) are not widely deployed yet.
Need to invalidate AES-128, AES-192 in the government sector. Move to AES-256, deploy SHA3 as soon as possible.
"Quantum Supremacy" may not happen now, but it's expected
"Quantum Supremacy" may not happen now, but it's expected
-
IBM quantum scientists are building a quantum computer with a 1,121-qubit processor, called Condor, inside a large dilution "super-fridge"
-
Condor lays the groundwork for scaling to fully error-corrected, interconnected, 1-million-plus-qubit quantum computers.
-
In 2021, IBM will debut the 127-qubit "Eagle" chip.
-
Eagle will be followed by the 433-qubit "Osprey" processor in 2022
-
These advances are necessary to establish a Quantum Industry: fabrication, cryogenic, and electronics, software capabilities, error-correction coding.
Situation before 2024
- NIST (National Institute of Standards and Technology) is currently in the process of standardizing a quantum-safe public key encryption system which will be completed by 2024.
- The NSA has followed suit by announcing its CNSA Encryption Suite which is meant to be a transitionary encryption standard quantum-safe encryption becomes standardized.
- The NSA has withdrawn its support of AES-128 and AES-192 as cryptographically secure long-term encryption schemes because of quantum computing
Introduction to Post-Quantum Cryptography
Introduction to Post-Quantum Cryptography
Post-Quantum Cryptography (Mật mã hậu lượng tử):
- Public key cryptography that run on classical computer
- Based on hard cryptography problem that cannot be solved efficiently by quantum computer
NOTE: KEM is Key Encapsulate Mechanism
Lattice-based Cryptography
Lattice-based Cryptography
Security problem relied on Shortest/Closest Vector Problem
NIST finalist KEM selection:
- CRYSTAL-Kyber
- SABER
- NTRU
NIST finalist Signature selection:
- Falcon
- CRYSTAL-Dilithium
Code-based Cryptography
Security problem relied in syndrome decoding
NIST finalist KEM selection:
- Classic McEliece
NIST finalist Signature selection:
- No Code-based submission in Signature category.
- Due to ridiculous signature size. (hundred of Mb)
Only suitable for KEM.
Multivariate Cryptography
Security problem relied in solving multivariate equations.
NIST finalist KEM selection:
-
No Multivate submission in KEM category.
NIST finalist Signature selection:
-
Rainbow
Only suitable for Signature
Isogeny-based Cryptography
Security problem relied on pseudo-random walks in supersingular isogeny graphs.
NIST finalist Signature selection:
- SIKE
It's only advantage is small public keysize.
Horribly slow.
Unacceptable speed in IoT device e.g: Cortex-M4
Hash-based Cryptography
Security problem relied on hash security.
NIST alternative Signature selection:
-
SPHINCS+
It's only advantage is re-use native hash instruction set in modern CPU.
Horribly slow.
Vulnerable to side-channel attack, signature can be forge at very small computation cost
PQC standardization timeline
2016: NIST called for proposal
2017: Round 1 began: 69 submissions
2018: First Experiment PQC in TLS
2019: Round 2 began: 26 candidates survived
2020: Round 3 began: 7 Finalist / 8 Alternates
Real-world Cryptography
1996: SSLv3
1999: TLS 1.0
2006: TLS 1.1
2008: TLS 1.2
2018: TLS 1.3. Adam Langley experimented on Chrome. It's shown that even though Lattice keysize is bigger, overall performance of lattice crypto is faster than isogenies
2020: Cloudflare experiments with Lattice and Isogeny, Isogeny has higher latency than Lattice.
TLS Post-Quantum Crypto Performance
2020 Cloudflare experiments
Lattice size: 1138 bytes
Isogeny size: 676 bytes
Public key + Ciphertext size
2020 Cloudflare experiments
- Isogeny has smaller keysize, but in practice, latency is higher than lattice
- Lattice-based with 2 times bigger in keysize, the latency is somewhat unnoticeable compare to current public cryptography
TLS Post-Quantum Crypto Experiment
- Big win to lattice
- Key size is a not a big deal
- Moore's Law is kinda stopped, we can't rely on hardware to do the hard work for us.
-
The overall Internet speed is faster.
Keysize versus computing speed is similar to Internet speed vs Moore's Law
You know which one is growing faster... :)
IoT device Post-Quantum Crypto Performance
Challenges:
-
Key size may not fit in RAM. <= Stack size
-
Too slow due to complication algorithm. <= Speed
-
Power consumption is a big concern. <= Energy
-
Bandwidth is limited. <= Key size
Benchmarking Speed of PQC KEM on ARM Cortex-M4
Benchmarking Speed of PQC KEM on ARM Cortex-M4
Benchmarking Speed of PQC KEM on ARM Cortex-M4
Benchmarking Speed of PQC Signature on ARM Cortex-M4
Keysize of PQC Signature
| Sign | Verify | |
|---|---|---|
| dilithium2 | 1184 | 2044 |
| falcon512 | 897 | 617 |
| SIKEp434 | 330 | 346 |
| Sign | Verify | |
|---|---|---|
| dilithium4 | 1760 | 3366 |
| falcon1024 | 1793 | 1233 |
| SIKEp751 | 564 | 596 |
Level 1
Level 3
Keysize of PQC KEM
| Public key | Ciphertext | |
|---|---|---|
| LightSaber | 672 | 736 |
| Kyber512 | 800 | 736 |
| Public key | Ciphertext | |
|---|---|---|
| Saber | 992 | 1088 |
| Kyber768 | 1184 | 1088 |
Level 1
Level 3
| Public key | Ciphertext | |
|---|---|---|
| FireSaber | 1312 | 1472 |
| Kyber1024 | 1568 | 1568 |
Level 5
Predict Future IoT
KEM
- SABER, Kyber: Good overall
- NTRU: Keygen is expensive
Signature
- Falcon: Slow
- SIKE: Small keysize, even slower than Falcon
- Dilithium: Good overall
Post-Quantum Crypto in WireGuard VPN
WireGuard is simple and fastest VPN at the moment, simple design.
Post-Quantum Crypto in WireGuard VPN
Wanna see how Post-Quantum Cryptography can perform in the fastest VPN ?
The key to observe here:
- Is the speed become faster or slower?
- Is the latency, keysize make a huge difference ?
Post-Quantum Crypto in WireGuard VPN
| VPN Software | Packet Number | Traffic (bytes) | Client time (ms) | Server Time (ms) |
|---|---|---|---|---|
| WireGuard | 2 | 324 | 0.572 | 0.005 |
| PQ-WireGuard | 2 | 2492 | 0.573 | 0.027 |
| OpenVPN (NIST P-256) | 19 | 5408 | 242.014 | 253.582 |
| OpenVPN (RSA-2048) | 21 | 7535 | 244.288 | 251.304 |
It is simple to draw conclusion, isn't it?
Post-Quantum Crypto in FPGA
Post-Quantum Crypto in FPGA
Performance in FPGA is important, simply because it answers these research questions
- Given the freedom to implement an algorithm, how fast can it be?
- Given reasonable number of LUT, DSP, FF, how fast can it still be?
- Given a tight resource for IoT, how slow and energy-efficient can it be?
At some point in the near future, given crypto algorithm,
it will have Hardware Accelerator, or
Hardware Security Module, or
become a critical component for Crypto Networking Card, etc...
Post-Quantum Crypto ARM NEON vs. FPGA
Post-Quantum Crypto ARM NEON vs. FPGA
Post-Quantum Crypto ARM NEON vs. FPGA
The result shows that FPGA can outperform Cortex-A53 1200 Mhz. Although FPGA run at slower clock ratio 322 Mhz, but still, faster.
- Hit the limit of NEON implementation.
- There are a lot of rooms for improvement in FPGA
- Again, definitely faster and smaller footprint than RSA, ECC.
- FPGA results shows that PQC is highly proficient in Crypto Networking Card, Hardware Security Module, Hardware Accelerator
Post-Quantum Crypto ARM NEON vs. FPGA
The result shows that FPGA can outperformCortex-A53 1200 Mhz. Although FPGA run at slower clock ratio 322 Mhz, but still, faster.
- Hit the limit of NEON implementation.
- There are a lot of rooms for improvement in FPGA
- Again, definitely faster and smaller footprint than RSA, ECC.
- FPGA results shows that PQC is highly proficient in Crypto Networking Card, Hardware Security Module, Hardware Accelerator
Challenge In Implementation of FPGA, IoT, CPU
Challenge Implementating PQC on FPGA, IoT, CPU
It must be Side-channel resistance!
- FPGA is vulnerable to side-channel
- IoT device is vulnerable to power-analysis.
- CPU is vulnerable at its core, CPU architecture: Meltdown, Spectre, Spectre variants.
Still, open problems in research community
A look into the future
RSA and ECC security in Quantum Computing Era
RSA-512 publicly broken: "Let's use RSA-768"
RSA-768 publicly broken: "Let's use RSA-1024"
RSA-2048 publicly broken by quantum computers: "Okay, let's use RSA-3072"
Future: "Still use RSA"
RSA and ECC security in Quantum Computing Era
Keysize must be increased
| Keysize | |
|---|---|
| Key | 1 Gb |
| Signature | ~1 Gb |
| KEM Ciphertext | 1 Gb |
| Encrypt Ciphertext | 1 Gb |
RSA and ECC security in Quantum Computing Era
| Keygen | Decrypt | Encrypt | |
|---|---|---|---|
| pqrsa15 | 10.5h | 22m | 3m |
| pqrsa20 | 11h | 35m | 6m |
| pqrsa25 | 2.2d | 1.5h | 8m |
| pqrsa30 | 2.3d | 2.1h | 10m |
Computational time must be increased too
Public exponent e = 3
Are lattice-based Crypto Quantum Safe ?
Is lattice-based Crypto Quantum Safe ?
Classical aspects:
- Heuristic Sieve Algorithm is well-known lattice-based crypto attack
- No one can answer why the result of the heuristic search is improving every year.
- Can be run massively in parallel. GPU, FPGA, ASIC really good at parallel algorithms.
Is lattice-based Crypto Quantum Safe ?
- 2010 - Dimension n= 112 is broken. [Sieving]
- 2011 - Dimension n= 120 is broken. [Sieving]
- 2013 - Dimension n= 130 is broken. [Sieving]
- 2014 - Dimension n= 138 is broken. [Sieving]
- 2017 - Dimension n = 150 is broken. [Sieving]
- 2018 - Dimension 150 < n < 155 is broken. [Sieving]
- 2019 - Dimension n = 157 is broken. [Sieving]
- 2020 - Dimension n = 170 is broken. [Sieving]
Is lattice-based Crypto Quantum Safe ?
No.
Shor's algorithm doesn't apply here, but Grover's quantum search is too strong..
- Sieving is improving each year....
- Remember, attacks always get better
Is Elliptic Curve Crypto Quantum Safe?
No.
- From 2017 to 2020, within 3 years, the resources of Quantum Circuit Depth is reduced from to , T-Gates reduce from to for 256-bit modulus.
- Still, far from practical deployment but the results are expected to be improved over years.
Reference
Quantum Computer
