Subject: =?iso-8859-1?Q?=3D?iso-8859-1?Q?Re: [hackers-il] Re: To Hash or not to Hash [was Re: \\\\\=

From: Arik Baratz <[email-masked]>
Date: Thu, 7 Feb 2002 20:53:56 +0000 (GMT)

\\\\\\\\\\"On Lisp\\\\ \\\\\\\\=3D?=
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1

On 07.02.2002 at 21:26:48, Nadav Har\\\'El <[email-masked]> wrote:

> PRNG and hash functions have a lot in common - many times you\\\'ll see code
> resembling a PRNG inside an hash function, and vice versa - hash functions
> used to \\\"mix\\\" pseudo-random number data in a PRNG. But they are still
two
> different concepts.

I beg to differ. PRNG and cryptographic hash functions are one and the same,
and
can be converted from one form to another:

let h(x) be a hash function of x:f->f
let s be the seed of the PRNG

to produce the next random number, R(n+1,s)=h(R(n,s)), while R(1)=h(seed).

and the reverse:

let r(n,s) be a pseudo number generator with seed s

h(x)=r(1,x)

Arik Baratz
System Engineer
[email-masked]

Office:
4 Hamelacha St.
Raa&#8217;nana 43661
ISRAEL

Tel:    +972 (9) 743-9250 ext. 214
Fax:   +972 (9) 743-9251
Cell:  +972 (52) 354 959
eFax: +1 (978) 926-8913
ICQ:  210 8214

Privileged and / or confidential Information may be contained in this
electronic
mail message. 

You may not copy or deliver this message to anyone without my consent.

If you are not the addressee indicated in this message, or you feel that this
message is not intended for you, Please destroy this message and kindly notify
the sender by replying to this electronic mail.

Please advise immediately if you or your employer do not agree to the use of
Internet email for messages of this kind.

Opinions, conclusions and other information in this message that do not relate
to the official business of Vidius shall be understood as neither given nor
endorsed by it.

Arik Baratz
System Engineer
[email-masked]

Office:
4 Hamelacha St.
Raa&#8217;nana 43661
ISRAEL

Tel:    +972 (9) 743-9250 ext. 214
Fax:   +972 (9) 743-9251
Cell:  +972 (52) 354 959
eFax: +1 (978) 926-8913
ICQ:  210 8214

Privileged and / or confidential Information may be contained in this electronic
mail message. 

You may not copy or deliver this message to anyone without my consent.

If you are not the addressee indicated in this message, or you feel that this
message is not intended for you, Please destroy this message and kindly notify
the sender by replying to this electronic mail.

Please advise immediately if you or your employer do not agree to the use of
Internet email for messages of this kind.

Opinions, conclusions and other information in this message that do not relate
to the official business of Vidius shall be understood as neither given nor
endorsed by it.

---

From: "Nadav Har'El" <[email-masked]>
Date: Fri, 8 Feb 2002 16:07:50 +0200

On Thu, Feb 07, 2002, Arik Baratz wrote about "=?iso-8859-1?Q?=3D?iso-8859-1?Q?Re: [hackers-il] Re: To Hash or not to Hash [was Re: \\\\\=":
>....

As I said, I *know* one can use a hash function to write a PRNG routine,
and vice versa. What I meant by "they are still two different concepts"
was that when choosing algorithms for a hash function and algorithms for
a PRNG, you many times make different requirements from the functions,
and end up making different choices.
One question is whether you need your hash/PRNG to have cryptographic
qualities. In most hash functions (used for hash tables, not for message
digest) you prefer speed to cryptographic qualities (i.e, you don't care
if someone can fabricate a key with a hash he wants). You also prefer speed
over perfect uniformity (since the uniformity's only reason is to improve
speed in searches!).

Your suggestion on how to generate cryptographic random numbers from a
cryptographic hash, by the way, is actually severely flawed. The problem
is that your seed is only as long as your output, and on every output you
"give away" your next seed, so that someone who eavesdrops on one random
number can figure the entire sequence. These two flaws are HUGE cryptographic
no-nos... The typical implementation is a little different:
  initialization:
     seed = <long random data, say 1024 bits from /dev/random>

  getting a random number:
     seed = messaroundwith(seed)
     return somehashdatafrom(seed))

  Where messaroundwith and somehashdatafrom is a function (typically based
  on secure hash functions like MD5) to change the seed. At no point is
  the whole seed returned; Even a sequence of 1000 consecutive PRNG results
  won't help the attacker guess in advance the next number in the sequence.

See the sslrand(3) manual (from OpenSSL), for example on how OpenSSL does
things. Secure digests, message authentication codes (MAC), random number
generators (PRNG) are a very complicated subject and a lot of research has
been done on the subject; It's another subject where reinventing your own
wheel will get you a square wheel :)

-- 
Nadav Har'El                        |      Friday, Feb  8 2002, 26 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |"Mommy! The garbage man is here!" "Well,
http://nadav.harel.org.il           |tell him we don't want any!"- Groucho Marx

---

From: Shlomi Fish <[email-masked]>
Date: Fri, 8 Feb 2002 21:14:45 +0200 (IST)

> wheel will get you a square wheel :)

Well said, but we are still allowed to speculate about it and discuss it
non-profesionally, no? That won't make us crypto experts, but it will make
us smarter.

Maybe Orr Dunkelman (who I'm pretty sure is not an hackers-il subscriber)
can enlighten us, being the crypto authority of the lin-club. Of course, I
think there still is some progress done in cryptology and people find
better methods for securing data and transactions all the time.

You know? I think I finally understood the difference between
cryptography and cryptology... go figure.

Regards,

	Shlomi Fish

There is no IGLU Cabal! They all fought over on how should be the
hackers-il authority on C and whether he should also cover C++. Strangely
enough each was convinced another person except himself should be this
authority. That made them all the weakest links which brought the demise
of the cabal.

> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Arik Baratz <[email-masked]>
Date: Fri, 8 Feb 2002 20:24:06 +0000 (GMT)

On 08.02.2002 at 16:09:14, Nadav Har\'El <[email-masked]> wrote:

> and vice versa. What I meant by \"they are still two different concepts\"

Apply what I\'ve said to non-cryptographic hashes and random numbers, and you
can see that even your regular \'mod n\' hash function can create an interesting
PRNG (alebit pretty lame one).

> cryptographic hash, by the way, is actually severely flawed. The problem

Yeah, I know. I could have done something better but I went for simplicity.

> \"give away\" your next seed, so that someone who eavesdrops on one random
>   won\'t help the attacker guess in advance the next number in the sequence.

How about (having hash function h(x) and seed s)

r(n+1)=h(r(n)+s) 

> been done on the subject; It\'s another subject where reinventing your own

What\'s wrong about square wheels? I\'m sure they have their uses...

Arik Baratz
System Engineer
[email-masked]

Office:
4 Hamelacha St.
Raa&#8217;nana 43661
ISRAEL

---

From: "Nadav Har'El" <[email-masked]>
Date: Sat, 9 Feb 2002 11:51:03 +0200

> How about (having hash function h(x) and seed s)

This is getting better :)

The only relatively-small flaws I can think about this scheme (at cursory
examination) is:
1. the "cycle" of your pseudo-random sequence is always less than 2^32 (when
   you get r(N)=r(1), the entire sequence repeats itself).
2. You rely very strongly on the quality of h() when you use simple addition
   for mixing in r(n). Usually you do it (addition, or xor) in a moving
   positing inside the s, to change more bits from s.

-- 
Nadav Har'El                        |    Saturday, Feb  9 2002, 27 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Martin Luther King said "I have a dream",
http://nadav.harel.org.il           |not "I have a plan".

---

From: "Nadav Har'El" <[email-masked]>
Date: Sat, 9 Feb 2002 11:59:16 +0200

>    you get r(N)=r(1), the entire sequence repeats itself).

I said that wrong. The 2^32 number was assuming that r(n) is a 32 bit
result. Anyway, the more fundenmental problem with your new scheme is that
once the sequence repeats a single result r(n), the entire sequence then
repeats itself. This doesn't happen with "truely" random numbers, so it
shouldn't happen with a good PRNG.

-- 
Nadav Har'El                        |    Saturday, Feb  9 2002, 27 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Why do we drive on a parkway and park on
http://nadav.harel.org.il           |a driveway?