Re: Reversible hash to transform series of small integers into well-distributed output values?

From: Jean-Luc Cooke (jlcooke_at_lager.engsoc.carleton.ca)
Date: 01/03/04


Date: 3 Jan 2004 04:47:33 GMT

standard hash isnt' reversible.

something completly different:

key = hex(00000000 00000000 00000000 00000000);

output = aes_enc(key, input);

Should do what you want.

JLC

Jeff <jskubick@hotmail.com> wrote:
> I'm trying to find a reasonable REVERSIBLE scheme for generating long,
> reasonably well-distributed strings from single integers between 0 and
> 32768 based upon some shared secret such that someone who KNOWS that
> each long character string ultimately represents a single 16-bit
> integer (but DOESN'T know the secret's value) would still have a hard
> time trying to replicate it through brute force.

> To give a specific example, suppose a website has 600 users whose user
> IDs are represented by the numbers 1 through 600. Using MD5, I could
> come up with a reasonably well-distributed set of output values by
> generating a random string of random length and prepending it to each
> of the integer values before taking the value's md5 hash and
> converting it to a 32-digit hexadecimal number. Someone who knows that
> 8f87f8ae92c2e8374f72c3b1143e2da2 represents one of the 600 possible
> values would still have a fairly hard time finding the other 599
> possible values in the 128-bit haystack... especially if they were
> chasing a moving target (the salt were changed regularly) and got
> locked out for a while if they made too many bad requests in a row.

> The problem, of course, is that md5 isn't reversible. I vaguely
> remember seeing a reference once to a scheme that specifically
> addressed the issue of creating big "needle-in-a-haystack" output
> values from a small, sequential set of 32-bit input values utilizing a
> shared secret, but can't find any obvious references to it anymore.

> Why not just store the 600 values in a local dictionary? Two
> reasons... I expect a lot more values than 600 in a fairly short time,
> and I'd like to use a different salt for each active user (generated
> randomly at login time)... so that a request by user #9 for
> /foo/bar/${big hash value} that returns a file corresponding to user
> #832 would correspond to NOTHING (in all likelihood) if user #614
> tried to request the same file since the salt used to calculate ${big
> hash value} would have been specific to user #9's current session and
> known ONLY to the object representing his current session.

> Any suggestions?

--