main
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
18// blockGeneric is a portable, pure Go version of the SHA-1 block step.
19// It's used by sha1block_generic.go and tests.
20func blockGeneric(dig *digest, p []byte) {
21 var w [16]uint32
22
23 // cs stores the pre-step compression state for only the steps required for the
24 // collision detection, which are 0, 58 and 65.
25 // Refer to ubc/const.go for more details.
26 cs := [shared.PreStepState][shared.WordBuffers]uint32{}
27
28 h0, h1, h2, h3, h4 := dig.h[0], dig.h[1], dig.h[2], dig.h[3], dig.h[4]
29 for len(p) >= shared.Chunk {
30 m1 := [shared.Rounds]uint32{}
31 hi := 1
32
33 // Collision attacks are thwarted by hashing a detected near-collision block 3 times.
34 // Think of it as extending SHA-1 from 80-steps to 240-steps for such blocks:
35 // The best collision attacks against SHA-1 have complexity about 2^60,
36 // thus for 240-steps an immediate lower-bound for the best cryptanalytic attacks would be 2^180.
37 // An attacker would be better off using a generic birthday search of complexity 2^80.
38 rehash:
39 a, b, c, d, e := h0, h1, h2, h3, h4
40
41 // Each of the four 20-iteration rounds
42 // differs only in the computation of f and
43 // the choice of K (K0, K1, etc).
44 i := 0
45
46 // Store pre-step compression state for the collision detection.
47 cs[0] = [shared.WordBuffers]uint32{a, b, c, d, e}
48
49 for ; i < 16; i++ {
50 // load step
51 j := i * 4
52 w[i] = uint32(p[j])<<24 | uint32(p[j+1])<<16 | uint32(p[j+2])<<8 | uint32(p[j+3])
53
54 f := b&c | (^b)&d
55 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K0
56 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
57
58 // Store compression state for the collision detection.
59 m1[i] = w[i&0xf]
60 }
61 for ; i < 20; i++ {
62 tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
63 w[i&0xf] = tmp<<1 | tmp>>(32-1)
64
65 f := b&c | (^b)&d
66 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K0
67 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
68
69 // Store compression state for the collision detection.
70 m1[i] = w[i&0xf]
71 }
72 for ; i < 40; i++ {
73 tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
74 w[i&0xf] = tmp<<1 | tmp>>(32-1)
75
76 f := b ^ c ^ d
77 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K1
78 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
79
80 // Store compression state for the collision detection.
81 m1[i] = w[i&0xf]
82 }
83 for ; i < 60; i++ {
84 if i == 58 {
85 // Store pre-step compression state for the collision detection.
86 cs[1] = [shared.WordBuffers]uint32{a, b, c, d, e}
87 }
88
89 tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
90 w[i&0xf] = tmp<<1 | tmp>>(32-1)
91
92 f := ((b | c) & d) | (b & c)
93 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K2
94 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
95
96 // Store compression state for the collision detection.
97 m1[i] = w[i&0xf]
98 }
99 for ; i < 80; i++ {
100 if i == 65 {
101 // Store pre-step compression state for the collision detection.
102 cs[2] = [shared.WordBuffers]uint32{a, b, c, d, e}
103 }
104
105 tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
106 w[i&0xf] = tmp<<1 | tmp>>(32-1)
107
108 f := b ^ c ^ d
109 t := bits.RotateLeft32(a, 5) + f + e + w[i&0xf] + shared.K3
110 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
111
112 // Store compression state for the collision detection.
113 m1[i] = w[i&0xf]
114 }
115
116 h0 += a
117 h1 += b
118 h2 += c
119 h3 += d
120 h4 += e
121
122 if hi == 2 {
123 hi++
124 goto rehash
125 }
126
127 if hi == 1 {
128 col := checkCollision(m1, cs, [shared.WordBuffers]uint32{h0, h1, h2, h3, h4})
129 if col {
130 dig.col = true
131 hi++
132 goto rehash
133 }
134 }
135
136 p = p[shared.Chunk:]
137 }
138
139 dig.h[0], dig.h[1], dig.h[2], dig.h[3], dig.h[4] = h0, h1, h2, h3, h4
140}
141
142func checkCollision(
143 m1 [shared.Rounds]uint32,
144 cs [shared.PreStepState][shared.WordBuffers]uint32,
145 state [shared.WordBuffers]uint32) bool {
146
147 if mask := ubc.CalculateDvMask(m1); mask != 0 {
148 dvs := ubc.SHA1_dvs()
149
150 for i := 0; dvs[i].DvType != 0; i++ {
151 if (mask & ((uint32)(1) << uint32(dvs[i].MaskB))) != 0 {
152 var csState [shared.WordBuffers]uint32
153 switch dvs[i].TestT {
154 case 58:
155 csState = cs[1]
156 case 65:
157 csState = cs[2]
158 case 0:
159 csState = cs[0]
160 default:
161 panic(fmt.Sprintf("dvs data is trying to use a testT that isn't available: %d", dvs[i].TestT))
162 }
163
164 col := hasCollided(
165 dvs[i].TestT, // testT is the step number
166 // m2 is a secondary message created XORing with
167 // ubc's DM prior to the SHA recompression step.
168 m1, dvs[i].Dm,
169 csState,
170 state)
171
172 if col {
173 return true
174 }
175 }
176 }
177 }
178 return false
179}
180
181func hasCollided(step uint32, m1, dm [shared.Rounds]uint32,
182 state [shared.WordBuffers]uint32, h [shared.WordBuffers]uint32) bool {
183 // Intermediary Hash Value.
184 ihv := [shared.WordBuffers]uint32{}
185
186 a, b, c, d, e := state[0], state[1], state[2], state[3], state[4]
187
188 // Walk backwards from current step to undo previous compression.
189 // The existing collision detection does not have dvs higher than 65,
190 // start value of i accordingly.
191 for i := uint32(64); i >= 60; i-- {
192 a, b, c, d, e = b, c, d, e, a
193 if step > i {
194 b = bits.RotateLeft32(b, -30)
195 f := b ^ c ^ d
196 e -= bits.RotateLeft32(a, 5) + f + shared.K3 + (m1[i] ^ dm[i]) // m2 = m1 ^ dm.
197 }
198 }
199 for i := uint32(59); i >= 40; i-- {
200 a, b, c, d, e = b, c, d, e, a
201 if step > i {
202 b = bits.RotateLeft32(b, -30)
203 f := ((b | c) & d) | (b & c)
204 e -= bits.RotateLeft32(a, 5) + f + shared.K2 + (m1[i] ^ dm[i])
205 }
206 }
207 for i := uint32(39); i >= 20; i-- {
208 a, b, c, d, e = b, c, d, e, a
209 if step > i {
210 b = bits.RotateLeft32(b, -30)
211 f := b ^ c ^ d
212 e -= bits.RotateLeft32(a, 5) + f + shared.K1 + (m1[i] ^ dm[i])
213 }
214 }
215 for i := uint32(20); i > 0; i-- {
216 j := i - 1
217 a, b, c, d, e = b, c, d, e, a
218 if step > j {
219 b = bits.RotateLeft32(b, -30) // undo the rotate left
220 f := b&c | (^b)&d
221 // subtract from e
222 e -= bits.RotateLeft32(a, 5) + f + shared.K0 + (m1[j] ^ dm[j])
223 }
224 }
225
226 ihv[0] = a
227 ihv[1] = b
228 ihv[2] = c
229 ihv[3] = d
230 ihv[4] = e
231 a = state[0]
232 b = state[1]
233 c = state[2]
234 d = state[3]
235 e = state[4]
236
237 // Recompress blocks based on the current step.
238 // The existing collision detection does not have dvs below 58, so they have been removed
239 // from the source code. If new dvs are added which target rounds below 40, that logic
240 // will need to be readded here.
241 for i := uint32(40); i < 60; i++ {
242 if step <= i {
243 f := ((b | c) & d) | (b & c)
244 t := bits.RotateLeft32(a, 5) + f + e + shared.K2 + (m1[i] ^ dm[i])
245 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
246 }
247 }
248 for i := uint32(60); i < 80; i++ {
249 if step <= i {
250 f := b ^ c ^ d
251 t := bits.RotateLeft32(a, 5) + f + e + shared.K3 + (m1[i] ^ dm[i])
252 a, b, c, d, e = t, a, bits.RotateLeft32(b, 30), c, d
253 }
254 }
255
256 ihv[0] += a
257 ihv[1] += b
258 ihv[2] += c
259 ihv[3] += d
260 ihv[4] += e
261
262 if ((ihv[0] ^ h[0]) | (ihv[1] ^ h[1]) |
263 (ihv[2] ^ h[2]) | (ihv[3] ^ h[3]) | (ihv[4] ^ h[4])) == 0 {
264 return true
265 }
266
267 return false
268}