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:
- 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.
- 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!
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.randomservices.org/random/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.