Hatrack River Forum: Math puzzle (probably impossible)

This is topic Math puzzle (probably impossible) in forum Books, Films, Food and Culture at Hatrack River Forum.

To visit this topic, use this URL:
http://www.hatrack.com/ubb/main/ultimatebb.php?ubb=get_topic;f=2;t=053218

Posted by Lisa (Member # 8384) on :

I have a lovely puzzle at work, and I'm going to throw it out to you all before I even get started on it. On the chance that it's not impossible, and on the chance (better) that I fail to figure it out, maybe someone here will do better.

We have a list of ten PIN numbers (I know that's redundant, but it's common usage) we've created. And we have the database where the PINs are stored. But the application, which we don't have source code for (and are unlikely to be able to get) encrypts the PINs before storing them.

We're doing an app for a customer who uses this app, and they want us to use the native PINs. Which are encrypted. And we don't know how. You see the problem.

Personally, I think it's a waste of time to even try. The encryption I use personally for PINs when I'm coding stuff is one line of code, but it's still un-decryptable, for the simple reason that more than one input value can result in the same output value.

And even if it's possible, it may be that a sample of 10 PINs isn't enough. However, the co-worker with access to the app is gone for the weekend, so that's what I have.

code:

PIN     Encrypted PIN
7665	14178
6885	16377
9633	11160
0085	15571
4442	11945
6611	9137
2211	8733
5544	12066
8774	15269
9999	17520

Anyone want to take a poke at this? Or should I not even bother with it?

Btw, the encryption algorithm I use involves the ASCII value of the string representation of each number, as well as its location in the PIN. It's not complicated; but it works for me. It could be that this works along the same lines. That's one of the things I'm going to look for.

[ July 03, 2008, 06:42 PM: Message edited by: Lisa ]

Posted by fugu13 (Member # 2859) on :

Without some more knowledge about the algorithm, it won't be easy.

I'm surprised at the absence of standard hashing functions. These problems are well solved, and hand-crafted ones almost always have significant vulnerabilities.

Even without the source code, you could almost certainly decompile the binary and find the piece of code doing the hashing.

A few more examples would be good, but you might be able to get something out. If you suspect that sort of pattern, I'd just treat it as a set of data involving the digits and their positions as observations and do a principal components analysis. Any hash that's a linear combination of those should drop right out, and even if that isn't purely it, it should give you some hints.

And keep in mind that attackers don't need to decrypt it, they just need to find one PIN that hashes to the same thing and that will work with the application.

Posted by Papa Janitor (Member # 7795) on :

Reorder the digits 4231, then add 7521.

Posted by Lisa (Member # 8384) on :

I don't really know how to decompile code.

I tried summing the product of their ASCII codes and positions, and I got this:

code:

PIN     EncPIN  Result
2211	8733	17.71399594
6611	9137	18.09306931
9633	11160	21.37931034
4442	11945	23.33007813
5544	12066	23.0707457
7665	14178	26.40223464
8774	15269	28.3283859
0085	15571	29.71564885
6885	16377	29.99450549
9999	17520	30.73684211

I'm not concerned about the columns matching, obviously, since there could be a factor. I wanted to see if they'd fall into the same numerical order. And they almost do. So I think I'm on the right track. But I could play with this forever and never get anything.

How would you go about decompiling an executable? Or a DLL, which is possible. I haven't even looked at the installation yet.

Posted by Lisa (Member # 8384) on :

quote:
Originally posted by Papa Janitor:
Reorder the digits 4231, then add 7521.

Really?! Holy crow... that's amazing. How did you figure it out?

Boy, was I overthinking that one. That's brilliant. Papa, you are my hero.

Posted by Papa Moose (Member # 1992) on :

Well, I figured as long as it was only probably impossible, I might as well give it a shot.

First thing I noticed was the difference between the first two being 404, which made me figure it was just a reordering of the PIN plus some constant. I sorted the results, and could then see patterns in the PINs.

I like the idea of being brilliant, but I'm not sure this was it. *smile*

Posted by Papa Moose (Member # 1992) on :

Whoops -- It's 3241, not 4231. (I figured it out right, but didn't check when I wrote it down.) There goes the brilliant thing.

Posted by Lisa (Member # 8384) on :

No, it doesn't go. Why did 404 mean something to you? Normally, when I see a difference that's divisible by 9, I figure it's switched digits. But 404?

Posted by Papa Moose (Member # 1992) on :

404 caught my eye in conjunction with the 22 and 66 in the two codes. And I started with those two because they were the smallest resulting numbers.

Posted by Lisa (Member # 8384) on :

Huh. That's cool. And really helpful, too. Thanks so much!

Posted by scifibum (Member # 7625) on :

Yeah, actually...very smart. (I still don't get why 404, 22, and 66 got your attention. You're like Rain Man.)

And I must say that this is a terrible example of how to do encryption.

Posted by Mike (Member # 55) on :

Nice. Of course, if you know (or suspect) it's reorder-and-add-something, the 9999 is a dead giveaway.

Posted by Tante Shvester (Member # 8202) on :

quote:
Originally posted by scifibum:
You're like Rain Man.

Seriously.

Posted by Nighthawk (Member # 4176) on :

I gotta say, that's the dumbest form of "encryption" I've ever seen. Please tell me this isn't for a major financial institution or government agency...

Posted by Tante Shvester (Member # 8202) on :

Or at least tell him which one.

Posted by Sterling (Member # 8096) on :

So he can avoid it, or take advantage of it? [Wink]

Posted by fugu13 (Member # 2859) on :

Yeah, this is why strong hashes with a salt are very important.

And applications that need to authenticate against the same information should do so through the central app (though, like usual, this one probably wasn't made to make that possible).

Excellent deductive work, Papa Moose [Smile]

Posted by Lisa (Member # 8384) on :

quote:
Originally posted by Nighthawk:
I gotta say, that's the dumbest form of "encryption" I've ever seen. Please tell me this isn't for a major financial institution or government agency...

I can't tell you, but it's even odder than that. Still, the PIN is only used for ancillary stuff, so maybe they didn't think it mattered.

Still, I'm pretty amused.

Posted by Xann. (Member # 11482) on :

quote:
Originally posted by Nighthawk:
I gotta say, that's the dumbest form of "encryption" I've ever seen. Please tell me this isn't for a major financial institution or government agency...

Still, if he hadn't figured this out, no one was even on the right track.

Posted by Shigosei (Member # 3831) on :

quote:
Yeah, this is why strong hashes with a salt are very important.

You're making me hungry.