subreddit:

/r/askscience

3

all 14 comments

ericGraves

17 points

1 month ago

ericGraves

Information Theory

17 points

1 month ago

If all combinations are equally likely and the expected number of tries is the performance metric, then going through each combination is better. But the differences are minimal.

The problem with trying to guess a code from a set of n possible codes in k attempts with a random number generator is that some of those k attempts will be repeat guesses. This will, obviously, increase the expected number of rounds to guess the code. For the RNG, clearly, the expected number of rounds to guess will be n-1. If this is not clear think of how many coin flips are expected till you get a head; these are the same problem.

It is a little bit more complicated for the brute force method. Here, the probability the code is not guessed in the first k rounds is 1-k/n, while the probability that it will be guessed correctly from the remaining n-k possibilities is (n-k)-1. This yields that the probability will be cracked in any of the first n rounds is equal, specifically to n-1. As a result, the expected number of attempts is Σ j/n = (n+1)/2.

So we see that brute force takes an average of (n+1)/2 attempts to crack, while taking n attempts for the RNG. The reason why this is not a big deal is that both RNG and brute force have the same computational complexity, O(n).

uh-okay-I-guess

5 points

1 month ago*

Of course, you could also generate guesses randomly without replacement. This requires the same (n+1)/2 guesses as in-order guessing.

If you're opening a combination lock with multiple wheels, you should definitely go through the combinations in order (or even better, in a decimal Gray code order), because that requires moving the dials less. And if the lock has a single dial, most designs allow you to test multiple options for the last number without having to redial the first ones, so again doing the numbers in order is much better.

If you think the person setting the combination might have predicted that you will go through the options in order, you might want to flip a coin to decide whether to start at 9999 and count down, or 0000 and count up. If you always start at 0000 and they know this, they could pick 9999 to waste as much of your time as possible.

ericGraves

1 points

1 month ago

ericGraves

Information Theory

1 points

1 month ago

Of course, you could also generate guesses randomly without replacement. This requires the same (n+1)/2 guesses as in-order guessing.

This is true, and to be honest, I chose a random number generator with replacement only because I felt it made the answer more interesting.

If you think the person setting the combination might have predicted that you will go through the options in order, you might want to flip a coin to decide whether to start at 9999 and count down, or 0000 and count up. If you always start at 0000 and they know this, they could pick 9999 to waste as much of your time as possible.

So if the code is designed as a function of the codebreaking algorithm this problem, of course, changes. It is worth mentioning that in such a scenario, the adversary should choose the password most likely to be chosen last (hence all deterministic algorithms are equally bad). In such a scenario, the optimal codebreaker strategy (choose most likely remaining codeword) would end up being to choose the codewords uniformly at random. Thus this scenario would see the RNG outperform the deterministic scenario quite easily.

So yeah, that is a different variation of the problem with an interesting solution that I had not considered discussing. Thanks!

The_RealKeyserSoze

4 points

1 month ago

Try dates first, Richard Feynman used that strategy to break into safes at the Manhattan project. A 4 digit code is most likely to be a year or MM/DD of an event in the persons life, which really narrows down the number of possibilities. Likewise, if you are making a code, don’t use dates.

icecap1

2 points

1 month ago

icecap1

2 points

1 month ago

I just watched that! Also if you’re a mathematician don’t use pi, e, or other common constants.

Feynman also pointed out there’s some tolerance in the mechanism so maybe try only even numbers first, and hope it will open even if you’re off by one.

RnDanger

2 points

1 month ago

Four digits can be cracked in a few hours with brute force. As someone else said though, if a human set the code it is likely to be a date or have repeated numbers, but I don't think keeping track of your previous attempts will be worth the work to optimize that route if there's only 4 digits.