Java convert hash to random string

Question

I'm trying to develop a reduction function for use within a rainbow table generator.

The basic principle behind a reduction function is that it takes in a hash, performs some calculations, and returns a string of a certain length.

At the moment I'm using SHA1 hashes, and I need to return a string with a length of three. I need the string to be made up on any three random characters from:

abcdefghijklmnopqrstuvwxyz0123456789

The major problem I'm facing is that any reduction function I write, always returns strings that have already been generated. And a good reduction function will only return duplicate strings rarely.

Could anyone suggest any ideas on a way of accomplishing this? Or any suggestions at all on hash to string manipulation would be great.

Thanks in advance

Josh

Answer 1

So it sounds like you've got 20 digits of base 255 (the length of a SHA1 hash) that you need to map into three digits of base 36. I would simply make a BigInteger from the hash bytes, modulus 36^3, and return the string in base 36.

public static final BigInteger N36POW3 = new BigInteger(""+36*36*36));
public static String threeDigitBase36(byte[] bs) {
  return new BigInteger(bs).mod(N36POW3).toString(36);
}
// ...
threeDigitBase36(sha1("foo")); // => "96b"
threeDigitBase36(sha1("bar")); // => "y4t"
threeDigitBase36(sha1("bas")); // => "p55"
threeDigitBase36(sha1("zip")); // => "ej8"

Of course there will be collisions, as when you map any space into a smaller one, but the entropy should be better than something even sillier than the above solution.

Answer 2

Applying the KISS principle:

• An SHA is just a String
• The JDK hashcode for String is "random enough"
• Integer can render in any base

This single line of code does it:

public static String shortHash(String sha) {
    return Integer.toString(sha.hashCode() & 0x7FFFFFFF, 36).substring(0, 3);
}

Note: The & 0x7FFFFFFF is to zero the sign bit (hash codes can be negative numbers, which would otherwise render with a leading minus sign).

Edit - Guaranteeing hash length

My original solution was naive - it didn't deal with the case when the int hash is less than 100 (base 36) - meaning it would print less than 3 chars. This code fixes that, while still keeping the value "random". It also avoids the substring() call, so performance should be better.

static int min = Integer.parseInt("100", 36);
static int range = Integer.parseInt("zzz", 36) - min;

public static String shortHash(String sha) {
    return Integer.toString(min + (sha.hashCode() & 0x7FFFFFFF) % range, 36);
}

This code guarantees the final hash has 3 characters by forcing it to be between 100 and zzz - the lowest and highest 3-char hash in base 36, while still making it "random".