Quantum Computer Algorithms: Part 3 - DES Decryption
by Dave D'Rave
Earlier in this series, we discussed oracle-type quantum algorithms.
In this article, we look at using an oracle algorithm to perform a known-plaintext attack on the DES block cipher systems. (DES is a well-known crypto system. Wikipedia has several articles on it.)
Mainstream block cipher systems, such as DES or AES, break long messages up into fixed-size chunks and then encrypt each block individually. The usual procedure is that the first block is encoded with the main key, and that all subsequent blocks are encoded using an incrementing key, or some combination of the previous blocks (block chaining). The situation is that if you can break the first block and recover the key, then you can break the entire message with very little additional effort.
Known Plaintext Attack
It often happens that we have intercepted the ciphertext and we have also obtained the plaintext. This is sometimes as simple as knowing that the message always starts with a date. The history of cryptography is full of examples of how plaintext was acquired.
The central idea is that, once you have known plaintext, you can build an oracle which accepts a key, the ciphertext, and the plaintext, and which outputs a single bit. The output is |1> if the input ciphertext decoded by the key is equal to the plaintext, and |0> otherwise.
For example, the DES block cipher uses 64-bit text blocks and a 56-bit key. The "good plaintext" oracle for DES accepts the 184 bits of input and outputs one bit.
The DES Oracle
The DES oracle is made of smaller blocks.
These are the decrypt block, the inverse decrypt block, and the compare block. The inverse decrypt block (f-1) is used to prevent noise errors from back-propagating into the output. Current technology requires that we use this block.
The decrypt block accepts a 64-bit ciphertext input and a 56-bit key input. It produces a 64-bit trial plaintext output. The compare block accepts a 64-bit trial plaintext input and a 64-bit known plaintext input. It produces a single bit output, which drives the output CNOT.
Note that the ciphertext and known plaintext are classical data, while the key, the trial plaintext, and the output are qubit data. If you provide a superposition as the key input, then the output will often be a superposition.
This fact is useful.
f(Ciphertext): The Quantum DES Decrypt Block
The algorithm for DES is widely available.
It is usually written in C, and is usually implemented as some mixture of for() loops and table lookups. The usual procedure is to first "unroll" the loops, which is a standard computer science operation, and then test that the algorithm still works.
Next, either run the unrolled version of the decryption algorithm through your quantum compiler, or run it through a convert-to-Qiskit program. At that point, you should have working code, and can run it when a suitable quantum computer becomes available. In the year 2029...
The unrolled algorithm for DES has 16 rounds of bit scrambling. Each round takes some function of the 64-bit intermediate ciphertext and some bit function of the key and then performs an exclusive-OR. This requires something like 120 two-input quantum gates to make up the key function and text function, along with something like another 64 gates for the actual XOR. Note that XOR is implemented by the quantum gate operator CNOT.
As a practical matter, you will need support gates and ancillae, so each round is going to cost maybe 250 gates. Given that we need 16 rounds, this is going to be 4000 gates. Because of phase noise effects, a practical system also needs an inverse DES block. The total adds up to 8000 gates.
The DES Decrypt Block, in Detail
The DES block consists of 16 sub-blocks called rounds.
The traditional (1970s) implementation uses the same code for each round, and customizes their behavior using what are called "subkeys." At this time, a quantum algorithm probably will use 16 slightly different rounds in order to reduce the total number of quantum gates which are needed.
Optimization methods, which hopefully speed things up, are discussed below.
(The technical reasons for this procedure involve the fact that early DES implementations used either 8-bit microprocessors or dedicated LSI hardware. The obvious way to do the software was to pre-compute the subkeys and then use 16 identical rounds, each with a different subkey. The obvious way to build a DES chip was to only have one round implementation and use it multiple times, with slightly different control inputs. In the quantum world, memory devices are a source of error. A straight pass-through design uses more gates but less memory, so it is preferred.)
The Inverse DES decrypt block is the same thing, except in reverse.
The Compare Block
The 64-bit compare consists of 64 one-bit compare operations followed by a large AND gate.
Each of the input bit pairs is individually compared, starting with the bit 0 pair and moving to the bit 63 pair. The AND gate is implemented as a 64-controlled NOT gate.
Because the 64-input CNOT gate is likely to be implemented as a funnel of two-input CNOT gates, the total compare block consumes a rather large amount of gate resources.
Superposition and Parallel Processing
In order to achieve substantial speed improvements, quantum computers use superposition.
For example, we could provide a key value of |all keys whose high-order 48-bits are zero> as inputs to a quantum DES algorithm. This input set contains a superposition of 256 keys.
If none of the keys provide a valid decode of the cyphertext, then the output will be a pure |0> state.
If one (and only one) of the keys is valid, then the output will be approximately k * (16*|0> + |1>).
As a practical matter, amplitude amplification methods are then used to produce a clean |0> or |1> output.
Depending on the noise characteristics of the quantum computer hardware, some kind of bisection algorithm or subset algorithm will be used to pick off the value of the individual key bits. Ideally, this is done one bit at a time, which means that 56 iterations of the DES algorithm will be needed to break a given message.
Tech Notes: Optimization Methods
All of the better quantum compilers include obvious optimizations, such as |X|X| equals |I|, or "if you see two NOT operators, remove them both."
This particular algorithm has a number of places where a quantum gate has two inputs and one of the inputs is known to be classical data. It is often the case that one or more gates can be removed, or that a two-input gate can be replaced by a one-input gate.
Example: Compare a qubit with another qubit bit, fully quantum:
Example: Compare a qubit with a 0 bit, semi-classical:
Note that both kinds of Compare output a quantum value. If the input was k (|0> + |1>), then a compare_with_zero operator will produce a superposition output.
The data comparison (or the logical comparison) is not the same as "Is this superposition state the same as that superposition state?"
To do that is more complicated. When doing a full phase comparison, the entanglement value matters.