Re: One-to-one Hash functions

From: Peter Pearson (ppearson_at_nowhere.invalid)
Date: 09/16/05 

Date: Fri, 16 Sep 2005 10:29:48 -0700

Unruh wrote:

> pazort@gmail.com writes:
>>Essentially, the function should behave in such a way so that if you
>>chose one string length less than or equal to 128-bits, then if you
>>took the hash of all of the possible strings of that size, there would
>>be no collisions, but that may also be able to produce a hash for
>>strings longer than 128 bits; I'm not concerned with collisions over
>>that size.
>
> Why in the world would you want that?

I agree. But, anyway, if you want some (limited) one-wayness
without depending upon a secret key, use this:

hash(x) = 2^x mod 340282366920938463463374607431768196021

Drawbacks:
 1. There will be a few collisions among the 2^128
    input strings of length 128 bits. However, the
    probability of hitting one by accident in a billion
    tries is smaller than the probability of getting
    struck by a meteorite while reading this posting.
 2. It is possible to find a preimage for any given hash
    by solving the discrete log problem for this 128-bit
    modulus, an undertaking that several readers of this
    newsgroup could complete in a day (I think).

In deference to normal standards of responsible adult behavior,
I should point out that, while we've had fun playing with your
strange question, if bad consequences would result from your
scheme's failure to do what you need, you should present this
group with a much clearer picture of your requirements, including
a description of the attacker (if any) who must be thwarted. 

-- 
Peter Pearson
To get my email address, substitute:
nowhere -> spamcop, invalid -> net

Relevant Pages

  • Re: [RFC/PATCH] Documentation of kernel messages
    ... Maybe a stupid idea but why do we want to assign these numbers by hand? ... I can imagine it could introduce collisions when merging tons of patches ... But maybe also 4 bytes would be enough, since the hash only has to be ... For 1000 messages the probability is ...
    (Linux-Kernel)
  • The certification password of Internet Explorer 7 and operation of auto complete
    ... About the certification password of Internet Explorer and operation ... By remembering the strings that are input in the following text ... In this registry, there are values whose name is a string of 42 bytes ... We cannot guess the original strings from the hash value, ...
    (Bugtraq)
  • The math of CRC functions
    ... text such that the chance of hash collisions is a small as possible ... I'm thinking CRC functions are a good answer. ... the inputs are all strings of ASCII text and thus the ... But what if all I care about is minimizing the chance of hash ...
    (sci.math)
  • Re: Basic Question
    ... example, which produces a 128-bit hash, is guaranteed not to produce any ... to produce collisions for some strings no longer than 129 bits. ... "substantially less" can be calculated given the exact meaning of ...
    (talk.politics.crypto)
  • Re: Maximum String size in Java?
    ... > for long strings, so on average, SFH bakes it in the performance ... >> distribution over the hash table size. ... > you need to be concerned about Unicode strings. ... construct a hash function that does appreciably better than the one ...
    (comp.programming)