Quantum search for passwords bruteforcing part 1

Using AWS Quantum Computing, I would like to share a proof-of-concept for bruteforcing passwords pertaining to a certain class of two factor authentication (2FA). Practical examples of immediate use for the cybersecurity community are rare, so I think this technique could help readers to understand the basis of QC and motivate them to explore this mostly untamed continent.

The quantum search algorithm that I'm going to explain, based on random walks, is much less efficient than standard recursive search algorithms but similar in speed to a classical random search. So don't expect any breakthrough here, this proof of concept is shared for educational use in a context that will make sense for IT Security engineers. This is the expectation, at least.

There's a lot of things to discuss so I will break the presentation in two parts: part 1 here will introduce the necessary building blocks, part 2 will detail the proof-of-concept.

Problem statement

Imagine we have a blank crossword made of n lines and n columns (the crossword is a square). We pick a white cell and elect it as the "starting position" S. From S, we will try to follow a random walk of p contiguous steps, but we are only allowed to step on white cells. Our walk is performed modulo n.

There are two notable kinds of random walks:

• Brownian motion: these are completely random walks. There are 4**p of them at any starting position (modulo n).
• self-avoiding walks: these random walks have an additional constraint: they never cross their path. There are about 2.85**p of them at any starting position when n is large, modulo n.

But we have one additional constraint to bear in mind: not all random walks are eligible! Only the ones stepping exclusively on white cells.

Now with a classical computer, up to a certain p we can easily solve the problem using a recursive approach like we would in a game of Chess. Alternatively, we can run a supervised Monte Carlo simulation. The latter is not very efficient but it lends itself very well to a quantum search so we’ll pick this one for our proof-of-concept.

In the context of generating random walks, a Monte Carlo simulation is nothing more than throwing dice to determine where we shall go from any given position on to the next. If we have a binary die made of two bits, we could say for example that '00' means go north, '11' go south, '01' go west and '10' go east.

Let's take an example with n=5 and p=2. Starting at position S and only white cells, there are 16 Brownian walks and 12 self-avoiding walks. Since there are no black cells, we can immediately roll two dice: one for the first move, the other to the second and final move.

The first move will always take us to a blue cell. The second one will take us either to an orange cell, to a green cell, or back to S. Since there are two ways to end a walk on an orange cell but only one way to end a walk on a green cell, it is a simple matter to verify that there are 12 self-avoiding paths indeed.

What I called above a supervised simulation is the same, but we take into account some information that will limit motion to a subset of potential moves. A crossword's black cells are a good example of information we can leverage: if we know where the black cells are, we can throw the dice to pick only passable (white) cells and avoid the unpassable (black) cells.

Let's imagine we start at center position S of this crossword:

The only possible 2-steps self-avoiding walks are: NN,NW,WW,WN,EE,NE,EN.

Time to implement our search algorithm with AWS Braket!

Overview of quantum computers

Quantum computing has been rolled out for everyone to enjoy as a service in AWS for a little more than a year now[*]. It comes with a very handy python SDK that we're going to use to build our proof of concept of quantum search.

Don't think a quantum computer is just an array of qubits. An illustration is better than a thousand words, so let's pick this simple picture taken from Marek Perkowski's wonderful keynote at reversible computing 2020:

The quantum mechanics area depicted above allows states manipulation through a number of reversible logic gates.

The special controller is not least important than the quantum part: it will let us tie the quantum state to some real life, problem specific data. As far as we are concerned, the real life information we're going to use are black cells locations.

To implement our random walk in AWS Braket with p=2 and n=5, we’re going to use 4 qubits: two for rolling a binary die to locate our first move, two for rolling a second die to locate our second and last move.

Making a 4 qubits quantum search

We'll proceed straightforwardly by following and extending the 3 qubits design set out in a complete 3-qubit Grover search on a programmable quantum computer.

From this article, here is the complete 3-qubits layout for finding solution |0111>+|101>. Take special notice of the oracle and amplification stages:

These two stages are essentially what we need to extend.

Oracle stage

We can obtain a 4-qubits Oracle able to find solution |0011>+|1011>+|0101>+|1101> by simply inserting a fourth qubit on the top of the scheme.

Here is how we do this: in AWS Braket, the original 3-qubits Oracle for |011>+|101> in the picture above is:

someCircuit.cz(0,2).cz(1,2)

Adding an extra qubit (in bold) to the 3-qubits Oracle to get |0011>+|1011>+|0101>+|1101> is very easy, we simply shift the qubits by one:

someCircuit.cz(1,3).cz(2,3)

Amplification stage

We just need to replace the 3-qubits CCZ gate with a 4-qubits one (let's call it CCCZ).

Tying the quantum computer to problem specific data

Using the power of AWS Braket SDK, the idea is to write a subroutine that will generate the proper Grover search pattern depending on local crossword constraints.

For example, let's pick our previously mentioned crossword:

We will now group the 7 possible paths NN,NW,WW,WN,EE,NE,EN in two families of 4 paths. We need an even number of paths for that, so let's introduce an eighth artificial but valid Brownian path: EW.

The 8 paths are then grouped as such: NN,NW,WW,WN and EE,EW,NW,NE.

Translated into bits, the first family is 0000,0001,0101,0100. It corresponds to state |0000>+|0001>+|0101>+|0100>, while the second family corresponds to state |1010>+|1001>+|0001>+|0010>.

Since we have carefully crafted the families, it's no surprise that both state match a four-solution oracle. The oracles are:

someCircuit.z(2).z(3).cz(1,2).cz(1,3)

and

someCircuit.z(0).z(2).cz(0,2) respectively.

When such a crossword is encountered at starting position (x,y), all our subroutine has to do is append both oracles to generate the proper circuit:

Then, unsurprisingly, rolling 2 dice (2x2qubits) will very often yield one of the eight expected paths.

Let's check it out with an actual sample run of 1000 measurements and only one round of amplification:

{'0100': 157, '0101': 142, '1001': 140, '1010': 136, '0010': 134, '0000': 129, '0001': 21, '1111': 21, '1000': 18, '0011': 18, '1011': 17, '1110': 16, '0111': 15, '0110': 14, '1100': 13, '1101': 9}

6 out of 7 eligible paths are over-represented as expected: WN,WW,EW,EE,NE,NN. Note that 1 is under-expressed: NW. This bias must be due to the way circuits combination is done, I haven't thought of the actual root cause nor of a fix[**] and probably will never, but I think it's good enough as an illustration.

Conclusion

We have managed to design a decently reliable quantum equivalent of a classical supervised Monte-Carlo simulation for finding self-avoiding paths of length 2.

This first installment was the most difficult, if you've managed to read on until here, then you're all good for part 2!

In part 2, I will show how all this seemingly complex but actually very basic machinery can be called into action to work on some concrete passwords bruteforcing use case.

Notes

[*]: AWS Braket was announced in August 2020. Azure announced a similar offering in February 2021 followed by Google Cloud in June 2021.

[**]: The safest way would be to carve out the specific 8-solution oracle matching our crossword pattern.