Checksum Collider Example

checksum-collider.go

//Simulation of the Birthday Paradox
//Find no. files needed for chance of a single collision
package main

import "fmt"
import "math"

func main() {

   var BITS float64 = 512
   var P float64 = 0.5
   var x float64 = 0
   var keyStrengthBits = math.Pow(2,BITS)
   var noFiles = math.Pow(2,(BITS/2)) //No Files to begin from
   for x < P {
      var k = noFiles
      x = 1 - math.Exp(-0.5 * k * (k - 1) / keyStrengthBits)
      if BITS >= 64 {
      noFiles = noFiles + (noFiles/100000) //math.Pow(N2,2) //+=1
      } else {
         noFiles = noFiles + 1
      }

      s := fmt.Sprintf("%g, %f", noFiles, x)
      fmt.Println(s)
   }
}

find-collisions,py

#similar script to see percentage of collisions, per each no. file
#less efficient, more thorough, good for graph generation
import math
N = 2**32
probUnique = 1.0
for k in xrange(0,100000):
    print k, 1 - math.exp(-0.5 * k * (k - 1) / N)

notes-on-checksums.txt

Zhimin Ding - bcdebe79c66b24c3f9cc5b61f6a6ee8425ce87b8 - SHA1

Sonya Behrnes - d0e29653ddca52e9c9dd4525731fef5e - MD5 

Sarah Cho - c9c44567cc434134b33f6178fa70591f3d0a9a979bb012de8512648e4eccab95 - SHA256

--

Wide variation in difference:

USA: f75d91cdd36b85cc4a8dfeca4f24fa14
USB: 7aca5ec618f7317328dcd7014cf9bdcf

--

SHA256 - 256-bit output - 64 character length - 400 Undecillion - 400,656,698,530,848,040,000,000,000,000,000,000,000
SHA1   - 160-bit output - 40 character length - 1 Septillion - 1,423,418,533,373,592,400,000,000
MD5    - 128-bit output - 32 character length - 21 Quintillion - 21,719,643,148,400,763,000
CRC32  - 32-bit output  - 8  character length - 77 Thousand, 165 - 77165

--

Represented using hexadecimal digits - 0-9 and A-F

--

2^64

18 446 744 073 709 551 616 - 18 billion billion - 18 quintillion inputs needed

For a 50% chance two MD5 checksums will collide. 

2^128 chance any random two inputs will collide. 

--

Checksum vs. Fixity

Checksum is a mathematical way of saying something has changed
If we had a collision, we can still verify it other ways - Filename, File Date, File Length, etc. 

--

More reading:

http://preshing.com/20110504/hash-collision-probabilities/

http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/

http://www.unixwiz.net/techtips/iguide-crypto-hashes.html 

--

http://stackoverflow.com/questions/201705/how-many-random-elements-before-md5-produces-collisions
http://lemire.me/blog/2013/06/17/hashing-and-the-birthday-paradox-cautionary-tale/

Try the code here: https://play.golang.org/p/q2bwtuK7i6

Algorithm here: http://preshing.com/20110504/hash-collision-probabilities/