1// Copyright 2009 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// Originally from: https://github.com/go/blob/master/src/crypto/sha1/sha1block.go
6// It has been modified to support collision detection.
7
8package sha1cd
9
10import (
11 "fmt"
12 "math/bits"
13
14 shared "github.com/pjbgf/sha1cd/internal"
15 "github.com/pjbgf/sha1cd/ubc"
16)
17
18var forceGeneric bool
19
20// blockGeneric is a portable, pure Go version of the SHA-1 block step.
21// It's used by sha1block_generic.go and tests.
22func blockGeneric(dig *digest, p []byte) {
23 var w [16]uint32
24
25 // cs stores the pre-step compression state for only the steps required for the
26 // collision detection, which are 0, 58 and 65.
27 // Refer to ubc/const.go for more details.
28 cs := [shared.PreStepState][shared.WordBuffers]uint32{}
29
30 h0, h1, h2, h3, h4 := dig.h[0], dig.h[1], dig.h[2], dig.h[3], dig.h[4]
31 for len(p) >= shared.Chunk {
32 m1 := [shared.Rounds]uint32{}
33 hi := 1
34
35 // Collision attacks are thwarted by hashing a detected near-collision block 3 times.
36 // Think of it as extending SHA-1 from 80-steps to 240-steps for such blocks:
37 // The best collision attacks against SHA-1 have complexity about 2^60,
38 // thus for 240-steps an immediate lower-bound for the best cryptanalytic attacks would be 2^180.
39 // An attacker would be better off using a generic birthday search of complexity 2^80.
40 rehash:
41 a, b, c, d, e := h0, h1, h2, h3, h4
42
43 // Each of the four 20-iteration rounds
44 // differs only in the computation of f and
45 // the choice of K (K0, K1, etc).
46 i := 0
47
48 // Store pre-step compression state for the collision detection.
49 cs[0] = [shared.WordBuffers]uint32{a, b, c, d, e}
50
51 for ; i < 16; i++ {
52 // load step
53 j := i * 4
54 w[i] = uint32(p[j])<<24 | uint32(p[j+1])<<16 | uint32(p[j+2])<<8 | uint32(p[j+3])
55
56 f := b&c | (^b)&d
57 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K0
58 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
59
60 // Store compression state for the collision detection.
61 m1[i] = w[i&0xf]
62 }
63 for ; i < 20; i++ {
64 tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
65 w[i&0xf] = tmp<<1 | tmp>>(32-1)
66
67 f := b&c | (^b)&d
68 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K0
69 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
70
71 // Store compression state for the collision detection.
72 m1[i] = w[i&0xf]
73 }
74 for ; i < 40; i++ {
75 tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
76 w[i&0xf] = tmp<<1 | tmp>>(32-1)
77
78 f := b ^ c ^ d
79 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K1
80 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
81
82 // Store compression state for the collision detection.
83 m1[i] = w[i&0xf]
84 }
85 for ; i < 60; i++ {
86 if i == 58 {
87 // Store pre-step compression state for the collision detection.
88 cs[1] = [shared.WordBuffers]uint32{a, b, c, d, e}
89 }
90
91 tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
92 w[i&0xf] = tmp<<1 | tmp>>(32-1)
93
94 f := ((b | c) & d) | (b & c)
95 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K2
96 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
97
98 // Store compression state for the collision detection.
99 m1[i] = w[i&0xf]
100 }
101 for ; i < 80; i++ {
102 if i == 65 {
103 // Store pre-step compression state for the collision detection.
104 cs[2] = [shared.WordBuffers]uint32{a, b, c, d, e}
105 }
106
107 tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
108 w[i&0xf] = tmp<<1 | tmp>>(32-1)
109
110 f := b ^ c ^ d
111 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K3
112 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
113
114 // Store compression state for the collision detection.
115 m1[i] = w[i&0xf]
116 }
117
118 h0 += a
119 h1 += b
120 h2 += c
121 h3 += d
122 h4 += e
123
124 if hi == 2 {
125 hi++
126 goto rehash
127 }
128
129 if hi == 1 {
130 h := [shared.WordBuffers]uint32{h0, h1, h2, h3, h4}
131 col := checkCollision(&m1, &cs, &h)
132 if col {
133 dig.col = true
134 hi++
135 goto rehash
136 }
137 }
138
139 p = p[shared.Chunk:]
140 }
141
142 dig.h[0], dig.h[1], dig.h[2], dig.h[3], dig.h[4] = h0, h1, h2, h3, h4
143}
144
145//go:noinline
146func checkCollision(
147 m1 *[shared.Rounds]uint32,
148 cs *[shared.PreStepState][shared.WordBuffers]uint32,
149 h *[shared.WordBuffers]uint32,
150) bool {
151 if mask := ubc.CalculateDvMask(m1); mask != 0 {
152 dvs := ubc.SHA1_dvs()
153
154 for i := 0; dvs[i].DvType != 0; i++ {
155 if (mask & ((uint32)(1) << uint32(dvs[i].MaskB))) != 0 {
156 var csState *[shared.WordBuffers]uint32
157 switch dvs[i].TestT {
158 case 58:
159 csState = &cs[1]
160 case 65:
161 csState = &cs[2]
162 case 0:
163 csState = &cs[0]
164 default:
165 panic(fmt.Sprintf("dvs data is trying to use a testT that isn't available: %d", dvs[i].TestT))
166 }
167
168 col := hasCollided(
169 dvs[i].TestT, // testT is the step number
170 // m2 is a secondary message created XORing with
171 // ubc's DM prior to the SHA recompression step.
172 m1, &dvs[i].Dm,
173 csState,
174 h)
175
176 if col {
177 return true
178 }
179 }
180 }
181 }
182 return false
183}
184
185//go:nosplit
186func hasCollided(step uint32, m1, dm *[shared.Rounds]uint32,
187 state *[shared.WordBuffers]uint32, h *[shared.WordBuffers]uint32) bool {
188 // Intermediary Hash Value.
189 ihv := [shared.WordBuffers]uint32{}
190
191 a, b, c, d, e := state[0], state[1], state[2], state[3], state[4]
192
193 // Walk backwards from current step to undo previous compression.
194 // The existing collision detection does not have dvs higher than 65,
195 // start value of i accordingly.
196 for i := uint32(64); i >= 60; i-- {
197 a, b, c, d, e = b, c, d, e, a
198 if step > i {
199 b = bits.RotateLeft32(b, -30)
200 f := b ^ c ^ d
201 e -= bits.RotateLeft32(a, 5) + f + shared.K3 + (m1[i] ^ dm[i]) // m2 = m1 ^ dm.
202 }
203 }
204 for i := uint32(59); i >= 40; i-- {
205 a, b, c, d, e = b, c, d, e, a
206 if step > i {
207 b = bits.RotateLeft32(b, -30)
208 f := ((b | c) & d) | (b & c)
209 e -= bits.RotateLeft32(a, 5) + f + shared.K2 + (m1[i] ^ dm[i])
210 }
211 }
212 for i := uint32(39); i >= 20; i-- {
213 a, b, c, d, e = b, c, d, e, a
214 if step > i {
215 b = bits.RotateLeft32(b, -30)
216 f := b ^ c ^ d
217 e -= bits.RotateLeft32(a, 5) + f + shared.K1 + (m1[i] ^ dm[i])
218 }
219 }
220 for i := uint32(20); i > 0; i-- {
221 j := i - 1
222 a, b, c, d, e = b, c, d, e, a
223 if step > j {
224 b = bits.RotateLeft32(b, -30) // undo the rotate left
225 f := b&c | (^b)&d
226 // subtract from e
227 e -= bits.RotateLeft32(a, 5) + f + shared.K0 + (m1[j] ^ dm[j])
228 }
229 }
230
231 ihv[0] = a
232 ihv[1] = b
233 ihv[2] = c
234 ihv[3] = d
235 ihv[4] = e
236 a = state[0]
237 b = state[1]
238 c = state[2]
239 d = state[3]
240 e = state[4]
241
242 // Recompress blocks based on the current step.
243 // The existing collision detection does not have dvs below 58, so they have been removed
244 // from the source code. If new dvs are added which target rounds below 40, that logic
245 // will need to be readded here.
246 for i := uint32(40); i < 60; i++ {
247 if step <= i {
248 f := ((b | c) & d) | (b & c)
249 t := bits.RotateLeft32(a, 5) + f + e + shared.K2 + (m1[i] ^ dm[i])
250 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
251 }
252 }
253 for i := uint32(60); i < 80; i++ {
254 if step <= i {
255 f := b ^ c ^ d
256 t := bits.RotateLeft32(a, 5) + f + e + shared.K3 + (m1[i] ^ dm[i])
257 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
258 }
259 }
260
261 ihv[0] += a
262 ihv[1] += b
263 ihv[2] += c
264 ihv[3] += d
265 ihv[4] += e
266
267 if ((ihv[0] ^ h[0]) | (ihv[1] ^ h[1]) |
268 (ihv[2] ^ h[2]) | (ihv[3] ^ h[3]) | (ihv[4] ^ h[4])) == 0 {
269 return true
270 }
271
272 return false
273}
274
275// rectifyCompressionState fixes the compression state when using the
276// SIMD implementations.
277//
278// Due to the way that hardware acceleration works, the rounds
279// are executed 4 at a time. Therefore, the state for cs58 and cs65
280// are not available directly through the assembly logic. The states
281// returned are for cs56 and cs64. This function updates indexes 1 and 2
282// of cs to contain the respective CS values for rounds 58 and 65.
283//
284//go:nosplit
285func rectifyCompressionState(
286 m1 *[shared.Rounds]uint32,
287 cs *[shared.PreStepState][shared.WordBuffers]uint32,
288) {
289 if cs == nil {
290 return
291 }
292
293 func3 := func(state [shared.WordBuffers]uint32, i int) [shared.WordBuffers]uint32 {
294 a, b, c, d, e := state[0], state[1], state[2], state[3], state[4]
295
296 f := ((b | c) & d) | (b & c)
297 t := bits.RotateLeft32(a, 5) + f + e + m1[i] + shared.K2
298 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
299 return [shared.WordBuffers]uint32{a, b, c, d, e}
300 }
301 func4 := func(state [shared.WordBuffers]uint32, i int) [shared.WordBuffers]uint32 {
302 a, b, c, d, e := state[0], state[1], state[2], state[3], state[4]
303 f := b ^ c ^ d
304 t := bits.RotateLeft32(a, 5) + f + e + m1[i] + shared.K3
305 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
306 return [shared.WordBuffers]uint32{a, b, c, d, e}
307 }
308
309 cs57 := func3(cs[1], 56)
310 cs[1] = func3(cs57, 57)
311 cs[2] = func4(cs[2], 64)
312}