Re: [fw-wiz] strong passwords

From: Mikael Olsson (mikael.olsson@clavister.com)
Date: 07/10/02 

From: Mikael Olsson <mikael.olsson@clavister.com>
To: miha@nil.si
Date: Wed Jul 10 12:51:12 2002

miha@nil.si wrote:
>
> Now, I don't have my copy of Applied Cryptography ready, but isn't 50:50
> chance much too high? If I remember correctly it is more in the lines of:
> birthday attacks are possible, just not very likely, but finding something
> that hashes to the same value as a specific text/password is next to
> impossible ( very hard ).

[trying to re-apply what i've forgotten -- remember I'm on vacation :)]

It's basically like this:

Laws of probability dictate that if you give a 64-bit input to a
hash that produces a 64-bit output, there is a _very good chance_
that there is at least one input that will produce the same output.

If this is not true, it isn't a one way function: it'd be a cipher.

Now, if you give the hash _more_ than 64 bits of input, there's
obviously going to be collisions, but that is to be expected.
65 bits input will have twice as many collisions as 64 bits.
66 bits input will have four times as many ...

Actually, it doesn't have to be 64-bit inputs, it can be any length
input. Basically, what the hash function does is take an input
and transform it into "a random output". So twist your thinking
around into thinking "x balls has to go into y buckets", and you
get:

For 50 balls going into 100 buckets:
- 30 balls alone in a bucket
- 15 balls sharing a bucket with one ball (single collision)
- 4 balls sharing a bucket with two balls (double collision)

[hash lookup tables are often designed with twice as many buckets as
 input items btw -- as you can see, the statistics look pretty good]

For 80 balls going into 100 buckets:
- 36 balls alone in a bucket
- 29 balls sharing a bucket with one ball (single collision)
- 11 balls sharing a bucket with two balls (double collision)

For 100 balls going into 100 buckets:
- 37 non-collisions
- 37 single collisions (hey, 50:50 :))
- 18 double collisions

So uhm.. yeah, i know, i'm probably confusing y'all. Let's see if
I can turn it right again.

So, for all possible inputs to hash, you get, statistically speaking:
- 37% collision free inputs
- 37% inputs that generate the same output as another input
- and 18% inputs that generate the same output as TWO other inputs.
And this is assuming that the hash is perfect.

NOW: if I've completely mucked up somewhere along my line of thought,
someone _please_ holler sometime real soon before I confuse everyone
too badly :)

/Mike, blames it all on being on vacation 

-- 
Mikael Olsson, Clavister AB
Storgatan 12, Box 393, SE-891 28 ÖRNSKÖLDSVIK, Sweden
Phone: +46 (0)660 29 92 00   Mobile: +46 (0)70 26 222 05
Fax: +46 (0)660 122 50       WWW: http://www.clavister.com
"It's July. I'm on vacation. Can't you tell? :)"

Relevant Pages

  • Re: A simple but confusing question
    ... Sampling balls from a bucket without replacement using Carroll's prior ... tossing a coin 'corresponds' to sampling without replacement. ... the prior on the probablity with which the balls are picked and put ...
    (sci.stat.math)
  • Re: Momentum conservation
    ... realize the amounts to be measured are extremely small. ... Wrap the balls in some material ... The boundary between the two halves of the collision might ... energy in collisions as well if, again, the time of maximum compression ...
    (sci.physics)
  • Re: A simple but confusing question
    ... >coin tossing experiment corresponds to sampling with replacement. ... does not assume that the bucket initially had half of its balls ... That is why I call this example a `paradox'. ...
    (sci.stat.math)
  • Re: A simple but confusing question
    ... Ian Jermyn ... > This is only approximately true, for N>> n, where N is the number of balls> in the bucket and n the number of draws. ... the prior> dominates. ...
    (sci.stat.math)
  • Re: A simple but confusing question
    ... Assume we know how many balls are in the bucket. ... number of white balls in the bucket be M. ... the data dominates our estimate of M. ...
    (sci.stat.math)