6
$\begingroup$

Where may I find the description and or pseudocode for the SHA0 algorithm. I am looking for something on these lines - HMAC RIPEMD.

I have been implementing a few of those (HMAC, HOTP, TOTP and MD4, MD5, RIPEMD-128,160)

$\endgroup$
  • 3
    $\begingroup$ Also the original attack paper (PDF) on SHA-0 contains a description which credits the specification to FIPS 180 (which I couldn't easily find). $\endgroup$ – SEJPM Sep 4 '18 at 19:45
  • 2
    $\begingroup$ @SEJPM - Do you mean this - csrc.nist.gov/publications/detail/fips/180/archive/1993-05-11 I am just implementing them for fun. I have already implemented MD4, MD5, RIPEMD-128,160. I wish I had done this years ago. It has granted me some insight into the hashing algorithms and a lot more questions to ponder on. $\endgroup$ – Lord Loh. Sep 4 '18 at 20:05
  • 3
    $\begingroup$ I have put a request with my University library for the FIPS-180 (1993). Lets see if their document delivery department delivers :-D. In the past they gave up on my requests for test image sets that were used in Jpeg 2000. $\endgroup$ – Lord Loh. Sep 4 '18 at 20:07
  • 3
    $\begingroup$ My university library's document delivery failed to deliver. They sent me this message - has been cancelled by the interlibrary loan staff for the following reason: ***We are unable to find a library willing to lend us this item. *** No library is able to supply this item. $\endgroup$ – Lord Loh. Sep 4 '18 at 21:04
  • 2
    $\begingroup$ More on topic, the page of IAIK Graz on SHA-0 Cryptanalysis contains a list of papers on the subject, of which at least "Collisions on SHA-0 in One Hour", "Near-Collisions of SHA-0" and "Differential Collisions in SHA-0" are publicly available and contain a description of the algorithm. That's second hand, but with the number of references to these papers they should be considered very reliable. They are all available, although the org. paper of Joux et all is a scanned PDF... $\endgroup$ – Maarten Bodewes Sep 4 '18 at 22:33
10
$\begingroup$

The reference on SHA(-0) is FIPS 180 (archived scan) of 1993 May 11, referenced on the NIST website (the link recently added there is to another scan lacking page 1 and the one before, thus foreword, abstract, explanation..). There's also this text draft of 1992 January 22 (also here with less indication on origin).


The Proposal for Change of that into SHA-1 was published on 1994 July 11 and is online at the Federal Register with partially garbled text, including for the security-critical change:

In Section 7 of [1] (page 9), the line which reads
    (b) For t=16 to 79 let Wt = Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16.
is to be replaced by
    (b) For t=16 to 79 let Wt = S1(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16).
where S1 is a left circular shift by one bit as defined in Section 3 of [1] (page 6), namely S1(X) = (X << 1) v (X >> 31).

Note: What's kept of the original PfC has messed-up sub/superscripts (a modern web artifact), and misses the closing parenthesis on the modified expression for Wt (possibly an omission in the original).
This is was a technical change in the design, critical for improved security, rather than a correction of a typographical error as could be understood by casual reading of the PfC. This change was introduced without rationale, and initially without ensuing changes in the test vectors. It is thus reasonable to suspect that it was intentionally sneaked quietly, with knowledge that the original was not as secure as intended against educated collision attacks.

The revised document is FIPS 180-1 of 1995 April 17, referenced on the NIST website (with a link to an external scan of the actual document).


Changing source code for SHA-1 into one for SHA(-0) is easy: just remove the one-bit rotations of a 32-bit word of the 512-bit message block. For example, in the reference implementation of RFC 6234, change

W[t] = SHA1_ROTL(1, W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);

to

W[t] =          (   W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
$\endgroup$
  • 2
    $\begingroup$ Thanks a bunch! I should have thought of the way back machine! $\endgroup$ – Lord Loh. Sep 5 '18 at 15:32
  • 2
    $\begingroup$ @Lord Loh: AFAIK the Wayback Machine has no good search engine, and did not contain the FIPS 180 scan before my answer. I stepped on that scan in 2016, and kept the URL. The website has vanished, but the researcher kept the same organization on his new website, which allowed to find a working URL, allowing the Wayback Machine to archive. For FIPS 180-1, I had a native PDF dated 1997. At that time I used a MacOS 9 browser keeping URLs as "finder comments", kept in my archives as NTFS streams emulated by Samba on an ext4 RAID6 volume on a NAS, and the Wayback Machine had that document archived. $\endgroup$ – fgrieu Sep 5 '18 at 16:35
  • 1
    $\begingroup$ Wow! I should upvote your answer more than once! $\endgroup$ – Lord Loh. Sep 5 '18 at 16:49
  • $\begingroup$ @LordLoh. Be sure to download the PDF yourself. If the website ever goes down and a new owner puts up an exclusionary robots.txt, the Wayback Machine will censor the website's archive. $\endgroup$ – forest Sep 21 '18 at 1:25
  • $\begingroup$ github.com/algorithmic-space/cryptoy/tree/master/specs - I have mirrored the pdf in my github repository :-) $\endgroup$ – Lord Loh. Sep 21 '18 at 6:39
5
$\begingroup$

Here is a copy directly from NIST at the DOI site.

And yes, I simply asked and got multiple, very polite responses. Thanks NIST!

$\endgroup$
  • 1
    $\begingroup$ The scan linked in this answer is missing two printed pages (page 1 and the one before), including foreword, abstract, explanation... that are in the one linked in my answer. On the other hand, we get the scan of the jacket, complete with "Penalty for private use $300" on the back. I guess they originate from the same paper copy since holes appear to be at the same position. $\endgroup$ – fgrieu Sep 7 '18 at 6:44
  • $\begingroup$ Weird that it misses the pages. Hmmm. $\endgroup$ – Maarten Bodewes Sep 7 '18 at 6:45
0
$\begingroup$

You can try this - https://github.com/tyage/sha0/blob/master/lib/sha0.rb I don't know how good or accurate it is.

$\endgroup$
  • $\begingroup$ I had come across this in my search. But was looking for more like an RFC / pseudocode from the original specification. $\endgroup$ – Lord Loh. Sep 5 '18 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.