hs1.go 3.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
  1. // hs1.go - HS1 hash function
  2. //
  3. // To the extent possible under law, Yawning Angel has waived all copyright
  4. // and related or neighboring rights to the software, using the Creative
  5. // Commons "CC0" public domain dedication. See LICENSE or
  6. // <http://creativecommons.org/publicdomain/zero/1.0/> for full details.
  7. package hs1siv
  8. import "encoding/binary"
  9. const (
  10. hs1NHLen = 64 // Parameter b
  11. hs1HashRounds = 6 // Parameter t
  12. hs1SIVLen = 32 // Parameter l
  13. m60 = (1 << 60) - 1
  14. m61 = (1 << 61) - 1
  15. hashStateSize = (hs1NHLen/4+4*(hs1HashRounds-1))*4 + hs1HashRounds*8 + hs1HashRounds*3*8
  16. )
  17. type hs1Ctx struct {
  18. nhKey [hs1NHLen/4 + 4*(hs1HashRounds-1)]uint32
  19. polyKey [hs1HashRounds]uint64
  20. asuKey [hs1HashRounds * 3]uint64
  21. }
  22. func (ctx *hs1Ctx) reset() {
  23. burnUint32s(ctx.nhKey[:])
  24. burnUint64s(ctx.polyKey[:])
  25. burnUint64s(ctx.asuKey[:])
  26. }
  27. // Return 63 bits congruent to ak+b mod (2^61-1). Assume 60-bit k,b 63-bit a.
  28. func polyStep(a, b, k uint64) uint64 {
  29. // No uint128_t or equivalent. Could use inline assembly here, but Go
  30. // can't/won't inline it, and the function call overhead will eclipse any
  31. // performance gain.
  32. m := uint64(uint32(a>>32))*uint64(uint32(k)) + uint64(uint32(k>>32))*uint64(uint32(a))
  33. h := uint64(uint32(a>>32)) * uint64(uint32(k>>32))
  34. l := uint64(uint32(a)) * uint64(uint32(k))
  35. return (l & m61) + (h << 3) + (l >> 61) + b + (m >> 29) + ((m << 32) & m61)
  36. }
  37. // Reduce a mod (2^61-1) in constant time.
  38. func polyFinalize(a uint64) uint64 {
  39. a = (a & m61) + (a >> 61)
  40. mask := uint64(int64((m61-1)-a) >> 63)
  41. return a - (mask & m61)
  42. }
  43. func asuHash(x uint64, k []uint64) uint32 {
  44. _ = k[2] // Bounds check elimination.
  45. t := k[0] + k[1]*uint64(uint32(x)) + k[2]*uint64(uint32(x>>32))
  46. return uint32(t >> 32)
  47. }
  48. func hashStepRef(ctx *hs1Ctx, in []byte, accum *[hs1HashRounds]uint64) {
  49. // len(in) MUST be a multiple of hs1NHLen.
  50. inBytes := len(in)
  51. for inBytes > 0 {
  52. var nhRes [hs1HashRounds]uint64
  53. for i := 0; 4*i < hs1NHLen; i += 4 {
  54. _ = in[15] // Bounds check elimination.
  55. mp0 := binary.LittleEndian.Uint32(in[0:4])
  56. mp1 := binary.LittleEndian.Uint32(in[4:8])
  57. mp2 := binary.LittleEndian.Uint32(in[8:12])
  58. mp3 := binary.LittleEndian.Uint32(in[12:16])
  59. for j := 0; j < hs1HashRounds; j += 2 {
  60. kp := ctx.nhKey[i+j*4:]
  61. _ = kp[7] // Bounds check elimination.
  62. nhRes[j+0] += uint64(mp0+kp[0]) * uint64(mp2+kp[2])
  63. nhRes[j+1] += uint64(mp0+kp[4]) * uint64(mp2+kp[6])
  64. nhRes[j+0] += uint64(mp1+kp[1]) * uint64(mp3+kp[3])
  65. nhRes[j+1] += uint64(mp1+kp[5]) * uint64(mp3+kp[7])
  66. }
  67. in = in[16:]
  68. }
  69. for j := 0; j < hs1HashRounds; j += 2 {
  70. accum[j] = polyStep(accum[j], nhRes[j]&m60, ctx.polyKey[j])
  71. accum[j+1] = polyStep(accum[j+1], nhRes[j+1]&m60, ctx.polyKey[j+1])
  72. }
  73. inBytes -= hs1NHLen
  74. }
  75. }
  76. func hashFinalizeRef(ctx *hs1Ctx, in []byte, accum *[hs1HashRounds]uint64, result []byte) {
  77. inBytes := len(in)
  78. if inBytes > 0 {
  79. var nhRes [hs1HashRounds]uint64
  80. for i := 0; 4*i < inBytes; i += 4 {
  81. _ = in[15] // Bounds check elimination.
  82. mp0 := binary.LittleEndian.Uint32(in[0:4])
  83. mp1 := binary.LittleEndian.Uint32(in[4:8])
  84. mp2 := binary.LittleEndian.Uint32(in[8:12])
  85. mp3 := binary.LittleEndian.Uint32(in[12:16])
  86. in = in[16:]
  87. for j := 0; j < hs1HashRounds; j += 2 {
  88. kp := ctx.nhKey[i+j*4:]
  89. _ = kp[7] // Bounds check elimination.
  90. nhRes[j+0] += uint64(mp0+kp[0]) * uint64(mp2+kp[2])
  91. nhRes[j+1] += uint64(mp0+kp[4]) * uint64(mp2+kp[6])
  92. nhRes[j+0] += uint64(mp1+kp[1]) * uint64(mp3+kp[3])
  93. nhRes[j+1] += uint64(mp1+kp[5]) * uint64(mp3+kp[7])
  94. }
  95. }
  96. for j := 0; j < hs1HashRounds; j += 2 {
  97. accum[j] = polyStep(accum[j], nhRes[j]&m60, ctx.polyKey[j])
  98. accum[j+1] = polyStep(accum[j+1], nhRes[j+1]&m60, ctx.polyKey[j+1])
  99. }
  100. }
  101. for j := 0; j < hs1HashRounds; j += 2 {
  102. s0 := asuHash(polyFinalize(accum[j]), ctx.asuKey[3*j:])
  103. s1 := asuHash(polyFinalize(accum[j+1]), ctx.asuKey[3*j+3:])
  104. binary.LittleEndian.PutUint32(result[j*4:], s0)
  105. binary.LittleEndian.PutUint32(result[j*4+4:], s1)
  106. }
  107. }