Re: who wants a crack at this
From: Francois Grieu (fgrieu_at_micronet.fr)
Date: 06/27/03
 Next message: Ernst Lippe: "Re: Is this Possible?"
 Previous message: ZBoub: "encryption & padding"
 In reply to: Roger Fleming: "Re: who wants a crack at this"
 Next in thread: CryptWolf: "Re: who wants a crack at this"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Fri, 27 Jun 2003 10:30:21 +0200
In article <fdbae11.0306261633.5bd9e666@posting.google.com>,
roger_for_nntp@hotmail.com (Roger Fleming) wrote about:
> hash (possibly excepting an implicit mod 2^32) is:
> hash = c[0]* m**7 + c[1]* m**6 + c[2]* m**5 + c[3]* m**4
> + c[4]* m**3 + c[5]* m**2 + c[6]* m + c[7]
> 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[4]* m**3 + c[5]* m**2 + c[6]* m + c[7]) 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[0]* m**7 + c[1]* m**6 + c[2]* m**5 + c[3]* 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.
François Grieu
 Next message: Ernst Lippe: "Re: Is this Possible?"
 Previous message: ZBoub: "encryption & padding"
 In reply to: Roger Fleming: "Re: who wants a crack at this"
 Next in thread: CryptWolf: "Re: who wants a crack at this"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
