Re: who wants a crack at this
From: Francois Grieu (fgrieu_at_micronet.fr)
Date: Fri, 27 Jun 2003 10:30:21 +0200
In article <firstname.lastname@example.org>,
email@example.com (Roger Fleming) wrote about:
> hash (possibly excepting an implicit mod 2^32) is:
> hash = c* m**7 + c* m**6 + c* m**5 + c* m**4
> + c* m**3 + c* m**2 + c* m + c
> Since m is known, all the values of m**i can be calculated in advance,
> leaving us with a simple linear equation on 8 unknowns - complicated
> very slightly by the small range of permitted values for c.
> If m is 26 or greater, and an implicit mod 2^32 is _not_ done, then
> the solution is unique and can be trivially found the same way you
> would convert numbers into base m.
Indeed, save this should be m>=27, since each c is in [0..26]
> If a mod 2^32 is done, then there will be a small number
> (=~ 26* (m**8 - 1)/(m - 1) / 2**32 ) of candidates for each value,
> each of which can be easily found by adding the appropriate number
> of 2**32's, then converting to base m.
I think the mod 2^32 case is harder: you do not know "the appropriate
number of 2**32's" and for m on say 10 bits, it is too costly to
enumerate the roughly 2^40 possible values.
An educated brute force attack is to make a table of the 27^4 values
of hash - ( c* m**3 + c* m**2 + c* m + c) mod 2^32
and organize it in a quicly searchable data structure (like a hash
table); then for each of the 27^4 values of
(c* m**7 + c* m**6 + c* m**5 + c* m**4 ) mod 2^32
we try to find if there is an entry in the table with this value,
in which case we have found a solution. The expected number of
searches is about 1000 before a solution is found.
[As an optimization, we can use that numbers in the table are
clustered as 27^3 sequences of 27 consecutive numbers, which allows
for a much more efficient data structure]
I wonder what are the more general approaches to solve the problem,
say if the hash was mod 2^128, with 27 digits in [0..26]
(27^27 is about 2^128), and m an arbitrary odd 128 bits integer.