Password Unhasher: An Implementation of Grover's Algorithm

Media claims Quantum Computing can crack modern cryptography and break the internet. But is this true? This implementation demonstrates how it might for certain non-quantum-proof hashing algorithms

Comment 4

Media claims Quantum Computing can crack modern cryptography and break the internet. But is this true? This implementation demonstrates how it might for certain non-quantum-proof hashing algorithms

Inspiration

In the WQCC Qiskit Fall Fest 2023 opening, Ari and the team showcased a bunch of Quantum Computing applications. These include developing new molecules, allow advances in Materials Science Research, or break current cryptography.

Cryptography is a fundamental aspect of the internet. If QC can break it, both media and professionals claim QC could destroy the internet as we know it.

Is this claim real or hype? And if it's real, how? How can qubits, x, or h gates break the internet?

What's the idea

If QC specialists were to dream about an algorithm, they would probably dream about Shor's algorithm: the algorithm capable of breaking current cryptography standards as we know them (such as RSA). But what about the others? Why not Grover's?

In this project I showcase the implementation of a less spoken algorithm that raises concerns to password security: Grover's algorithm.

Here's a very interesting read and visual depiction on how Grover's algorithm works: https://web.archive.org/web/20171221161408/http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm

Summarized in simple terms: Grover's algorithm is a search algorithm that can search in an unordered database at O(sqrt(N)) instead of the fastest classical for an unordered database, O(N), as long as an Oracle function is provided.

Cool. But what is the Oracle? What can it be?

The Oracle is a function that recognizes the value(s) we're looking for, and can be implemented as a quantum circuit. (More technical description: https://quantumcomputing.stackexchange.com/questions/1419/does-the-oracle-in-grovers-algorithm-need-to-contain-information-about-the-enti)

The main issue behind the Oracle is it's creation, which can be resource expensive in certain search implementations. This means it may (or rather will) perform worse than in the classical implementations of the same search cases.

There's one example where the oracle is required in both classical and quantum implementations, making quantum the clear out-performer: password hashing.

Here's everything you need to know about password hashing and salting: https://stytch.com/blog/what-is-password-hashing/

What it actually does

This implementation simulates a password hashing situation with Grover's algorithm. It runs in a very simple and small test case:

  1. Password is an integer with a defined amount of bits. The recommended example is 8 bits, meaning password is an integer from 0 to 512. More bits makes it slow
  2. The hashing algorithm (in classical) takes the password as bits and adds a defined amount of salt bits (random bits) to the start. E.g. if adding 2 bits of salt, 1001 could become 111001 or 011001 or ...
  3. The hash algorithm then takes the password as bits, and flips every even bit. E.g. 1001 becomes 0011
  4. Grover's algorithm is ran with the hash algorithm as the Oracle and with the fully hashed value. The hashing algorithm is implemented by applying an x gate the even qubits if the total number of bits is odd, and an x gate on the odd qubits if the total number of bits is even.
  5. Grover's algorithm finds both the inputted hash and the password in bits (+ the salt bits which are removed) with the Quantum Circuit.

This example has some obvious limitations, as it's unrealistic to simplify a hashing algorithm to such extent and it only works with a password from 0 to 512 (which is ridiculous), but it's a working depiction of how the Grover's algorithm could potentially be implemented with real hashing algorithms and real cryptography scenarios, assuming we can get to the necessary quantum hardware potential and we can adequately replicate hashing algorithms in quantum circuits.

The power behind this algorithm, which has stunned me the entire time throughout the implementation, is that it doesn't matter where you put the salt, or how much you put. It will always find the right implementation as long as it knows where the salt was added and how many bits were added (which is public/standardized for many hashing algorithms, or easily obtainable if, for example, the hashed password have been hacked, as the salting protocol is required to rehash and confirm a password is correct).

So, try adding more salt and less bits. It gives more extreme variations in hash values, but still works!

How I built it

The implementation was built with Python and Qiskit on Jupyter Notebook.

Challenges I ran into

  1. Understanding Quantum Algorithm.
  2. Understanding Quantum Algorithm.
  3. Running Qiskit in local device instead of Quantum Lab.
  4. Implementing Quantum Algorithm.
  5. Understanding Quantum Alrogithm.
  6. More doubting on how the algorithm actually solves the issue
  7. Finding the real life implementation that could work
  8. WHAT IS AN ORACLE

Accomplishments that I'm proud of / What I've learned

  1. The implementation works! :D
  2. I learned the general idea behind Grover's algorithm 3 I've learned about a bunch of quantum algorithms out of the leading Shore's algorithm 4 I've learned from scratch about password hashing and salting, and recreated a simple, 100% secure-you-should-definitely-use hashing algorithm
  3. I've learned about setting up environments locally and how to pair it with GitHub (such that, if I change devices, I can redownload everything again easily, requirements.txt)
  4. Practiced my python again after not using it in a while.
  5. Video editing and presentation skills with very little prep time!

What's next for Grover's Algo implementation in reversing Hashing Algo

There's a bunch of areas that can be improved with the implementation:

  1. Implement with a real hashing algorithm
  2. Implement with larger passwords, more qubits
  3. Give a more neat interface, or add functionality for public to use
  4. Run on real quantum computer

These are mainly limited by our current quantum hardware potential, so it's hard to plan how much of this can be implemented.

Picture from: https://www.wired.com/story/bcrypt-password-hashing-25-years/

Built With

Share this project:

Updates