A company uses a set of locks to secure their employees' offices. Each lock can be operated by a key distinct from other locks (the office holder's key) as well as a master key that is common to all locks. Each lock has 7 pins (7 positions on the key), and each of these positions has 6 possible cut depths. Any user's key can be represented as a series of these depths, e.g. 3-4-1-6-6-2-3. The master key can also be represented this way; let's say the master is: 5-2-3-4-2-6-1. There are two rules for users' keys:

  1. For each position, the user's code cannot be the same as the master key. E.g., no user could ever have a key that has a 5 in the first position.
  2. A user's code for any given position cannot be +/- 1 off from the master. E.g. in the first position, a user key cannot be 4 or 6. In the last position, a user's key cannot be 2.

Now consider a malicious insider, Eve, who can obtain access to other peoples' keys, but not the master key. Eve wants to determine the master key code. Suppose Eve samples legal user keys uniformly at random, without replacement (but the answer with replacement would be good, too, if it's simple).

Is it possible to determine approximately how many keys would Eve need to examine to have, say, a 50% chance of knowing the master key exactly by process of elimination? 90? We are not allowing Eve to make an attempt on the master lock before she is sure what it is.

A computational solution is welcome!

  • $\begingroup$ Does 50% mean "over the randomness of the keys, there is a 50% chance that the master key uniquely follows from these user keys"? Or does it also include Eve's potential "guess" success rate at the end, in case the master key is not yet uniquely determined? $\endgroup$ – TMM Apr 17 '17 at 2:19
  • $\begingroup$ Have you tried a Monte Carlo approach yourself to estimate the solutions? It should not be too hard to implement the whole procedure. $\endgroup$ – TMM Apr 17 '17 at 2:58
  • $\begingroup$ I wonder whether there's a clever insight that shortcuts this, but of course I am willing to do a simulation myself and will post the code when I do so. $\endgroup$ – Ben Golub Apr 17 '17 at 3:03

The key (no pun intended) is that each position gets 'scanned' by the random generation of user keys independently of the others.

Take the first position. The question is, how long do we have to wait until, in that position, we get each of the four or five legal non-master depths realized. Then we know what the master must be. I'll take five depths to eliminate as the worst case.

This is related to the Coupon Collector's problem (in each position): https://en.wikipedia.org/wiki/Coupon_collector%27s_problem The Wikipedia article provides good upper bounds on how long we must wait for all the legal depths in a given position to be observed.

As a very crude upper bound, I used http://www.math.uah.edu/stat/apps/SpecialCalculator.html with m=5, k=5 (5 possible non-master depths, want to see each of them) and putting in x=25 I see that after 25 samples I have a better than .98 probability that all five depths in a given position have been realized and this position has been solved.

Because the positions are independent, the probability that I have solved all 7 positions after 25 tries is (.98)^7 is 87%. You can play around with the numbers to figure out what is needed for a 50% lower bound on the probability of knowing the master (I get 18 keys) and for a 95% lower bound (I get 30 keys).

These numbers of keys are conservative (worst case) because they are designed for the 11...1 or 66...6 keys - they assume that only one depth is illegal, in which case it takes longer to identify it.

  • $\begingroup$ You should take into account that in each position, there is a 2/6 chance of getting 4 legal user positions and a 4/6 chance of having only 3 legal positions. There are never 5 depths to be realized, so your calculations are off regardless. $\endgroup$ – TMM Apr 17 '17 at 12:32
  • $\begingroup$ And this approach only givesyou an approximation. If I draw a 3 in position 1 for the user key, I can eliminate 2,4 as well, eliminating three positions. If I then draw a 5 or 6, I know the master key is a 1, while if I draw a 1, 2 or 4 I only elimininate one position. The coupon adjacencies makes them dependent and so this cannot be accurately modeled via a CCP. $\endgroup$ – TMM Apr 17 '17 at 12:36
  • $\begingroup$ Good point! That was lazy/sloppy! $\endgroup$ – Ben Golub Apr 18 '17 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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