Labyrinthine passwords versus Quantum Computers

In this third blog on quantum computing security we're going to do some secrets bruteforcing.

In part 1 , we put together the various building blocks needed for today's small proof of concept

In part 2 , we broke a toy hash function using AWS Braket quantum computing services with full-blown quantum acceleration.

The first two parts were quite technical for they required some implicit understanding of quantum gates and reversible computing . This is not the case today, you won't see a single line of code :-)

Unnamed but useful artifacts...

What are we going to bruteforce exactly? A family of strong passwords which do not appear to have a well-defined name... By default, I have chosen to refer to them as labyrinthine passwords. Don't be afraid by the name, they are just long and random passwords. The weird name comes from the way they are generated (more of that in a second).

Labyrinthine passwords are more common than one might surmise: as far as I'm concerned, I've been using such passwords on a daily basis to fill-in long, robust passwords into many of my online accounts for years now.

Two factors: a maze and a path

A labyrinthine password qualifies as 2FA because its knowledge relies on something I have and something I know.

The thing I have is called a maze, that is a n*m matrix made of random characters taken from the alphabet defined by your application's password policy. (eg: alphanumeric characters).

The thing I know is a path winding through the maze.

Overlaying the path on top of the maze will reveal the labyrinthine password.

In the example below, the password (in red) is revealed by applying the path (yellow) at coordinates (1,3) in a 6*5 matrix (top left coordinates are 0,0):

Renewing the password is simply a matter of generating a new random matrix while keeping the same path:

Quite handy, don't you think? All you have to do to be safe is keep a long path "pattern" safely in your head.

Problem statement

Imagine I have access to the passwords history of a given online account and to all its corresponding mazes. I also have access to the current password's maze, but not to the password itself. Lastly, I don't have access to the path.

The problem we are going to investigate is the following: is it possible to deduce the path from the data at hand?

Obviously knowing the path as well as the current maze will reveal the current password.

Is this problem realistic?

If you put yourself in the shoes of a labyrinthine password user, you will easily agree that all the mazes have a good chance to have been saved as pictures on the user's local computer. Including of course the maze of the current password.

Now what about the password history? I have already warned a few years ago of the dangers of keeping password histories. But as explained in my past article: if the passwords sequence has been produced by a Bernoulli process, then uncovering an historical password following a breach into the service is as difficult as uncovering the current password.

The good news is that for all that it matters, Labyrinthine passwords behave like Bernoulli generated passwords. But if the passwords history is encrypted by the service rather than the password hashes history (the best practice), then we meet the pre-requisites of our problem statement.

Since we don't known whether the service follows this best practice, we have an interesting, realistic use case to work on!

The algorithm

For a given maze at index "h" in the maze history, we need to iterate over all the n*m starting positions and run a Grover quantum search in the hope of finding the corresponding password.

There's a lesson to be learnt from my two previous articles on Grover searches:

• In part 1, we worked out a quantum search which is no more efficient than a classical Monte Carlo simulation . In fact it is even way slower than a classical recursive search algorithm
• In part 2, we did just the opposite: we managed to work out a quantum search which is far quicker than any classical computer could achieve

The lesson is that, for a Grover search to be efficient, the associated quantum Oracle must be given some function to invert (that is, by the way, the reason why Grover was designed in the first place: to invert functions, not to actually search for anything). And for the inversion to be of any use, the function must be "many-to-less".

Too often do we see instances of quantum searches which look for something they already know...

One typical example is Simon's algorithm , where the solution is encoded into the Oracle.

While experimenting with AWS Braket in part 2, I was able to achieve quantum acceleration because I had two elements at my disposal: an image (i.e the outcome of a function) and a hashing function (a many-to-one function). What I did was use Grover by the book to invert the function to find all pre-images.

Here, I have two different elements at my disposal: an image (the password) and a pre-image (the corresponding maze). I don't know the function that yields the password from the maze, so I must contend with Grover making educated guesses to find the password given the maze, exactly as I did in part 1. These guesses are nothing more than picking a direction among valid ones.

So Grover searches will be slow, we won't achieve lightning fast acceleration. (the quantum Oracle is helpless, it simply doesn't have enough hints).

All this means that unless proved otherwise, Labyrinthine passwords are quantum resistant, because the only way to break them at quantum speed would be to have access to the current password hash and to invert it with a quantum circuit far beyond the capabilities of current Quantum Computers.

(Reasonable) assumption on random walks design

Our Grover-educated guesses are implemented by random walks . We investigated two types of walks in part 1: Brownian motion and self-avoiding walks.

Without big loss of generality, we narrow the scope of our investigations on Labyrinthine passwords by assuming the path we try to uncover is built from either one or the other walk.

You'll note something very counter-intuitive here: passwords based on Brownian motion (a truly random process) are much less random than passwords based on self-avoiding walks! This is because the former will re-use the same character several times resulting in a potentially very weak password.

Naturally, users will be more inclined to resort to self-avoiding walks. But you have to be aware that even self-avoiding walks do not capture all possible Labyrinthine passwords: security-minded users will often use discontinuous walks.

Building a crossword at each starting position

Regardless of the kind of random walk we select, for educated guess to work we need to know the local crossword at each n*m starting position.

This can be done very easily in two steps:

1. For each given maze, we build a lexical survey. We only have to build this once per maze, so it's not a big overhead. This survey records, for each cell of the matrix, whether the character is found in the password, and if so at which position. For example, a character at coordinates (4,5) of the maze could be at the third and seventh position in the password, while character at coordinates (5,5) could not be found at all in the password.
2. We then leverage the information contained in the lexical survey to reveal the crossword of all passable cells for any given starting position. (So we build n*m crosswords for each maze). A passable cell can be part of a random walk (a white cell in a crossword), an unpassable cell can't (a black cell).

If we consider self-avoiding walks, we can further restrict eligible cells by marking cells which are already part of the walk as unpassable.

The construction of a lexical survey can be done in O(2) for each maze.

Finding eligible paths

Once the lexical survey and crosswords are ready, we can iterate over all starting positions and run our quantum circuit to find eligible paths within all crosswords, one at a time.

If we find such a path within a given maze, we can check if the same walk yields the proper password for all records in the user's password history (and their corresponding mazes).

Note this key fact: verifying a path is orders of magnitude quicker than finding one.

If a match is found consistently across the whole passwords history, we add the path to a list of eligible candidates. The list of candidates is very likely to be extremely small if the history depth is greater than the length (or width) of the mazes.

So we will find the path among this list eventually, hence the current user password.

Conclusion

Here we have a simple AWS Braket proof-of-concept that solves a concrete use-case for cybersecurity: a random enumeration of all potential paths to uncover the user's password, that is to say: some workable statistical quantum bruteforcing algorithm.

Admittedly this PoC is so slow it's not going to be of any use in real life, but I think what makes it interesting is that it is less artificial than the usual examples of Grover searches one finds on the Internet and maybe more importantly

it comforts us in the robustness of Labyrinthine passwords as long as we do not keep a record of our past mazes

As long as we live in a world of passwords, Labyrinthine passwords will be much better than our usual not-so-random passwords. For applications which do not support passwordless authentication, I can only invite you to go labyrinthine. As a bonus, you will shine in society thanks to this word!

I hope this three-parts series is going to give you some incentive to explore more quantum computing on your own!

Appendix: the quantum-classical information tradeoff

On a 2D lattice, as mentioned in part 1 the number of self-avoiding walks of length p is about 2.85**p but the actual number of cells (white or black) is dictated by the surface of a ball of radius p. The surface of this ball is only 2*(p**2+p) cells.

What this means is that, when p is large, the number of cells becomes vanishingly small compared with the number of walks because the ratio is O(2)/O(p)

There is a very theoretical way to exploit this fact: in our quantum walk subroutine, the number of classical information that we tie to the quantum circuitry is measured by the number of "if" statements. This number is equal to the number of eligible walks. Maybe we could try to adjust the quantum-classical information tradeoff by designing a subroutine containing less classical information and more quantum information by resorting to exactly one "if" statement for each black cell location. This way, with large p, the quantity of classical information that we leverage would become vanishingly small while the quantum circuitry would become increasingly deep and complex.

There is a catch: the deeper a quantum circuit, the higher the risk of quantum decoherence.

Should such an unlikely scheme be feasible, we could throw p quantum dices at once and get a self-avoiding path of length p stepping only on white cells with some high probability... (Greater that random guessing, at least).