gnarl_hash.mx raw
1 package hamcrypto
2
3 // Trinary SWIFFT hash for the Gnarl scheme.
4 // Ring: Z_271[x]/(x^27 + 1), n=27, m=12.
5
6 import "crypto/rand"
7
8 const (
9 GnarlM = 12
10 GnarlInputBits = GnarlM * GnarlN
11 gnarlInputBytes = (GnarlInputBits + 7) / 8
12 GnarlHashBits = GnarlN * 9
13 GnarlHashBytes = (GnarlHashBits + 7) / 8
14 GnarlMidBits = GnarlN * 8
15 GnarlMidBytes = GnarlMidBits / 8
16 GnarlShardBits = GnarlN * 2
17 GnarlShardBytes = (GnarlShardBits + 7) / 8
18 GnarlMidR = 243
19 GnarlShardR = 3
20 )
21
22 type GnarlHash [GnarlHashBytes]byte
23 type GnarlMid [GnarlMidBytes]byte
24 type GnarlShard [GnarlShardBytes]byte
25
26 var gnarlKeys [GnarlM][GnarlN]uint16
27
28 const gnarlBasisPad = 32
29
30 var gnarlKeyBasis [GnarlM][GnarlN][gnarlBasisPad]uint16
31
32 func initGnarlKeys() {
33 seed := uint64(0)
34 seedStr := "gnarl-hamadryad-v1-dendrite-trinary"
35 for i := int32(0); i < int32(len(seedStr)); i++ {
36 seed ^= uint64(seedStr[i]) << ((uint(i) * 7) % 64)
37 }
38
39 xorshift := func() (v uint64) {
40 seed ^= seed << 13
41 seed ^= seed >> 7
42 seed ^= seed << 17
43 return seed
44 }
45
46 for i := int32(0); i < GnarlM; i++ {
47 var poly [GnarlN]uint16
48 for j := int32(0); j < GnarlN; j++ {
49 poly[j] = uint16(xorshift() % uint64(GnarlP))
50 }
51 ntt27(&poly)
52 gnarlKeys[i] = poly
53 }
54
55 // Precompute basis tables.
56 for i := int32(0); i < GnarlM; i++ {
57 for k := int32(0); k < GnarlN; k++ {
58 var ek [GnarlN]uint16
59 ek[k] = 1
60 ntt27(&ek)
61 for j := int32(0); j < GnarlN; j++ {
62 gnarlKeyBasis[i][k][j] = mod271(uint32(gnarlKeys[i][j]) * uint32(ek[j]))
63 }
64 }
65 }
66 }
67
68 // gnarlCompress computes one SWIFFT compression: 41 bytes -> 27 coefficients in Z_271.
69 func gnarlCompress(block *[gnarlInputBytes]byte) (result [GnarlN]uint16) {
70 var acc [gnarlBasisPad]uint32
71 gnarlAccumulate(&acc, &gnarlKeyBasis, block)
72 for j := int32(0); j < GnarlN; j++ {
73 result[j] = mod271(acc[j])
74 }
75 intt27(&result)
76 return result
77 }
78
79 // gnarlAccumulate scans bits in block and accumulates basis table rows.
80 func gnarlAccumulate(acc *[gnarlBasisPad]uint32, basis *[GnarlM][GnarlN][gnarlBasisPad]uint16, block *[gnarlInputBytes]byte) {
81 for i := int32(0); i < GnarlM; i++ {
82 bitBase := i * GnarlN
83 for k := int32(0); k < GnarlN; k++ {
84 bitIdx := bitBase + k
85 byteIdx := bitIdx / 8
86 bitOff := uint(bitIdx % 8)
87 if byteIdx < gnarlInputBytes && block[byteIdx]&(1<<bitOff) != 0 {
88 row := &basis[i][k]
89 for j := int32(0); j < gnarlBasisPad; j++ {
90 acc[j] += uint32(row[j])
91 }
92 }
93 }
94 }
95 }
96
97 func packCoeffs243(coeffs [GnarlN]uint16) (out GnarlHash) {
98 bitPos := int32(0)
99 for i := int32(0); i < GnarlN; i++ {
100 v := coeffs[i] % GnarlP
101 for b := int32(0); b < 9; b++ {
102 if v&(1<<uint(b)) != 0 {
103 byteIdx := bitPos / 8
104 bitIdx := uint(bitPos % 8)
105 out[byteIdx] |= 1 << bitIdx
106 }
107 bitPos++
108 }
109 }
110 return out
111 }
112
113 func unpackCoeffs243(h GnarlHash) (coeffs [GnarlN]uint16) {
114 bitPos := int32(0)
115 for i := int32(0); i < GnarlN; i++ {
116 var v uint16
117 for b := int32(0); b < 9; b++ {
118 byteIdx := bitPos / 8
119 bitIdx := uint(bitPos % 8)
120 if h[byteIdx]&(1<<bitIdx) != 0 {
121 v |= 1 << uint(b)
122 }
123 bitPos++
124 }
125 coeffs[i] = v
126 }
127 return coeffs
128 }
129
130 func packCoeffs216(coeffs [GnarlN]uint16) (out GnarlMid) {
131 for i := int32(0); i < GnarlN; i++ {
132 out[i] = byte(coeffs[i] % GnarlMidR)
133 }
134 return out
135 }
136
137 func packCoeffs54(coeffs [GnarlN]uint16) (out GnarlShard) {
138 bitPos := int32(0)
139 for i := int32(0); i < GnarlN; i++ {
140 v := coeffs[i] % GnarlShardR
141 for b := int32(0); b < 2; b++ {
142 if v&(1<<uint(b)) != 0 {
143 byteIdx := bitPos / 8
144 bitIdx := uint(bitPos % 8)
145 out[byteIdx] |= 1 << bitIdx
146 }
147 bitPos++
148 }
149 }
150 return out
151 }
152
153 // gnarlHashCore computes the trinary Hamadryad hash, returning raw Z_271 coefficients.
154 func gnarlHashCore(msg []byte) (chain [GnarlN]uint16) {
155 padded := []byte{:int32(len(msg))}
156 copy(padded, msg)
157 padded = append(padded, 0x80)
158 for (int32(len(padded))+8)%gnarlInputBytes != 0 {
159 padded = append(padded, 0)
160 }
161 msgLenBits := uint64(len(msg)) * 8
162 padded = append(padded,
163 byte(msgLenBits),
164 byte(msgLenBits>>8),
165 byte(msgLenBits>>16),
166 byte(msgLenBits>>24),
167 byte(msgLenBits>>32),
168 byte(msgLenBits>>40),
169 byte(msgLenBits>>48),
170 byte(msgLenBits>>56),
171 )
172
173 off := int32(0)
174 for off < int32(len(padded)) {
175 var block [gnarlInputBytes]byte
176 copy(block[:], padded[off:off+gnarlInputBytes])
177 result := gnarlCompress(&block)
178 for j := int32(0); j < GnarlN; j++ {
179 chain[j] = mod271(uint32(chain[j]) + uint32(result[j]))
180 }
181 off += gnarlInputBytes
182 }
183 return chain
184 }
185
186 // GHash computes the 243-bit GnarlHash of an arbitrary-length message.
187 func GHash(msg []byte) (h GnarlHash) {
188 coeffs := gnarlHashCore(msg)
189 return packCoeffs243(coeffs)
190 }
191
192 // GMid computes the 216-bit GnarlMid of an arbitrary-length message.
193 func GMid(msg []byte) (m GnarlMid) {
194 coeffs := gnarlHashCore(msg)
195 return packCoeffs216(coeffs)
196 }
197
198 // GShard computes the 54-bit GnarlShard of an arbitrary-length message.
199 func GShard(msg []byte) (s GnarlShard) {
200 coeffs := gnarlHashCore(msg)
201 return packCoeffs54(coeffs)
202 }
203
204 // Mid extracts the GnarlMid tier from a full GnarlHash.
205 func (h *GnarlHash) Mid() (m GnarlMid) {
206 coeffs := unpackCoeffs243(*h)
207 return packCoeffs216(coeffs)
208 }
209
210 // Shard extracts the GnarlShard tier from a full GnarlHash.
211 func (h *GnarlHash) Shard() (s GnarlShard) {
212 coeffs := unpackCoeffs243(*h)
213 return packCoeffs54(coeffs)
214 }
215
216 func (h *GnarlHash) IsZero() (result bool) {
217 for i := int32(0); i < GnarlHashBytes; i++ {
218 if h[i] != 0 {
219 return false
220 }
221 }
222 return true
223 }
224
225 func (m *GnarlMid) IsZero() (result bool) {
226 for i := int32(0); i < GnarlMidBytes; i++ {
227 if m[i] != 0 {
228 return false
229 }
230 }
231 return true
232 }
233
234 func (s *GnarlShard) IsZero() (result bool) {
235 for i := int32(0); i < GnarlShardBytes; i++ {
236 if s[i] != 0 {
237 return false
238 }
239 }
240 return true
241 }
242
243 // Sum returns coefficient-wise sum (mod 271) of two GnarlHash values.
244 func (h *GnarlHash) Sum(other *GnarlHash) (result GnarlHash) {
245 a := unpackCoeffs243(*h)
246 b := unpackCoeffs243(*other)
247 var res [GnarlN]uint16
248 for i := int32(0); i < GnarlN; i++ {
249 res[i] = mod271(uint32(a[i]) + uint32(b[i]))
250 }
251 return packCoeffs243(res)
252 }
253
254 // RandomGnarlHash generates a cryptographically random GnarlHash value.
255 func RandomGnarlHash() (h GnarlHash) {
256 _, err := rand.Read(h[:])
257 if err != nil {
258 panic("crypto/rand failed")
259 }
260 h[GnarlHashBytes-1] &= 0x07
261 return h
262 }
263