hamadryad.mx raw
1 // Hamadryad: SWIFFT-derived lattice hash.
2 // Ring: Z_257[x]/(x^64 + 1), n=64, m=16.
3 // Output: 448-bit (56 bytes) canonical hash, 48-bit (6 bytes) shard.
4 package hamcrypto
5
6 import "crypto/rand"
7
8 const (
9 HamN = 64
10 HamM = 16
11 HamP = 257
12 HamR = 128
13 HamInputBits = HamM * HamN
14 HamFullBits = HamN * 9
15 HamBits = HamN * 7
16 HamBytes = HamBits / 8
17 ShardBits = 48
18 ShardBytes = ShardBits / 8
19 )
20
21 type Hamadryad [HamBytes]byte
22 type Shard [ShardBytes]byte
23
24 // Disperse extracts the 48-bit Shard from a full Hamadryad.
25 func (p *Hamadryad) Disperse() (s Shard) {
26 copy(s[:], p[:ShardBytes])
27 return s
28 }
29
30 // hamKeys holds the m=16 fixed random polynomials in NTT form.
31 var hamKeys [HamM][HamN]uint16
32
33 const hamInputBytes = HamInputBits / 8
34
35 // Single init for the crypto package: NTT tables + key generation.
36 func main() {
37 initNTTTables()
38 initNTT27Tables()
39 initHamKeys()
40 initGnarlKeys()
41 }
42
43 func initHamKeys() {
44 seed := uint64(0)
45 seedStr := "hamadryad-swifft-v1-dendrite-kismet"
46 for i := int32(0); i < int32(len(seedStr)); i++ {
47 seed ^= uint64(seedStr[i]) << ((uint(i) * 7) % 64)
48 }
49
50 xorshift := func() (v uint64) {
51 seed ^= seed << 13
52 seed ^= seed >> 7
53 seed ^= seed << 17
54 return seed
55 }
56
57 for i := int32(0); i < HamM; i++ {
58 var poly [HamN]uint16
59 for j := int32(0); j < HamN; j++ {
60 poly[j] = uint16(xorshift() % uint64(HamP))
61 }
62 ntt64(&poly)
63 hamKeys[i] = poly
64 }
65 }
66
67 // hamCompress computes one SWIFFT compression: 128 bytes -> 64 coefficients in Z_257.
68 func hamCompress(block *[hamInputBytes]byte) (acc [HamN]uint16) {
69 for i := int32(0); i < HamM; i++ {
70 var poly [HamN]uint16
71 base := i * (HamN / 8)
72 for j := int32(0); j < HamN; j++ {
73 byteIdx := base + j/8
74 bitIdx := uint(j % 8)
75 if block[byteIdx]&(1<<bitIdx) != 0 {
76 poly[j] = 1
77 }
78 }
79 ntt64(&poly)
80 for j := int32(0); j < HamN; j++ {
81 product := mod257(int32(poly[j]) * int32(hamKeys[i][j]))
82 acc[j] = mod257(int32(acc[j]) + int32(product))
83 }
84 }
85 intt64(&acc)
86 return acc
87 }
88
89 // packCoeffs packs 64 Z_128 coefficients (7 bits each) into 56 bytes.
90 func packCoeffs(coeffs [HamN]uint16) (out Hamadryad) {
91 bitPos := int32(0)
92 for i := int32(0); i < HamN; i++ {
93 v := coeffs[i] % HamR
94 for b := int32(0); b < 7; b++ {
95 if v&(1<<uint(b)) != 0 {
96 byteIdx := bitPos / 8
97 bitIdx := uint(bitPos % 8)
98 out[byteIdx] |= 1 << bitIdx
99 }
100 bitPos++
101 }
102 }
103 return out
104 }
105
106 // unpackCoeffs unpacks a Hamadryad back into 64 Z_128 coefficients.
107 func unpackCoeffs(p Hamadryad) (coeffs [HamN]uint16) {
108 bitPos := int32(0)
109 for i := int32(0); i < HamN; i++ {
110 var v uint16
111 for b := int32(0); b < 7; b++ {
112 byteIdx := bitPos / 8
113 bitIdx := uint(bitPos % 8)
114 if p[byteIdx]&(1<<bitIdx) != 0 {
115 v |= 1 << uint(b)
116 }
117 bitPos++
118 }
119 coeffs[i] = v
120 }
121 return coeffs
122 }
123
124 // Hash computes the Hamadryad hash of an arbitrary-length message.
125 func Hash(msg []byte) (h Hamadryad) {
126 var chain [HamN]uint16
127
128 // Pad message: append 0x80, then zeros, then 8-byte LE length.
129 padded := []byte{:int32(len(msg))}
130 copy(padded, msg)
131 padded = append(padded, 0x80)
132 for (int32(len(padded))+8)%hamInputBytes != 0 {
133 padded = append(padded, 0)
134 }
135 // Append message length in bits as 8-byte LE.
136 msgLenBits := uint64(len(msg)) * 8
137 padded = append(padded,
138 byte(msgLenBits),
139 byte(msgLenBits>>8),
140 byte(msgLenBits>>16),
141 byte(msgLenBits>>24),
142 byte(msgLenBits>>32),
143 byte(msgLenBits>>40),
144 byte(msgLenBits>>48),
145 byte(msgLenBits>>56),
146 )
147
148 // Process each 128-byte block.
149 off := int32(0)
150 for off < int32(len(padded)) {
151 var block [hamInputBytes]byte
152 copy(block[:], padded[off:off+hamInputBytes])
153 result := hamCompress(&block)
154 for j := int32(0); j < HamN; j++ {
155 chain[j] = mod257(int32(chain[j]) + int32(result[j]))
156 }
157 off += hamInputBytes
158 }
159
160 return packCoeffs(chain)
161 }
162
163 // Sum returns the coefficient-wise sum (mod 128) of two Hamadryad hashes.
164 func (p *Hamadryad) Sum(other *Hamadryad) (result Hamadryad) {
165 a := unpackCoeffs(*p)
166 b := unpackCoeffs(*other)
167 var res [HamN]uint16
168 for i := int32(0); i < HamN; i++ {
169 res[i] = (a[i] + b[i]) % HamR
170 }
171 return packCoeffs(res)
172 }
173
174 // IsZero reports whether the Hamadryad hash is all zeros.
175 func (p *Hamadryad) IsZero() (result bool) {
176 for i := int32(0); i < HamBytes; i++ {
177 if p[i] != 0 {
178 return false
179 }
180 }
181 return true
182 }
183
184 // RandomHamadryad generates a cryptographically random Hamadryad value.
185 func RandomHamadryad() (p Hamadryad) {
186 _, err := rand.Read(p[:])
187 if err != nil {
188 panic("crypto/rand failed")
189 }
190 return p
191 }
192