syscall convention - analysis of collision probability.

dwheelerat_private

Well, it's dangerous to do, but I thought I'd actually do some analysis
and report on it.  I've written a program that determines the probability
of a hash collision if security modules use MD5 hashes slimmed to 32 bits
(assuming different names are used).

Basically, MD5 works, even if you're only using 32 bits, as a practical
method for distinguishing modules.

Given 10 security modules, the odds are 0.00000105% (about 1 in a 100 million)
for a collision.

The odds go up with more modules, but the numbers are EXTREMELY small...
the odds of a hash collision are nearly non-existant, even if there are
1000 different security modules (!).  I'd expect no more than 100 such
modules, so this just isn't a problem.  Even if there WAS a collision, it's
not a serious problem - they can collide, or one can ignore this convention,
or one can change its name.

Here's sample data..

#
Modules Probability of collision
====== ========================
    20 0.00000442%
    30 0.00001013%
    40 0.00001816%
    50 0.00002852%
    60 0.00004121%
    70 0.00005623%
    80 0.00007357%
    89 0.00009118%
   100 0.00011525%    <-- about 1 in a million, if 100 modules.
   200 0.00046333%
   500 0.00290452%
  1000 0.01162922%    <-- about 1 in 10,000, if 1000 (!) modules.

And here's the code I used to generate these numbers:

#!/usr/bin/env python

s=2.**32  # The space of possible random numbers.
n=1000   # The largest number of independent random variables.

p=0.0     # The probability of collision.
for i in xrange(2, n+1):
  p = p + (1.-p)*((i-1.)/s)
  print "%6d %4.8f%%" % (i, p*100.)

_______________________________________________
linux-security-module mailing list
linux-security-moduleat_private
http://mail.wirex.com/mailman/listinfo/linux-security-module