Re: who wants a crack at this
From: Roger Fleming (roger_for_nntp_at_hotmail.com)
Date: 06/27/03
- Next message: Benjamin Goldberg: "Re: Avoiding C++ Templates In Cipher Implementation"
- Previous message: unknown: "Re: integrity aware PCBC paper"
- In reply to: Jeff Mott: "who wants a crack at this"
- Next in thread: Francois Grieu: "Re: who wants a crack at this"
- Reply: Francois Grieu: "Re: who wants a crack at this"
- Reply: CryptWolf: "Re: who wants a crack at this"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 26 Jun 2003 17:33:17 -0700
Jeff Mott wrote:
> The following is a rudamentary hashing algorithm written in
> JavaScript. I'm attempting to demonstrate to someone else that it is
> not secure. [...]
> var alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHI";
Why does alpha repeat 9 letters? Surely indexOf only returns the index
of the first character it finds, so these characters will never be
used? It would probably be more useful to include digits so passwords
could be alphanumeric. As it stands, (and IIRC my Javascript) all
non-alphabetic characters are effectively converted to 'A'.
> function makehash(pw, mult)
> {
> pw = pw.toUpperCase();
> var hash = 0;
> for (var i = 0; i < 8; ++i)
> {
> var letter = pass.substr(i, 1);
> var c = alpha.indexOf(letter) + 1;
> hash = hash * mult + c;
> }
> return hash;
> }
Your friend has probably been confused by the multiple meanings of the
word "hash". The function listed above is very similar to a broad
class of functions used to generate NON-CRYPTOGRAPHIC hashes, where we
are interested only in the probability of accidental collisions, not
the ease of calculating a deliberate collision. Depending on the
actual value of mult, this could be a good non-crypto hash (well,
apart from smashing case on the input and then truncating it).
You are correct in saying that it is very weak as a cryptographic
function. The final value of hash (possibly excepting an implicit mod
2^32) is simply:
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. 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.
If m is only slightly less than 26, it may be worth trying the above
method anyway, by assuming that X, Y and Z are unlikely to be in the
password.
It does seem to get a little harder if m is smaller than 26. In that
case, it might be easiest to imagine your c[] expressed in base m.
Then, the LSD of has is simply the LSP of c[7]; the second lowest
digit is the first digit of c[6] + the second digit of c[7], mod m;
third digit is third of c[7], second of c[6], first of c[5], and any
carry from previous; and so on. At each position, the possibilities
become increasingly ambiguous. So if you start with the LSD of c[7]
you can work your way backwards, and gradually build up a whole heap
of candidate passwords. Each will work just as well at fooling this
password checker (they are collisions), but only one will be the
actual password. Most likely, that will be the one that isn't pure
gibberish.
Cheers,
Roger
- Next message: Benjamin Goldberg: "Re: Avoiding C++ Templates In Cipher Implementation"
- Previous message: unknown: "Re: integrity aware PCBC paper"
- In reply to: Jeff Mott: "who wants a crack at this"
- Next in thread: Francois Grieu: "Re: who wants a crack at this"
- Reply: Francois Grieu: "Re: who wants a crack at this"
- Reply: CryptWolf: "Re: who wants a crack at this"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
