The Friday Fragment
Since it's spring break (and I'll be kayaking tomorrow), this week's Friday Fragment comes to you a day early.
This Week's Fragment
Mark Dupe has forgotten his Linux password. But he has done two (insecure) things that should make it easy to hack his way back in: 1) his password is always his user name, followed by a two-digit number (he "rolls" it), and 2) he has a readable backup of his /etc/shadow file. Here is the entry for his account:
markdupe:$6$mLo3uqlc$EM4O2X5zaUo.zWzZW2Ksz.IZyxKL6cz0DIjd.wJB3s.6uuKQ7K7/ 3cSz3eEL3D0VXzgbmtxSlkeoZLGYMIp89/:14706:0:99999:7:::
Can you write code or a script to determine his password?
If you want to “play along”, post the password and/or code as a comment or send it via email. To avoid “spoilers”, simply don’t expand comments for this post. Mark will thank you, at least until someone else hacks into his account.
Last Week's Fragment - Solution
Last week's puzzle required correcting a check routing transit number (374088048) and/or credit card number (4754 2700 7476 257_x_) from a torn slip of paper handwritten by Pierre Lefebvre. I received some excellent responses on this; see the comments for last week's post.
As Joel Odom pointed out, you can plug in possible digits until you get a valid checksum. Credit card numbers use a mod 10 checksum (the Luhn formula), where you double alternate digits, add the digits of the products, and then add these to the other digits. The total should be evenly divisible by 10.
For 4754 2700 7476 257_x_ (where x is the missing digit), the alternate "doubled" digits are:
(4*2), (5*2), (2*2), (0*2), (7*2), (7*2), (2*2), (7*2) or: 8, 10, 4, 0, 14, 14, 4, 14
adding the digits of the products: 8 + 1+0 + 4 + 0 + 1+4 + 1+4 + 4 + 1+4 = 32 adding in the alternate ("un-doubled") digits gives: 32 + 7 + 4 + 7 + 0 + 4 + 6 + 5 = 65
To make this an even multiple of 10, that last missing digit must be 5 (65 + 5 = 70), so the credit card number is 4754 2700 7476 2575.
The routing transit number was a bit trickier because there wasn't a missing digit, and I didn't specify exactly what was wrong. But routing transit numbers follow strict rules; for example, the first two digits have to be within certain ranges that identify the Fed district, credit unions/thrifts, special types of checks, etc. As Joe Richardson pointed out, Wikipedia is right on this one, and from their article you can determine that a valid RT can start with 3, but cannot start with 37.
To find the correct second digit (3_x_4088048), we use a routing/transit mod check. It's similar to the credit card algorithm, except that it uses weights: 3, 7, 1, repeating (many check old-timers know 37137137 by heart). Wikipedia and IRS publication 1346 document this, among other places. Here, too, when running a mod check against all the digits, the remainder must be evenly divisible by 10. So, we have:
((3*3) + (x*7) + (4*1) + (0*3) + (8*7) + (8*1) + (0*3) + (4*7) + (8*1)) % 10 = 0 or ((9 + 7_x_ + 4 + 0 + 56 + 8 + 0 + 28 + 8 ) % 10 = 0 or ((7_x_ + 113) % 10 = 0
Plugging in values for x, we see that
(((7 * 1) + 113) % 10 = 0
So the second digit should be 1, and the correct routing/transit is 314088048.
Kudos to Joe Richardson for correcting the routing/transit, and further determining that this belongs to the memorable Alamo Federal Credit Union. His Rescue 5 product can correct these and other account problems automagically. Joe also determined that the credit card number is a rebate card issued by MetaBank. Right again: it's an old rebate card of mine that I've used up.
As Joe pointed out, there are good implementations of both check digit algorithms readily available on the net, in almost every language imaginable. Even Wikipedia has several, but be careful: their routing/transit code is wrong. It seems Wikipedia is continuing their tradition of posting bad code; see another example I pointed out in an encryption research paper.
One big question remains: how did Inspector Lestrade solve this so quickly in his head? Frankly, I think he was bluffing about the Visa number. That calculation is simple, but usually does require pencil and paper to get it right. We would all be very impressed, however, if he memorized all the routing/transit rules and could do weighted mod checks in his head.
Well, Lestrade had an advantage: he recognized from the name (Pierre Lefebvre) and handwriting that the second digit was a 1, not a 7. In handwritten French, ones (_1_s) look like sevens (_7_s), which is why the French put an extra line through sevens to distinguish them. From the Sherlock Holmes stories, it's questionable whether Lestrade even understands the French language, but he certainly would have recognized the handwriting.