A random math question.

[brooksmoses]

So, suppose you've got one of those electronic push-button combination locks, with (say) four-digit passcodes, and you want to try to unlock it by going through all the passcodes sequentially. Assuming you enter the passcodes independently, you've got 10 possibilities for each digit, so you need to enter 10⁴ passcodes, so 40,000 button-pushes are required.

However, in practice the locks are designed not to get too confused by random inputs. A simplistic way of implementing such a thing that seems consistent with observed behavior of some real-world locks is to unlock at any point when the last four button pushes correspond to the correct passcode. This means that, for instance, if you push "1 2 3 4", and then push "5", it will unlock if the passcode is 2345. Thus, with the ten button presses "1 2 3 4 5 6 7 8 9 0", you can try the seven distinct passcodes 1234, 2345, 3456, 4567, 5678, 6789, and 7890.

Thus, the question: Given such a lock, what is the minimum number of button-pushes required to try out all of the passcodes, and how do you generate an ordering of button-pushes to do that?

An obvious lower bound is 10,003 -- you need three at the beginning that don't test anything, and then after that you can test no more than one new passcode per push, so at least 10,000 for all of them. But it's not immediately obvious (to me, anyway) that a sequence exists that will run through all of the passcodes without duplicates. Thus, the question is to either generate such a sequence, or to generate a minimal sequence and prove that it's minimal.

Comments

[suzanne.livejournal.com]

Love you. Just saying.

[technolope.livejournal.com]

There was an article in 2600 a few years ago that tackled that very same problem. The answer wasn't 10,003, it was somewhat higher, but not extraordinarily high. I don't have a reference to the article, though.

[novalis.livejournal.com]

you want this (http://en.wikipedia.org/wiki/De_Bruijn_sequence)

[brooksmoses]

Thanks! That's nifty -- and rather entertaining that whoever wrote that page used my exact problem as an example.

(The funny thing is, yes, I had a lock in question that I was thinking about when I wrote it -- but it actually only has five buttons, labeled "1|2", "3|4", "5|6", "7|8", and "9|0", which dramatically shrinks the search space.)

[aquaeri.livejournal.com]

Yes, I knew that's what he wanted but couldn't remember the name.

[cjsmith.livejournal.com]

I think it is almost eerie that I was imagining this same problem a day or two ago (while looking at the alarm panel in my house). Fun and amusing, but also almost eerie. :-)

[seawasp]

I find it interesting that it works that way. If *I* were installing a security lock, I want it to open when you input the code, not when you input the code contained in a friggin' string of random numbers.

In fact, I want you to have three chances to input the code, and then the lethal gas is released and the automated machine-gun emplacements fire. If you make a mistake, you hit the *clear* button and try again.

[tiger-spot.livejournal.com]

The code box I use regularly requires that you push "#" after you input the code. No lethal gas, though; it's outside so it would only dissipate and inconvenience the other commuters.

[suzanne.livejournal.com]

"In fact, I want you to have three chances to input the code, and then the lethal gas is released and the automated machine-gun emplacements fire. If you make a mistake, you hit the *clear* button and try again."

That might be difficult to get past the inspectors, but it does have a certain old-world charm.

[brooksmoses]

And then I demonstrate why you probably don't actually want that, by waiting until you leave the house, and then entering two wrong codes and a random number.

Actually, I don't think you want a "clear" button either. I've just demonstrated that you pretty much need to habitually hit the "clear" button before entering the rest of the code. Now, consider that the only thing that makes it a "clear" button is a label that you read; the software and action to press it are the same. Thus, you functionally have a five-digit base-11 code where anyone who's trying to break in knows the first digit and can eliminate one possibility from the other four digits. If you're going to dedicate the hardware to supporting this, there is absolutely no reason not to simply support any arbitrary five-digit base-11 codes, and avoid giving the attacker that information.

And that same logic will get you from a 3-digit base-9 code with a clear button up to a 4-digit base-10 code like I specified, too. The fundamental point is that using up a button and a "is-this-right?"-check for a dedicated "clear" operation is not the most effective use of your programmable hardware.

[seawasp]

Um, how did you demonstrate I don't want that?

Your way: infinite retries until, eventually, you get in.

My way: three chances to get in, if you fail... YOU WILL BE EX-TER-MIN-AT-ED!

Obviously aim the lethal weapons such that they don't damage my precious house, of course. If it's an indoor security lock, use something like electrical charges. Or laughing gas. Or an army of trained weasels to run up your jockey shorts.

Your way: you can enter a string of numbers and try multiple codes in succession to break my security.

My way: If you don't actually know my code, you have to enter each individual code, in full, at a time. No freebies, no riding on prior work.

Yours is VASTLY less secure. It allows you to try forever until you succeed, and allows you to design test sequences which will much more efficiently run through the combination.

Where you get the idea that you know the first number, I don't know. Because you don't.

[zwol.livejournal.com]

No, he's entirely right (ignoring the "three strikes and you're dead" mode, which nobody actually wants). Lemme take a whack at explaining it.

If the door unlocks when the last four digits are the code, no matter what previous keypresses are, then you can crack the machine with a De Bruijn sequence of 10,000 keypresses.

If you have to hit "clear" before the machine will accept a new four-digit number, then you can crack the machine by trying all possible combinations of four-digit numbers, which is 50,000 keypresses (counting the "clear" before each one).

But, if the machine wants a five-digit sequence, and doesn't care about history, then you can crack it with a De Bruijn sequence ... of 100,000 keypresses. Twice as hard as your system.

[brooksmoses]

Okay, let me try again, because there are two separate questions, and I apparently didn't distinguish them clearly enough.

First, there's the "infinite tries" vs. "finite tries" question. The general problem with "finite tries" is that I can basically DOS you out of your house by entering wrong numbers. If it's not safe to enter too many wrong numbers, I can set a little remote-control robot to do it -- and, if your trap is as powerful as you say, then it's probably worth the bother just for the fun of watching it go off. And then you have to buy more weasels and laughing gas.

Furthermore, what do you do after the weapons go off? Do you allow more tries -- in which case I can intentionally set it off from a distance and then safely try again? (Or, alternately, even if it's too slow to do that, I can really run up your weasel-and-laughing-gas bill overnight.) Or do you not allow more tries, in which case I've just locked you out of your house?

(Similarly, if I know your PayPal account name, and if PayPal is still doing their "lock you out and make you reset your password if you try too many times", I can trivially make you have to reset your password by entering enough bad passwords. At one time, if you mis-answered your security question to reset your password, they locked you out of that, too, and you had to fax in documentation. This is a much more practical application of this principle -- do you really want your PayPal security such that I, knowing only your email address, can lock you out of your account?)

Now, I hypothesized that we'd settled this first question in the direction of allowing infinite tries. The second, rather more interesting question is whether you require entering clear between each of those entries.

If you require entering clear before each entry, and you think your passcode is 1234, then you effectively have a five-button passcode. Your real passcode is "clear 1 2 3 4".

Now, let me take your lock, and take a sticker that says "A" (hexadecimal for 11), and put it on top of the "clear" button. I don't change the lock hardware in any way.

That changes your lock into a lock with the following features: (1) The buttons I have to push are all numeric, and I have to push five of them in sequence to enter the passcode. (2) The passcode is A1234, but I don't know that. (3) If I enter that passcode anywhere in the middle of any arbitrary string of numbers, the lock will open.

Moreover, because of the way things are set up, the lock also has these features: (4) I know the first digit of your passcode must be A. (5) I know that none of the other digits of your passcode are A.

(I know both of these because I am the one who stuck the "A" sticker on your "clear" button, remember? That's where I got the idea that I know the first button in the passcode. It has to be "A".)

So, given all this, why would you ever want a lock that has restrictions 4 and 5? If you are willing to put in the expense for an extra button, why label it "clear" instead of "A" and thereby tell me exactly when to press it in the sequence? And if you are willing to press a five-button sequence to get in, why make the first button always an obvious-to-anyone "clear" rather than some unknown digit? Why not just change the programming of your 8-bit microcontroller a little -- keeping the same exact hardware except for the label on that one button -- and allow arbitrary five-digit base-11 passcodes (with no clear button), thereby making it even harder to find the sequence?

I don't see any benefit at all -- either in ease of use or in cheaper hardware -- for having a clear-plus-four-digit base-10 passcode versus having a five-digit no-clear base-11 passcode.

So I would consider it clear that, given an infinite number of tries, if you are willing to "pay" for the extra cost of adding the "clear" button to a four-digit base-10 passcode, you would be willing to upgrade to a five-digit-without-clear base-11 passcode because there it's exactly the same cost as adding the "clear" button. Since the latter is significantly more secure than the former, I don't see why you'd want the former.

[seawasp]

Firstly, there's a lot of systems -- most of the ones I've used over the years, in fact -- that have the X tries and You Are Dead approach, with X most commonly being 3. So your idea that no one would want such a system is... odd, to say the least. No computer system I've ever used (since the Good Old Days, anyway) would allow infinite retries, or even large numbers of them -- SPECIFICALLY to prevent this kind of "I'll get your password EVENTUALLY, my pretty!" attack.

There's any number of ways to deal with the "Bozo triggered my lock-out" trick; I have a special key that I can use to reset it, your lock-out alerts me and I can then do a remote reset, it will reset itself after some period of time (that I know and you do not), etc. It all depends on why you have the security set up and what your priorities are. The BEST security is still loyal human beings, but that's expensive and difficult to arrange. But I don't need to worry about keypunches on them.


Second, your "your password is Clear 1234" is just flat wrong. The password is 1234, and I can get in by entering those four digits, NO clear needed. Unless I screw up. Clear is only for "I started entering and I realized I messed it up and I want to back up before I enter a WRONG 4 digit code".

So no, I'm not willing, in your terminology, to press a five-button sequence to get in; I have a 4 digit sequence to get in with a button that lets me reset if I realize in time that I hit the wrong button. Moving your hypothetical to a 5 digit sequence with a known first number isn't equivalent.

[mapache]

But how do you know it's in a state where you don't need to push clear? If anyone entered anything while you weren't there, the system is in an unknown state, and you need to clear it, as you could be one keypress away from locking yourself out. If you're somehow introducing timing so that it auto-clears after a set period of time, then we just complicated the hardware.

And, as to the x-fails-equals-lockout, the correct way to implement this without allowing intentional DOS-via-lockout is to require exponential backoff. That is, screw up once, and you can try again. Screw up twice, and you have to wait a few seconds, keep screwing up, and the retry period increases up to some set max, then decays when left alone. (For a single-point-of-access system, like a door lock, this prevents brute force attacks while also preventing DOS lockouts. For a system like a password on a website, which can be accessed from multiple locations, you can still DOS it by keeping up a constant stream of bad passwords instead of stopping, so that's why you have to put in by-source lockouts too, at which point the attacker escalates to DDOS and now you have a real problem where you have to choose between allowing brute force attacks or locking out users.)

[seawasp]

How do I know? I'd presume the way I know on the ACTUAL security systems I use every day: I can see on the little LCD screen that there are entered symbols. I can't tell what they are, naturally -- they show up as asterisks, etc. -- but I can certainly tell. So if someone else had entered a partial code and left without clearing, it'd be obvious on the little screen.

And I hope you won't tell me you wouldn't have a screen because it's too complicated. Such screens are on every security system I've had to deal with in the past five years, at least, ranging from the one we use to secure the building at work to the POP/Debit Card stations at the supermarket. You need such feedback to make sure you actually hit the buttons correctly, etc. Standard interface design.

[tiger-spot.livejournal.com]

The code box on the bike shelter at the train station doesn't have a screen.

[brooksmoses]

The 4-digit-code elecronic lock on my mom's house that I was thinking of when I came up with this question doesn't have a screen, either. Nor does the one on the doors of my grandfather's Lincoln. Those are the types of systems I was thinking of; the ones you're thinking of are different, and I don't actually recall seeing one attached to a physical lock, though I suppose I have on an industrial/business installation somewhere.

(Beeping seems to work equally well as feedback to indicate that a button has been pushed, and a little piezo is a fair bit easier to drive than an LCD.)

I'll grant that if you have a screen or other indicator of the number of buttons already pressed, the analysis is somewhat different. In particular, that interface already presumes that you have a well-defined start to the sequence that you're matching against the passcode, so you need the "clear" button to tell the display's digit-counter how to work.