February 17, 2005

Collision Search Attacks on SHA1 - the Shandong note

The note on the SHA1 attack from the team from Shandong - Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu - is now available in PDF. Firstly, it is a summary, not the real paper, so the attack is not outlined. Examples are given of _reduced rounds in SHA1_ which is not the real SHA1. However, they established their credibility at Crypto 2004 by turning around attacks over night on new challenges. Essential text, sans numbers, below...

Collision Search Attacks on SHA1
Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu
February 13, 2005

1 Introduction

In this note, we summarize the resulted of our new collision search attacks on SHA1. Technical details will be provided in a forthcoming paper.

We have developed a set of new techniques that are very effective for searching collisions in SHA1. Our analysis shows that collisions of SHA1 can be found with complextity less than 269 hash operations. This is the first attack on the full 80-step SHA1 with complexity less than 280 theoretical bound. Based on our estimation, we expected that real collisions of SHA1 reduced to 70-steps can be found using today's supercomputers.

In the past few years, there have been significant research advances in the analysis of hash functions. The techniques developed in the early work provide an important foundation for our new attacks on SHA1. In particular, our analysis is built upon the original differential attack on SHA0, the near collision attack on SHA0, the multi-block collision techniques, as well as the message modification techniques used in the collision search attack on MD5. Breaking SHA1 would not be possible without these powerful analytical techniques.

Our attacks naturally apply to SHA0 and all reduced variants of SHA1. For SHA0, the attack is so effective that we were able to find real collisions of the full SHA0 with less than 239 hash operations. We also implemented the attack on SHA1 reduced to 58 steps and found collisions with less than 233 hash operations. Two collision examples are given in this note.

2 A collision example for SHA0

<skip some numbers>

Table 1: A collision of the full 80-step SHA0. The two messages that collide are (M0, M1) and (M0 , M'1). Note that padding rules were not applied to the messages.

3 A collision example for 58-step SHA1

<skip some numbers>

"Table 2: A collision of SHA1 reduced to 58 steps. The two messages that collide are M0 and M'0. Note that padding rules were not applied to the messages."

The last footnote generated some controversy which is now settled: padding is irrelevant. A quick summary of our knowledge is that "the Wang,Yin,Yu attack that can reduce the strength of SHA-1 from 80 bits to 69 bits." This still falls short of a practical attack, as it leaves SHA-1 as stronger than MD5 (only 64 bit strength), but SHA-1 is now firmly on the "watch" list. To use my suggested lingo, it is no longer Pareto-complete, so any further use would have to be justified within the context of the application.

Posted by iang at February 17, 2005 08:40 AM | TrackBack
Comments

Hi, Ian - Thanks for posting this, I haven't seen it anywhere else. BTW you are missing a couple of subscript-closing tags after M_0, everything else is so tiny as to be unreadable. I had to use View Source to see it.

As far as the padding issue, it is perfectly normal for them not to include the final padding. None of the collision examples they showed in August had the padding either. The point is, once you have some blocks that collide, you can add to the collisions as much as you want. As long as you append the same thing to both, you will still have a collision. So you simply append the padding after the collision and it all works.

This should not be interpreted as meaning that the attack does not apply to full SHA-1 just because of that comment about the padding, "Note that padding rules were not applied to the messages." They are simply pointing to a detail of how they present their results. It does not indicate any weakness or limitation in the attack.

Posted by: Hal Finney at February 17, 2005 03:47 PM

> Stefan Brands just posted on my blog (and I saw
> reference to this in other blogs, posted anon)
> saying that "it seems that Schneier forgot to
> mention that the paper has a footnote which
> says that the attack on full SHA-1 only works
> if some padding (which SHA-1 requires) is not
> done."
>
> http://www.financialcryptography.com/mt/archives/000355.html


No, that's not what it says. It says that "Note that padding rules were not applied to the message." This is exactly the same as the previous breaks; it just means that the collision appears in the chaining output... if you just append anything at all to the end of the texts, and pad it correctly, you will have valid SHA-1 hashes. Nothing different here than from the MD4/MD5/SHA-0 breaks.

Posted by: Greg R at February 17, 2005 05:20 PM

> Stefan Brands just posted on my blog (and I saw
> reference to this in other blogs, posted anon)
> saying that "it seems that Schneier forgot to
> mention that the paper has a footnote which
> says that the attack on full SHA-1 only works
> if some padding (which SHA-1 requires) is not
> done."

To be sure, in my comment I mentioned that this quote was not mine but taken from the e-mail of a McGill researcher that had just reached me five minutes before. I just learned that this researcher in turn was quoting another well-respected researcher who had seen an advance copy of the draft. The wonders of passing on messages on the basis of credentials :-)

Stefan
www.idcorner.org

Posted by: Stefan at February 17, 2005 08:26 PM

Yes, Sorry about that, Stefan, I do humbly apologise! I was too quick in typing, and realised afterwards my error.

As to the question of credentials, we do need to resolve that!

Posted by: Iang at February 17, 2005 08:33 PM

I've heard that there is a 19-page paper circulating somewhere--it may be in submission to Crypto or something. Anyone have an idea where to find it?

-John

Posted by: John Kelsey at February 18, 2005 09:43 AM

I've now heard back from the reputable source (not Stefan) that indicated the original warning about the footnote: now that the paper is in hand, it appears to have been an incorrect assessment. So everyone is now in agreement that the attack is simply 2^69 bits, and the padding is of no relevance.

(As yet no sign of the full paper here! Even if it was sent here though I wouldn't be able to type in 19 pages.)

Posted by: Iang at February 18, 2005 10:13 PM

Hi,

I’m just a nobody in the crypto world (and any other worlds), so I only have something simple - in logic - to contribute here; so please – be kind – don’t laugh if I’m wrong. I think some of the crypto community is just a little too serious about the significance of collisions in one-way hash functions; collisions were something already expected from hash functions. The question is: can it be exploited practically?

For example, if implementing a message id for every possible combinations of messages in the universe would be a perfect collision free hash function; but that is just too linear and predictable, the id can be traced right back to a message, and it’s also impossible to implement considering the size of the table. Making “MD” the message digest for “Message Digest” is another simple hash function implementation; but there will be way too many possible collisions – like: “Message Digest5”? “Million Dollars”? or “Mother Don”? But even then, how many of these collision messages can seriously fooled a message recipient? “Million Dollars” for example, would probably be a real tempting choice for the malicious Mallory, but it’d still be a little confusing for Bob. Bob is not gonna be able to tell if she means “Million Dollars for you”? or “Send Million Dollars” (in which case, the MD needs to be “SMD”). Mallory could go for “MDTMN”, appending “To Me Now” to “Million Dollars”, but he still needs to figure out how to correctly encrypt the “To Me Now” part, or Bob might just see “Message Digest wha*&^%$#@!?” with signature “MDTMD”. It’ll be easy to find a million possible messages corresponding to the MD “MD”, and surely many are meaningful ones; but if someone is to exploit this to find the message, he’ll also face the task of finding the right one out of so many seem-to-be-right ones. So it seems having collisions might actually help security in a way. With one-way hash functions like SHA-1, the colliding messages for “Message Digest” is probably more going to be like “*&^%$#@!”: meaningless. And suppose the number of possible colliding messages is something like 2^(160-69) - assuming limited message length, Eve will have a very hard time finding the right message out of so many possibilities (if she can actually predict them easily); even harder if there are some other meaningful messages with the same MD.

So I think the real significance of the Shandong team finding is the Chinese may have proved they’re now ranked amongst the world’s super computing powers. I don’t see how random collisions in one-way hash functions can be a serious enough security threat to make the one-way hash function a broken junk. But please do correct me if I’m wrong.

Posted by: Yen at February 21, 2005 07:48 AM

Hi:
Had anyone tested the test vectors for SHA-1 given in the collision search attacks on SHA1.
If yes please let me know.

Posted by: Praveen at February 23, 2005 01:12 AM

Praveen,

Seems like everybody is waiting for somebody else to do the work.. well, I guess curiosity kills the cat..

Here is what I found with the messages. The 58th-step hashes do match for the two messages, but the number I got is different from the 'h1' in the paper. I don't know what kind of SHA-1 was implemented for the paper, but I'm quite sure my SHA-1 module is fine. The NIST test case of ASCII "abc" was put through the module first and produced correct results.

See the numbers below.

M0
0 67452301 efcdab89 98badcfe 10325476 c3d2e1f0
1 b2dff369 67452301 7bf36ae2 98badcfe 10325476
2 63c4b1a2 b2dff369 59d148c0 7bf36ae2 98badcfe
3 21c2b110 63c4b1a2 6cb7fcda 59d148c0 7bf36ae2
4 d526702c 21c2b110 98f12c68 6cb7fcda 59d148c0
5 ac4ec847 d526702c 0870ac44 98f12c68 6cb7fcda
6 c6d362df ac4ec847 35499c0b 0870ac44 98f12c68
7 fedf5182 c6d362df eb13b211 35499c0b 0870ac44
8 9a011586 fedf5182 f1b4d8b7 eb13b211 35499c0b
9 14c400ae 9a011586 bfb7d460 f1b4d8b7 eb13b211
10 7dfbe037 14c400ae a6804561 bfb7d460 f1b4d8b7
11 c16f7ec0 7dfbe037 8531002b a6804561 bfb7d460
12 726e4ae7 c16f7ec0 df7ef80d 8531002b a6804561
13 c1a839e2 726e4ae7 305bdfb0 df7ef80d 8531002b
14 e54d04c6 c1a839e2 dc9b92b9 305bdfb0 df7ef80d
15 153ba8f4 e54d04c6 b06a0e78 dc9b92b9 305bdfb0
16 c0d64826 153ba8f4 b9534131 b06a0e78 dc9b92b9
17 147d4058 c0d64826 054eea3d b9534131 b06a0e78
18 e461e220 147d4058 b0359209 054eea3d b9534131
19 ce1df558 e461e220 051f5016 b0359209 054eea3d
20 5e5b3fb3 ce1df558 39187888 051f5016 b0359209
21 4b677212 5e5b3fb3 33877d56 39187888 051f5016
22 4bf71507 4b677212 d796cfec 33877d56 39187888
23 49e94c70 4bf71507 92d9dc84 d796cfec 33877d56
24 dcf8b25b 49e94c70 d2fdc541 92d9dc84 d796cfec
25 93d5228f dcf8b25b 127a531c d2fdc541 92d9dc84
26 6125fb2b 93d5228f f73e2c96 127a531c d2fdc541
27 8f908be1 6125fb2b e4f548a3 f73e2c96 127a531c
28 4a77363c 8f908be1 d8497eca e4f548a3 f73e2c96
29 ff239bb0 4a77363c 63e422f8 d8497eca e4f548a3
30 ef956859 ff239bb0 129dcd8f 63e422f8 d8497eca
31 54ae55d3 ef956859 3fc8e6ec 129dcd8f 63e422f8
32 a621f9ba 54ae55d3 7be55a16 3fc8e6ec 129dcd8f
33 2f1abebf a621f9ba d52b9574 7be55a16 3fc8e6ec
34 80e6475c 2f1abebf a9887e6e d52b9574 7be55a16
35 d0a4b9ef 80e6475c cbc6afaf a9887e6e d52b9574
36 534c5fb3 d0a4b9ef 203991d7 cbc6afaf a9887e6e
37 99d06606 534c5fb3 f4292e7b 203991d7 cbc6afaf
38 8dd54d7c 99d06606 d4d317ec f4292e7b 203991d7
39 8a19d0a8 8dd54d7c a6741981 d4d317ec f4292e7b
40 a6faa511 8a19d0a8 2375535f a6741981 d4d317ec
41 a5b11b6d a6faa511 2286742a 2375535f a6741981
42 abee3f71 a5b11b6d 69bea944 2286742a 2375535f
43 f37f0648 abee3f71 696c46db 69bea944 2286742a
44 98bcd7e3 f37f0648 6afb8fdc 696c46db 69bea944
45 336146e9 98bcd7e3 3cdfc192 6afb8fdc 696c46db
46 bbb96c36 336146e9 e62f35f8 3cdfc192 6afb8fdc
47 63fee1b4 bbb96c36 4cd851ba e62f35f8 3cdfc192
48 8c97f438 63fee1b4 aeee5b0d 4cd851ba e62f35f8
49 8fe05a9d 8c97f438 18ffb86d aeee5b0d 4cd851ba
50 1ee99f6f 8fe05a9d 2325fd0e 18ffb86d aeee5b0d
51 dc3c9013 1ee99f6f 63f816a7 2325fd0e 18ffb86d
52 8bd58e52 dc3c9013 c7ba67db 63f816a7 2325fd0e
53 9f10dbc8 8bd58e52 f70f2404 c7ba67db 63f816a7
54 13ef5790 9f10dbc8 a2f56394 f70f2404 c7ba67db
55 0553cd66 13ef5790 27c436f2 a2f56394 f70f2404
56 1d628100 0553cd66 04fbd5e4 27c436f2 a2f56394
57 c69503f9 1d628100 8154f359 04fbd5e4 27c436f2
58 3023c438 c69503f9 0758a040 8154f359 04fbd5e4
59 f76cb30f 3023c438 71a540fe 0758a040 8154f359
60 c16ec0d8 f76cb30f 0c08f10e 71a540fe 0758a040
61 8b3ad4e3 c16ec0d8 fddb2cc3 0c08f10e 71a540fe
62 ad71f311 8b3ad4e3 305bb036 fddb2cc3 0c08f10e
63 6b3a54d9 ad71f311 e2ceb538 305bb036 fddb2cc3
64 f712c417 6b3a54d9 6b5c7cc4 e2ceb538 305bb036
65 ecdb21d2 f712c417 5ace9536 6b5c7cc4 e2ceb538
66 8d795749 ecdb21d2 fdc4b105 5ace9536 6b5c7cc4
67 4f79f3b1 8d795749 bb36c874 fdc4b105 5ace9536
68 c07ce060 4f79f3b1 635e55d2 bb36c874 fdc4b105
69 ca0f4e43 c07ce060 53de7cec 635e55d2 bb36c874
70 a8a8fbb5 ca0f4e43 301f3818 53de7cec 635e55d2
71 b59bf4b5 a8a8fbb5 f283d390 301f3818 53de7cec
72 26e22807 b59bf4b5 6a2a3eed f283d390 301f3818
73 d5cfa569 26e22807 6d66fd2d 6a2a3eed f283d390
74 a481a976 d5cfa569 c9b88a01 6d66fd2d 6a2a3eed
75 7c364bfe a481a976 7573e95a c9b88a01 6d66fd2d
76 cb5f624b 7c364bfe a9206a5d 7573e95a c9b88a01
77 406ad09e cb5f624b 9f0d92ff a9206a5d 7573e95a
78 9c1f2847 406ad09e f2d7d892 9f0d92ff a9206a5d
79 425dc5e2 9c1f2847 901ab427 f2d7d892 9f0d92ff
b4ea80a8 322b716b 7fc2a70f a04d089d b6aaba82

M0'
0 67452301 efcdab89 98badcfe 10325476 c3d2e1f0
1 d2dff369 67452301 7bf36ae2 98badcfe 10325476
2 83c4b1b4 d2dff369 59d148c0 7bf36ae2 98badcfe
3 21c2b311 83c4b1b4 74b7fcda 59d148c0 7bf36ae2
4 d526b01a 21c2b311 20f12c6d 74b7fcda 59d148c0
5 b456c646 d526b01a 4870acc4 20f12c6d 74b7fcda
6 c7d3a2df b456c646 b549ac06 4870acc4 20f12c6d
7 fecf520b c7d3a2df ad15b191 b549ac06 4870acc4
8 99ff1586 fecf520b f1f4e8b7 ad15b191 b549ac06
9 94c3ffac 99ff1586 ffb3d482 f1f4e8b7 ad15b191
10 7dfbe037 94c3ffac a67fc561 ffb3d482 f1f4e8b7
11 416f7fc2 7dfbe037 2530ffeb a67fc561 ffb3d482
12 726e4ae7 416f7fc2 df7ef80d 2530ffeb a67fc561
13 c1a839e0 726e4ae7 905bdff0 df7ef80d 2530ffeb
14 e54d04c6 c1a839e0 dc9b92b9 905bdff0 df7ef80d
15 153ba8f5 e54d04c6 306a0e78 dc9b92b9 905bdff0
16 c0d64826 153ba8f5 b9534131 306a0e78 dc9b92b9
17 147d405a c0d64826 454eea3d b9534131 306a0e78
18 e461e222 147d405a b0359209 454eea3d b9534131
19 ce1df559 e461e222 851f5016 b0359209 454eea3d
20 5e5b3fb3 ce1df559 b9187888 851f5016 b0359209
21 4b677210 5e5b3fb3 73877d56 b9187888 851f5016
22 4bf71505 4b677210 d796cfec 73877d56 b9187888
23 49e94c71 4bf71505 12d9dc84 d796cfec 73877d56
24 dcf8b25b 49e94c71 52fdc541 12d9dc84 d796cfec
25 93d5228f dcf8b25b 527a531c 52fdc541 12d9dc84
26 6125fb29 93d5228f f73e2c96 527a531c 52fdc541
27 8f908be0 6125fb29 e4f548a3 f73e2c96 527a531c
28 4a77363c 8f908be0 58497eca e4f548a3 f73e2c96
29 ff239bb2 4a77363c 23e422f8 58497eca e4f548a3
30 ef95685b ff239bb2 129dcd8f 23e422f8 58497eca
31 54ae55d3 ef95685b bfc8e6ec 129dcd8f 23e422f8
32 a621f9ba 54ae55d3 fbe55a16 bfc8e6ec 129dcd8f
33 2f1abebd a621f9ba d52b9574 fbe55a16 bfc8e6ec
34 80e6475c 2f1abebd a9887e6e d52b9574 fbe55a16
35 d0a4b9ef 80e6475c 4bc6afaf a9887e6e d52b9574
36 534c5fb3 d0a4b9ef 203991d7 4bc6afaf a9887e6e
37 99d06604 534c5fb3 f4292e7b 203991d7 4bc6afaf
38 8dd54d7c 99d06604 d4d317ec f4292e7b 203991d7
39 8a19d0aa 8dd54d7c 26741981 d4d317ec f4292e7b
40 a6faa511 8a19d0aa 2375535f 26741981 d4d317ec
41 a5b11b6f a6faa511 a286742a 2375535f 26741981
42 abee3f71 a5b11b6f 69bea944 a286742a 2375535f
43 f37f064a abee3f71 e96c46db 69bea944 a286742a
44 98bcd7e3 f37f064a 6afb8fdc e96c46db 69bea944
45 336146e9 98bcd7e3 bcdfc192 6afb8fdc e96c46db
46 bbb96c36 336146e9 e62f35f8 bcdfc192 6afb8fdc
47 63fee1b4 bbb96c36 4cd851ba e62f35f8 bcdfc192
48 8c97f438 63fee1b4 aeee5b0d 4cd851ba e62f35f8
49 8fe05a9d 8c97f438 18ffb86d aeee5b0d 4cd851ba
50 1ee99f6f 8fe05a9d 2325fd0e 18ffb86d aeee5b0d
51 dc3c9013 1ee99f6f 63f816a7 2325fd0e 18ffb86d
52 8bd58e52 dc3c9013 c7ba67db 63f816a7 2325fd0e
53 9f10dbc8 8bd58e52 f70f2404 c7ba67db 63f816a7
54 13ef5790 9f10dbc8 a2f56394 f70f2404 c7ba67db
55 0553cd66 13ef5790 27c436f2 a2f56394 f70f2404
56 1d628100 0553cd66 04fbd5e4 27c436f2 a2f56394
57 c69503f9 1d628100 8154f359 04fbd5e4 27c436f2
58 3023c438 c69503f9 0758a040 8154f359 04fbd5e4
59 f76cb313 3023c438 71a540fe 0758a040 8154f359
60 c16ec1d8 f76cb313 0c08f10e 71a540fe 0758a040
61 8b3af4c3 c16ec1d8 fddb2cc4 0c08f10e 71a540fe
62 ad75ee15 8b3af4c3 305bb076 fddb2cc4 0c08f10e
63 6bb9d4b5 ad75ee15 e2cebd30 305bb076 fddb2cc4
64 06feacd5 6bb9d4b5 6b5d7b85 e2cebd30 305bb076
65 e9d9ae9d 06feacd5 5aee752d 6b5d7b85 e2cebd30
66 9e186b3b e9d9ae9d 41bfab35 5aee752d 6b5d7b85
67 0a14db72 9e186b3b 7a766ba7 41bfab35 5aee752d
68 ee4036c4 0a14db72 e7861ace 7a766ba7 41bfab35
69 c74854f8 ee4036c4 828536dc e7861ace 7a766ba7
70 a94fc71d c74854f8 3b900db1 828536dc e7861ace
71 232c8bd9 a94fc71d 31d2153e 3b900db1 828536dc
72 40759dc0 232c8bd9 6a53f1c7 31d2153e 3b900db1
73 5f2a875e 40759dc0 48cb22f6 6a53f1c7 31d2153e
74 506a906f 5f2a875e 101d6770 48cb22f6 6a53f1c7
75 9067de61 506a906f 97caa1d7 101d6770 48cb22f6
76 ec68629c 9067de61 d41aa41b 97caa1d7 101d6770
77 db41cbf7 ec68629c 6419f798 d41aa41b 97caa1d7
78 784e0231 db41cbf7 3b1a18a7 6419f798 d41aa41b
79 49c4c137 784e0231 f6d072fd 3b1a18a7 6419f798
1d887dc1 39926cc0 f6ce5d8a 0702c773 feecfa97

NIST ASCII "abc" Test Case
0 67452301 efcdab89 98badcfe 10325476 c3d2e1f0
1 0116fc33 67452301 7bf36ae2 98badcfe 10325476
2 8990536d 0116fc33 59d148c0 7bf36ae2 98badcfe
3 a1390f08 8990536d c045bf0c 59d148c0 7bf36ae2
4 cdd8e11b a1390f08 626414db c045bf0c 59d148c0
5 cfd499de cdd8e11b 284e43c2 626414db c045bf0c
6 3fc7ca40 cfd499de f3763846 284e43c2 626414db
7 993e30c1 3fc7ca40 b3f52677 f3763846 284e43c2
8 9e8c07d4 993e30c1 0ff1f290 b3f52677 f3763846
9 4b6ae328 9e8c07d4 664f8c30 0ff1f290 b3f52677
10 8351f929 4b6ae328 27a301f5 664f8c30 0ff1f290
11 fbda9e89 8351f929 12dab8ca 27a301f5 664f8c30
12 63188fe4 fbda9e89 60d47e4a 12dab8ca 27a301f5
13 4607b664 63188fe4 7ef6a7a2 60d47e4a 12dab8ca
14 9128f695 4607b664 18c623f9 7ef6a7a2 60d47e4a
15 196bee77 9128f695 1181ed99 18c623f9 7ef6a7a2
16 20bdd62f 196bee77 644a3da5 1181ed99 18c623f9
17 4e925823 20bdd62f c65afb9d 644a3da5 1181ed99
18 82aa6728 4e925823 c82f758b c65afb9d 644a3da5
19 dc64901d 82aa6728 d3a49608 c82f758b c65afb9d
20 fd9e1d7d dc64901d 20aa99ca d3a49608 c82f758b
21 1a37b0ca fd9e1d7d 77192407 20aa99ca d3a49608
22 33a23bfc 1a37b0ca 7f67875f 77192407 20aa99ca
23 21283486 33a23bfc 868dec32 7f67875f 77192407
24 d541f12d 21283486 0ce88eff 868dec32 7f67875f
25 c7567dc6 d541f12d 884a0d21 0ce88eff 868dec32
26 48413ba4 c7567dc6 75507c4b 884a0d21 0ce88eff
27 be35fbd5 48413ba4 b1d59f71 75507c4b 884a0d21
28 4aa84d97 be35fbd5 12104ee9 b1d59f71 75507c4b
29 8370b52e 4aa84d97 6f8d7ef5 12104ee9 b1d59f71
30 c5fbaf5d 8370b52e d2aa1365 6f8d7ef5 12104ee9
31 1267b407 c5fbaf5d a0dc2d4b d2aa1365 6f8d7ef5
32 3b845d33 1267b407 717eebd7 a0dc2d4b d2aa1365
33 046faa0a 3b845d33 c499ed01 717eebd7 a0dc2d4b
34 2c0ebc11 046faa0a cee1174c c499ed01 717eebd7
35 21796ad4 2c0ebc11 811bea82 cee1174c c499ed01
36 dcbbb0cb 21796ad4 4b03af04 811bea82 cee1174c
37 0f511fd8 dcbbb0cb 085e5ab5 4b03af04 811bea82
38 dc63973f 0f511fd8 f72eec32 085e5ab5 4b03af04
39 4c986405 dc63973f 03d447f6 f72eec32 085e5ab5
40 32de1cba 4c986405 f718e5cf 03d447f6 f72eec32
41 fc87dedf 32de1cba 53261901 f718e5cf 03d447f6
42 970a0d5c fc87dedf 8cb7872e 53261901 f718e5cf
43 7f193dc5 970a0d5c ff21f7b7 8cb7872e 53261901
44 ee1b1aaf 7f193dc5 25c28357 ff21f7b7 8cb7872e
45 40f28e09 ee1b1aaf 5fc64f71 25c28357 ff21f7b7
46 1c51e1f2 40f28e09 fb86c6ab 5fc64f71 25c28357
47 a01b846c 1c51e1f2 503ca382 fb86c6ab 5fc64f71
48 bead02ca a01b846c 8714787c 503ca382 fb86c6ab
49 baf39337 bead02ca 2806e11b 8714787c 503ca382
50 120731c5 baf39337 afab40b2 2806e11b 8714787c
51 641db2ce 120731c5 eebce4cd afab40b2 2806e11b
52 3847ad66 641db2ce 4481cc71 eebce4cd afab40b2
53 e490436d 3847ad66 99076cb3 4481cc71 eebce4cd
54 27e9f1d8 e490436d 8e11eb59 99076cb3 4481cc71
55 7b71f76d 27e9f1d8 792410db 8e11eb59 99076cb3
56 5e6456af 7b71f76d 09fa7c76 792410db 8e11eb59
57 c846093f 5e6456af 5edc7ddb 09fa7c76 792410db
58 d262ff50 c846093f d79915ab 5edc7ddb 09fa7c76
59 09d785fd d262ff50 f211824f d79915ab 5edc7ddb
60 3f52de5a 09d785fd 3498bfd4 f211824f d79915ab
61 d756c147 3f52de5a 4275e17f 3498bfd4 f211824f
62 548c9cb2 d756c147 8fd4b796 4275e17f 3498bfd4
63 b66c020b 548c9cb2 f5d5b051 8fd4b796 4275e17f
64 6b61c9e1 b66c020b 9523272c f5d5b051 8fd4b796
65 19dfa7ac 6b61c9e1 ed9b0082 9523272c f5d5b051
66 101655f9 19dfa7ac 5ad87278 ed9b0082 9523272c
67 0c3df2b4 101655f9 0677e9eb 5ad87278 ed9b0082
68 78dd4d2b 0c3df2b4 4405957e 0677e9eb 5ad87278
69 497093c0 78dd4d2b 030f7cad 4405957e 0677e9eb
70 3f2588c2 497093c0 de37534a 030f7cad 4405957e
71 c199f8c7 3f2588c2 125c24f0 de37534a 030f7cad
72 39859de7 c199f8c7 8fc96230 125c24f0 de37534a
73 edb42de4 39859de7 f0667e31 8fc96230 125c24f0
74 11793f6f edb42de4 ce616779 f0667e31 8fc96230
75 5ee76897 11793f6f 3b6d0b79 ce616779 f0667e31
76 63f7dab7 5ee76897 c45e4fdb 3b6d0b79 ce616779
77 a079b7d9 63f7dab7 d7b9da25 c45e4fdb 3b6d0b79
78 860d21cc a079b7d9 d8fdf6ad d7b9da25 c45e4fdb
79 5738d5e1 860d21cc 681e6df6 d8fdf6ad d7b9da25
a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d

Posted by: Yen at February 25, 2005 08:36 PM

oops.. mis-stepped just a little bit.. here is take two

M0
0 b2dff369 67452301 7bf36ae2 98badcfe 10325476
1 63c4b1a2 b2dff369 59d148c0 7bf36ae2 98badcfe
2 21c2b110 63c4b1a2 6cb7fcda 59d148c0 7bf36ae2
3 d526702c 21c2b110 98f12c68 6cb7fcda 59d148c0
4 ac4ec847 d526702c 0870ac44 98f12c68 6cb7fcda
5 c6d362df ac4ec847 35499c0b 0870ac44 98f12c68
6 fedf5182 c6d362df eb13b211 35499c0b 0870ac44
7 9a011586 fedf5182 f1b4d8b7 eb13b211 35499c0b
8 14c400ae 9a011586 bfb7d460 f1b4d8b7 eb13b211
9 7dfbe037 14c400ae a6804561 bfb7d460 f1b4d8b7
10 c16f7ec0 7dfbe037 8531002b a6804561 bfb7d460
11 726e4ae7 c16f7ec0 df7ef80d 8531002b a6804561
12 c1a839e2 726e4ae7 305bdfb0 df7ef80d 8531002b
13 e54d04c6 c1a839e2 dc9b92b9 305bdfb0 df7ef80d
14 153ba8f4 e54d04c6 b06a0e78 dc9b92b9 305bdfb0
15 c0d64826 153ba8f4 b9534131 b06a0e78 dc9b92b9
16 147d4058 c0d64826 054eea3d b9534131 b06a0e78
17 e461e220 147d4058 b0359209 054eea3d b9534131
18 ce1df558 e461e220 051f5016 b0359209 054eea3d
19 5e5b3fb3 ce1df558 39187888 051f5016 b0359209
20 4b677212 5e5b3fb3 33877d56 39187888 051f5016
21 4bf71507 4b677212 d796cfec 33877d56 39187888
22 49e94c70 4bf71507 92d9dc84 d796cfec 33877d56
23 dcf8b25b 49e94c70 d2fdc541 92d9dc84 d796cfec
24 93d5228f dcf8b25b 127a531c d2fdc541 92d9dc84
25 6125fb2b 93d5228f f73e2c96 127a531c d2fdc541
26 8f908be1 6125fb2b e4f548a3 f73e2c96 127a531c
27 4a77363c 8f908be1 d8497eca e4f548a3 f73e2c96
28 ff239bb0 4a77363c 63e422f8 d8497eca e4f548a3
29 ef956859 ff239bb0 129dcd8f 63e422f8 d8497eca
30 54ae55d3 ef956859 3fc8e6ec 129dcd8f 63e422f8
31 a621f9ba 54ae55d3 7be55a16 3fc8e6ec 129dcd8f
32 2f1abebf a621f9ba d52b9574 7be55a16 3fc8e6ec
33 80e6475c 2f1abebf a9887e6e d52b9574 7be55a16
34 d0a4b9ef 80e6475c cbc6afaf a9887e6e d52b9574
35 534c5fb3 d0a4b9ef 203991d7 cbc6afaf a9887e6e
36 99d06606 534c5fb3 f4292e7b 203991d7 cbc6afaf
37 8dd54d7c 99d06606 d4d317ec f4292e7b 203991d7
38 8a19d0a8 8dd54d7c a6741981 d4d317ec f4292e7b
39 a6faa511 8a19d0a8 2375535f a6741981 d4d317ec
40 a5b11b6d a6faa511 2286742a 2375535f a6741981
41 abee3f71 a5b11b6d 69bea944 2286742a 2375535f
42 f37f0648 abee3f71 696c46db 69bea944 2286742a
43 98bcd7e3 f37f0648 6afb8fdc 696c46db 69bea944
44 336146e9 98bcd7e3 3cdfc192 6afb8fdc 696c46db
45 bbb96c36 336146e9 e62f35f8 3cdfc192 6afb8fdc
46 63fee1b4 bbb96c36 4cd851ba e62f35f8 3cdfc192
47 8c97f438 63fee1b4 aeee5b0d 4cd851ba e62f35f8
48 8fe05a9d 8c97f438 18ffb86d aeee5b0d 4cd851ba
49 1ee99f6f 8fe05a9d 2325fd0e 18ffb86d aeee5b0d
50 dc3c9013 1ee99f6f 63f816a7 2325fd0e 18ffb86d
51 8bd58e52 dc3c9013 c7ba67db 63f816a7 2325fd0e
52 9f10dbc8 8bd58e52 f70f2404 c7ba67db 63f816a7
53 13ef5790 9f10dbc8 a2f56394 f70f2404 c7ba67db
54 0553cd66 13ef5790 27c436f2 a2f56394 f70f2404
55 1d628100 0553cd66 04fbd5e4 27c436f2 a2f56394
56 c69503f9 1d628100 8154f359 04fbd5e4 27c436f2
57 3023c438 c69503f9 0758a040 8154f359 04fbd5e4
58 f76cb30f 3023c438 71a540fe 0758a040 8154f359
59 c16ec0d8 f76cb30f 0c08f10e 71a540fe 0758a040
60 8b3ad4e3 c16ec0d8 fddb2cc3 0c08f10e 71a540fe
61 ad71f311 8b3ad4e3 305bb036 fddb2cc3 0c08f10e
62 6b3a54d9 ad71f311 e2ceb538 305bb036 fddb2cc3
63 f712c417 6b3a54d9 6b5c7cc4 e2ceb538 305bb036
64 ecdb21d2 f712c417 5ace9536 6b5c7cc4 e2ceb538
65 8d795749 ecdb21d2 fdc4b105 5ace9536 6b5c7cc4
66 4f79f3b1 8d795749 bb36c874 fdc4b105 5ace9536
67 c07ce060 4f79f3b1 635e55d2 bb36c874 fdc4b105
68 ca0f4e43 c07ce060 53de7cec 635e55d2 bb36c874
69 a8a8fbb5 ca0f4e43 301f3818 53de7cec 635e55d2
70 b59bf4b5 a8a8fbb5 f283d390 301f3818 53de7cec
71 26e22807 b59bf4b5 6a2a3eed f283d390 301f3818
72 d5cfa569 26e22807 6d66fd2d 6a2a3eed f283d390
73 a481a976 d5cfa569 c9b88a01 6d66fd2d 6a2a3eed
74 7c364bfe a481a976 7573e95a c9b88a01 6d66fd2d
75 cb5f624b 7c364bfe a9206a5d 7573e95a c9b88a01
76 406ad09e cb5f624b 9f0d92ff a9206a5d 7573e95a
77 9c1f2847 406ad09e f2d7d892 9f0d92ff a9206a5d
78 425dc5e2 9c1f2847 901ab427 f2d7d892 9f0d92ff
79 4da55da7 425dc5e2 e707ca11 901ab427 f2d7d892
b4ea80a8 322b716b 7fc2a70f a04d089d b6aaba82

M0'
0 d2dff369 67452301 7bf36ae2 98badcfe 10325476
1 83c4b1b4 d2dff369 59d148c0 7bf36ae2 98badcfe
2 21c2b311 83c4b1b4 74b7fcda 59d148c0 7bf36ae2
3 d526b01a 21c2b311 20f12c6d 74b7fcda 59d148c0
4 b456c646 d526b01a 4870acc4 20f12c6d 74b7fcda
5 c7d3a2df b456c646 b549ac06 4870acc4 20f12c6d
6 fecf520b c7d3a2df ad15b191 b549ac06 4870acc4
7 99ff1586 fecf520b f1f4e8b7 ad15b191 b549ac06
8 94c3ffac 99ff1586 ffb3d482 f1f4e8b7 ad15b191
9 7dfbe037 94c3ffac a67fc561 ffb3d482 f1f4e8b7
10 416f7fc2 7dfbe037 2530ffeb a67fc561 ffb3d482
11 726e4ae7 416f7fc2 df7ef80d 2530ffeb a67fc561
12 c1a839e0 726e4ae7 905bdff0 df7ef80d 2530ffeb
13 e54d04c6 c1a839e0 dc9b92b9 905bdff0 df7ef80d
14 153ba8f5 e54d04c6 306a0e78 dc9b92b9 905bdff0
15 c0d64826 153ba8f5 b9534131 306a0e78 dc9b92b9
16 147d405a c0d64826 454eea3d b9534131 306a0e78
17 e461e222 147d405a b0359209 454eea3d b9534131
18 ce1df559 e461e222 851f5016 b0359209 454eea3d
19 5e5b3fb3 ce1df559 b9187888 851f5016 b0359209
20 4b677210 5e5b3fb3 73877d56 b9187888 851f5016
21 4bf71505 4b677210 d796cfec 73877d56 b9187888
22 49e94c71 4bf71505 12d9dc84 d796cfec 73877d56
23 dcf8b25b 49e94c71 52fdc541 12d9dc84 d796cfec
24 93d5228f dcf8b25b 527a531c 52fdc541 12d9dc84
25 6125fb29 93d5228f f73e2c96 527a531c 52fdc541
26 8f908be0 6125fb29 e4f548a3 f73e2c96 527a531c
27 4a77363c 8f908be0 58497eca e4f548a3 f73e2c96
28 ff239bb2 4a77363c 23e422f8 58497eca e4f548a3
29 ef95685b ff239bb2 129dcd8f 23e422f8 58497eca
30 54ae55d3 ef95685b bfc8e6ec 129dcd8f 23e422f8
31 a621f9ba 54ae55d3 fbe55a16 bfc8e6ec 129dcd8f
32 2f1abebd a621f9ba d52b9574 fbe55a16 bfc8e6ec
33 80e6475c 2f1abebd a9887e6e d52b9574 fbe55a16
34 d0a4b9ef 80e6475c 4bc6afaf a9887e6e d52b9574
35 534c5fb3 d0a4b9ef 203991d7 4bc6afaf a9887e6e
36 99d06604 534c5fb3 f4292e7b 203991d7 4bc6afaf
37 8dd54d7c 99d06604 d4d317ec f4292e7b 203991d7
38 8a19d0aa 8dd54d7c 26741981 d4d317ec f4292e7b
39 a6faa511 8a19d0aa 2375535f 26741981 d4d317ec
40 a5b11b6f a6faa511 a286742a 2375535f 26741981
41 abee3f71 a5b11b6f 69bea944 a286742a 2375535f
42 f37f064a abee3f71 e96c46db 69bea944 a286742a
43 98bcd7e3 f37f064a 6afb8fdc e96c46db 69bea944
44 336146e9 98bcd7e3 bcdfc192 6afb8fdc e96c46db
45 bbb96c36 336146e9 e62f35f8 bcdfc192 6afb8fdc
46 63fee1b4 bbb96c36 4cd851ba e62f35f8 bcdfc192
47 8c97f438 63fee1b4 aeee5b0d 4cd851ba e62f35f8
48 8fe05a9d 8c97f438 18ffb86d aeee5b0d 4cd851ba
49 1ee99f6f 8fe05a9d 2325fd0e 18ffb86d aeee5b0d
50 dc3c9013 1ee99f6f 63f816a7 2325fd0e 18ffb86d
51 8bd58e52 dc3c9013 c7ba67db 63f816a7 2325fd0e
52 9f10dbc8 8bd58e52 f70f2404 c7ba67db 63f816a7
53 13ef5790 9f10dbc8 a2f56394 f70f2404 c7ba67db
54 0553cd66 13ef5790 27c436f2 a2f56394 f70f2404
55 1d628100 0553cd66 04fbd5e4 27c436f2 a2f56394
56 c69503f9 1d628100 8154f359 04fbd5e4 27c436f2
57 3023c438 c69503f9 0758a040 8154f359 04fbd5e4
58 f76cb313 3023c438 71a540fe 0758a040 8154f359
59 c16ec1d8 f76cb313 0c08f10e 71a540fe 0758a040
60 8b3af4c3 c16ec1d8 fddb2cc4 0c08f10e 71a540fe
61 ad75ee15 8b3af4c3 305bb076 fddb2cc4 0c08f10e
62 6bb9d4b5 ad75ee15 e2cebd30 305bb076 fddb2cc4
63 06feacd5 6bb9d4b5 6b5d7b85 e2cebd30 305bb076
64 e9d9ae9d 06feacd5 5aee752d 6b5d7b85 e2cebd30
65 9e186b3b e9d9ae9d 41bfab35 5aee752d 6b5d7b85
66 0a14db72 9e186b3b 7a766ba7 41bfab35 5aee752d
67 ee4036c4 0a14db72 e7861ace 7a766ba7 41bfab35
68 c74854f8 ee4036c4 828536dc e7861ace 7a766ba7
69 a94fc71d c74854f8 3b900db1 828536dc e7861ace
70 232c8bd9 a94fc71d 31d2153e 3b900db1 828536dc
71 40759dc0 232c8bd9 6a53f1c7 31d2153e 3b900db1
72 5f2a875e 40759dc0 48cb22f6 6a53f1c7 31d2153e
73 506a906f 5f2a875e 101d6770 48cb22f6 6a53f1c7
74 9067de61 506a906f 97caa1d7 101d6770 48cb22f6
75 ec68629c 9067de61 d41aa41b 97caa1d7 101d6770
76 db41cbf7 ec68629c 6419f798 d41aa41b 97caa1d7
77 784e0231 db41cbf7 3b1a18a7 6419f798 d41aa41b
78 49c4c137 784e0231 f6d072fd 3b1a18a7 6419f798
79 b6435ac0 49c4c137 5e13808c f6d072fd 3b1a18a7
1d887dc1 39926cc0 f6ce5d8a 0702c773 feecfa97

NIST ASCII "abc" Test Case
0 0116fc33 67452301 7bf36ae2 98badcfe 10325476
1 8990536d 0116fc33 59d148c0 7bf36ae2 98badcfe
2 a1390f08 8990536d c045bf0c 59d148c0 7bf36ae2
3 cdd8e11b a1390f08 626414db c045bf0c 59d148c0
4 cfd499de cdd8e11b 284e43c2 626414db c045bf0c
5 3fc7ca40 cfd499de f3763846 284e43c2 626414db
6 993e30c1 3fc7ca40 b3f52677 f3763846 284e43c2
7 9e8c07d4 993e30c1 0ff1f290 b3f52677 f3763846
8 4b6ae328 9e8c07d4 664f8c30 0ff1f290 b3f52677
9 8351f929 4b6ae328 27a301f5 664f8c30 0ff1f290
10 fbda9e89 8351f929 12dab8ca 27a301f5 664f8c30
11 63188fe4 fbda9e89 60d47e4a 12dab8ca 27a301f5
12 4607b664 63188fe4 7ef6a7a2 60d47e4a 12dab8ca
13 9128f695 4607b664 18c623f9 7ef6a7a2 60d47e4a
14 196bee77 9128f695 1181ed99 18c623f9 7ef6a7a2
15 20bdd62f 196bee77 644a3da5 1181ed99 18c623f9
16 4e925823 20bdd62f c65afb9d 644a3da5 1181ed99
17 82aa6728 4e925823 c82f758b c65afb9d 644a3da5
18 dc64901d 82aa6728 d3a49608 c82f758b c65afb9d
19 fd9e1d7d dc64901d 20aa99ca d3a49608 c82f758b
20 1a37b0ca fd9e1d7d 77192407 20aa99ca d3a49608
21 33a23bfc 1a37b0ca 7f67875f 77192407 20aa99ca
22 21283486 33a23bfc 868dec32 7f67875f 77192407
23 d541f12d 21283486 0ce88eff 868dec32 7f67875f
24 c7567dc6 d541f12d 884a0d21 0ce88eff 868dec32
25 48413ba4 c7567dc6 75507c4b 884a0d21 0ce88eff
26 be35fbd5 48413ba4 b1d59f71 75507c4b 884a0d21
27 4aa84d97 be35fbd5 12104ee9 b1d59f71 75507c4b
28 8370b52e 4aa84d97 6f8d7ef5 12104ee9 b1d59f71
29 c5fbaf5d 8370b52e d2aa1365 6f8d7ef5 12104ee9
30 1267b407 c5fbaf5d a0dc2d4b d2aa1365 6f8d7ef5
31 3b845d33 1267b407 717eebd7 a0dc2d4b d2aa1365
32 046faa0a 3b845d33 c499ed01 717eebd7 a0dc2d4b
33 2c0ebc11 046faa0a cee1174c c499ed01 717eebd7
34 21796ad4 2c0ebc11 811bea82 cee1174c c499ed01
35 dcbbb0cb 21796ad4 4b03af04 811bea82 cee1174c
36 0f511fd8 dcbbb0cb 085e5ab5 4b03af04 811bea82
37 dc63973f 0f511fd8 f72eec32 085e5ab5 4b03af04
38 4c986405 dc63973f 03d447f6 f72eec32 085e5ab5
39 32de1cba 4c986405 f718e5cf 03d447f6 f72eec32
40 fc87dedf 32de1cba 53261901 f718e5cf 03d447f6
41 970a0d5c fc87dedf 8cb7872e 53261901 f718e5cf
42 7f193dc5 970a0d5c ff21f7b7 8cb7872e 53261901
43 ee1b1aaf 7f193dc5 25c28357 ff21f7b7 8cb7872e
44 40f28e09 ee1b1aaf 5fc64f71 25c28357 ff21f7b7
45 1c51e1f2 40f28e09 fb86c6ab 5fc64f71 25c28357
46 a01b846c 1c51e1f2 503ca382 fb86c6ab 5fc64f71
47 bead02ca a01b846c 8714787c 503ca382 fb86c6ab
48 baf39337 bead02ca 2806e11b 8714787c 503ca382
49 120731c5 baf39337 afab40b2 2806e11b 8714787c
50 641db2ce 120731c5 eebce4cd afab40b2 2806e11b
51 3847ad66 641db2ce 4481cc71 eebce4cd afab40b2
52 e490436d 3847ad66 99076cb3 4481cc71 eebce4cd
53 27e9f1d8 e490436d 8e11eb59 99076cb3 4481cc71
54 7b71f76d 27e9f1d8 792410db 8e11eb59 99076cb3
55 5e6456af 7b71f76d 09fa7c76 792410db 8e11eb59
56 c846093f 5e6456af 5edc7ddb 09fa7c76 792410db
57 d262ff50 c846093f d79915ab 5edc7ddb 09fa7c76
58 09d785fd d262ff50 f211824f d79915ab 5edc7ddb
59 3f52de5a 09d785fd 3498bfd4 f211824f d79915ab
60 d756c147 3f52de5a 4275e17f 3498bfd4 f211824f
61 548c9cb2 d756c147 8fd4b796 4275e17f 3498bfd4
62 b66c020b 548c9cb2 f5d5b051 8fd4b796 4275e17f
63 6b61c9e1 b66c020b 9523272c f5d5b051 8fd4b796
64 19dfa7ac 6b61c9e1 ed9b0082 9523272c f5d5b051
65 101655f9 19dfa7ac 5ad87278 ed9b0082 9523272c
66 0c3df2b4 101655f9 0677e9eb 5ad87278 ed9b0082
67 78dd4d2b 0c3df2b4 4405957e 0677e9eb 5ad87278
68 497093c0 78dd4d2b 030f7cad 4405957e 0677e9eb
69 3f2588c2 497093c0 de37534a 030f7cad 4405957e
70 c199f8c7 3f2588c2 125c24f0 de37534a 030f7cad
71 39859de7 c199f8c7 8fc96230 125c24f0 de37534a
72 edb42de4 39859de7 f0667e31 8fc96230 125c24f0
73 11793f6f edb42de4 ce616779 f0667e31 8fc96230
74 5ee76897 11793f6f 3b6d0b79 ce616779 f0667e31
75 63f7dab7 5ee76897 c45e4fdb 3b6d0b79 ce616779
76 a079b7d9 63f7dab7 d7b9da25 c45e4fdb 3b6d0b79
77 860d21cc a079b7d9 d8fdf6ad d7b9da25 c45e4fdb
78 5738d5e1 860d21cc 681e6df6 d8fdf6ad d7b9da25
79 42541b35 5738d5e1 21834873 681e6df6 d8fdf6ad
a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d

Posted by: Yen at February 25, 2005 10:15 PM

I noticed that the SHA0 80 step hash collision
only involved changing bits 31, 6,& 1 (left char is msb).

I wonder if those bits always work.

Posted by: Ron at April 20, 2005 05:33 PM
Post a comment









Remember personal info?






Hit preview to see your comment as it would be displayed.