So, just to focus this question, I don’t want to touch the subject of password patterns or password generation. Let’s focus only on “random passwords” (for whatever that means) of a given entropy. (In other words, let’s assume there is a fool-proof function genpwd(entropy_bits) that generates a password with the given entropy and we’ll just use whatever it spits out.)
Also, to focus even more, the intended use-case is for encrypted offline storage (which includes anything from GnuPG keys, Age encrypted files, full-disk-encryption, etc.).
Furthermore, the only threat we want to protect against is brute-force against the cryptographic primitives. Furthermore say the attacker has enough hardware power (say a few millions $) and enough patience (say a few years). And let’s also assume we’ve reached the peak of the technology capabilities (both hardware and software).
(I am well aware that by now I have waved away so many potential attack vectors that we are currently in the theoretical space…)
Given all that, the obvious answer is “just use a password with at least as many entropy bits as the underlying cryptographic construct”. (For example in the case of something based on AES-128, just use a 128 entropy bits password, passed through an at least 128 bit hash function; key derivation with iterations isn’t needed.)
However, at the other end there is memorability which pushes the entropy down. As a user I would prefer to use a short and memorable password (regardless of what that means), which means having fewer entropy bits.
Another complication is password derivation functions (like Argon, scrypt, bcrypt, the newer bscrypt, or in the worst case some variant of PBKDF) which helps us gain some entropy bits through time spent.
So my question is: given adequate defaults for a password derivation function, how many bits of entropy do I require for my password to be practically unbreakable in my lifetime (~100 years)?
Is 64 bits enough? Is 72 bits enough? Should I go up to 128 bits?
The number of bits depends a lot on the password KDF. Argon2 has tuneable parameters for CPU and RAM usage. You can pick settings that take, say, 1GiB of RAM and 30s of CPU time and then calculate the cost in cloud resources to be able to crack it for any amount of entropy. That then gives you a cost for someone to break and you can compare that to the value of whatever it’s protecting. Like many other security questions, it’s far easier to reason about as an economic question.
Exactly this. If you crank up the KDF cycles, even shorter passwords can become almost unbreakable.
I agree that changing the KDF parameters (iterations, memory, etc.) yields different improvements in the overall security. However, say one chooses such a KDF with such parameters that on an average laptop would take ~100ms to ~500ms to derive. (More than that the users would get upset.) :)
Also, the issue of time and cost depends on having good estimates. Could you point to some base-line figures for these estimates?
(I’ve looked at HashCat’s speed on the latest Nvidia RTX 4090, and I assumed 1K of those at a cost of ~$2M, but then I don’t think if such a GPU is the best baseline for this task.)
It depends a lot on the application. For example, I’ve been working on a cloud backup system in my spare time and I have cranked up the Argon2 settings to require about 30s to derive a key from the password. You need to do that only when provisioning a backup or restore client to a machine, so I’m not worried that it’s slow. Argon2 is designed to be very memory intensive, and I’ve set it to use 1GiB of state, which severely limits the utility of GPU or FPGA acceleration for attacking it. Your Nvidia RTX 4090 would be limited to no more than 24 parallel cracking attempts and so would probably be more expensive than a CPU-based attacker.
Who is storing this, and what is the attack vector?
The cost model is drastically different for “my local password->drive encryption” vs “my password->access to all my passwords stored on a remote server”.
Take the hard disk encryption w/a local only password. The solution on decent hardware is a 128 or 256bit random key, with an hsm gating access to the encryption material - or performing the encrypt/decrypt itself.
In the absence of an hsm but still local only you can easily burn a few hundred ms + gigs of memory on PBKDF/scrypt/etc during initial boot to get the drive key. Note that time+memory is important, and the modern pbkdfs are generally configurable to use as much of both as you want. What you want is as much as you can get away with without your user’s noticing the delay.
If instead you’re a hypothetical password syncing company, you should be investing in enterprise/high throughput HSMs to gate access to the user’s [encrypted] data on the basis that user passwords are generally not great. This means if someone gets a dump of your user’s data it’s all encrypted via strong actually random keys, rather than relying on whatever weak passwords they chose + a pbkdf.
For data encryption purposes It’s also good (sane?) practice to use the root key material to encrypt actual random keys for the real encryption, otherwise changing password suddenly requires re-encrypting everything.
Little bit of self-advertising: I wrote a tool called passgen that lets you generate passwords from regexes and it will tell you how many bits of entropy the password it generated has, even if you tell it to pick words from a wordlist or use a markov chain to generate pronounceable passwords. Just in case anyone is looking for something like that, I’d appreciate some feedback :)
That seems like the ultimate password generation solution for all the crazy password requirements websites have.
That is exactly where the idea came from! It seems like the situation has improved, but 10 years ago or so you really needed a different regex for each site.
I’ve had luck with long abbrase generated passphrases.
I always liked this paper to talk a bit about this[1]. I think of particular interest is Figure 2. I stopped doing research on passwords circa 2016, so I wouldn’t be surprised if there is newer work helping characterize password strength vs offline password cracking.
[1] Florêncio, Dinei, Cormac Herley, and Paul C. Van Oorschot. “An {Administrator’s} Guide to Internet Password Research.” 28th large installation system administration conference (LISA14). 2014. here: https://www.microsoft.com/en-us/research/wp-content/uploads/2014/11/WhatsaSysadminToDo.pdf
Thanks for the link. The figure 2 you’ve mentioned touches upon a different topic (that I haven’t asked yet, but I thought about) which tackles the issue of passwords used for “online authentication”.
The paper you’ve cited mentions that above
10^6options (that is ~20 bits of entropy) a password is safe for online use.(Here by “online authentication” I mean a password that is used solely for authentication purposes, is never reused in another context, and can easily be changed or reset.)
However, I’ll have to read the full paper to see what other information I can extract.
I think this question is kind of impossible to answer as framed.
You say you don’t want to talk about password patterns or generation; but that you want a memorable password. You talk about having a password with a known entropy, and that you want it to stretch to fit the key. You say we should “assume we’ve reached the peak of the technology capabilities (both hardware and software).”
In the terms you’ve set up, the entropy of the password is the entropy of the key. Is 64 bits enough? Well, that depends. How long does
genpwdtake to run? On what hardware? What is your attacker’s strategy? How much use has the key seen, and in what cryptosystem?If you can reliably measure the entropy of a non-random password (not really possible; entropy is a property of the choice and encoding process), and an attacker has to make 2^64 guesses to exhaustively search the keyspace, and each guess takes the attacker 1 picosecond of compute time, the total time will be about 7 months. You can put in other parameters to see the results.
But once again, I don’t think that’s a useful result. If you’re using the key once to encrypt a single kilobyte of data that you keep in a chest at the bottom of the ocean, how you think about those numbers will be different to if you’re typing your password into an untrusted machine six times a day. You simply have to have a threat model in order to draw any meaningful conclusion about what’s enough.
These are good questions:
genpwdisO(1)and is instantaneous; (thus why I mentioned the usage of a PBKDF;)I agree you can’t do that. That’s why I’ve assumed there is a “magic”
genpwd(bits)function that does it’s “magic” and we just use whatever comes out of there.And this is exactly my problem: where do I come-up with this “1 picosecond” time value? Is there a good source for such estimates?
Because if it’s 10 times less, then there’s another 3 bits of entropy gone…
I agree, and for all these points (how often is the password used, where is the encrypted file stored, etc.) one could make reasonable guesses. But not for the question I’ve asked. :)
You can make an estimate of cost now. For example (and this isn’t necessarily the best attack setup), you can use AES-NI on an Intel i7-908X to perform AES encryption at 1.3 cycles / byte. AES has a 16 byte block size. To make things round, let’s say you’re getting 16 cycles per block (and you’re decrypting one block per guess), running at 3.6GHz. That gives you 225Mguesses / second / core. That means a 64 bit keyspace gives you 162 years with a single 16 core processor. A dedicated 16 core host on AWS is $0.449 / hour on demand. Renting 162 of them for a year, with public 1 year reservation discount, paid upfront, will set you back $375k.
So, in some sense, 64 bits of entropy costs $375k to break; and you can just do some multiplication to find new results. 65 bits? That’s twice the space, so $750k. 64 bits but in three years when costs have come down by 75%? $94k.
But the number of variables is enormous, and the uncertainty over a long time is even larger. What if we get a usable quantum computer and Grover’s algorithm is in play? What do you think the cost of computer time will be in 2097? Do you think clock speeds will increase dramatically in the next 100 years, or have we reached a limit? Will the cost of ASIC manufacturing come down enough to result in economical specialized attack hardware? How will population growth affect the cost of energy?
(Also, I know you asked about time and I talked about cost, but the two are very roughly interchangeable in this analysis; a $1e100 cost is just as unachievable as a 1e100s time to recover the key.)
I believe the AWS approach dangerously underestimates the attacker’s capabilities. Someone willing to pay more than $100K will almost certainly resort to FPGA, or even ASIC. And you can cram lots of AES cores in one decent FPGA, which will then search the key space like mad for much cheaper than AWS ever will.
For attacks of this scale, normal CPUs or GPUs aren’t the real threat model. Instead I’d take a look at more stable cost models such as energy×die-area. And this is where memory-hard algorithms like Argon2 really shine: since they’re optimised for the hardware they’ll typically run on (or at least part of it, newer algs take advantage of the cache hierarchy as well), the cost an attacker pay for a single guess is very close to the cost a user pays for a legitimate check (where “very close” is within a single order of magnitude).
So, if you use something like Argon2i or Argon2id with lots of memory, in parallel, with a total running time of one second, it’s pretty safe to assume that with current technology, the attacker will not guess any faster than 100 password per second per machine, where “machine” means the cheapest & most efficient specialised hardware your attacker could manufacture. Assuming your adversary is China or Taiwan, and they have fabs.
So if your attacker wants enough machines to guess 2^64 guesses in one year, they need 2^64 / 365 / 24 / 3600 / 100 machines, or 5.8 billion machines. That means 5.8 trillion dollars, not counting electricity consumption. I love Argon2.
I took a similar approach, but got the numbers out of thin air:
PBKDF2-HMAC-MD5with999iterations; (on Nvidia RTX 4090 it can generate these at a rate of ~46 millions per second;)If you multiply all those (with a bit of rounding as otherwise would overflow
float64) you get the minimum number of bits of entropy.But all all of the above is laughable because every line is just an assumption out of thin air…
As said initially, I would like to focus this thread on the security and entropy aspects, and not on password patterns, memorization or related techniques.
However, given this is such a popular topic (perhaps even more popular than the actual security aspects), I’ve submitted this question to the community about this subject.