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

Expand Messages
• ... 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
Message 1 of 13 , Feb 7, 2002
• 0 Attachment
> 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.
• ... 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
Message 2 of 13 , Feb 7, 2002
• 0 Attachment
On Thu, Feb 07, 2002, Chen Shapira wrote about "RE: [hackers-il] Re: To Hash or not to Hash [was Re: \\\"On Lisp\ \\" now a=":
>
> > 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 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
nyh@... |-----------------------------------------
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.
• 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
Message 3 of 13 , Feb 7, 2002
• 0 Attachment
\" 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 <chen@...> wrote:

>
> > 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.
>
>
> To unsubscribe from this group, send an email to:
> hackers-il-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

Arik Baratz
System Engineer
arikb@...

Office:
4 Hamelacha St.
Raa’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.

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.
• ... 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
Message 4 of 13 , Feb 7, 2002
• 0 Attachment
On Thu, 7 Feb 2002, Chen Shapira wrote:

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

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

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

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

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

----------------------------------------------------------------------
Shlomi Fish shlomif@...
Home E-mail: shlomif@...

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"
• ... 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
Message 5 of 13 , Feb 8, 2002
• 0 Attachment
On Fri, Feb 08, 2002, Shlomi Fish wrote about "[hackers-il] RE: Re: To Hash or not to Hash [was Re: \\\"On Lisp\ \\" now a=":
> 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.

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
nyh@... |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Hi! I'm a signature virus! Copy me into
• ... 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
Message 6 of 13 , Feb 8, 2002
• 0 Attachment
On Fri, 8 Feb 2002, Nadav Har'El wrote:

> On Fri, Feb 08, 2002, Shlomi Fish wrote about "[hackers-il] RE: Re: To Hash or not to Hash [was Re: \\\"On Lisp\ \\" now a=":
> > 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.
>
> 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.
>

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
> PRNGs.
>

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

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.

>
> --
> Nadav Har'El | Friday, Feb 8 2002, 26 Shevat 5762
> nyh@... |-----------------------------------------
> Phone: +972-53-245868, ICQ 13349191 |Hi! I'm a signature virus! Copy me into
>
>
> To unsubscribe from this group, send an email to:
> hackers-il-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish shlomif@...
Home E-mail: shlomif@...

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"
• ... Well, it is quite possible, of course. For well-behaved distributions (typically those with easily invertable CDF) it is often even efficient. In the
Message 7 of 13 , Feb 10, 2002
• 0 Attachment
Arik Baratz <arikb@...> writes:

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

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 | ogoldshmidt@...
If it aint't broken it hasn't got enough features yet.
• ... This quote precedes just about every RNG publication I have ever seen, of course ;-) ... It is very random (a colleague of mine and I submitted it, among
Message 8 of 13 , Feb 10, 2002
• 0 Attachment
Shlomi Fish <shlomif@...> writes:

> To quote von-Neumann:
>
> Anyone who considers arithmetical methods of producing random numbers is,
> of course, in a state of sin.

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

> The Linux Kernel has a random number device, which uses timings of events
> 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).

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

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):

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

--
Oleg Goldshmidt | ogoldshmidt@...
If it aint't broken it hasn't got enough features yet.
• ... 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
Message 9 of 13 , Feb 10, 2002
• 0 Attachment
On 10 Feb 2002, Oleg Goldshmidt wrote:

> Shlomi Fish <shlomif@...> writes:
>
> > To quote von-Neumann:
> >
> > Anyone who considers arithmetical methods of producing random numbers is,
> > of course, in a state of sin.
>
> This quote precedes just about every RNG publication I have ever seen,
> of course ;-)
>

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.

> > The Linux Kernel has a random number device, which uses timings of events
> > 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).
>

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

> > 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.
>
> 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)

> 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):
>
>
> Just in case it is relevant for understanding the context of this
> summary, here is my original request for pointers:
>
>

Regards,

Shlomi Fish

> --
> Oleg Goldshmidt | ogoldshmidt@...
> If it aint't broken it hasn't got enough features yet.
>
>
> To unsubscribe from this group, send an email to:
> hackers-il-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish shlomif@...
Home E-mail: shlomif@...

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"
• ... /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
Message 10 of 13 , Feb 11, 2002
• 0 Attachment
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=":
> > > The Linux Kernel has a random number device, which uses timings of events
> > > 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
>...
>
> I did not know it was not very fast. That does make it problematic.

/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

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
nyh@... |-----------------------------------------
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.
• 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.
Message 11 of 13 , Feb 11, 2002
• 0 Attachment
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/
• ... A controvertial patch, since relying on the randomness of externally connected devices such as network cards would open a security hole. Any software on
Message 12 of 13 , Feb 11, 2002
• 0 Attachment
On Mon, Feb 11, 2002 at 12:59:03PM +0200, mulix wrote:
> 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.

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.
• ... A controvertial patch, since relying on the randomness of externally connected devices such as network cards would open a security hole. Any software on
Message 13 of 13 , Feb 11, 2002
• 0 Attachment
On Mon, Feb 11, 2002 at 12:59:03PM +0200, mulix wrote:
> 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.

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.
Your message has been successfully submitted and would be delivered to recipients shortly.