20
$\begingroup$

I understand this may not be the best place to ask a question like this, but I believe that this community may be the best/only place I can ask such a question.

I have inputs and outputs from an in-house hash developed years ago and the developer is no longer working with us any more. I need to determine the process that is the hash. Before you mention how this may be impossible, it appears to be a relatively simple hash and I have a few theories that appear to get me started in the right direction. First, the data:

 Input   Hash
1293239 EHELKHE
1331487 ILZXFZF
1320709 IKYJXWH
1328166 GUVUMMY
1156693 HFXLFYZ
1313273 ELHZLZV
1287367 GKDMWGM
1318623 EHDHYYF

This does not appear to be a very good hash, in my opinion. For starters, the output length matches the input length, this may be coincidence though. The main thing that catches my eye is that the output characters seem to all exist in a particular pool of possibilities. Here's a list of unique output characters: DEFGHIJKLMUVWXYZ. This lines up exactly with the hex values of 0123456789ABCDEF, in fact, in ASCII values, the two sets are 20 off from eachother. So I hypothesis:

D = 0
E = 1
F = 2
G = 3
H = 4
I = 5
J = 6
K = 7
L = 8
M = 9
U = A
V = B
W = C
X = D
Y = E
Z = F

From there, I'm out of ideas. I've compared the hash results with many standard hashes and have seen no correlation and have determined that it is most likely an original process. I've played with the numbers as best as I can and I have made no progress. What techniques are available to analyze this hash?

Improve this question
$\endgroup$
5
  • $\begingroup$ So you have 7*4 = 28 bits of output here. $\endgroup$
    – Paŭlo Ebermann
    Aug 3, 2011 at 21:20
  • 2
    $\begingroup$ This is technically off topic, based on question #3 in the FAQ. But... we can have fun every once in a while, right? $\endgroup$
    – John Gietzen
    Dec 5, 2011 at 23:17
  • $\begingroup$ @JohnGietzen, Which FAQ are you talking about? crypto.stackexchange.com/faq? $\endgroup$
    – Pacerier
    Nov 21, 2014 at 6:17
  • $\begingroup$ @Pacerier, this question is 3 years old. $\endgroup$
    – John Gietzen
    Nov 21, 2014 at 20:03
  • $\begingroup$ @JohnGietzen, So what was #3 of that FAQ talking about? $\endgroup$
    – Pacerier
    Nov 22, 2014 at 6:50

3 Answers 3

Reset to default
34
$\begingroup$

You are correct that it is a "bad hash". In fact it is not a hash at all. I've worked at a company that used a slightly different scheme for obfuscating database keys/numbers in URLs. And I also worked for another company that used a scheme that looked surprisingly similar for unlock codes for electronic devices.

The formula for converting "hashes" back into inputs looks like:

  1. Take the "hash" (column "hash" below") and use your substitution cipher (E goes to 1, etc) to turn it into hex (column "subs" below).

  2. Convert the result into decimal (column "to dec" below).

  3. You have an 8 digit number, swap the first and last half of the digits (column "swap" below).

  4. Divide the result in 3 by 13 to obtain the customer id (column "divide" below).

"hash".....subs......to dec......swap.....divide
EHELKHE - 1418741 - 21071681 - 16812107 - 1293239
ILZXFZF - 58FD2F2 - 93311730 - 17309331 - 1331487
IKYJXWH - 57E6DC4 - 92171716 - 17169217 - 1320709
GUVUMMY - 3ABA99E - 61581726 - 17266158 - 1328166
HFXLFYZ - 42D82EF - 70091503 - 15037009 - 1156693
ELHZLZV - 184F8FB - 25491707 - 17072549 - 1313273
GKDMWGM - 3709C39 - 57711673 - 16735771 - 1287367
EHDHYYF - 1404EE2 - 20991714 - 17142099 - 1318623

For folks who might find this in the future, it helps to make a spreadsheet and multiplication tables (customer id * 1 through customer id * 50). Formulas like these are usually simple linear formulas like $mx + b$, sometimes with a modulo involved (such as $mx + b \mod c$). And sometimes with "junk" digits added to make things harder to reverse engineer.

D.W.'s idea of "chosen plaintext" attack is also a good one. If you had pairs of customer id and "hashes" that varied by a single digit in the customer id, that would probably make it easier to attack.

And "security by obscurity" is no security at all. I spent about 2 hours avoiding homework tonight.

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ So it is better called encoding than hash. It has a kind of checksum build in, by making every number divisible by 13. Nice find. $\endgroup$
    – Paŭlo Ebermann
    Aug 5, 2011 at 14:22
  • 5
    $\begingroup$ Wow, that works great! It also works on a few of the values I didn't mention in the list. It may have been a little underhanded, but it left me a way to blind test any answers people would post. One piece of info about step 3, if you have less than 8 digits, pad the left side with 0s before swapping. Thank you so much. $\endgroup$
    – user316
    Aug 5, 2011 at 15:26
  • $\begingroup$ Is there a name for this encoding? $\endgroup$
    – Corey Ogburn
    Feb 23, 2012 at 20:07
  • $\begingroup$ @CoreyOgburn, it is more of an obfuscation than anything else. I don't know of any official name for it, but most of the "math" is the same thing used for linear congruential generators for PRNG. en.wikipedia.org/wiki/Linear_congruential_generator $\endgroup$
    – Tangurena
    Feb 24, 2012 at 18:35
  • $\begingroup$ @Tangurena, You spent 2 hours breaking it? $\endgroup$
    – Pacerier
    Nov 21, 2014 at 6:19
9
$\begingroup$

I agree that reverse-engineering the binary code might be a worthwhile approach.

Another option is to try a chosen-plaintext attack. e.g., try hashing 0000, 0001, 0002, ..., 0009, 0010, .., 0090, .., 1000, .., 9000, and see what you can learn from that.

Improve this answer
$\endgroup$
6
$\begingroup$

Since the input is base-10 and the output is base-16, the output actually looks bigger than the input.

Do you have access to a binary code implementation? Disassembling or debugging that would be easiest.

How many hashed pair samples do you have access to? Can you generate more with chosen inputs?

What was the skill set and mindset of the developer who built it? When did he make it?

Is this a software license key crack? :-)

EDIT: Since it's compiled C++, you can disassemble or debug the executable to extract the algorithm. This will always be easier than attempting to reverse it as a black box.

Hint: To find crypto code, look for XOR instructions where the operands are not the same register to itself. If you find magic constants being used, do a web search for them. They may tell you exactly which algorithm is being used.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't know anything about the previous developer, but I know that his code was added to the site years ago. It's not a license key crack, we use it to individually reference IDs (the input) without revealing the IDs when they make it to the website. $\endgroup$
    – user316
    Aug 3, 2011 at 16:04
  • $\begingroup$ The site is rather messed up honestly. It's compiled C++. Hence why we're replacing it with something better. We don't have the source, just the business requirements. The problem is that it needs to work with existing data in our DB. So I have to recreate the hash. $\endgroup$
    – user316
    Aug 3, 2011 at 16:22
  • 1
    $\begingroup$ @user316 - there is another solution. You could just get a list of the values you need hash's for and compute them with the old code. Then migrate the data for the new site that way. $\endgroup$
    – Chad
    Aug 3, 2011 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.