======================================== BUG REPORT: by [EMAIL PROTECTED] ----------------------------------------
I found that ssh-1 function in the openssl-0.9.6[ac] distribution may not be correct. It may produce incorrect result for certain input example data, which is found at the NIST web site. (see the references below). The testing done by the installed test program withi OpenSSL is insufficient. ======================================== BACKGROUND: ---------------------------------------- The openssl-0.9.6[ac]/crypto/sha/ directory contains SHA-1 implementation and there is a simple test program called sha1test.c under the directory. The program tests the generation of sha-1 hash sums for 3 (three) input test data listed in FIPS-180 document [1]. I found by executing the code that three output data match the expected values in FIPS-180. During make test, the three tests passes OK. ./sha1test test 1 ok test 2 ok test 3 ok *HOWEVER*, SHA-1 is a rather tricky algorithm and the implementation may contain subtle errors which are not uncovered by testing against only three input data examples ([2], [4]). I hope many seasoned programmers agree with this observation. Indeed, I suspect that NIST was alarmed at the buggy implementations that were sent to their formal validation testing. NIST is now offering a collection of additional test input exampls, and the expected sha-1 hash sum values for these input data (see [3]). There are about 200+ samples in the NIST file. When I learned the existence of larger collection of sha-1 example input test vectors and the expected values, I became interested in testing the correctlness of ssh-1 implementations available in source code formats. ======================================== HOW I FOUND THE PROBLEM using NIST SHA1 Sample Vector File. ---------------------------------------- I downloaded the NIST SHA1 Sample vector files, and read about the elaborate bit string representation method used in the data files. The data files are small, but once the bit strings are expanded, we will test about 5-6MB of input data. After reading Readme.txt and figuring out the decoding method, I tested two SHA-1 implementations using the available input vectors. The two tested implementations are - one from OpenSSL sha-1 in crypto/sha, and - the other done by Steve Reid. For the latter, see for example, ftp://ftp.funet.fi/pub/crypt/hash/sha/sha1.c These two certainly produce expected results for the three (3) example values mentioned in FIPS-180-1 document. So far, so good. I ran the two implementations against the input vectors in the NIST Sample Vector files. I only tested the partial input vectors (TYPE-1, and TYPE-2 in NIST Sample Vector sample files). Using this limited input data, I found discrepancy between the output from the OpenSL's SHA-1 and the expected value in the example files. Steve Reid implementation produced expected results for all the input test cases I examined. There were 229 input tests (excluding Type-3 test). OpenSSL sha-1 produced incorrect results in 101 cases. Reid sha-1 produced correct results for all cases. It seems to me that the openssh sha-1 code produces correct results for shorter messages. (The first error was observed for 1024 bits data.) So my suspicion is that the code mishandles the elaborate padding handling specified for SHA-1 algorithm, but I am not sure. There are other possible causes. (I am using gcc 2.95.4 under linux. gcc -v output: Reading specs from /usr/lib/gcc-lib/i386-linux/2.95.4/specs gcc version 2.95.4 20011006 (Debian prerelease)). In any case, my tentative conclusion is SHA-1 implementation in OpenSSL may be broken. ======================================== TESTING psedo code: ---------------------------------------- step 1. Read the compact representation of NIST input vector. step 2. expand the input into a real binary array into a dynamically allocated array pointed at by lp. step.3 - produce sha-1 hash sum using Reid sha-1. This is done by calling reid_sha_memory(lp, len / 8, reid_digest); (reid_sha_memory code is attached in the end.*/ - produce sha-1 hash sum using OpenSSL sha-1 This is done by simpling calling SHA1(lp, len/8 , digest); Note that the second argument is byte length (not the bit length). step.4 compare the digest produced by the two implementations as well as the expected value offered by NIST. Repeat the above steps for NIST sampel data files. (Except for the TYPE-3 input data. I found handling type-3 more work to do, and just decided to report the current finding so far.) ======================================== WHY I AM SENDING THIS OUT: ---------------------------------------- I am sending this to alert the OpenSSL developers, and to a wider audience, who may be into secure hash research, to invite feedback about my observation. I am not 100% sure if my testing is correct. Other people may want to validate my bug report by independent testing. But given that - Reid implementation matches the NIST expected values for all the 229 cases which I tested, and - OpenSSL sha-1 produces correct results for about half the cases, I think this means that my testing setup itself is more or less correct :-) and the code of sha-1 in OpenSSL is indeed buggy. (Since the certificate [and/or other application data that uses sha-1] may not be that large to trigger the bugs of sha-1, this problem may have been overlooked for a long time by openssl developers.) ======================================== REFERENCES ---------------------------------------- [1] FIPS 180-1 web page where the algorithm is discussed. http://www.itl.nist.gov/fipspubs/fip180-1.htm [2] Comment by John Halleck, whose SHA-1 implemenation in Ada has passed NIST Validation testing. http://www.cc.utah.edu/~nahaj/ada/sha/ [3] For a large set of sha-1 test vector/value pairs, see the following URL. http://csrc.ncsl.nist.gov/cryptval/ Follow the FIPS-180 link there, and you will arrive at Secure Hash Standard (SHS) http://csrc.ncsl.nist.gov/cryptval/shs.html There you have "SHA-1 Sample Vectors". NIST says, "This file describes tests and vectors that can be used to informally verify the correctness of an SHA-1 implementation. However, use of these vectors does not take the place of validation obtained through the Cryptographic Module Validation Program." So you must make sure your implementation produce correct result based on the Sample Vectors, AND you need to go through the Validation process at NIST to obtain the formal validatation. [4] Validation List There is a list of validated sha-1 implementations. http://csrc.ncsl.nist.gov/cryptval/shs/shaval.htm John Halleck's ADA implementation is listed as entry No. 39 in the SHA1 validation list available at: ======================================== Appendix. ---------------------------------------- Below I quote a few Incorrect Output examples. Sorry, the long one line output needed to be folded manually and so may be hard to read (or my cut/paste error may have crept in.) (1) INPUT len= 1024 bit of binary data 111111111111111111111111000000000000000000000011110000000000000 000000000000000011111111111111111111110000000000000000000000000 000000111111111111111111111111111100000000000000000000111100000 000000000001111111111111111111110001000000000000000111110000000 000000001111110000000000000000000000000000001110000000000000000 000000000000011111111111111111111111111111000000011111111111111 111111111111100000000000000000000110000000000000000000011111111 111111111111111111111110000000000000000000000111111111111111111 111111110000000001111111111111111111111111111100000000000000001 111000000000000000000000000001111111111111111111111111111111100 000000000000000111111111111111111110000000000000011111111111111 111111111111110000000000000000011111111111111111110000001111111 111111111111111110000000000011111111111111111111111111000000000 000000000000000000011111000000000000000000111111111111111000000 001111111111111111000000000000000000001111111111111111111110000 111111111000000000000111100000000111111111111111110000000000000 0000000000000000 Input(hex) 0xff 0xff 0xff 0x00 0x00 0x03 0xc0 0x00 0x00 0x01 0xff 0xff 0xf8 0x00 0x00 0x00 0x0f 0xff 0xff 0xff 0x00 0x00 0x0f 0x00 0x00 0xff 0xff 0xf8 0x80 0x00 0xf8 0x00 0x0f 0xc0 0x00 0x00 0x00 0xe0 0x00 0x00 0x00 0xff 0xff 0xff 0xf8 0x0f 0xff 0xff 0xfe 0x00 0x00 0x18 0x00 0x00 0x7f 0xff 0xff 0xff 0x00 0x00 0x03 0xff 0xff 0xff 0x00 0x7f 0xff 0xff 0xfc 0x00 0x03 0xc0 0x00 0x00 0x0f 0xff 0xff 0xff 0xf0 0x00 0x07 0xff 0xff 0x80 0x01 0xff 0xff 0xff 0xe0 0x00 0x0f 0xff 0xfe 0x07 0xff 0xff 0xf8 0x00 0xff 0xff 0xff 0xc0 0x00 0x00 0x03 0xe0 0x00 0x07 0xff 0xf0 0x0f 0xff 0xf0 0x00 0x00 0xff 0xff 0xf8 0x7f 0xc0 0x03 0xc0 0x3f 0xff 0xe0 0x00 0x00 0x00 REID: EDE4DEB4 293CFE41 38C2C056 B7C46FF8 21CC0ACC <-- correct before SHA1 len=1024 SSL : 49EBEB2D 150900BF 214FC844 35A2FB56 4FC7B35F <-- incorrect ANSWER: EDE4DEB4293CFE4138C2C056B7C46FF821CC0ACC <-- NIST expected value ***** reid and SSL sha1 differed. ****: len=1024 (2) INPUT len= 1032 bits 111110001111111111100000000000000011111111111100000000000000000 000000011111111111111111111111111111110000000000000000000000010 000001111111111111111111111111111001111111100000000000000000000 000000000001111110000000111111111111111111111111111111000001111 111111111111111000000000000000000000001111111111110000001111111 110000000000000000000000000000000111111111111111111100000000000 000000111111111111111111111111000000000000000000000000011111111 111111111111110000001111111111110000000000000000111000000011111 111100000000011111111111000000000000000000000000000001111000000 000001100000111111111111100000000000000000000000000000111111111 100000000000011111111111111111111111111111100000000000000000000 000000000000111111111111111111000000000000000000000000000011111 111111111111100000000000000000000000000011100000000000000000000 000000000011110000111111111111111111111111110000001111111111111 000000000000000000000000000000011111111111110011111111111000000 011111111111111111111111100001111111111111111100000000000000000 000000000000111111111111 Input(hex) 0xf8 0xff 0xe0 0x00 0x3f 0xfc 0x00 0x00 0x03 0xff 0xff 0xff 0xf8 0x00 0x00 0x08 0x1f 0xff 0xff 0xfe 0x7f 0x80 0x00 0x00 0x00 0xfc 0x07 0xff 0xff 0xff 0xe0 0xff 0xff 0xe0 0x00 0x00 0x3f 0xfc 0x0f 0xf8 0x00 0x00 0x00 0x0f 0xff 0xfe 0x00 0x00 0xff 0xff 0xff 0x00 0x00 0x00 0x7f 0xff 0xfe 0x07 0xff 0x80 0x00 0x70 0x1f 0xf0 0x07 0xff 0x00 0x00 0x00 0x07 0x80 0x0c 0x1f 0xff 0x00 0x00 0x00 0x07 0xfe 0x00 0x1f 0xff 0xff 0xff 0x80 0x00 0x00 0x00 0x7f 0xff 0xe0 0x00 0x00 0x01 0xff 0xff 0x80 0x00 0x00 0x0e 0x00 0x00 0x00 0x07 0x87 0xff 0xff 0xfe 0x07 0xff 0xc0 0x00 0x00 0x00 0x7f 0xfc 0xff 0xe0 0x3f 0xff 0xff 0xc3 0xff 0xfe 0x00 0x00 0x00 0x0f 0xff REID: A771FA5C 812BD0C9 596D869E C99E4F4A C988B13F before SHA1 len=1032 SSL : ECBEC8ED F7B6035E 6241F4D3 0ABBAFA9 E30BD856 ANSWER: A771FA5C812BD0C9596D869EC99E4F4AC988B13F (3) INPUT len= 2056 0000000000000000000001111111111111111111000000000000000000000111 1111111111111111111100000000000111111111111111111111111111111111 1111111110000000000000000000000000000000000001100000000000001111 0111111111111111111111111111111111000000000000000000000011111111 1111111100000000000000000000000000011111111100001111111111111111 1111111111111111100000000000000001110000000000000000000000000000 0011111111111111100000000000111111111111111111111111111111110000 0000000001111111111111111100000000000000000000000000000000000000 1111111111111111111111111111111100000000011111111111111111111111 1111111111111110000111111111111111111111111111111111111000000000 0000001111111111111111111111111111111100000000000000000000000000 0111111111111111111100000000000000000000000000000000000000000011 1111111111111111000000111111111111111111111111111111111111000000 0000000000000000111111111100000000000000000000000000000111111111 1110000000000000000000000000111111111111111111111111111111111111 1111000000000000000111111111111111111111111111110000000000000000 0000000111111111111111111111111111100000000000000000000000000000 0111100000000111111111110000000000000000000000001111111110000000 0001111111111111111111111111111111000000000000000000000000000011 1111111111111111111111111111111111111111100000000000000000000000 1111111111111111000000000000000000000000000001111111111111111111 1111111111111100000111111111111111111111111111111111111111100000 0000000000000000000001110000000000000000000111111111111000000000 0000000000000000000000000001111111111111111111111111111111111111 1111110000011111111111111111111111111111111111000000000000000000 0000000000000000000111110000000000000011111111111000000000000000 0000000000000000000000000000001111111111111111111111111111111111 1000000000000000011111111110000000011111111111111111111111111111 1110000111111111111111000000000000000000000000000000000001111111 1111111111111111111001111111111111111111111111111111111111110000 0000000000000000001111111111111111111111111111111111111000000000 0000000000000111111111111111111111111111111000000000000000000000 00000000 Input(hex) 0x00 0x00 0x07 0xff 0xff 0x00 0x00 0x07 0xff 0xff 0xf0 0x01 0xff 0xff 0xff 0xff 0xff 0x80 0x00 0x00 0x00 0x06 0x00 0x0f 0x7f 0xff 0xff 0xff 0xc0 0x00 0x00 0xff 0xff 0x00 0x00 0x00 0x1f 0xf0 0xff 0xff 0xff 0xff 0x80 0x00 0x70 0x00 0x00 0x00 0x3f 0xff 0x80 0x0f 0xff 0xff 0xff 0xf0 0x00 0x7f 0xff 0xc0 0x00 0x00 0x00 0x00 0xff 0xff 0xff 0xff 0x00 0x7f 0xff 0xff 0xff 0xfe 0x1f 0xff 0xff 0xff 0xfe 0x00 0x03 0xff 0xff 0xff 0xfc 0x00 0x00 0x00 0x7f 0xff 0xf0 0x00 0x00 0x00 0x00 0x03 0xff 0xff 0x03 0xff 0xff 0xff 0xff 0xc0 0x00 0x00 0xff 0xc0 0x00 0x00 0x01 0xff 0xe0 0x00 0x00 0x0f 0xff 0xff 0xff 0xff 0xf0 0x00 0x1f 0xff 0xff 0xff 0x00 0x00 0x01 0xff 0xff 0xff 0xe0 0x00 0x00 0x00 0x78 0x07 0xff 0x00 0x00 0x00 0xff 0x80 0x1f 0xff 0xff 0xff 0xc0 0x00 0x00 0x03 0xff 0xff 0xff 0xff 0xff 0x80 0x00 0x00 0xff 0xff 0x00 0x00 0x00 0x07 0xff 0xff 0xff 0xfc 0x1f 0xff 0xff 0xff 0xff 0xe0 0x00 0x00 0x07 0x00 0x00 0x1f 0xfe 0x00 0x00 0x00 0x00 0x1f 0xff 0xff 0xff 0xff 0xfc 0x1f 0xff 0xff 0xff 0xfc 0x00 0x00 0x00 0x00 0x1f 0x00 0x03 0xff 0x80 0x00 0x00 0x00 0x00 0x03 0xff 0xff 0xff 0xff 0x80 0x00 0x7f 0xe0 0x1f 0xff 0xff 0xff 0xe1 0xff 0xfc 0x00 0x00 0x00 0x00 0x7f 0xff 0xff 0xe7 0xff 0xff 0xff 0xff 0xf0 0x00 0x00 0x3f 0xff 0xff 0xff 0xfe 0x00 0x00 0x07 0xff 0xff 0xff 0xe0 0x00 0x00 0x00 REID: E99D5662 12BBBCEE E903946F 6100C9C9 6039A8F4 SSL : 6C0479E2 7B8E6610 9311208F 42253767 4150CEBA ANSWER: E99D566212BBBCEEE903946F6100C9C96039A8F4 ***** reid and SSL sha1 differed. ****: len=2056 cf. The length of input data (in bits) when the miismatch occurred. ***** reid and SSL sha1 differed. ****: len=1024 ***** reid and SSL sha1 differed. ****: len=1032 ***** reid and SSL sha1 differed. ****: len=2056 ***** reid and SSL sha1 differed. ****: len=3080 ***** reid and SSL sha1 differed. ****: len=4104 ***** reid and SSL sha1 differed. ****: len=5128 ***** reid and SSL sha1 differed. ****: len=6152 ***** reid and SSL sha1 differed. ****: len=7176 ***** reid and SSL sha1 differed. ****: len=8200 ***** reid and SSL sha1 differed. ****: len=9224 ***** reid and SSL sha1 differed. ****: len=10248 ***** reid and SSL sha1 differed. ****: len=11272 ***** reid and SSL sha1 differed. ****: len=12296 ***** reid and SSL sha1 differed. ****: len=13320 ***** reid and SSL sha1 differed. ****: len=14344 ***** reid and SSL sha1 differed. ****: len=15368 ***** reid and SSL sha1 differed. ****: len=16392 ***** reid and SSL sha1 differed. ****: len=17416 ***** reid and SSL sha1 differed. ****: len=18440 ***** reid and SSL sha1 differed. ****: len=19464 ***** reid and SSL sha1 differed. ****: len=20488 ***** reid and SSL sha1 differed. ****: len=21512 ***** reid and SSL sha1 differed. ****: len=22536 ***** reid and SSL sha1 differed. ****: len=23560 ***** reid and SSL sha1 differed. ****: len=24584 ***** reid and SSL sha1 differed. ****: len=25608 ***** reid and SSL sha1 differed. ****: len=26632 ***** reid and SSL sha1 differed. ****: len=27656 ***** reid and SSL sha1 differed. ****: len=28680 ***** reid and SSL sha1 differed. ****: len=29704 ***** reid and SSL sha1 differed. ****: len=30728 ***** reid and SSL sha1 differed. ****: len=31752 ***** reid and SSL sha1 differed. ****: len=32776 ***** reid and SSL sha1 differed. ****: len=33800 ***** reid and SSL sha1 differed. ****: len=34824 ***** reid and SSL sha1 differed. ****: len=35848 ***** reid and SSL sha1 differed. ****: len=36872 ***** reid and SSL sha1 differed. ****: len=37896 ***** reid and SSL sha1 differed. ****: len=38920 ***** reid and SSL sha1 differed. ****: len=39944 ***** reid and SSL sha1 differed. ****: len=40968 ***** reid and SSL sha1 differed. ****: len=41992 ***** reid and SSL sha1 differed. ****: len=43016 ***** reid and SSL sha1 differed. ****: len=44040 ***** reid and SSL sha1 differed. ****: len=45064 ***** reid and SSL sha1 differed. ****: len=46088 ***** reid and SSL sha1 differed. ****: len=47112 ***** reid and SSL sha1 differed. ****: len=48136 ***** reid and SSL sha1 differed. ****: len=49160 ***** reid and SSL sha1 differed. ****: len=50184 ***** reid and SSL sha1 differed. ****: len=51208 ***** reid and SSL sha1 differed. ****: len=52232 ***** reid and SSL sha1 differed. ****: len=53256 ***** reid and SSL sha1 differed. ****: len=54280 ***** reid and SSL sha1 differed. ****: len=55304 ***** reid and SSL sha1 differed. ****: len=56328 ***** reid and SSL sha1 differed. ****: len=57352 ***** reid and SSL sha1 differed. ****: len=58376 ***** reid and SSL sha1 differed. ****: len=59400 ***** reid and SSL sha1 differed. ****: len=60424 ***** reid and SSL sha1 differed. ****: len=61448 ***** reid and SSL sha1 differed. ****: len=62472 ***** reid and SSL sha1 differed. ****: len=63496 ***** reid and SSL sha1 differed. ****: len=64520 ***** reid and SSL sha1 differed. ****: len=65544 ***** reid and SSL sha1 differed. ****: len=66568 ***** reid and SSL sha1 differed. ****: len=67592 ***** reid and SSL sha1 differed. ****: len=68616 ***** reid and SSL sha1 differed. ****: len=69640 ***** reid and SSL sha1 differed. ****: len=70664 ***** reid and SSL sha1 differed. ****: len=71688 ***** reid and SSL sha1 differed. ****: len=72712 ***** reid and SSL sha1 differed. ****: len=73736 ***** reid and SSL sha1 differed. ****: len=74760 ***** reid and SSL sha1 differed. ****: len=75784 ***** reid and SSL sha1 differed. ****: len=76808 ***** reid and SSL sha1 differed. ****: len=77832 ***** reid and SSL sha1 differed. ****: len=78856 ***** reid and SSL sha1 differed. ****: len=79880 ***** reid and SSL sha1 differed. ****: len=80904 ***** reid and SSL sha1 differed. ****: len=81928 ***** reid and SSL sha1 differed. ****: len=82952 ***** reid and SSL sha1 differed. ****: len=83976 ***** reid and SSL sha1 differed. ****: len=85000 ***** reid and SSL sha1 differed. ****: len=86024 ***** reid and SSL sha1 differed. ****: len=87048 ***** reid and SSL sha1 differed. ****: len=88072 ***** reid and SSL sha1 differed. ****: len=89096 ***** reid and SSL sha1 differed. ****: len=90120 ***** reid and SSL sha1 differed. ****: len=91144 ***** reid and SSL sha1 differed. ****: len=92168 ***** reid and SSL sha1 differed. ****: len=93192 ***** reid and SSL sha1 differed. ****: len=94216 ***** reid and SSL sha1 differed. ****: len=95240 ***** reid and SSL sha1 differed. ****: len=96264 ***** reid and SSL sha1 differed. ****: len=97288 ***** reid and SSL sha1 differed. ****: len=98312 ***** reid and SSL sha1 differed. ****: len=99336 ***** reid and SSL sha1 differed. ****: len=100360 ***** reid and SSL sha1 differed. ****: len=101384 ***** reid and SSL sha1 differed. ****: len=102408 cf. reid_sha_memory (unsigned char *buf, /* input */ int len, /* length in byte */ unsigned char digest[20] /* output digest[20]; */ ) { SHA1_CTX context; /* state */ SHA1Init (&context); /* init�� */ while (len > 0) { if (len < 16384) { SHA1Update (&context, buf, len); len = 0; } else { SHA1Update (&context, buf, 16384); buf += 16384; len -= 16384; } } SHA1Final (digest, &context); } [end of memo] ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
