Why Hash Functions Are One-Way: The Unbreakable Link Between Cryptography and the P vs NP Problem
Why is a Hash Function Never Bidirectional?
One of the fundamental questions in computer science and cryptography is: why can’t a hash function used for password security be reversible?
The answer lies in the very design of these functions. A hash function, like those used in popular libraries such as bcrypt, transforms a password into a unique string called a “hash.” However, it is virtually impossible to reverse this process and retrieve the original password from the hash. Let’s delve into why this is a critical feature.
The Basics: What is a Hash Function?
A hash function is a mathematical transformation that takes an input (such as a password) and produces a fixed-size output, typically an alphanumeric string. These functions have three key properties:
- Determinism: The same input always produces the same output.
- Efficiency: Computing the hash is fast.
- Irreversibility: It is infeasible to deduce the original input from the hash.
Modern cryptographic hash functions are also designed to resist attacks through features like collision resistance (ensuring two different inputs do not produce the same hash) and robustness against brute-force attacks.
Why Are Hash Functions One-Way?
The irreversibility of hash functions is rooted in fundamental principles of algorithmic complexity theory. Reversing a hash, i.e., finding the original input, is an extremely complex task because it would require trying all possible combinations (e.g., all possible strings up to a certain length).
In cryptography, this irreversibility often relies on unresolved mathematical conjectures, notably the famous P vs NP problem.
The Link to the P ≟ NP Problem
The P vs NP problem is one of the great unsolved mysteries in mathematics and theoretical computer science. It seeks to answer a fundamental question: if a solution can be verified quickly, can it also be found quickly?
How Does This Relate to Hash Functions?
- Quick Verification: When you enter a password, the system hashes it and compares it to the stored hash. This verification is fast and efficient.
- Hard to Reverse: Reversing the process, i.e., finding the input from the hash, corresponds to solving an NP-complete problem, which means we currently know of no efficient algorithm to solve it (and we doubt one exists).
If P = NP were ever proven, then every problem that is hard to solve today would become as easy to solve as it is to verify. This would have major implications:
- Current cryptographic systems, which rely on the infeasibility of reversing hash functions or solving hard mathematical problems (like factoring large numbers in RSA), would become vulnerable.
- Asymmetric cryptography, digital signatures, and even blockchains could be compromised.
Why This Conjecture is So Important
The P vs NP problem is considered one of the greatest mysteries of modern mathematics. If P = NP were proven, it would disrupt:
- Cryptography: Passwords, online transactions, and secure communications would no longer be safe.
- Mathematics: Many unsolved problems would suddenly become accessible.
- Engineering and Medicine: Complex problems like protein folding could see groundbreaking advancements.
However, the majority of the scientific community believes that P ≠ NP, which ensures the continued security of hash functions like bcrypt.
My original article:https://www.elmesmar.fr/2024/11/pourquoi-les-fonctions-de-hachage-sont.html
