Subject: RE: [hackers-il] Re: To Hash or not to Hash [was Re: \\\"On Lisp\ \\" now a=

From: Chen Shapira <[email-masked]>
Date: Thu, 7 Feb 2002 21:14:30 +0200

> Perhaps all you want is to distribute a set of values in a 
> uniform fashion.

Any ideas on how to do this?
Or more generally: Suppose I want to create a large amount of random
variables, all independent, all with a specific distribution function
(either discrete or continuous).
How do I do something like that? any known algorithms?

I-want-to-see-the-law-of-large-numbers-ly yours,
Chen.

---

From: "Nadav Har'El" <[email-masked]>
Date: Thu, 7 Feb 2002 21:25:19 +0200

> How do I do something like that? any known algorithms?

I may be misunderstanding you, but isn't as psuedo-random-number-generator
*exactly* what you are after?
I mean, for each key a PRNG generates a sequence of values distributed in a
given distribution (usually a uniform distribution over, say, [0,1], but it's
easy to convert it to any distribution you want). For different seeds, an
ideal PRNG will generate *independent* random sequences (variables).

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.

-- 
Nadav Har'El                        |    Thursday, Feb  7 2002, 26 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Tea or coffee? Coffee, without cream. It
http://nadav.harel.org.il           |will be without milk, we have no cream.

---

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

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

Curiously enough, I have come upon this problem not long ago. What I have
contrived was to map a uniform distribution function to another, say, normal
function.

Impossible you say? You are correct. But I did an approximation. Still didn\'t
test it, it\'s all on paper yet.

-- Arik

On 07.02.2002 at 21:16:32, Chen Shapira <[email-masked]> wrote:

> 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/ 
> 
> 

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: Shlomi Fish <[email-masked]>
Date: Fri, 8 Feb 2002 09:04:35 +0200 (IST)

> How do I do something like that? any known algorithms?

To quote von-Neumann:

Anyone who considers arithmetical methods of producing random numbers is,
of course, in a state of sin.

Any pseudo-number generation routine is a heuristic that aims to generate
numbers that seem random to the above layer. They are not really random.

The Linux Kernel has a random number device, which uses timings of events
to generate random numbers, which are more true. I also heard of a device
that uses small differences in temperature to generate random numbers.

Sometimes, however, one will prefer to use a pseudo-random number
generator in order to be able to re-create the behaviour by feeding it
with the same seed. So, pseudo-random numbers are not necessarily
inferior, and sometimes even much superior.

There was a research by a few Finnish workers a few years ago (I read it
in "Nature") where they showed that several pseudo-random number
methodologies did not pass several basic randomosity tests. It was quite
interesting toread.

> I-want-to-see-the-law-of-large-numbers-ly yours,

Then read integers by using /dev/urandom, sum them up in fixed quantities
(use 64-bit precision), and plot their distribution. You should get a bell
curve. If not - tell the Linux developers, that it does not work.

Regards,

	Shlomi Fish

> 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: "Nadav Har'El" <[email-masked]>
Date: Fri, 8 Feb 2002 16:22:47 +0200

> numbers that seem random to the above layer. They are not really random.

This is a very narrow-minded view of the state-of-the-art in random number
generation and its modern uses.

It is possible to generate "real" random numbers from physical processes,
like Linux's /dev/random does, and like the Intel's newer chips have random
number generations on them (if you want, I can send you their white-paper,
it's quite interesting - some of the things they do are actually based on
Von-Neumann's ideas :) ).
But typically, these physical processes can generate a limited number of
quality random numbers per second. Say, 1024 bits a second.

What do you do if you application needs thousands or millions of quality
random numbers each second? Consider, for example, an SSL webserver that
serves 4000 pages a second, or a online-casino server that needs to generate
many random numbers each second. Both need quality random numbers (meaning
that the distribution is indeed uniform, with the proper mean, and so on) and
need secure random numbers (an adversery can't guess the next number in
the sequence, even if he knows the results of all the previous dice-throws).

So what you do is to use a cryptographic-quality PRNG based on a truely-
random (from /dev/random or hardware) seed, and every once in a while (say,
every second) mix new truely-random data into the seed.

The numbers you generate this way are "truely random" in every way you can
think of (except perhaps the philosophical sense). They are correctly
distributed, pass every randomness tests (unless you have bugs, of course),
and even given the ENTIRE list of random numbers R1...Rn there is no way
for the advesary to calculate R(n+1) withing a resonable time.

Again, read OpenSSL's sslrand(3) for a short discussion of cryptographic
PRNGs.

-- 
Nadav Har'El                        |      Friday, Feb  8 2002, 26 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Hi! I'm a signature virus! Copy me into
http://nadav.harel.org.il           |your signature to help me spread!

---

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

> for the advesary to calculate R(n+1) withing a resonable time.

I still insist on calling the numbers between to calls to /dev/random
pseudo-random. Maybe they can pass every randomness test I can think of
that does not have a-priori knowledge, but are still generated by a
deterministic algorithm.

If you wish to call them "truely random" fine, but I still insist they are
pseudo-random "limquta'in".

> Again, read OpenSSL's sslrand(3) for a short discussion of cryptographic

Maybe I will. I'm not too much into crypto now.

As a side note I should say, that when I wanted to say that when I wrote
the first version of Freecell Solver, I generated a list of 1000 boards by
using a perl script. I called Perl's srand() function but also called it
for each board, believing I'll get a better randomness. But then it was
hard to re-create these boards, without copying all of them.

The re-solution was that I know use the Microsoft Freecell Deals, and to
lesser extent the PySol deals to test new versions of the solver. This is
just another example, where pseudo-random numbers actually work to your
advantage.

So far my best experience in cryptography was when I implemented RSA
encryption and decryption in Scheme (for very small keys) for my SICP
course. It was pretty entertaining but I did not understand too much why
it should have worked. And I think it is an important factor when giving a
computer exercise.

Regards,

	Shlomi Fish

There is no IGLU Cabal! At least there is not a true IGLU Cabal. But there
is a pseudo-IGLU Cabal.

---

From: Oleg Goldshmidt <[email-masked]>
Date: 10 Feb 2002 21:34:36 -0500

Arik Baratz <[email-masked]> writes:

> Impossible you say? You are correct. But I did an
> approximation. Still didn\'t test it, it\'s all on paper yet.

Well, it is quite possible, of course. For well-behaved distributions
(typically those with easily invertable CDF) it is often even
efficient. In the general case the rejection method will work, but
might be wasteful. Without even going to my bookshelf I am sure that
Knuth has a lot to say about it. The theory part of Numerical Recipes
is short but clear (don't touch the implementation though).

In fact, a much more fundamental and difficult problem is to find a
good and efficient uniform pseudo-random generator. For any serious
work one has to be very careful about readily available algorithms and
implementations (e.g. see my comment regarding NR above). On the other
hand, don't expect to come up with a good RNG yourself. Not that it is
impossible, just quite improbable ;-).

-- 
Oleg Goldshmidt | [email-masked] 
If it aint't broken it hasn't got enough features yet.

---

From: Oleg Goldshmidt <[email-masked]>
Date: 10 Feb 2002 21:46:13 -0500

> of course, in a state of sin.

This quote precedes just about every RNG publication I have ever seen,
of course ;-)

> to generate random numbers, which are more true. 

It is very random (a colleague of mine and I submitted it, among quite
a few others, to a battery of tests), but not very efficient. It might
be, incidentally, quite suitable for seeding a PRNG. If you can afford
the lack of portability, that is (seeding RNGs randomly is an
interesting problem in itself, once you start thinking about the
requirements, after discovering that what you thought should be random
isn't).

> methodologies did not pass several basic randomosity tests. 

Can you provide a reference? I have a long-standing interest in the subject.

A few years ago I studied the state of the art in some depth. The
following is a very brief summary (the full report is, and will
remain, property of my employer at the time unless they will grant me
a release):

http://groups.google.com/groups?selm=m3emyz0xsm.fsf%40NOSPAM.netvision.net.il&output=gplain

Just in case it is relevant for understanding the context of this
summary, here is my original request for pointers:

http://groups.google.com/groups?selm=lvzpj6d5sq.fsf%40NOSPAM.netvision.net.il&output=gplain

---

From: Shlomi Fish <[email-masked]>
Date: Mon, 11 Feb 2002 06:18:20 +0200 (IST)

> This quote precedes just about every RNG publication I have ever seen,

I happen to like this quote very much. Albeit I think that if you know
what your application considers as random, you might be able to compose a
good pseudo-random number generator.

> requirements, after discovering that what you thought should be random

I did not know it was not very fast. That does make it problematic.

> Can you provide a reference? I have a long-standing interest in the subject.

Unfortunately, Google returns junk. The article was written in the
magazine "Nature" (a very famous British publication - one of the two
topmost scientific publications in the world) It was written by its
editor. I don't remember the editor's name, etc. but I remember the
general wave of the article.

I cannot find it in the nature.com/nature search, so I'm sorry I could not
be of more assistant. (please reply to me by E-mail if you wish to hear
what I can remember of it)

Regards,

	Shlomi Fish

---

From: "Nadav Har'El" <[email-masked]>
Date: Mon, 11 Feb 2002 12:00:15 +0200

On Mon, Feb 11, 2002, Shlomi Fish wrote about "[hackers-il] Re: RE: Re: To Hash or not to Hash [was Re: \\\"On Lisp\ \\" now a=":
>...

/dev/random's not being fast is a bit of an understatement. I just tried
	cat /dev/random >/tmp/z1

With me moving the mouse around, pressing keys, doing things on the network,
playing music, and a lot of other stuff going on for random events - and
after 56 seconds I got 6952 bytes in /tmp/z1. That's 124 random bytes (992
random bits) per second - slow by any kind of standard. And there's nothing
much that can be done about this - a faster CPU wouldn't help a bit.

Intel's on-chip random number generator (which has more physical sources of
randomness) generates what they call an "exceptional performance": 75 Kbit/sec
which is enough for many applications, but not all (it is certainly not enough
for Monte-Carlo or similar simulations, but you don't need cryptographic-
quality RNG for that anyway).

/dev/urandom will of course get you bits faster (I measured 5.8Mbit/sec),
but it is essentially a PRNG seeded once in a while by "real" random events -
which you seem not to like (but I think is good enough).

P.S. Guess what? Intel's paper "Analysis of the Intel Random Number Generator"
also includes the following quote:
	Anyone who considers arithmetical methods of producing random
	digits is, of course, in a state of sin. (John Von Neumann, 1951)
:)
See http://nadav.harel.org.il/pub/CRIwp.pdf for the full paper.

-- 
Nadav Har'El                        |      Monday, Feb 11 2002, 29 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |What's the difference between roast beef
http://nadav.harel.org.il           |and pea soup? Anyone can roast beef.

---

From: mulix <[email-masked]>
Date: Mon, 11 Feb 2002 12:59:03 +0200 (IST)

just a quick note that there's a kernel patch to allow all or most of
the network devices to contribute to /dev/random's entropy pool, rather
than just a few. no idea if it's applied in the mainline kernel, though.
-- 
mulix

http://vipe.technion.ac.il/~mulix/
http://syscalltrack.sf.net/

---

From: Adi Stav <[email-masked]>
Date: Mon, 11 Feb 2002 15:41:06 +0200

> than just a few. no idea if it's applied in the mainline kernel, though.

A controvertial patch, since relying on the randomness of 
externally connected devices such as network cards would open
a security hole. Any software on the machine that relies on 
randomness will risk having its random number source not only 
/read/ but actually /affected/ by an attacker that can, e.g., 
send packets to the network card with careful timing.

This reminds me an old Gaal Yahas (where /is/ he lately?) sig:

"Real programmers type `cat /dev/random >a.out' and affect the
universe randomisity field."
 
which could actually be made reality.

A better idea was for servers to open up their on-board 
unconnected microphone ports and use the static. Which relates
to yet another "Real Programmers" sig.

---

From: Adi Stav <[email-masked]>
Date: Mon, 11 Feb 2002 16:48:26 +0200