Subject: checksums?

From: Tzahi Fadida <[email-masked]>
Date: Wed, 23 Mar 2005 14:31:30 +0200

Hi,
Can someone clarify for me a few things about checksums like md5 or sha,
etc...:
- when you create a checksum from a specific string it will always
  return the same checksum.
- Is there an upper bound on the amount of same checksums
  occuring from different strings on a population of lets
  say f different strings? is there an approximation? anything?
  any article about this?

10x.

Regards,
	tzahi.

* - * - *
Itzhak Fadida
MSc Student
Information System Engineering Area
Faculty of Industrial Engineering & Management
Technion - Israel Institute of Technology
Technion City, Haifa, Israel 32000
Technion Email: [email-masked]
Alternative Email: [email-masked]
Office Phone(from Israel): 04-8292226
Office Location: Technion, Cooper Bldg. room 427.
* - * - * - * - * - * - * - * - * - * - * - * - * - * - *

WARNING TO SPAMMERS:  see at
http://members.lycos.co.uk/my2nis/spamwarning.html

---

From: Shlomi Fish <[email-masked]>
Date: Wed, 23 Mar 2005 14:57:08 +0200

>   return the same checksum.

Right. Such checksum are entirely deterministic on the string they process.

>   say f different strings? 

Well, such hash functions should have a property that there's an equal chance 
to get each possible checksum. If there are N different checksums in the 
checksum space, and there are f strings, then the chance that all the 
checksums will be different is:

((N-1)/N)*((N-2)/N)*((N-3)/N)... ((N-(f-1))/N)

Regards,

	Shlomi Fish

>   is there an approximation? anything? 
>   any article about this?
>
> 10x.
>
> Regards,
> 	tzahi.
>
> * - * - *
> Itzhak Fadida
> MSc Student
> Yahoo! Groups Links

-- 

---------------------------------------------------------------------
Shlomi Fish      [email-masked]
Homepage:        http://www.shlomifish.org/

Hacker sees bug. Hacker fixes bug.

---

From: Eran Tromer <[email-masked]>
Date: Wed, 23 Mar 2005 15:27:04 +0200

Hi Tzahi,

> Can someone clarify for me a few things about checksums like md5 or sha,
...
>   say f different strings? is there an approximation? anything?

Are you interested in average-case situations, or in worst-case
situations where you have an adversary working against you and trying to
feed you bad data?

In the former case, you can heuristically pretend that each hash value
f(x) is drawn independent and uniformly at random, and apply standard
statistics to estimate whatever probabilities you're interested in.

In the latter case, things can get quite nasty if the hash function is
insecure. For example, for MD5 and SHA1, recent cryptanalytic attacks
show how to build arbitrarily large sets of strings that have the same
hash value. But if you take a sufficiently strong hash function (e.g.,
SHA-256), then for many practical purposes you can still apply the above
heuristic.

If you want strict, unconditional, worst-case bounds, you're probably
looking at the wrong tools. In that case you'd need a combinatorial or
algebraic construction, rather than a cryptographic one.

  Eran

---

From: Tzahi Fadida <[email-masked]>
Date: Wed, 23 Mar 2005 18:00:49 +0200

well, I want to try something like:
I have a set of f strings with a fixed upper bound on their size.
actullay these strings
are tuples in a relation.
now you should know that f is an exponential numer among n relations.
actually
it could be the number of tuples received from a cartesian product of n
relations.
The problem starts when I have to check if a result tuple is in the f
tuples.
there are several ways to attack this:
1. scan sequentially f tuples.
2. build a huge index. but I only search existence and don't care about
contents.
3. don't keep the result tuples on disk and hash it using md5 etc.. and
put it into an extandable hashtable.
but understand that for 10% of the time I will think that a result tuple
is in there.

Regards,
	tzahi.

> -----Original Message-----
> From: Eran Tromer [mailto:[email-masked]] 
> Sent: Wednesday, March 23, 2005 3:27 PM
> To: [email-masked]
> Subject: Re: [hackers-il] checksums?
> 
> 
> 
> Hi Tzahi,
> 
> Are you interested in average-case situations, or in 
> worst-case situations where you have an adversary working 
> against you and trying to feed you bad data?
> 
> f(x) is drawn independent and uniformly at random, and apply 
> standard statistics to estimate whatever probabilities you're 
> interested in.
> 
> In the latter case, things can get quite nasty if the hash 
> function is insecure. For example, for MD5 and SHA1, recent 
> cryptanalytic attacks show how to build arbitrarily large 
> sets of strings that have the same hash value. But if you 
> take a sufficiently strong hash function (e.g., SHA-256), 
> then for many practical purposes you can still apply the 
> above heuristic.
> 
> If you want strict, unconditional, worst-case bounds, you're 
> probably looking at the wrong tools. In that case you'd need 
> a combinatorial or algebraic construction, rather than a 
> cryptographic one.
> 
>   Eran
> 
> 
>  
> Yahoo! Groups Links
> 
> 
> 
>  
> 
> 
> 
>

---

From: Tzahi Fadida <[email-masked]>
Date: Wed, 23 Mar 2005 18:32:51 +0200

> ((N-1)/N)*((N-2)/N)*((N-3)/N)... ((N-(f-1))/N)
lets say the above = P

For large N and small f it would be close to 1.
Well, I am not a mathematician, but is this applies to all checksums?
For example if I have an md5 checksum of 32 bits(bytes) then it means
that N=2^32 and thus
if f=1024 then the chance of encountering 1 checksum from 2 different
strings
is the above P?

---

From: Eran Tromer <[email-masked]>
Date: Wed, 23 Mar 2005 18:50:33 +0200

> now you should know that f is an exponential numer among n relations.

Sorry, can't parse that.

> it could be the number of tuples received from a cartesian product of n

If your tuple set is a nice cartesian product AxBxZx...xZ, why don't you
just store A,...,Z and check coordinate-wise membership?

> put it into an extandable hashtable.

There are some data structures designed for membership testing. Google
on "Bloom filters", for example.

> but understand that for 10% of the time I will think that a result tuple

There's certainly no such universal rule; it depends on the data
structure and parameters.

  Eran

---

From: Tzahi Fadida <[email-masked]>
Date: Wed, 23 Mar 2005 19:10:57 +0200

> > now you should know that f is an exponential numer among n 

I meant f is a number. if we have n relations in a database and each
relation
is of size s_i then f could go up to s_1*s_2*...*s_n

> 
> Sorry, can't parse that.
> 
> > actually
> > it could be the number of tuples received from a cartesian 
> product of 
> > n relations.
> 
> If your tuple set is a nice cartesian product AxBxZx...xZ, 
> why don't you just store A,...,Z and check coordinate-wise membership?

I reffered to the size. there is no structure. 

> 
> > 2. build a huge index. but I only search existence and don't care 
> > about contents. 3. don't keep the result tuples on disk and hash it 
> > using md5 etc.. and put it into an extandable hashtable.
> 
> There are some data structures designed for membership 
> testing. Google on "Bloom filters", for example.

10x!, I'll check it.

> 
> > but understand that for 10% of the time I will think that a result 
> > tuple is in there.
> 
> There's certainly no such universal rule; it depends on the 
> data structure and parameters.

That's not good. I was hoping that at least if there was an upper bound
on the size
of the string there would be something.

---

From: "Nadav Har'El" <[email-masked]>
Date: Wed, 23 Mar 2005 19:27:03 +0200

On Wed, Mar 23, 2005, Tzahi Fadida wrote about "RE: [hackers-il] checksums?":
>..

There are several questions which you should ask yourself:

1. How many bits of hash code are "enough", to keep the error risk very low?

   For all intents and purposes, you can assume that a (good) hash function's
   output will be uniform across its output domain. So, if you want to hash
   two strings, and use 128 bits of hash (2^128 possible hash codes), the
   chance that two strings get the same hash code is a mere 1/2^128, or one in
   about 700 sextillion (europian nomenclature). Now that's a tiny risk ;)

   But what if you hash a 2^32 strings? What is the chance that two come out
   the same? Don't be tempted to just multiply 2^32 by 1/2^128 - this is an
   incorrect answer. This is known as the "birthday paradox" - there are 365
   different birth dates in the year, but yet if you take just 23 people,
   there's a 50% chance that two of them were born on the same date.
   See http://en.wikipedia.org/wiki/Birthday_paradox for more information.

   Now for a correct estimate: if we have M hash codes (2^128 in my example)
   and F different strings to hash (2^32 in my example), the chance of two
   strings getting the same hash is smaller than: (see the above link)

		P = 1 - e ^ -(F^2-F)/2M

   In our example, P = 1 - e ^ -(2^64-2^32)/2^129 ~= 1 - 1/(e^2^-65)
   and this is a tiny, tiny, TINY risk (feel free to estimate it with some
   first-year calculus). But as the number of strings F approaches the
   square root of the number of codes (M), your risk becomes large.

   So, to be on the safe side, just pick a hash table whose space is more
   than square that of the given strings. Do you have 2^32 possible strings?
   use a 128 bit hash. Do you have 2^64 possible strings? use a 256 bit hash.

1. How big is each of these strings, in relation to the hash code you'll
   need to keep?

   If the strings are dense in your space, hashes might not save you
   anything. For example, if you have 2^32 strings, but each string is
   just 128 bits long, hashes won't save you any space because we've
   established earlier that a hash length of 128 bits is recommended.
   But, if you have just 2^32 strings the length of each is 10,000 bits,
   then you can definitely save space by hashing.

-- 
Nadav Har'El                        |  Wednesday, Mar 23 2005, 13 Adar II 5765
[email-masked]             |-----------------------------------------
Phone +972-523-790466, ICQ 13349191 |Despite the cost of living, have you
http://nadav.harel.org.il           |noticed how it remains so popular?

---

From: Eran Tromer <[email-masked]>
Date: Wed, 23 Mar 2005 19:27:23 +0200

>>testing. Google on "Bloom filters", for example.

I found a nice survey paper on Bloom filters a while ago; I'll sent it
to you off-list.

> on the size of the string there would be something.

No, there certainly *are* bounds, and you *can* make the error
probability as low as you want -- but you'll have to choose (and pay the
resource cost of) the appropriate construction and parameters, and make
appropriate assumptions about the distribution of your data.

  Eran