20
$\begingroup$

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?

Improve this question
$\endgroup$
18
  • 14
    $\begingroup$ $2^{128}=340282366920938463463374607431768211456$ $\endgroup$
    – Ruggero
    Commented Feb 17, 2017 at 11:00
  • 42
    $\begingroup$ 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}$. $\endgroup$
    – TMM
    Commented Feb 17, 2017 at 11:47
  • 23
    $\begingroup$ 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. $\endgroup$
    – nasukkin
    Commented Feb 17, 2017 at 18:23
  • 13
    $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Feb 17, 2017 at 19:43
  • 6
    $\begingroup$ 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. $\endgroup$
    – Akshat Mahajan
    Commented Feb 17, 2017 at 20:18

8 Answers 8

Reset to default
25
$\begingroup$

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

Improve this answer
$\endgroup$
74
$\begingroup$

"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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – e-sushi
    Commented Feb 18, 2017 at 13:56
42
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • 25
    $\begingroup$ 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. $\endgroup$
    – Matt
    Commented Feb 17, 2017 at 16:48
  • 10
    $\begingroup$ @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 :) . $\endgroup$
    – axapaxa
    Commented Feb 17, 2017 at 17:03
  • 5
    $\begingroup$ @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. $\endgroup$
    – supercat
    Commented Feb 17, 2017 at 18:21
  • 2
    $\begingroup$ @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 :). $\endgroup$
    – axapaxa
    Commented Feb 17, 2017 at 19:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tim
    Commented Feb 18, 2017 at 4:21
15
$\begingroup$

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)!

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Feb 17, 2017 at 19:48
  • 2
    $\begingroup$ 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. $\endgroup$
    – jpmc26
    Commented Feb 17, 2017 at 23:48
  • 2
    $\begingroup$ @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. $\endgroup$
    – David Foerster
    Commented Feb 18, 2017 at 0:32
  • 1
    $\begingroup$ See the Wikipedia article on micromorts for getting some feeling of small probabilities. $\endgroup$
    – Tgr
    Commented Feb 18, 2017 at 0:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – SGR
    Commented Feb 20, 2017 at 10:14
9
$\begingroup$

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).

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ (-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. $\endgroup$
    – TMM
    Commented Feb 19, 2017 at 23:48
  • $\begingroup$ @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. $\endgroup$
    – SlipperyPete
    Commented Feb 20, 2017 at 8:08
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "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. $\endgroup$
    – user
    Commented Feb 18, 2017 at 13:50
  • $\begingroup$ @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. $\endgroup$
    – Stephen Lujan
    Commented Feb 22, 2017 at 15:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.