20

We have always measured password or private key strength by the amount of entropy it contains, but what if the attacker who cracks it is lucky.

Consider the following simple scenario, we have 1 bit [0,1] secret , the attacker should choose between 2 combinations, but the attacker already has a 50% chance of guessing the right one.

Now consider a 128 bit secret. It should have 2^128 combinations, so the attacker should go through 340282366920938000000000000000000000000 combinations before guessing the secret, but he actually only has to go through half of that: 170141183460469000000000000000000000000, because he probably has a 50% chance of guessing it right.

So if at each bit he has a 50% chance, that means that 1 bit is actually only half bit.

And if he is very lucky, say 90% chance, that means that 1 bit is actually only 0.1 bit.So in face of a very lucky opponent, a 128 bit password has only 12.8 bit strength.

What is your opinion about this?

cryptonoob400
  • 533
  • 1
  • 3
  • 12
  • 14
    $2^{128}=340282366920938463463374607431768211456$ – Ruggero Feb 17 '17 at 11:00
  • 42
    If you guess a $128$ bit string and you are "lucky" half of the time, you only get $127$ bits of "security" infornally speaking - not $64$ bits. This is because $2^{128}/2 = 2^{127}$. – TMM Feb 17 '17 at 11:47
  • 23
    The numbers you're talking about here are big. Like, really, really big. Like, it's-almost-impossible-to-wrap-your-mind-around big. To put things into perspective, the odds of winning the California Powerball jackpot is about 1 in 293,000,000. The chance of making that 2^128 guess is like winning the jackpot 10^30 times in a row. Possible, yes, but very far removed from statistical feasibility. – nasukkin Feb 17 '17 at 18:23
  • 13
    Your maths is off there. Chances are about the same as winning the jackpot four times, then betting on a single number in roulette and winning three times. – gnasher729 Feb 17 '17 at 19:43
  • 6
    There is no difference in your example from someone who just magically guesses the correct password to someone's laptop. I mean, you can't defend against _that_ - the whole point of cryptography is simply to make such scenarios statistically unlikely, you can't make it one hundred percent impossible. – Akshat Mahajan Feb 17 '17 at 20:18
  • 4
    Luck doesn't work that way... but even if you did have an attacker with the magical property that they guess bits right 90% of the time rather than 50% of the time, your math is wrong. Their chances of guessing 128 bits correctly are 2^-19.5, not 2^-12.8. That's a factor of 100 difference. – hobbs Feb 17 '17 at 20:53
  • 3
    Voting to close as primarily opinion-based since it is explicitly asking for opinions. – fkraiem Feb 17 '17 at 23:50
  • 3
    @fkraiem Or you could edit it out. That might make it Unclear, but including the phrase, "What is your opinion about this?" doesn't really make it opinion based. Editing out problematic content is preferable, especially when it doesn't change the nature of the question. – jpmc26 Feb 17 '17 at 23:51
  • 1
    @jpmc26 It is already *also* unclear as it is, since it does not really ask any question. – fkraiem Feb 17 '17 at 23:54
  • 1
    What if I mash my hand on my keyboard and accidentally type the winning lottery numbers *and* the nuclear missile launch codes? – user253751 Feb 18 '17 at 04:30
  • @jpmc26 No I am not; both reasons apply. Others may as well. – fkraiem Feb 18 '17 at 08:41
  • 1
    To put it overly simply: you can go from being ridiculously unlikely for *one* attacker to guess *one* key, to being ridiculously unlikely that *any* attacker will ever guess *any* key, just by adding enough bits. – mwfearnley Feb 18 '17 at 17:48
  • 1
    Also putting down a flag to close as primarily opinion-based. Because "luck" is a nebulous and ill-defined attribute an attacker can have, acceptable answers to this question are likely to be firmly rooted in educated guesses and speculation. The top answer (@GianlucaGhettini) and the community reaction to it seem to support this. – Jules Feb 18 '17 at 17:58
  • This is so extremely unlikely that a Bayesian analysis will show that conditioning on having this experience makes it overwhelmingly likely that the attacker should expect to be dreaming or hallucinating. So, just wait for the 6 am alarm to go off next. – Count Iblis Feb 18 '17 at 23:44
  • 1
    If you would be 90% element-wise lucky you would indeed see a reduction from 128 bit to 12.8 bit. But do realize that would be a situation where you say: 'The first bit is 1 with 90% chance; The second bit is ... with 90% chance,...,the 128th bit is ... with 90% chance'; In practice there are very few situations where an attacker could get this kind of 'luck'. Perhaps the closest would be him knowing that you only used a limited set from the allowed characters. (And yes, in that case your entropy would indeed drop dramatically.) – Dennis Jaheruddin Feb 19 '17 at 16:26
  • The alternative answer is that generating really random numbers is impossible or slow. – HopefullyHelpful Feb 20 '17 at 09:13
  • Where is the actual question in this "question"? The properties of a search space should be assumed to be understood, including the fact that (statistically!) not the entire space has be searched. I fail to see what the *question* is. – Tom Feb 20 '17 at 14:59
  • One of Polish banks requested a person to fill in `1` character of password... [photo by Niebezpiecznik.pl](https://niebezpiecznik.pl/wp-content/uploads/2014/11/1__Niebezpiecznik.png). That's luck! – styrofoam fly Feb 21 '17 at 01:41

8 Answers8

74

"lucky" is not a property of the attacker. There's no "lucky" attacker nor "normal" attacker. They both have the same probability (low, very low) to guess the key. You can decrease the probability at will by increasing the length of the key (i.e. the no. of bits). You cannot really argue "what if the attacker is lucky" because "being lucky" is a posteriori statement; you say that an attacker is lucky only when he/she was... lucky

Gianluca Ghettini
  • 981
  • 1
  • 5
  • 12
  • Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/53850/discussion-on-answer-by-gianluca-ghettini-password-cracking-what-if-attacker-is). – e-sushi Feb 18 '17 at 13:56
42

Note: This answer assumes that by "lucky" OP meant "able to remove X% of valid answers", because I believe that was intent. Of course you can't measure luck ;)

And if he is very lucky, say 90% chance, that means that 1 bit is actually only 0.1 bit.So in face of a very lucky opponent, a 128 bit password has only 12.8 bit strength.

Well, let's validate that... Since 128bit password has 2^128 combinations: $2^{128} * 0.1 = 340282366920938463463374607431768211456 * 0.1 = 34028236692093846346337460743176821145.6$

$ \log_2(34028236692093846346337460743176821145.6) \approx 124$

This doesn't match with your calculation of $128*0.1=12.8$ because you divide bits, which is incorrect.

Attacker can't simply pick bits one by one. It's like lock and key: Lock

You can't simply open one pin and know if you are right. Lock will only rotate if all pins are correct. Otherwise it won't rotate. So while lock with one pin is as easy as trying that one pin, lock with two pins you already don't know which pin is wrongly set. Same happens with cryptography. One bit encryption doesn't let you see how it scales (so you assumed linear growth - wrong). It's not that you can pick each bit at once. You need to crack all at once. And somewhat like with lockpicking, cryptographic algorithm is broken when you find that some pins actually give you some hints as to what state of "lock" is.

axapaxa
  • 2,920
  • 10
  • 21
  • So... any reason for downvote? – axapaxa Feb 17 '17 at 14:21
  • Don't know, but I like the picture. :-) – 700 Software Feb 17 '17 at 14:29
  • 25
    I get your analogy but when picking a pin tumbler lock you certainly can do one pin at a time and generally know when any given pin is set properly. – Matt Feb 17 '17 at 16:48
  • 10
    @Matt not in ideal lock. Thats why I also gave analogy to breaking cipher and lock. Just as locks have their mistakes, ciphers do too (like infamous RC4). But of course, that analogy isn't perfect :) . – axapaxa Feb 17 '17 at 17:03
  • 5
    @axapaxa: If a lock does not endeavor to be pick-resistant, randomly wiggling the pins while engaging moderate tension will often cause them to latch at the right position. Security pins are harder to get into position while the lock is under tension, but even high quality locks often give a level of feedback about progress which would be totally unacceptable in a lock that could be probed multiple times per second. – supercat Feb 17 '17 at 18:21
  • @supercat Which is what lockpicks are for? – JAB Feb 17 '17 at 18:37
  • 2
    @supercat you are absolutely correct. non Pick-resistant might be considered close to security by obscurity (looks safe until you start poking around ;) ). I understand that my analogy isn't perfect (which i acknowledged before), but I hope you don't think perfect analogy was my intent (it wasn't). You understand both crypto and locks, my analogy was for people without crypto knowledge. Please don't derail topic by adding unnecessary details. I'm sure people who are interested in those topics will find interesting materials elsewhere :). – axapaxa Feb 17 '17 at 19:09
  • 2
    Sometimes Hollywood will make a password cracker guess 1 letter a time, and you see the progress wth each new letter. That's not how it works in real life. – Tim Feb 18 '17 at 04:21
  • @Tim: Unless you're cracking something like a [LM hash](https://en.wikipedia.org/wiki/LAN_Manager#Algorithm)... – user1686 Feb 18 '17 at 20:49
  • @Tim or WPS. Brute forcing WPS is really full of hollywood-drama cliche, first you guess the first half, then the second half!!! -> https://sviehb.files.wordpress.com/2011/12/viehboeck_wps.pdf – Gianluca Ghettini Feb 18 '17 at 22:38
  • 1
    As a child, I was nearly always able to crack the 4-digit chain combination locks (usually, on bikes) very quickly by feeling a slight increase in "give" for each dial when it was showing the right number. I was always surprised that most of the other kids couldn't feel what to me was a really obvious change in the amount of "play". But I've never been able to do that with similar combination locks on suitcases in later life. – FumbleFingers Feb 19 '17 at 16:02
  • @FumbleFingers sometimes the sound gives it away – Tim Feb 19 '17 at 20:49
25

So if at each bit he has a 50% chance, that means that 1 bit is actually only half bit.

And if he is very lucky, say 90% chance, that means that 1 bit is actually only 0.1 bit.So in face of a very lucky opponent, a 128 bit password has only 12.8 bit strength.

You're miscomputing how "luck" affects the number of bits. For a 50% chance, that does not multiply the number of bits by 0.5, it reduces it by log20.5 bits -- -1 bit. So that 128 bit key is only as strong as 127 bits when you only need a 50% of guessing it.

Similarly, for a "lucky" opponent of the 90% level, that reduces the key by log20.1, or about -3.3 bits. So that 128 bit key has been reduced to about 125 bits, not 12.8 bits.

Even with an an extremely lucky 1-in-a-million guess (like winning the lottery), that still only reduces it by log20.000001, or about 20 bits, still leaving you with more than 100 bits of security

Community
  • 1
Chris Dodd
  • 374
  • 2
  • 3
15

I'm not sure what you're trying to understand and if the other answers cover it, so I'm trying a different approach and interpret your question like this:

What if an attacker guesses the right sequence of 128 bits on her first try by pure chance?

That's certainly possible but so unlikely that we don't normally consider that possibility. If you want to consider this risk there's nothing you can do with cryptography since that is a matter of risk management which belongs into the field of economic sciences.

The likelihood of an attacker guessing the sequence of 128 bits of your encryption key correctly with just one brute-force attempt is 2-128. Since people are notoriously bad at imagining very small or very large quantities we can only grasp what that means in relation to other quantities of the same type.

Let's assume that every person on this planet (about 1010) attempts to guess your key at a frequency of 109 s-1 over the span of your life and the following 900 years (100 a + 900 a ≃ 1011 s) for a total of 1020 attempts over that time span. The chance that at least one of these succeeds is:

$$ 1 - (1 - 2^{-128})^{10^{20}} ≃ 3 \cdot 10^{-19} $$

If you think that risk might be too high for you think again, because the likelihood of dying due to a cataclysmic meteorite impact is estimated at roughly 10-5. That's about 1013 times as likely as the key guessing event and has an arguably much more severe impact (pun intended) on your and everybody's lives.

Conclusion: If you worry about your key being guessed at random by a ceaseless concerted effort of every human being from your birth till after your existence was likely forgotten you worry about the wrong thing. Stop researching cryptography and become an aeronautical engineer (or whatever you call someone who works on ways to avoid the collision of earth with huge space rocks)!

David Foerster
  • 889
  • 1
  • 6
  • 12
  • 4
    I read in a book about statistics that a real life event with a probability of 1 in 10^18 or 1 in 2^60 can be considered "impossible". One in a million chances happen daily to 100s of people. One in a trillion happen to someone every year. One in 10^18 doesn't happen. The real life event where a hacker tried crack a code and got it right in only 2^68 guesses _doesn't happen_. – gnasher729 Feb 17 '17 at 19:48
  • 2
    I think there's an implicit assumption that these $10^{10}$ guessers are guessing randomly. It's fine for imaging scales, but humans are notoriously bad random number generators. so the actual probability is likely even lower, assuming a truly random key to begin with. +1 for an excellent answer discussing probabilities. – jpmc26 Feb 17 '17 at 23:48
  • 2
    @jpmc26: It also assumes that the guessing people work randomly, meaning they don't coordinate their work. The same bit sequence may be guessed multiple times during that millennium. – David Foerster Feb 18 '17 at 00:32
  • 1
    See the Wikipedia article on [micromorts](https://en.wikipedia.org/wiki/Micromort) for getting some feeling of small probabilities. – Tgr Feb 18 '17 at 00:57
  • 1
    @gnasher729 I was taught in GCSE Chemistry that there was a general ratio for figuring out how fast a reaction happens. if the result was below 15 the reaction was considered to never happen. An example would be water boiling. At 20C, the reaction would have a rate of less than 15, so we consider it to never happen. However, individual molecules in the water could obtain enough energy to turn into water vapor. So parts of a system may happen, but the system as a whole is thought of the never change. – SGR Feb 20 '17 at 10:14
  • @gnasher729 I think you mean "a real life event with a _daily_ probability of 1 in 10^18". – JiK Feb 20 '17 at 10:41
9

So if at each bit he has a 50% chance, that means that 1 bit is actually only half bit.

No, it is not. Because 'bit' is a quantity of information we should know to reduce entropy twice by definition. The 50% chance was already considered there: entropy is a measure of uncertainty (something a priori) and has nothing to do with luck (something a posteriori).

Enr1g
  • 198
  • 2
  • 9
1

From computer point of view, there is no difference between "is lucky" and "knows password". You are Bob if You know Bob's password - that's very basic assumption of Kerckhoffs's principle and Bitcoin.

https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle

spam
  • 129
  • 1
1

So Far, None of these answers are at all answering what I atleast interpret the question to be asking, all I see are many answers berating the asker for their question, even the few that mention actually answering "What would happen?", Immediately switch to speaking about the improbability of it.

So, Ignoring the utter utter improbability of such a circumstance, it is still possible, so if it were to happen that an attacker were to guess the password significantly sooner than probability would dictate likely, and one would assume you were hoping for with the encryption, then:

They know the password, simple as that.

What happens after that depends on their original intent & Human Psychology, the two circumstances that come to mind for me are,

  • They use the password for their original intention and hack in, steal files, install malware, etc.

  • Or they, also knowing the probability of this event, literally can't believe their luck and proceed to waste time re-cracking the encryption, fretting over the clearly far better than expected security you have, continuing to eat the lunch they were in the process of eating while they waited because they expected it to take longer and haven't checked yet, or similar.

Though you would likely have a far better answer for those last options if you asked on a psychology or suchlike site.

SlipperyPete
  • 27
  • 2
  • 1
    (-1) The OP was asking about how his calculations (based on a misunderstanding about bits/probabilities) showed that a "lucky" attacker may actually succeed with pretty high probability, compared to how hard it is supposed to be. This question has nothing to do with human psychology, which is why all these other answers take a different approach than you. His question is not about what would be the real-life consequences if someone guesses correctly. – TMM Feb 19 '17 at 23:48
  • @TMM I wasn't trying to indicate that the question had anything to do with psychology, just the followup of the last section of my answer, and despite the OP's misunderstanding of the bit's/probabilities, I understood his question to be "What if attacker is lucky?" with the misunderstood math being an attempt to express this in probability terms. – SlipperyPete Feb 20 '17 at 08:08
0

So if at each bit he has a 50% chance, that means that 1 bit is actually only >half bit.

And if he is very lucky, say 90% chance, that means that 1 bit is actually only >0.1 bit.So in face of a very lucky opponent, a 128 bit password has only 12.8 >bit strength.

Everyone has a 50% chance at every bit. That doesn't make it effectively less than a bit of entropy. Think of each bit as a separate coin toss. No one is more or less likely than 50% to guess the result of a fair coin toss. The universe will not bend it's rules for anyone and give them a 90%. Your chances of correctly guessing the results of 128 subsequent coin tosses are 1 in 2^128.

Stephen Lujan
  • 109
  • 2
  • *"Your chances of correctly guessing the results of 128 subsequent coin tosses are 1 in 2^128."* That, of course, arguably assumes perfectly fair coin tosses, which is not the case in real life. I would argue that a CSPRNG generates output that is likely to be a lot less statistically biased than the average coin-tosser, let alone one who tries to game the coin tossing. – user Feb 18 '17 at 13:50
  • @MichaelKjörling That's because you're not using my theoretical perfect coin. :) Anyways I'm just trying to address what seemed like a fundamental misunderstanding in probabilities. When someone asks why the sky is blue, I wouldn't jump into an explanation of the physics behind Rayleigh scattering. I would be more likely to be understood if I just say that the air scatters blue light. I was trying to give the simplest possible explanation, which I felt the other answers didn't quite go for. – Stephen Lujan Feb 22 '17 at 15:24