Reversing cryptographic primitives using quantum computing

Topics: quantum computing, cryptography security

Synopsis: In the last year there were several advances in practical quantum computing: now there are free quantum chips available on the cloud for everyone, and the largest quantum chips exceeds 50 qubits, a number called "the quantum supremacy" because theoretically a quantum chip exceeds the power of a classical computer. We'll explain how to program a quantum chips and give the results of our research regarding reversing some cryptographic building blocks like P-Box, S-Box, CRC-8 and XOR functions using quantum circuits. We'll see the implementations and run some circuits on real hardware to see how near we are from attacking real cryptography.

Transcript

1. Reversing cryptographic primitives using quantum computing Renaud Lifchitz, Econocom digital.security Black Alps, Switzerland, November, 8-9 2018
2. 2 Outline (1/2) Quantum computing basics Principles Simple quantum gates Challenges Quantum computing simulators Overview of public quantum cloud computing services
3. 3 Outline (2/2) Quantum computing & cryptography P-Box modeling & implementation 2 ways to reverse a cryptographic primitive CRC-8 modeling & optimal implementation AES (Rijndael’s) S-box modeling & implementation Reversing XOR encryption using an oracle Quantum threats against current cryptography Post-quantum cryptography
4. 4 Speaker’s bio • French security expert @ Econocom digital.security • Main activities: • Penetration testing & security audits • Security research • Security trainings • Main interests: • Security of protocols (authentication, cryptography, information leakage, zero-knowledge proofs...) • Number theory (integer factorization, primality testing, elliptic curves...)
5. Quantum computing basics
6. Principles
7. 7 Qubit representations (1/2) • Constant qubits 0 and 1 are represented as |0 and |1 • They form a 2-dimension basis, e.g. |0 = 1 0 and |1 = 0 1 • An arbitrary qubit q is a linear superposition of the basis states: |q = α|0 + β|1 = α β where α ∈ C, β ∈ C • When q is measured, the real probability that its state is measured as |0 is |α|2 so |α|2 + |β|2 = 1 • Combination of qubits forms a quantum register and can be done using the tensor product: |10 = |1 ⊗ |0 =   0 0 1 0   • First qubit of a combination is usually the most significant qubit of the quantum register
8. 8 Qubit representations (2/2) Bloch sphere: a qubit can also be viewed as a unit vector within a sphere - 3 angles (2 angles and a phase)
9. 9 Basics of quantum gates • For thermodynamic reasons, a quantum gate must be reversible • It follows that quantum gates have the same number of inputs and outputs • A n-qubit quantum gate can be represented by a 2nx2n unitary matrix • Applying a quantum gate to a qubit can be computed by multiplying the qubit vector by the operator matrix on the left • Combination of quantum gates can be computed using the matrix product of their operator matrix • In theory, quantum gates don’t use any energy nor give off any heat
10. Simple quantum gates
11. 11 Pauli-X gate Pauli-X gate Number of qubits: 1 Symbol: Description: Quantum equivalent of a NOT gate. Rotates qubit around the X-axis by Π radians. X.X = I. Operator matrix: X = 0 1 1 0
12. 12 Hadamard gate Hadamard gate Number of qubits: 1 Symbol: Description: Mixes qubit into an equal superposition of |0 and |1 . Operator matrix: H = 1 √ 2 1 1 1 −1
13. 13 Hadamard gate • The Hadamard gate is a special transform mapping the qubit-basis states |0 and |1 to two superposition states with “50/50” weight of the computational basis states |0 and |1 : H.|0 = 1 √ 2 |0 + 1 √ 2 |1 H.|1 = 1 √ 2 |0 − 1 √ 2 |1 • For this reason, it is widely used for the first step of a quantum algorithm to work on all possible input values in parallel
14. 14 CNOT gate CNOT gate Number of qubits: 2 Symbol: Description: Controlled NOT gate. First qubit is control qubit, second is target qubit. Leaves control qubit unchanged and flips target qubit if control qubit is true. Operator matrix: CNOT =      1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0     
15. 15 SWAP gate SWAP gate Number of qubits: 2 Symbol: Description: Swaps the 2 input qubits. Operator matrix: SWAP =      1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1     
16. 16 Universal gates A set of quantum gates is called universal if any classical logic operation can be made with only this set of gates. Examples of universal sets of gates: • Hadamard gate, Phase shift gate (with θ = Π 4 and θ = Π 2 ) and Controlled NOT gate • Toffoli gate only
17. Challenges
18. 18 Challenges (1/2) • Qubits and qubit registers cannot be independently copied in any way • In simulation like in reality, number of used qubits must be limited (qubit reuse wherever possible) • Qubit registers shifts are costly, moving gates “reading heads” is somehow easier • In reality, quantum error codes should be used to avoid partial decoherence during computation
19. 19 Challenges (2/2) For serious purposes we need: • A high number of qubits (about 50 qubits is enough for quantum supremacy) • A good qubit and gate fidelity (low-error rate) • Optionally, error correction High number of qubits is not the most important, most algorithms are limited by circuit depth (≈ 20-30 gates) because of qubit and gate fidelity.
20. Quantum computing simulators
21. 21 Quantum Inspire https://www.quantum-inspire.com/
22. 22 Quirk http://algassert.com/quirk
23. 23 Quantum Circuit Simulator (Android) Design and simulation of a qubit entanglement circuit https://play.google.com/store/apps/details?id=mert.qcs
24. 24 Quantum computing simulators A longer list: https://quantiki.org/wiki/list-qc-simulators
25. Overview of public quantum cloud computing services
26. 26 Public quantum cloud computing services • Bristol University “Quantum in the Cloud” (http://www.bristol.ac.uk/physics/research/quantum/ engagement/qcloud/): up to 2-3 qubits • Alibaba Quantum Computing Cloud Service (http://quantumcomputer.ac.cn): up to 11 qubits • IBM “Q Experience” (https://www.research.ibm.com/ibm-q/technology/devices/): up to 14 qubits, 20 qubits for private clients • Rigetti “Quantum Cloud Services” (https://www.rigetti.com/qpu): up to 19 qubits, 128 qubits to come • D-Wave “Leap” (https://cloud.dwavesys.com/leap/): up to 1000 qubits, adiabatic quantum chip, not universal, mainly for optimization problems
27. Quantum computing & cryptography
28. P-Box modeling & implementation
29. 29 Modeling permutations and their reverse Modeling a complex permutation and its reverse requires: • Decomposing the permutation in single (two-elements) permutations • Implementing it using several SWAP gates • Converting SWAP gates to CNOT gates for practical reasons • Inverting the whole circuit (most gates are their own inverse!) • Simplifying the circuit
30. 2 ways to reverse a cryptographic primitive
31. 31 2 ways to reverse a cryptographic primitive • Implement a reversible circuit and execute it in the reverse way. Problems: • Function is not often reversible, solutions: embed function (add input bits as output bits and various other simple techniques) • Ancilla qubits are often numerous (but efficient if they are in minority) • Grover oracle: implement the primitive in the direct way and query a Grover oracle (specific quantum-only algorithm) to find the correct input
32. CRC-8 modeling & optimal implementation
33. 33 Reverse CRC-8 modeling: the steps • Naive CRC-8 implementation (moving “reading heads” to shift qubits) using ancilla qubits • Simplify if possible • Compute the CRC-8 truth table • Use a reversible computation framework to find a (optimum) circuit
34. 34 CRC-8: a nearly naive implementation A quantum CRC-8 circuit with only CNOT gates
35. 35 revkit: a useful framework for reversible computation • Interesting framework for reversible & quantum circuits • Takes various kinds of inputs (truth tables, circuits, boolean functions) • Has different synthesis & optimization strategies • Able to embed non-reversible functions into reversible ones • Sometimes able to find optimum circuits (if not too big) • https://msoeken.github.io/revkit.html
36. 36 Reverse-CRC-8 optimal implementation (1/2) Our optimal reverse-CRC-8 circuit instructions using Quantum Inspire
37. 37 Reverse-CRC-8 optimal implementation (2/2) Optimal circuit visualized using Quantum Inspire
38. 38 Reversing a single CRC-8 using quantum computing (1/4) Quantum simulation without noise using Quantum Inspire
39. 39 Reversing a single CRC-8 using quantum computing (2/4) Quantum simulation with typical noise using Quantum Inspire
40. 40 Reversing a single CRC-8 using quantum computing (3/4) Reversing a single CRC-8 on real quantum hardware (program, IBM Q 14 Melbourne)
41. 41 Reversing a single CRC-8 using quantum computing (4/4) Reversing a single CRC-8 on real quantum hardware (results, IBM Q 14 Melbourne)
42. 42 Reversing multiple CRC-8s with fixed and unfixed bits Quantum simulation & results using Quirk: fixed null bits have been found in the input for 8 different outputs! (https://tinyurl.com/rcrc8multi)
43. AES (Rijndael’s) S-box modeling & implementation
44. 44 AES S-Box implementation Source: Wikipedia
45. 45 Reverse AES S-Box implementation Our reverse AES S-Box circuit with 281 Pauli-X, CNOT and Toffoli gates (optimal circuit requires at least 14 gates)
46. Reversing XOR encryption using an oracle
47. 47 Reversing XOR encryption using an oracle • Idea: for a given key size, implement a direct XOR encryption and find the candidate keys by minimizing the bytes MSBs (for ASCII text encryption)
48. Quantum threats against current cryptography
49. 49 Quantum threats against symmetric cryptography Main threat is Grover algorithm: • Pure quantum algorithm for searching among N unsorted values • Complexity: O( √ N) operations and O(log N) storage place • Probabilistic, iterating and optimal algorithm Defense: doubling all symmetric key sizes is enough to be out of reach from quantum attacks
50. 50 Quantum threats against asymmetric cryptography Main threat is Shor algorithm: • Pure quantum algorithm for integer factorization that runs in polynomial time formulated in 1994 • Complexity: O((log N)3) operations and storage place • Probabilistic algorithm that basically finds the period of the sequence ak mod N and non-trivial square roots of unity mod N • Uses QFT, some steps are performed on a classical computer • Breaks RSA, DSA, ECDSA, ECDLP efficiently Defense: use a PQC alorithm
51. Post-quantum cryptography
52. 52 Progress in number of qubits (1/2)
53. 53 Progress in number of qubits (2/2) 2000 2005 2010 2015 2020 0 50 100 Year # qubits available (universal quantum chip) Looks like a Moore law...
54. 54 Quantum Resistant Cryptography Currently there are 6 main different approaches: • Lattice-based cryptography • Multivariate cryptography • Hash-based cryptography • Code-based cryptography • Supersingular Elliptic Curve Isogeny cryptography • Symmetric Key Quantum Resistance Annual event about PQC: PQCrypto conference (https://twitter.com/pqcryptoconf, 10th edition in 2019)
55. 55 Quantum Resistant Cryptography Very few asymmetric PQ algorithms, the most well-known is NTRU, a lattice-based shortest vector problem: • NTRUEncrypt for encryption (1996) • NTRUSign for digital signature https://www.onboardsecurity.com/products/ntru-crypto
56. 56 Thank you! Questions? info@digital.security