## Posts tagged ‘code’

### My Insecurity Over Security Codes

Every time I attempt to access one of my company’s applications via our single sign-on (SSO) system, I’m required to request a validation code that is then sent to my smartphone, and then I enter that code on the login page.

It’s a minor nuisance that drives me insane.

The purpose of the codes are to provide an additional level of security, but given how un-random the codes seem to be, it doesn’t feel very secure to me. This screenshot shows some of the codes that I’ve received recently:

Here’s what I’ve observed:

- Every security code contains 6 digits.
- The first 3 digits in the code form either an arithmetic or geometric sequence, or the first 3 digits contain a repeated digit.
- Similarly, the last 3 digits in the code form either an arithmetic or geometric sequence, or the last 3 digits contain a repeated digit.

As an example, one of the codes in the screenshot above is 421774. The first 3 digits form the (descending) geometric sequence 4, 2, 1, and the digit 7 appears twice in the second half of the code.

I believe the reason for these patterns is to make the codes more memorable to those of us who have to transcribe them from our phones to our laptops.

This got me thinking. The likelihood of someone correctly guessing a six-digit code is 1 in 1,000,000. But what is the likelihood that someone could correctly guess a six-digit code if it adheres to the rules above?

If you’d like to answer this question on your own, stop reading here. To put some space between you and my solution, here’s a security-related joke:

“I don’t understand how someone stole my identity,” Lily said. “My PIN is so secure!”

“What’s your PIN?” Millie asked.

“The year of Knut Långe’s death,” Lily replied.

“Who is Knut Långe?”

“A King of Sweden who usurped the throne from Erik Eriksson.”

“And what year did he die?”

“1234.”

(Incidentally, Data Genetics reviewed 3.4 million stolen website passwords, and they found that 1234 was the most popular four-digit code. The researchers claimed that they could use this information to make predictions about ATM PINs, too, but I don’t think so. All this shows is that 1234 is the most commonly *stolen* password, and therefore this inference suffers from survivorship bias. Without having data on all the codes that were *not* stolen, it’s impossible to make a reasonable claim. But, I digress.)

To determine the number of validation codes that adhere to the patterns I observed, I started by counting the number of arithmetic sequences. With only 3 digits, there are 20 possible sequences:

- 012
- 024
- 036
- 048
- 123
- 135
- 147
- 159
- 234
- 246
- 258
- 345
- 357
- 369
- 456
- 468
- 567
- 579
- 678
- 789

But each of those could also appear in reverse (210, 975, etc.), giving a total of 40.

There are far fewer geometric sequences; in fact, only 3 of them:

- 124
- 139
- 248

And again, each of those could appear in reverse, giving a total of 6.

Finally, there are 10 × 9 × 8 = 720 three-digit numbers with no repeated digits, which means there are 1,000 ‑ 720 = 280 numbers with a repeated digit. (Here, “number” refers to any string of 3 digits, including those that start with a 0, like 007 or 092.)

Consequently, there are 40 + 6 + 280 = 326 possible combinations for the first 3 digits and also 326 combinations for the last 3 digits, which gives a total of **326 × 326 = 106,276 possible validation codes**.

That means that it would be about 10× more likely for a phisher to correctly guess a validation code that follows these rules than to guess a completely random six-digit code. But said another way, the odds are still significantly against a phisher who’s trying to steal my code. And quite frankly, if someone wants to exert that kind of effort to pirate my access to Microsoft Word online, well, I say, go for it.

### Codes, Keypads, and Sequences

When my colleague Chris Meador says, “I’ve thought of a math problem,” rest assured that I’ll spend a good portion of that workday trying to find a solution instead of tackling the items on my to-do list.

Last week, he emailed me the following:

My garage door opener has an exterior keypad that allows me to open the door by entering a 5‑digit number. There is no ENTER key, so the keypad “listens” for the correct code and disregards a false start. How many key presses would it take to test every possible code?

Theoretically, there are 10^{5} possible codes, so entering all of them sequentially would require 5 × 10^{5} key presses. However — because the keypad ignores false starts — some key presses can be saved. For example, typing 123456 will actually test two codes, 12345 and 23456.

Chris continued by asking:

Is it possible to construct an optimal string of key presses of minimal length that tests every possible code?

And with that, my Tuesday was ruined.

I had seen this problem before, or at least a version of it. The top four students at the MathCounts National Competition compete in a special event called the Masters Round, and one year the problem was about something called **D Sequences**. The author used this nickname because such sequences of minimal length are known as *de Bruijn sequences*, after the mathematician Nicolas Govert de Bruijn who proved a conjecture about the number of binary sequences in 1946.

Luckily for Chris, he caught a nasty viral infection last week, which gave him plenty of time to lie in bed thinking about the problem. He emailed me on Monday to inform me of his progress:

I did not manage to prove anything, but I did write a computer program that generates sequences using a pretty straightforward algorithm, and I was able to confirm that solutions are possible for 2‑, 3‑, 4‑, and 5‑digit codes.

That note reminded me that the best way to ensure a happy life is to surround yourself with intelligent people who share similar interests. Chris concluded his email to me with this:

I’d say [that my garage] is pretty secure, since it would take me about 14 hours to punch in all the possible numbers, reading from a list.

Feel free to read more about **de Bruijn sequences** at MathWorld, but you might want to try the following problems first.

- Construct a de Bruijn sequence that contains every two-digit permutation of 0’s and 1’s.
- Construct a de Bruijn sequence that contains every three-character permutation from an alphabet with three characters.
- What is the minimum length of a string of letters that would contain every possible five-letter “word,” that is, every possible permutation of 5 letters, using the Latin alphabet?

Counting things is something that mathematicians, especially those studying combinatorics, do quite often. Yet how they count can be atypical:

When asked how many legs a sheep has, the mathematician replied, “I see two legs in front, two in back, two on the left, and two on the right. That’s eight total, but I counted every leg twice, so the answer is four.”

And there you have it.