Sorceress

Avalanche Matrix Builder

Feb 2nd, 2021 (edited)
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. 'Avalanche Matrix Builder (c)2021, @_sorceress
  2. '---------------------------------------------
  3.  
  4. 'Plots output bits of the hash horizontally (Hi->Lo), and input bits of the key vertically (First->Last)
  5. 'The matrix shows the amount of bit flips in each output bit, when each input bit is flipped
  6. 'This is averaged over a large number of input keys. It may be impractical to try all input keys.
  7.  
  8. 'red = always/never flipped (bad)
  9. 'orange = flipped <1/3 or >2/3 of the time (not good, but acceptable for a few bits)
  10. 'green = flipped between 1/3 and 2/3 of the time (good)
  11.  
  12. KeyBytes = 3 'size of keys, in bytes. 1->4
  13. KeySamples = 50000 'number of random keys to analyse
  14.  
  15. 'choose your hash function at the bottom on this listing
  16.  
  17.  
  18.  
  19. SCREEN _NEWIMAGE(640, 480, 256)
  20.  
  21. DIM Pow(31) AS _UNSIGNED LONG
  22. Pow(0) = 1: FOR i = 1 TO 31: Pow(i) = Pow(i - 1) * 2: NEXT
  23. DIM h AS _UNSIGNED LONG, h0 AS _UNSIGNED LONG
  24. DIM F(31, 31) AS LONG
  25.  
  26. 'build the avalanche matrix
  27. KeyBits = KeyBytes * 8: L = Pow(KeyBits)
  28. RANDOMIZE TIMER
  29. FOR i = 0 TO KeySamples
  30. LOCATE 1, 1: PRINT INT(100 * i / KeySamples); "%"
  31. Key0 = INT(RND * L) 'random key
  32. sKey = Key0: GOSUB Hash: h0 = h 'hash the key to compare against
  33. FOR b0 = 0 TO KeyBits - 1 'consider bitflips
  34. sKey = Key0 XOR Pow(b0): GOSUB Hash
  35. FOR b1 = 0 TO 31
  36. IF (h AND Pow(b1)) <> (h0 AND Pow(b1)) THEN F(b1, b0) = F(b1, b0) + 1
  37. 'bit b1 was flipped in the output, when bit b0 was flipped in the input. count this flip.
  38. NEXT
  39. NEXT
  40. NEXT
  41.  
  42. 'now display the avalanche matrix
  43. d = KeySamples / 2 ' ideally the bits get flipped half of the time, so d is the number of flips corresponding to that ideal.
  44. FOR b0 = 0 TO KeyBits - 1
  45. FOR b1 = 0 TO 31
  46. excess = ABS(F(31 - b1, b0) - d) 'How many more/less flips than d did we get?
  47. IF excess = d THEN COLOR 4 'red
  48. IF excess < d THEN COLOR 43 'orange
  49. IF excess < d / 3 THEN COLOR 2 'green
  50. LOCATE b0 + 1, b1 * 2 + 1 + b1 \ 8: PRINT "[]"
  51. NEXT
  52. NEXT
  53.  
  54. END
  55.  
  56. '==========================================================
  57. Hash:
  58. GOSUB jenkins
  59. RETURN
  60.  
  61. fnv1a: 'FNV1-a. A general purpose hash with good collision behaviour, but not great avalanching.
  62. h = 2166136261
  63. FOR j = 1 TO KeyBytes
  64. ch = sKey AND 255
  65. h = (h XOR ch) * 16777619
  66. sKey = sKey \ 256
  67. NEXT
  68. RETURN
  69.  
  70. djb2a: 'Bernstein's hash. Excellent collision behaviour for short alphanumeric keys, but terrible avalanching.
  71. h = 5381
  72. FOR j = 1 TO KeyBytes
  73. ch = sKey AND 255
  74. h = (h * 33) XOR ch
  75. sKey = sKey \ 256
  76. NEXT
  77. RETURN
  78.  
  79. jenkins: 'Jenkins one at a time. A bit slower with more overhead, but excellent avalanching.
  80. h = 0
  81. FOR j = 1 TO KeyBytes
  82. ch = sKey AND 255
  83. h = h + ch
  84. h = h * 1025
  85. h = h XOR (h \ 64)
  86. sKey = sKey \ 256
  87. NEXT
  88. h = h * 9
  89. h = h XOR (h / 2048)
  90. h = h * 32769
  91. RETURN
  92.  
RAW Paste Data