Becoming physically immune to brute-force attacks - Seirdy
Preface
This is a tale of the intersection between thermal physics, cosmology, and a tiny amount of computer science to answer a seemingly innocuous question: “How strong does a password need to be for it to be physically impossible to brute-force, ever?”
TLDR at the bottom.
Note: this post contains equations. Since none of the equations were long or complex, I decided to just write them out in code blocks instead of using images or MathML the way Wikipedia does.
Update: I implemented the ideas in this blog post (and more) in a program/library, MOAC
Toggle table of contents
Introduction
Permalink to section
I realize that advice on password strength can get outdated. As supercomputers grow more powerful, password strength recommendations need to be updated to resist stronger brute-force attacks. Passwords that are strong today might be weak in the future. How long should a password be in order for it to be physically impossible to brute-force, ever?
This question might not be especially practical, but it’s fun to analyze and offers interesting perspective regarding sane upper-limits on password strength.
Asking the right question
Permalink to section
Let’s limit the scope of this article to passwords used in encryption/decryption. An attacker is trying to guess a password to decrypt something.
Instead of predicting what tomorrow’s computers may be able to do, let’s examine the biggest possible brute-force attack that the laws of physics can allow.
A supercomputer is probably faster than your phone; however, given enough time, both are capable of doing the same calculations. If time isn’t the bottleneck, energy usage is. More efficient computers can flip more bits with a finite amount of energy.
In other words, energy efficiency and energy availability are the two fundamental bottlenecks of computing. What happens when a computer with the highest theoretical energy efficiency is limited only by the mass-energy of the entire observable universe?
Let’s call this absolute unit of an energy-efficient computer the MOAC (Mother of All Computers). For all classical computers that are made of matter, do work to compute, and are bound by the conservation of energy, the MOAC represents a finite yet unreachable limit of computational power. And yes, it can play Solitaire with amazing framerates.
How strong should your password be for it to be safe from a brute-force attack by the MOAC?
Quantifying password strength.
A previous version of this section wasn’t clear and accurate. I’ve since removed the offending bits and added a clarification about salting/hashing to the Caveats and estimates section.
A good measure of password strength is entropy bits. The entropy bits in a password is a base-2 logarithm of the number of guesses required to brute-force it.note 1
A brute-force attack that executes 2n guesses is certain to crack a password with n entropy bits, and has a one-in-two chance of cracking a password with n+1 entropy bits.
For scale, AES-256 encryption is currently the industry standard for strong symmetric encryption, and uses key lengths of 256-bits. An exhaustive key search over a 256-bit key space would be up against its 2256 possible permutations. When using AES-256 encryption with a key derived from a password with more than 256 entropy bits, the entropy of the AES key is the bottleneck; an attacker would fare better by doing an exhaustive key search for the AES key than a brute-force attack for the password.
To calculate the entropy of a password, I recommend using a tool such as zxcvbn or KeePassXC.
The Problem
Permalink to section
Define a function P. P determines the probability that MOAC will correctly guess a password with n bits of entropy after using e energy:
P(n, e)
If P(n, e) ≥ 1, the MOAC will certainly guess your password before running out of energy. The lower P(n, e) is, the less likely it is for the MOAC to guess your password.
Caveats and estimates
Permalink to section
I don’t have a strong physics background.
A brute-force attack will just guess a single password until the right one is found. Brute-force attacks won’t “decrypt” stored passwords, because they’re not supposed to be stored encrypted; they’re typically salted and hashed.
When estimating, we’ll prefer higher estimates that increase the odds of it guessing a password; after all, the point of this exercise is to establish an upper limit on password strength. We’ll also simplify: for instance, the MOAC will not waste any heat, and the only way it can guess a password is through brute-forcing. Focusing on too many details would defeat the point of this thought experiment.
Quantum computers can use Grover’s algorithm for an exponential speed-up; to account for quantum computers using Grover’s algorithm, calculate P(n/2, e) instead.
Others are better equipped to explain encryption/hashing/key-derivation algorithms, so I won’t; this is...