Loading ...
Sorry, an error occurred while loading the content.
 

=?iso-8859-1?Q?RE: [hackers-il] Re: To Hash or not to Hash [was Re: \\\\\\\"On Lisp\\ \\\\=

Expand Messages
  • Arik Baratz
    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 1 of 13 , Feb 7, 2002
      \" 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.

      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.
    • Shlomi Fish
      ... 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 2 of 13 , Feb 7, 2002
        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
        interesting toread.

        > 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 Page: http://t2.technion.ac.il/~shlomif/
        Home E-mail: shlomif@...

        "Let's suppose you have a table with 2^n cups..."
        "Wait a second - is n a natural number?"
      • Nadav Har'El
        ... 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 3 of 13 , Feb 8, 2002
          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
          http://nadav.harel.org.il |your signature to help me spread!
        • Shlomi Fish
          ... 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 4 of 13 , Feb 8, 2002
            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
            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.

            >
            > --
            > 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
            > http://nadav.harel.org.il |your signature to help me spread!
            >
            >
            > 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 Page: http://t2.technion.ac.il/~shlomif/
            Home E-mail: shlomif@...

            "Let's suppose you have a table with 2^n cups..."
            "Wait a second - is n a natural number?"
          • Oleg Goldshmidt
            ... 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 5 of 13 , Feb 10, 2002
              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.
            • Oleg Goldshmidt
              ... 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 6 of 13 , Feb 10, 2002
                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):

                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

                --
                Oleg Goldshmidt | ogoldshmidt@...
                If it aint't broken it hasn't got enough features yet.
              • Shlomi Fish
                ... 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 7 of 13 , Feb 10, 2002
                  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):
                  >
                  > 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
                  >

                  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 Page: http://t2.technion.ac.il/~shlomif/
                  Home E-mail: shlomif@...

                  "Let's suppose you have a table with 2^n cups..."
                  "Wait a second - is n a natural number?"
                • Nadav Har'El
                  ... /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 8 of 13 , Feb 11, 2002
                    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
                    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
                    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.
                  • mulix
                    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 9 of 13 , Feb 11, 2002
                      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/
                    • Adi Stav
                      ... 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 10 of 13 , Feb 11, 2002
                        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.
                      • Adi Stav
                        ... 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 11 of 13 , Feb 11, 2002
                          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.