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

Re: [hackers-il] Re: To Hash or not to Hash [was Re: \"On Lisp\" now available ]

Expand Messages
  • Nadav Har'El
    ... Oh, I see - you meant choosing, once, a *hash function* at random, but then use the same hash function all the time? Ok. -- Nadav Har El
    Message 1 of 22 , Feb 7, 2002
    • 0 Attachment
      On Thu, Feb 07, 2002, Ofir Carny wrote about "RE: [hackers-il] Re: To Hash or not to Hash [was Re: \"On Lisp\" now available ]":
      > As I said, it is only good for specific applications, obviously, you can't
      > change a hash function without rebuilding an existing table, however in some
      > applications it is enough to prevent a malicious attempt to 'break' your
      > function.

      Oh, I see - you meant choosing, once, a *hash function* at random, but then
      use the same hash function all the time? Ok.

      --
      Nadav Har'El | Thursday, Feb 7 2002, 25 Shevat 5762
      nyh@... |-----------------------------------------
      Phone: +972-53-245868, ICQ 13349191 |Unlike Microsoft, a restaurant will give
      http://nadav.harel.org.il |me food for free if I find a bug in it!
    • Shlomi Fish
      ... There is a methodology to construct a random hash function out of a universal set of hash functions. This is called Universal Hashing, and I studied about
      Message 2 of 22 , Feb 7, 2002
      • 0 Attachment
        On Thu, 7 Feb 2002, Nadav Har'El wrote:

        > On Thu, Feb 07, 2002, Ofir Carny wrote about "RE: [hackers-il] Re: To Hash or not to Hash [was Re: \"On Lisp\" now available ]":
        > > As I said, it is only good for specific applications, obviously, you can't
        > > change a hash function without rebuilding an existing table, however in some
        > > applications it is enough to prevent a malicious attempt to 'break' your
        > > function.
        >
        > Oh, I see - you meant choosing, once, a *hash function* at random, but then
        > use the same hash function all the time? Ok.
        >

        There is a methodology to construct a random hash function out of a
        universal set of hash functions. This is called Universal Hashing, and I
        studied about it in my DS and Algorithms course. An example for it, would
        be to randomize an arbitrary string to prepend (or append) to the data
        before it is MD5'ed. That way, even if the user deliberately creates
        different strings whose first 32-bit MD5 bits are the same, he'll still
        won't be able to out-smart the hash, because the prefix will make their
        salt values completely different.

        Of course, letting the user know what the prefix is will render it
        useless. So it's kind of like a "security by obscurity" methodolgy.

        Regards,

        > --
        > Nadav Har'El | Thursday, Feb 7 2002, 25 Shevat 5762
        > nyh@... |-----------------------------------------
        > Phone: +972-53-245868, ICQ 13349191 |Unlike Microsoft, a restaurant will give
        > http://nadav.harel.org.il |me food for free if I find a bug in it!
        >
        >
        > 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?"
      • Arik Baratz
        ailable ]?= MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 ... - ... function ... Oh yeah? how about f(x) = rand(seed)? Obviously, if f(x)=C,
        Message 3 of 22 , Feb 7, 2002
        • 0 Attachment
          ailable ]?=
          MIME-Version: 1.0
          Content-Type: text/plain; charset=iso-8859-1

          On 07.02.2002 at 09:01:02, Shlomi Fish <shlomif@...> wrote:

          > >
          > > Hashes are application specific. A good hash is good in a specific situation
          -
          > > that is, for each function f(x) of a random variable x there is a hash
          function
          > > h(f(x)) that generates a uniform distribution.
          > Actually if f(x) = C, where C is a constant, no such hash function exist
          > or can exist.

          Oh yeah? how about f(x) = rand(seed)? Obviously, if f(x)=C, you might want to
          use a data structure different than a hash anyways.

          > > If you want a catch-all hash function, use a cryptographic hash like MD5.
          > Have you ever tried running md5sum on a CD-ROM you just downloaded from
          > the Internet? It takes forever to run. Usually, one will prefer to use a
          > non-cryptographic hash function because it is faster and albeit can be
          > tricked, usually generates equally good results. If there are a limited
          > number of elements, than a Perfect Hash, which you\'ll have to compile from
          > the set, would probably be a better choice.
          >
          > This is of course assuming the keys are fully serializable in some way.
          > Sometimes, preparing a serialized key is not very straightforward.

          Actually I have just md5sum-ed a 2GB file, so I know how slow it is... I totaly
          agree that baring special circumstances (i.e. in order to create the trapdoor
          effect, say, in issuing confirmation numbers for flights, when the confirmation
          cannot lead back to info in the ticket).

          > > If you
          > > want a lean and mean function, you\\\'d have to analyze the domain you are
          working
          > > with and think up a function that hashes it ok.
          > That was the case with Freecell Solver, where I recently switched from MD5
          > to Perl\'s hash function and did not notice too big a difference in the
          > speed.
          >
          > However, the hash function being chosen is just one of the elements of
          > constructing a good hash (albeit a very important one, because a hash is
          > only as good as it). Refer to my previous posts for other elements like
          > chaining vs. open addressing, promoting or caching elements, etc. In C++,
          > I\'m not sure how well can one re-use the chain\'s elements, when they are
          > re-hashed, and just pointing them to differnt elements, which is another
          > technique I used in FCS.
          >
          > What I like about ANSI C, is that it does what you want when you want it,
          > and if you know what you\'re doing there are very little side-effects. It
          > does provide for a greater error ratio, than most other languages I know,
          > though.
          >
          > > The glibc hash is very simplistic - you can beat it in many ways.
          > >
          >
          > s/glibc/glib/? (glibc does not contain a hash, AFAI\'m aware).

          yes

          > My point was that if you are working on a Gtk+/GNOME application, you are
          > stuck with the glib\'s hash whether you want it or not, because it\'s part
          > of the Gtk+/GNOME architecture. You can code your own hash in ANSI C, but
          > then you may be criticized for making the code unreadable, or deviating
          > from the Standard Way of Doing Things<tm> there. And in Glib\'s 1.2 at
          > least, I believe it\'s impossible to define a hash with the same interface
          > as Glib\'s hash, not to mention that the interface itself is not very
          > optimizied (or sensible).

          Well, the SWoDT is not always the best, and you ought not always to listen to
          what other people say about your style. Well, maybe listen, but not always
          embrace.

          -- Arik
        • Arik Baratz
          vailable ]?= MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Perhaps all you want is to distribute a set of values in a uniform fashion. -- Arik
          Message 4 of 22 , Feb 7, 2002
          • 0 Attachment
            vailable ]?=
            MIME-Version: 1.0
            Content-Type: text/plain; charset=iso-8859-1


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

            -- Arik

            On 07.02.2002 at 12:09:56, Ofir Carny <ofir@...> wrote:

            > As I said, it is only good for specific applications, obviously, you can\'t
            > change a hash function without rebuilding an existing table, however in some
            > applications it is enough to prevent a malicious attempt to \'break\' your
            > function.
            >
            > I didn\'t refer to the chain, however (unrelated), you can use a second
            > function to use the table for the chain, avoiding memory allocation for
            > collisions in a constant sized table.
            > -----Original Message-----
            > From: Nadav Har\'El [mailto:nyh@...]
            > Sent: Thursday, February 07, 2002 11:39 AM
            > To: hackers-il@yahoogroups.com
            > Subject: Re: [hackers-il] Re: To Hash or not to Hash [was Re: \\\"On
            > Lisp\\\" now available ]
            >
            >
            > On Thu, Feb 07, 2002, Ofir Carny wrote about \"RE: [hackers-il] Re: To Hash
            > or not to Hash [was Re: \\\"On Lisp\\\" now available ]\":
            > > As far as I remember, for some applications, you can also use a random
            > hash
            > > in order to avoid being tricked.
            > >
            > > This means a hash function which is not constant (or depends on another
            > not
            > > constant parameter).
            >
            > What do you mean? If you place an entry somewhere in the table, and next
            > time you go looking for it your \"random hash\" lands you somewhere else,
            how
            > will you find that existing entry? Maybe you mean ordering entries in one
            > hash chain in a random order? But I can\'t see what that would get you -
            > hash chains are supposed to be short anyway.
            >
            > --
            > Nadav Har\'El | Thursday, Feb 7 2002, 25 Shevat
            > 5762
            > nyh@...
            > |-----------------------------------------
            > Phone: +972-53-245868, ICQ 13349191 |The world is coming to an end ... SAVE
            > http://nadav.harel.org.il |YOUR BUFFERS!!!
            >
            > 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/
            >
            >
            >
            > **********************************************************************
            > This email and any files transmitted were checked by
            > Port Authority Enterprise for unathorized content.
            > **********************************************************************
            >
            >
            >
            > 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.
          • Nadav Har'El
            ... Wow, something is *REALLY* wrong with your mail program, Vidius filter, or whatever... A part of the the subject got hacked off into the main text (as you
            Message 5 of 22 , Feb 7, 2002
            • 0 Attachment
              On Thu, Feb 07, 2002, Arik Baratz wrote about "=?iso-8859-1?Q?Re: [hackers-il] Re: To Hash or not to Hash [was Re: \\\"On Lisp\\\" now av=":
              > ailable ]?=
              > MIME-Version: 1.0
              > Content-Type: text/plain; charset=iso-8859-1

              Wow, something is *REALLY* wrong with your mail program, Vidius filter,
              or whatever... A part of the the subject got hacked off into the main
              text (as you can see in the quote above),

              > > > want a lean and mean function, you\\\'d have to analyze the domain you are
              > working
              > > > with and think up a function that hashes it ok.
              > > That was the case with Freecell Solver, where I recently switched from MD5
              > > to Perl\'s hash function and did not notice too big a difference in the

              and something caused all single quotes in your message (even its subject line)
              to be backslashed, sometimes by more than one backslash. What is this - a
              mailer written in a shell? :)

              Weird ;)


              --
              Nadav Har'El | Thursday, Feb 7 2002, 26 Shevat 5762
              nyh@... |-----------------------------------------
              Phone: +972-53-245868, ICQ 13349191 |I before E except after C. We live in a
              http://nadav.harel.org.il |weird society!
            • Arik Baratz
              On Lisp now av=3D?= MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 ... [hackers-il] Re: To Hash or not to Hash [was Re:
              Message 6 of 22 , Feb 7, 2002
              • 0 Attachment
                \\\\\\"On Lisp\\\\\\\" now av=3D?=
                MIME-Version: 1.0
                Content-Type: text/plain; charset=iso-8859-1

                On 07.02.2002 at 21:18:58, Nadav Har\'El <nyh@...> wrote:

                > On Thu, Feb 07, 2002, Arik Baratz wrote about \"=?iso-8859-1?Q?Re:
                [hackers-il] Re: To Hash or not to Hash [was Re: \\\\\\\"On Lisp\\\\\\\" now
                av=\":
                > > ailable ]?=
                > > MIME-Version: 1.0
                > > Content-Type: text/plain; charset=iso-8859-1
                >
                > Wow, something is *REALLY* wrong with your mail program, Vidius filter,
                > or whatever... A part of the the subject got hacked off into the main
                > text (as you can see in the quote above),

                I\'m in the united states right now, and I\'m using JawMail
                http://jawmail.sf.net beta version. It has some flaws, I admit.
                >
                > > > > want a lean and mean function, you\\\\\\\'d have to analyze the domain
                you are
                > > working
                > > > > with and think up a function that hashes it ok.
                > > > That was the case with Freecell Solver, where I recently switched from
                MD5
                > > > to Perl\\\'s hash function and did not notice too big a difference in
                the
                >
                > and something caused all single quotes in your message (even its subject
                line)
                > to be backslashed, sometimes by more than one backslash. What is this - a
                > mailer written in a shell? :)
                >
                > Weird ;)

                Not in shell, in PHP. It\'s somewhat buggy, but it works...


                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.
              • mulix
                ... [snipped other such monstrosities, and then arik said] ... egads, whatever happened to good ol telnet my.mail.server.com 25 and talking SMTP like
                Message 7 of 22 , Feb 7, 2002
                • 0 Attachment
                  On Thu, 7 Feb 2002, Arik Baratz wrote:

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

                  [snipped other such monstrosities, and then arik said]
                  > Not in shell, in PHP. It\'s somewhat buggy, but it works...

                  egads, whatever happened to good ol' telnet my.mail.server.com 25 and
                  talking SMTP like reasonable human beings?

                  ObHackersIL - nothing. things have certainly hit a low point.
                  --
                  mulix

                  http://vipe.technion.ac.il/~mulix/
                  http://syscalltrack.sf.net/
                Your message has been successfully submitted and would be delivered to recipients shortly.