60

Could anyone point to a quote in a published work - or suggest a recognised expert who might provide a quote - which answers the following question

How much entropy in a password would guarantee that it is secure against an offline guessing attack even if the attacker has the most powerful hardware in the world?

I am writing an article about creating a secure password based on true randomness and I would like to include a figure for guaranteed security but I would rather not offer my own opinions and arguments, I would like to quote a recognised expert or published work.

In more detail what is meant above by these terms is as follows.

If a password has enough entropy then presumably it is uncrackable in our current threat model, which is the one where the attacker has a cryptographic hash of the password and is repeatedly making a password guess, hashing the guess and comparing the hash.

By entropy I mean that the password creator has chosen randomly, with equal probability for each choice, a password from N possible passwords. The entropy in bits is then log₂(N)

So quote needs to cover how much entropy in bits (or how big is N) to guarantee that the password is secure against this kind of attack, even if the attacker has the most powerful hardware in the world.

Rodrigo de Azevedo
  • 242
  • 2
  • 13
Stephen Hewitt
  • 711
  • 1
  • 6
  • 6
  • 27
    Question: by "the most powerful hardware in the world" do you mean "the most powerful hardware that may plausibly exist in the world today", "the most powerful hardware that our current understanding of physics suggests could ever plausibly exist", or somewhere between these two extremes? Both of the current answers are based on the second of these options, but for *realistic* purposes, the third is probably the most useful. – Jules Aug 30 '17 at 12:57
  • 29
    _"So quote needs to cover how much entropy in bits (or how big is N) to guarantee that the password is secure against this kind of attack ..."_ - You can **never** guarantee that. No matter how much entropy your password has, there's always a chance that an attacker guesses it. This also applies to keys for normal encryption. The only thing you can do is define what probability is acceptable to you and work from there. – marcelm Aug 30 '17 at 15:10
  • 3
    @marcelm Not necessarily; it depends what you're guaranteeing - whenever we're dealing with brute-force attacks, it's always an *average case* guarantee. Of course it's possible to guess lucky on the first try, but it's equally likely to need to guess all-but-one possibilities first. In particular, *"the password is secure against this kind of attack"* is a guarantee that *on average* the attack will take more time / energy than available - that is exactly the "defining an acceptably low probability" that you're reffering to, usually set at 128 bits of guesswork. – Mike Ounsworth Aug 30 '17 at 17:21
  • You may also find the following question helpful about how secure an 80-bit password is: https://security.stackexchange.com/questions/69374/is-an-80-bit-password-good-enough-for-all-practical-purposes – Cody P Aug 30 '17 at 20:38
  • 4
    Surely there's a chance that any computer could get lucky and succeed in a brute force attack against any arbitrary length in a short amount of time, right? Maybe I'm being overly pedantic with the word "guarantee". – Todd Wilcox Aug 31 '17 at 02:24
  • 1
    The only entropy that is "truly" unbreakable is ∞ bit – Tobias Kienzler Aug 31 '17 at 05:50
  • 3
    If I can still guess your password, no matter how long it is, is it still guaranteed uncrackable? Otherwise, what do you mean? –  Aug 31 '17 at 07:11
  • 2
    For those being pedantic about what "uncrackable" means, I believe he means an attacker with "the most powerful hardware in the world" or the most powerful possible hardware would not have a greater than 50% chance of finding the password in 10, or maybe 100, years. Yes, there's still a chance you'd get lucky on your first try and you'd always be successful with an arbitrarily large number of years, but trying to crack such a password would be like trying to solve a Rubix cube by randomly turning layers. – Cody P Aug 31 '17 at 14:48
  • 5
    _"For those being pedantic about what "uncrackable" means, I believe he means an attacker ... would not have a greater than 50% change of finding the password ..."_ - And that is **exactly** the reason I'm being pedantic. In such an analysis I would find 50% completely unacceptable, and I would insist on specifying a lower resultant probability, more like 10**-18. The probability you work with is important and is intrinsically part of the problem, so it should really be specified from the start. – marcelm Sep 01 '17 at 10:19
  • If you think about it the answer might be less useful than you think. Since you can't remember or generate a pure random password manually, no matter if it has 80, 128 or more bits of entropy you can just go with a typical strength (I.e. 128 bits aka 22 base64 characters) even when a bit smaller might still be unobtainable – eckes Sep 01 '17 at 19:44
  • A "greater than 50% chance" makes not really sense, does it? Crackable in this case means attacker is able to enumerate and validate all posssible passwords within some reasonable time. By assuming equal distribution you can then turn this into a probability for single guesses (if you really want to). – eckes Sep 01 '17 at 19:47
  • 2
    @marcelm - If you're doing security and not being pedantic - you're probably doing it wrong. – Don Branson Sep 01 '17 at 20:16
  • Over a 100yr, each year GPU will be at least 20%, and by my calculations that 82.8m times faster total. Given CPU will have similar increases, if only in core counts, they will be similarly faster. And that is per CPU or GPU we might have 10+ per computer in 100yr. Making brute force a lot more practical. Also quantum computing could completely eclipse those numbers in a 100yr. So saying uncrackable only makes your look like an idiot when it is cracked. Especially with side channel attacks. – cybernard Sep 02 '17 at 01:27
  • @marcelm I'm trying to be pedantic in a way that we can discuss practical meanings of uncrackable instead of giving up and saying no password is uncrackable (or debating in the answers themselves what uncrackable means). Note that the 50% chance of cracking the password in an unreasonably difficult attack is like the LD50 (50% chance of rats dying) toxicity standard. The standard establishes a level at which you've clearly failed and you should never even get close to that 50% failure level of danger. You decide based on your risk aversion how far from that standard they want to be. – Cody P Sep 05 '17 at 13:02
  • 1
    @marcelm Cody P and everyone Good points - being asked to clarify what does "uncrackable" mean is harder than I thought - Let's say if the most powerful hardware ran for a million years then it would have a one in a million chance of finding the password. Cody P's definition analogous to LD50 is fine too. If an expert would say that with X bits there is 50% chance of cracking it in a year, then I can just add about 40 bits (according to taste) to get about one in a million chance in a million years. – Stephen Hewitt Sep 10 '17 at 21:23
  • @cybernard Side channel attacks have absolutely nothing to do with security from brute force. No matter how effective those attacks are, they are weaknesses in implementations, not in algorithms. I could give you an encrypted hard drive and no amount of side-channel attack would help you crack it. – forest Sep 22 '18 at 11:14
  • @cybernard Additionally, quantum computers can only attack symmetric ciphers with grover's algorithm, which is not very efficient when you need to parallelize it. Not to mention, you can completely negate even a perfect, ideal quantum computer's advantage by doubling the key size just once. – forest Sep 22 '18 at 11:15

4 Answers4

119

There's a quote for you in this crypto.SE answer, by Bruce Schneier in Applied Cryptography (1996), pp. 157–8.

You can also find Bruce Schneier citing himself in his blog (2009), if you want an online citation.

Here is the full quote, in case of the links breaking:

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38×10-16erg/°Kelvin, and that the ambient temperature of the universe is 3.2°Kelvin, an ideal computer running at 3.2°K would consume 4.4×10-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21×1041 ergs. This is enough to power about 2.7×1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all of its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn’t have the energy left over to perform any useful calculations with this counter.

But that’s just one star, and a measly one at that. A typical supernova releases something like 1051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

Update: If you want a citation to assess the strength of a randomly generated password, you can use this website that is regularly updated with recommendations made by different institutes. A random password is equivalent to a symmetric key, so this is the value you are looking for. (Here is a wayback machine link, if this website were to close.)

A. Hersean
  • 10,046
  • 3
  • 28
  • 42
  • Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/65108/discussion-on-answer-by-a-hersean-expert-quote-on-entropy-for-uncrackable-passw). – Rory Alsop Sep 05 '17 at 07:23
27

Let's take a different crack from a monetary perspective instead of a physics perspective. Skylar Nagao at Peerio stated that:

In a 2014 research paper on password memorability, security researchers Joseph Bonneau (Stanford) and Stuart Schechter (Microsoft) estimated the cost of an attack based on the total annual payout to bitcoin miners in 2013.

"In 2013, Bitcoin miners collectively performed ≈ 275 SHA-256 hashes in exchange for bitcoin rewards worth ≈ US$257M… this is the only publicly known operation performing in excess of 264 cryptographic operations and hence provides the best estimate available. Even assuming a centralized effort could be an order of magnitude more efficient, this still leaves us with an estimate of US$1M to perform a 270 SHA-256 evaluations and around US$1B for 280 evaluations."

Here we have the billion dollar password estimate — even for a centralized state attacker, it would cost about $1 billion US dollars to compute 280 SHA-256 hash functions over the course of a year. This is like saying it would cost $1 billion USD to try 280 lock combinations over a year. Since an attacker would be ‘likely’ to guess correctly with just one guess after the halfway point, Peerio uses an 81-bit (280 times two) minimum standard for our computer generated passphrases. We chose this standard because we wanted to make sure even a state level attacker would need to drop $1 billion US dollars to have even a coin’s toss chance of cracking a Peerio passphrase.

An 81-bit password is estimated to cost 1 billion to be likely to crack and so is considered by Peerio to be "uncrackable". In layman's terms 81-bits would work out to 17 random lower-case letters, 13 random characters from a US keyboard, or 7-8 words randomly chosen from a dictionary.

There are admittedly a lot of technical details like prices, risk levels, and hashing algorithms. Perhaps the passwords are hashed much, much more strongly with bcrypt. Perhaps these figures are out of date and more modern mining costs or the latest mining revenue data puts the hashes/dollar as high as 1016 hashes/dollar. Maybe Bitcoin isn't the best comparison due to market differences or hardware differences. At the end of the day we still have an order of magnitude for the lowest cost of hashing at scale.

Even if some nation-state or millionaire put together a hash-breaking farm the size of Bitmain's Ordos mine, they'd still take months to have a good chance of finding your 80-bit password password from an insecure hash, and throw away millions or even billions of dollars of cost and lost potential revenue. If any government could hit a billion terahashes per second, I bet they have better things to do with that money-making machine than crack your 81-bit password.

If we're talking about guarantees and defense against incredibly powerful adversaries, it's important to note that there are plenty of ways to get around an uncrackable password. Methods include session hijacking, MITM attacks, password reset exploits, keyloggers, asking the website/admin for access, and phishing. Although some threats like physically tampering with your computer may seem absurd, they're more reasonable than a billion dollar password cracking effort (relevant xkcd).

forest
  • 64,616
  • 20
  • 206
  • 257
Cody P
  • 1,148
  • 6
  • 14
  • 1
    This is a really good use of available data. It's worth mentioning that this is something of a lower bound, since proper password hashes (scrypt, etc) are designed to be slower to compute than SHA-256. Even iterating SHA-256 allows you to crank up the work factor. – bmm6o Sep 01 '17 at 20:16
  • A bit ironically, 2013 was just the 'tip' of Bitcoin mining shifting en masse to ASICs which resulted in more than thousand-fold increase in capacity, about as much as the shift to GPUs in 2010-11; now (2018) it is about 2^90/year. Mining revenue has increased but only a little more than ten-fold (including the second scheduled halving of the block reward in 2016). – dave_thompson_085 Jul 19 '18 at 04:14
8

UPDATE:

A really good YouTube video exploring this topic is:

How secure is 256 bit security? by 3Blue1Brown

I don't have a quote or original source, but I often answer questions like this with an energy reduction. The argument goes like this: assume humanity can one day make processors at some physics limit of efficiency. Then compute the amount of electricity it would take those processors to crack the password, then compute the number of stars the size of the sun you would need to consume to produce that much electricity. Short version: to crack one of the 32-char random passwords from a password manager, you're looking at consuming like 2x1015 stars in electricity costs alone. For example, see my recent answers here:

Should I vary the length of my completely-random passwords for the best security?

and here

Why brute-force the password instead of the key directly?

I'm actually not sure where I originally got the idea, but it might give you a starting point for googling to find a quotable source.

Remember also than when talking about "passwords" in the general public, you need to be very careful to frame it as "properly random passwords from a password manager". If you allow users to choose their own passwords then the length is more or less irrelevant because humans choose stupidly predictable passwords, for example, this article:

How to Break 30 Per Cent of Passwords in Seconds

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • Note: this answer is for classical computers. Grover's algorithm can brute force in $O(\sqrt{n})$ steps so 256 bit becomes 128 bit (but the constant factor might get much larger). – Reinstate Monica Aug 30 '17 at 15:10
  • 2
    Don't be so sure on the [sqrt(n)](https://eprint.iacr.org/2017/811) thing. (This paper came out just a few days ago, hot off the presses) – mikeazo Aug 30 '17 at 15:25
  • @mikeazo Interesting but what I glean from that abstract is that sqrt(n) still holds but the constant factor for quantum computers would be much, much larger due to lack of parallelization. Still we could brute force a 256 bit password in many fewer than 2x10^15 stars. – Reinstate Monica Aug 30 '17 at 15:29
  • 1
    @Solomonoff'sSecret Good point. I should re-do the calculations with $O(\sqrt{n})$ atomic operations. That said, while quantum computers are more time-efficient than classical (relative to the size of the searchspace), it's hard to imagine that they are more energy-efficient. I see numbers like 2^20 - 2^50 for number of quantum gates per operation, and for number of physical qubits per fault-tolerant logical qubit, which works against the Grover's speedup in terms of energy consumption. – Mike Ounsworth Aug 30 '17 at 15:50
2

I'm in agreement with what others have written. As an additional piece of information, see this recent (relative) talk on Argon2. One page (slide #8) gives a relative recent quote on effects of advances in hardware on practical strength of passwords under brute-force attacks. Namely

Brute-force attacks (such as key guessing) are most efficient on custom hardware: multiple computing cores on large ASICs. Practical example of SHA-2 hashing (Bitcoin):

  • 232 hashes/joule on ASIC;
  • 217 hashes/joule on laptop.

Consequences:

  • Keys lose 15 bits
  • Passwords become 3 lowercase letters shorter
  • PINs lose 5 digits

ASIC-equipped attackers are the threat from the near future. ASICs have high entry costs, but FPGA and GPU are employed too.

Hopefully this gives you a practical, updated perspective on the 'effective' length of key sizes under brute-force attacks using modern hardware.

Kaiyi Li
  • 101
  • 3