1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 package org.eclipse.jgit.util.sha1;
45
46 import static java.lang.Integer.lowestOneBit;
47 import static java.lang.Integer.numberOfTrailingZeros;
48 import static java.lang.Integer.rotateLeft;
49 import static java.lang.Integer.rotateRight;
50
51 import java.util.Arrays;
52
53 import org.eclipse.jgit.lib.MutableObjectId;
54 import org.eclipse.jgit.lib.ObjectId;
55 import org.eclipse.jgit.util.NB;
56 import org.eclipse.jgit.util.SystemReader;
57 import org.slf4j.Logger;
58 import org.slf4j.LoggerFactory;
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78 public class SHA1 {
79 private static Logger LOG = LoggerFactory.getLogger(SHA1.class);
80 private static final boolean DETECT_COLLISIONS;
81
82 static {
83 SystemReader sr = SystemReader.getInstance();
84 String v = sr.getProperty("org.eclipse.jgit.util.sha1.detectCollision");
85 DETECT_COLLISIONS = v != null ? Boolean.parseBoolean(v) : true;
86 }
87
88
89
90
91
92
93 public static SHA1 newInstance() {
94 return new SHA1();
95 }
96
97 private final State h = new State();
98 private final int[] w = new int[80];
99
100
101 private final byte[] buffer = new byte[64];
102
103
104 private long length;
105
106 private boolean detectCollision = DETECT_COLLISIONS;
107 private boolean foundCollision;
108
109 private final int[] w2 = new int[80];
110 private final State state58 = new State();
111 private final State state65 = new State();
112 private final State hIn = new State();
113 private final State hTmp = new State();
114
115 private SHA1() {
116 h.init();
117 }
118
119
120
121
122
123
124
125
126
127
128
129
130
131 public SHA1 setDetectCollision(boolean detect) {
132 detectCollision = detect;
133 return this;
134 }
135
136
137
138
139
140
141 public void update(byte b) {
142 int bufferLen = (int) (length & 63);
143 length++;
144 buffer[bufferLen] = b;
145 if (bufferLen == 63) {
146 compress(buffer, 0);
147 }
148 }
149
150
151
152
153
154
155
156 public void update(byte[] in) {
157 update(in, 0, in.length);
158 }
159
160
161
162
163
164
165
166
167
168
169
170 public void update(byte[] in, int p, int len) {
171
172
173 int bufferLen = (int) (length & 63);
174 length += len;
175
176 if (bufferLen > 0) {
177 int n = Math.min(64 - bufferLen, len);
178 System.arraycopy(in, p, buffer, bufferLen, n);
179 p += n;
180 len -= n;
181 if (bufferLen + n < 64) {
182 return;
183 }
184 compress(buffer, 0);
185 }
186 while (len >= 64) {
187 compress(in, p);
188 p += 64;
189 len -= 64;
190 }
191 if (len > 0) {
192 System.arraycopy(in, p, buffer, 0, len);
193 }
194 }
195
196 private void compress(byte[] block, int p) {
197 initBlock(block, p);
198 int ubcDvMask = detectCollision ? UbcCheck.check(w) : 0;
199 compress();
200
201 while (ubcDvMask != 0) {
202 int b = numberOfTrailingZeros(lowestOneBit(ubcDvMask));
203 UbcCheck.DvInfo dv = UbcCheck.DV[b];
204 for (int i = 0; i < 80; i++) {
205 w2[i] = w[i] ^ dv.dm[i];
206 }
207 recompress(dv.testt);
208 if (eq(hTmp, h)) {
209 foundCollision = true;
210 break;
211 }
212 ubcDvMask &= ~(1 << b);
213 }
214 }
215
216 private void initBlock(byte[] block, int p) {
217 for (int t = 0; t < 16; t++) {
218 w[t] = NB.decodeInt32(block, p + (t << 2));
219 }
220
221
222 for (int t = 16; t < 80; t++) {
223 int x = w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16];
224 w[t] = rotateLeft(x, 1);
225 }
226 }
227
228 private void compress() {
229
230
231 int a = h.a, b = h.b, c = h.c, d = h.d, e = h.e;
232
233
234 e += s1(a, b, c, d,w[ 0]); b = rotateLeft( b, 30);
235 d += s1(e, a, b, c,w[ 1]); a = rotateLeft( a, 30);
236 c += s1(d, e, a, b,w[ 2]); e = rotateLeft( e, 30);
237 b += s1(c, d, e, a,w[ 3]); d = rotateLeft( d, 30);
238 a += s1(b, c, d, e,w[ 4]); c = rotateLeft( c, 30);
239 e += s1(a, b, c, d,w[ 5]); b = rotateLeft( b, 30);
240 d += s1(e, a, b, c,w[ 6]); a = rotateLeft( a, 30);
241 c += s1(d, e, a, b,w[ 7]); e = rotateLeft( e, 30);
242 b += s1(c, d, e, a,w[ 8]); d = rotateLeft( d, 30);
243 a += s1(b, c, d, e,w[ 9]); c = rotateLeft( c, 30);
244 e += s1(a, b, c, d,w[ 10]); b = rotateLeft( b, 30);
245 d += s1(e, a, b, c,w[ 11]); a = rotateLeft( a, 30);
246 c += s1(d, e, a, b,w[ 12]); e = rotateLeft( e, 30);
247 b += s1(c, d, e, a,w[ 13]); d = rotateLeft( d, 30);
248 a += s1(b, c, d, e,w[ 14]); c = rotateLeft( c, 30);
249 e += s1(a, b, c, d,w[ 15]); b = rotateLeft( b, 30);
250 d += s1(e, a, b, c,w[ 16]); a = rotateLeft( a, 30);
251 c += s1(d, e, a, b,w[ 17]); e = rotateLeft( e, 30);
252 b += s1(c, d, e, a,w[ 18]); d = rotateLeft( d, 30);
253 a += s1(b, c, d, e,w[ 19]); c = rotateLeft( c, 30);
254
255 e += s2(a, b, c, d,w[ 20]); b = rotateLeft( b, 30);
256 d += s2(e, a, b, c,w[ 21]); a = rotateLeft( a, 30);
257 c += s2(d, e, a, b,w[ 22]); e = rotateLeft( e, 30);
258 b += s2(c, d, e, a,w[ 23]); d = rotateLeft( d, 30);
259 a += s2(b, c, d, e,w[ 24]); c = rotateLeft( c, 30);
260 e += s2(a, b, c, d,w[ 25]); b = rotateLeft( b, 30);
261 d += s2(e, a, b, c,w[ 26]); a = rotateLeft( a, 30);
262 c += s2(d, e, a, b,w[ 27]); e = rotateLeft( e, 30);
263 b += s2(c, d, e, a,w[ 28]); d = rotateLeft( d, 30);
264 a += s2(b, c, d, e,w[ 29]); c = rotateLeft( c, 30);
265 e += s2(a, b, c, d,w[ 30]); b = rotateLeft( b, 30);
266 d += s2(e, a, b, c,w[ 31]); a = rotateLeft( a, 30);
267 c += s2(d, e, a, b,w[ 32]); e = rotateLeft( e, 30);
268 b += s2(c, d, e, a,w[ 33]); d = rotateLeft( d, 30);
269 a += s2(b, c, d, e,w[ 34]); c = rotateLeft( c, 30);
270 e += s2(a, b, c, d,w[ 35]); b = rotateLeft( b, 30);
271 d += s2(e, a, b, c,w[ 36]); a = rotateLeft( a, 30);
272 c += s2(d, e, a, b,w[ 37]); e = rotateLeft( e, 30);
273 b += s2(c, d, e, a,w[ 38]); d = rotateLeft( d, 30);
274 a += s2(b, c, d, e,w[ 39]); c = rotateLeft( c, 30);
275
276 e += s3(a, b, c, d,w[ 40]); b = rotateLeft( b, 30);
277 d += s3(e, a, b, c,w[ 41]); a = rotateLeft( a, 30);
278 c += s3(d, e, a, b,w[ 42]); e = rotateLeft( e, 30);
279 b += s3(c, d, e, a,w[ 43]); d = rotateLeft( d, 30);
280 a += s3(b, c, d, e,w[ 44]); c = rotateLeft( c, 30);
281 e += s3(a, b, c, d,w[ 45]); b = rotateLeft( b, 30);
282 d += s3(e, a, b, c,w[ 46]); a = rotateLeft( a, 30);
283 c += s3(d, e, a, b,w[ 47]); e = rotateLeft( e, 30);
284 b += s3(c, d, e, a,w[ 48]); d = rotateLeft( d, 30);
285 a += s3(b, c, d, e,w[ 49]); c = rotateLeft( c, 30);
286 e += s3(a, b, c, d,w[ 50]); b = rotateLeft( b, 30);
287 d += s3(e, a, b, c,w[ 51]); a = rotateLeft( a, 30);
288 c += s3(d, e, a, b,w[ 52]); e = rotateLeft( e, 30);
289 b += s3(c, d, e, a,w[ 53]); d = rotateLeft( d, 30);
290 a += s3(b, c, d, e,w[ 54]); c = rotateLeft( c, 30);
291 e += s3(a, b, c, d,w[ 55]); b = rotateLeft( b, 30);
292 d += s3(e, a, b, c,w[ 56]); a = rotateLeft( a, 30);
293 c += s3(d, e, a, b,w[ 57]); e = rotateLeft( e, 30);
294 state58.save(a, b, c, d, e);
295 b += s3(c, d, e, a,w[ 58]); d = rotateLeft( d, 30);
296 a += s3(b, c, d, e,w[ 59]); c = rotateLeft( c, 30);
297
298 e += s4(a, b, c, d,w[ 60]); b = rotateLeft( b, 30);
299 d += s4(e, a, b, c,w[ 61]); a = rotateLeft( a, 30);
300 c += s4(d, e, a, b,w[ 62]); e = rotateLeft( e, 30);
301 b += s4(c, d, e, a,w[ 63]); d = rotateLeft( d, 30);
302 a += s4(b, c, d, e,w[ 64]); c = rotateLeft( c, 30);
303 state65.save(a, b, c, d, e);
304 e += s4(a, b, c, d,w[ 65]); b = rotateLeft( b, 30);
305 d += s4(e, a, b, c,w[ 66]); a = rotateLeft( a, 30);
306 c += s4(d, e, a, b,w[ 67]); e = rotateLeft( e, 30);
307 b += s4(c, d, e, a,w[ 68]); d = rotateLeft( d, 30);
308 a += s4(b, c, d, e,w[ 69]); c = rotateLeft( c, 30);
309 e += s4(a, b, c, d,w[ 70]); b = rotateLeft( b, 30);
310 d += s4(e, a, b, c,w[ 71]); a = rotateLeft( a, 30);
311 c += s4(d, e, a, b,w[ 72]); e = rotateLeft( e, 30);
312 b += s4(c, d, e, a,w[ 73]); d = rotateLeft( d, 30);
313 a += s4(b, c, d, e,w[ 74]); c = rotateLeft( c, 30);
314 e += s4(a, b, c, d,w[ 75]); b = rotateLeft( b, 30);
315 d += s4(e, a, b, c,w[ 76]); a = rotateLeft( a, 30);
316 c += s4(d, e, a, b,w[ 77]); e = rotateLeft( e, 30);
317 b += s4(c, d, e, a,w[ 78]); d = rotateLeft( d, 30);
318 a += s4(b, c, d, e,w[ 79]); c = rotateLeft( c, 30);
319
320
321 h.save(h.a + a, h.b + b, h.c + c, h.d + d, h.e + e);
322 }
323
324 private void recompress(int t) {
325 State s;
326 if (t == 58) {
327 s = state58;
328 } else if (t == 65) {
329 s = state65;
330 } else {
331 throw new IllegalStateException();
332 }
333 int a = s.a, b = s.b, c = s.c, d = s.d, e = s.e;
334
335
336 if (t == 65) {
337 { c = rotateRight( c, 30); a -= s4(b, c, d, e,w2[ 64]);}
338 { d = rotateRight( d, 30); b -= s4(c, d, e, a,w2[ 63]);}
339 { e = rotateRight( e, 30); c -= s4(d, e, a, b,w2[ 62]);}
340 { a = rotateRight( a, 30); d -= s4(e, a, b, c,w2[ 61]);}
341 { b = rotateRight( b, 30); e -= s4(a, b, c, d,w2[ 60]);}
342
343 { c = rotateRight( c, 30); a -= s3(b, c, d, e,w2[ 59]);}
344 { d = rotateRight( d, 30); b -= s3(c, d, e, a,w2[ 58]);}
345 }
346 { e = rotateRight( e, 30); c -= s3(d, e, a, b,w2[ 57]);}
347 { a = rotateRight( a, 30); d -= s3(e, a, b, c,w2[ 56]);}
348 { b = rotateRight( b, 30); e -= s3(a, b, c, d,w2[ 55]);}
349 { c = rotateRight( c, 30); a -= s3(b, c, d, e,w2[ 54]);}
350 { d = rotateRight( d, 30); b -= s3(c, d, e, a,w2[ 53]);}
351 { e = rotateRight( e, 30); c -= s3(d, e, a, b,w2[ 52]);}
352 { a = rotateRight( a, 30); d -= s3(e, a, b, c,w2[ 51]);}
353 { b = rotateRight( b, 30); e -= s3(a, b, c, d,w2[ 50]);}
354 { c = rotateRight( c, 30); a -= s3(b, c, d, e,w2[ 49]);}
355 { d = rotateRight( d, 30); b -= s3(c, d, e, a,w2[ 48]);}
356 { e = rotateRight( e, 30); c -= s3(d, e, a, b,w2[ 47]);}
357 { a = rotateRight( a, 30); d -= s3(e, a, b, c,w2[ 46]);}
358 { b = rotateRight( b, 30); e -= s3(a, b, c, d,w2[ 45]);}
359 { c = rotateRight( c, 30); a -= s3(b, c, d, e,w2[ 44]);}
360 { d = rotateRight( d, 30); b -= s3(c, d, e, a,w2[ 43]);}
361 { e = rotateRight( e, 30); c -= s3(d, e, a, b,w2[ 42]);}
362 { a = rotateRight( a, 30); d -= s3(e, a, b, c,w2[ 41]);}
363 { b = rotateRight( b, 30); e -= s3(a, b, c, d,w2[ 40]);}
364
365 { c = rotateRight( c, 30); a -= s2(b, c, d, e,w2[ 39]);}
366 { d = rotateRight( d, 30); b -= s2(c, d, e, a,w2[ 38]);}
367 { e = rotateRight( e, 30); c -= s2(d, e, a, b,w2[ 37]);}
368 { a = rotateRight( a, 30); d -= s2(e, a, b, c,w2[ 36]);}
369 { b = rotateRight( b, 30); e -= s2(a, b, c, d,w2[ 35]);}
370 { c = rotateRight( c, 30); a -= s2(b, c, d, e,w2[ 34]);}
371 { d = rotateRight( d, 30); b -= s2(c, d, e, a,w2[ 33]);}
372 { e = rotateRight( e, 30); c -= s2(d, e, a, b,w2[ 32]);}
373 { a = rotateRight( a, 30); d -= s2(e, a, b, c,w2[ 31]);}
374 { b = rotateRight( b, 30); e -= s2(a, b, c, d,w2[ 30]);}
375 { c = rotateRight( c, 30); a -= s2(b, c, d, e,w2[ 29]);}
376 { d = rotateRight( d, 30); b -= s2(c, d, e, a,w2[ 28]);}
377 { e = rotateRight( e, 30); c -= s2(d, e, a, b,w2[ 27]);}
378 { a = rotateRight( a, 30); d -= s2(e, a, b, c,w2[ 26]);}
379 { b = rotateRight( b, 30); e -= s2(a, b, c, d,w2[ 25]);}
380 { c = rotateRight( c, 30); a -= s2(b, c, d, e,w2[ 24]);}
381 { d = rotateRight( d, 30); b -= s2(c, d, e, a,w2[ 23]);}
382 { e = rotateRight( e, 30); c -= s2(d, e, a, b,w2[ 22]);}
383 { a = rotateRight( a, 30); d -= s2(e, a, b, c,w2[ 21]);}
384 { b = rotateRight( b, 30); e -= s2(a, b, c, d,w2[ 20]);}
385
386 { c = rotateRight( c, 30); a -= s1(b, c, d, e,w2[ 19]);}
387 { d = rotateRight( d, 30); b -= s1(c, d, e, a,w2[ 18]);}
388 { e = rotateRight( e, 30); c -= s1(d, e, a, b,w2[ 17]);}
389 { a = rotateRight( a, 30); d -= s1(e, a, b, c,w2[ 16]);}
390 { b = rotateRight( b, 30); e -= s1(a, b, c, d,w2[ 15]);}
391 { c = rotateRight( c, 30); a -= s1(b, c, d, e,w2[ 14]);}
392 { d = rotateRight( d, 30); b -= s1(c, d, e, a,w2[ 13]);}
393 { e = rotateRight( e, 30); c -= s1(d, e, a, b,w2[ 12]);}
394 { a = rotateRight( a, 30); d -= s1(e, a, b, c,w2[ 11]);}
395 { b = rotateRight( b, 30); e -= s1(a, b, c, d,w2[ 10]);}
396 { c = rotateRight( c, 30); a -= s1(b, c, d, e,w2[ 9]);}
397 { d = rotateRight( d, 30); b -= s1(c, d, e, a,w2[ 8]);}
398 { e = rotateRight( e, 30); c -= s1(d, e, a, b,w2[ 7]);}
399 { a = rotateRight( a, 30); d -= s1(e, a, b, c,w2[ 6]);}
400 { b = rotateRight( b, 30); e -= s1(a, b, c, d,w2[ 5]);}
401 { c = rotateRight( c, 30); a -= s1(b, c, d, e,w2[ 4]);}
402 { d = rotateRight( d, 30); b -= s1(c, d, e, a,w2[ 3]);}
403 { e = rotateRight( e, 30); c -= s1(d, e, a, b,w2[ 2]);}
404 { a = rotateRight( a, 30); d -= s1(e, a, b, c,w2[ 1]);}
405 { b = rotateRight( b, 30); e -= s1(a, b, c, d,w2[ 0]);}
406
407 hIn.save(a, b, c, d, e);
408 a = s.a; b = s.b; c = s.c; d = s.d; e = s.e;
409
410 if (t == 58) {
411 { b += s3(c, d, e, a,w2[ 58]); d = rotateLeft( d, 30);}
412 { a += s3(b, c, d, e,w2[ 59]); c = rotateLeft( c, 30);}
413
414 { e += s4(a, b, c, d,w2[ 60]); b = rotateLeft( b, 30);}
415 { d += s4(e, a, b, c,w2[ 61]); a = rotateLeft( a, 30);}
416 { c += s4(d, e, a, b,w2[ 62]); e = rotateLeft( e, 30);}
417 { b += s4(c, d, e, a,w2[ 63]); d = rotateLeft( d, 30);}
418 { a += s4(b, c, d, e,w2[ 64]); c = rotateLeft( c, 30);}
419 }
420 { e += s4(a, b, c, d,w2[ 65]); b = rotateLeft( b, 30);}
421 { d += s4(e, a, b, c,w2[ 66]); a = rotateLeft( a, 30);}
422 { c += s4(d, e, a, b,w2[ 67]); e = rotateLeft( e, 30);}
423 { b += s4(c, d, e, a,w2[ 68]); d = rotateLeft( d, 30);}
424 { a += s4(b, c, d, e,w2[ 69]); c = rotateLeft( c, 30);}
425 { e += s4(a, b, c, d,w2[ 70]); b = rotateLeft( b, 30);}
426 { d += s4(e, a, b, c,w2[ 71]); a = rotateLeft( a, 30);}
427 { c += s4(d, e, a, b,w2[ 72]); e = rotateLeft( e, 30);}
428 { b += s4(c, d, e, a,w2[ 73]); d = rotateLeft( d, 30);}
429 { a += s4(b, c, d, e,w2[ 74]); c = rotateLeft( c, 30);}
430 { e += s4(a, b, c, d,w2[ 75]); b = rotateLeft( b, 30);}
431 { d += s4(e, a, b, c,w2[ 76]); a = rotateLeft( a, 30);}
432 { c += s4(d, e, a, b,w2[ 77]); e = rotateLeft( e, 30);}
433 { b += s4(c, d, e, a,w2[ 78]); d = rotateLeft( d, 30);}
434 { a += s4(b, c, d, e,w2[ 79]); c = rotateLeft( c, 30);}
435
436
437 hTmp.save(hIn.a + a, hIn.b + b, hIn.c + c, hIn.d + d, hIn.e + e);
438 }
439
440 private static int s1(int a, int b, int c, int d, int w_t) {
441 return rotateLeft(a, 5)
442
443 + ((b & c) | ((~b) & d))
444 + 0x5A827999 + w_t;
445 }
446
447 private static int s2(int a, int b, int c, int d, int w_t) {
448 return rotateLeft(a, 5)
449
450 + (b ^ c ^ d)
451 + 0x6ED9EBA1 + w_t;
452 }
453
454 private static int s3(int a, int b, int c, int d, int w_t) {
455 return rotateLeft(a, 5)
456
457 + ((b & c) | (b & d) | (c & d))
458 + 0x8F1BBCDC + w_t;
459 }
460
461 private static int s4(int a, int b, int c, int d, int w_t) {
462 return rotateLeft(a, 5)
463
464 + (b ^ c ^ d)
465 + 0xCA62C1D6 + w_t;
466 }
467
468 private static boolean eq(State q, State r) {
469 return q.a == r.a
470 && q.b == r.b
471 && q.c == r.c
472 && q.d == r.d
473 && q.e == r.e;
474 }
475
476 private void finish() {
477 int bufferLen = (int) (length & 63);
478 if (bufferLen > 55) {
479
480 buffer[bufferLen++] = (byte) 0x80;
481 Arrays.fill(buffer, bufferLen, 64, (byte) 0);
482 compress(buffer, 0);
483 Arrays.fill(buffer, 0, 56, (byte) 0);
484 } else {
485
486 buffer[bufferLen++] = (byte) 0x80;
487 Arrays.fill(buffer, bufferLen, 56, (byte) 0);
488 }
489
490
491
492
493
494 NB.encodeInt32(buffer, 56, (int) (length >>> (32 - 3)));
495 NB.encodeInt32(buffer, 60, (int) (length << 3));
496 compress(buffer, 0);
497
498 if (foundCollision) {
499 ObjectId id = h.toObjectId();
500 LOG.warn("possible SHA-1 collision " + id.name());
501 throw new Sha1CollisionException(id);
502 }
503 }
504
505
506
507
508
509
510
511
512
513
514 public byte[] digest() throws Sha1CollisionException {
515 finish();
516
517 byte[] b = new byte[20];
518 NB.encodeInt32(b, 0, h.a);
519 NB.encodeInt32(b, 4, h.b);
520 NB.encodeInt32(b, 8, h.c);
521 NB.encodeInt32(b, 12, h.d);
522 NB.encodeInt32(b, 16, h.e);
523 return b;
524 }
525
526
527
528
529
530
531
532
533
534
535 public ObjectId toObjectId() throws Sha1CollisionException {
536 finish();
537 return h.toObjectId();
538 }
539
540
541
542
543
544
545
546
547
548
549
550 public void digest(MutableObjectId id) throws Sha1CollisionException {
551 finish();
552 id.set(h.a, h.b, h.c, h.d, h.e);
553 }
554
555
556
557
558
559
560
561
562
563
564
565
566 public boolean hasCollision() {
567 return foundCollision;
568 }
569
570
571
572
573
574
575 public SHA1 reset() {
576 h.init();
577 length = 0;
578 foundCollision = false;
579 return this;
580 }
581
582 private static final class State {
583 int a;
584 int b;
585 int c;
586 int d;
587 int e;
588
589 final void init() {
590
591 save(0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0);
592 }
593
594 final void save(int a1, int b1, int c1, int d1, int e1) {
595 a = a1;
596 b = b1;
597 c = c1;
598 d = d1;
599 e = e1;
600 }
601
602 ObjectId toObjectId() {
603 return new ObjectId(a, b, c, d, e);
604 }
605 }
606 }