[144268] in cryptography@c2.net mail archive
SHA-3 Round 1: Buffer Overflows
daemon@ATHENA.MIT.EDU (R.A. Hettinga)
Mon Feb 23 11:26:04 2009
From: "R.A. Hettinga" <rah@shipwright.com>
To: Cryptography <cryptography@metzdowd.com>,
cypherpunks@al-qaeda.net,
gold-silver-crypto@rayservers.com
Date: Sun, 22 Feb 2009 17:09:30 -0500
<http://blog.fortify.com/blog/fortify/2009/02/20/SHA-3-Round-1>
Off by On
A Software Security Blog
Search:
Friday, 20 February 2009
SHA-3 Round 1: Buffer Overflows
=AB Gartner Magic Quadrant for Static Analysis | Main
NIST is currently holding a competition to choose a design for the =20
SHA-3 algorithm (Bruce Schneier has a good description of secure =20
hashing algorithms and why this is important). The reference =20
implementations of a few of the contestants have bugs in them that =20
could cause crashes, performance problems, or security problems if =20
they are used in their current state. Based on our bug reports, some =20
of those bugs have already been fixed. Here's the full story:
The main idea behind the competition is to have the cryptographic =20
community weed out the less secure algorithms and choose from the =20
remainder. A couple of us at Fortify (thanks to Doug Held for his =20
help) decided to do our part. We're not hard-core cryptographers, so =20
we decided to take a look at the reference implementations.
This competition is to pick an algorithm, but all of the submissions =20
had to include a C implementation, to demonstrate how it works and =20
test the speed, which will be a factor in the final choice. We used =20
Fortify SCA to audit the 42 projects accepted into Round 1. We were =20
impressed with the overall quality of the code, but we did find =20
significant issues in a few projects, including buffer overflows in =20
two of the projects. We have emailed the submission teams with our =20
findings and one team has already corrected their implementation.
Confirmed issues:
Implementation
Buffer Overflow
Out-of-bounds Read
Memory Leak
Null Dereference
Blender
1
0
0
0
Crunch
0
0
0
4
FSB
0
0
3
11
MD6
3
2
0
0
Vortex
0
0
1
15
One of the projects with buffer issues was MD6, the implementation =20
provided Professor Ron Rivest and his team. All of the problems came =20
back to the hashval field of the md6_state struct:
unsigned char hashval[ (md6_c/2)*(md6_w/8) ];
The buffer size is determined by two constants:
#define w md6_w /* # bits in a word (64) */
#define c md6_c /* # words in compression output (16) */
At several points, this buffer is read or written to using a different =20=
bound:
if (z=3D=3D1) /* save final chaining value in st->hashval */
{ memcpy( st->hashval, C, md6_c*(w/8) );
return MD6_SUCCESS;
}
Further analysis showed that ANSI standard layout rules would make =20
incorrect behavior unlikely, but other compilers may have allowed it =20
to be exploited. The MD6 team has doubled the size of the vulnerable =20
buffer, which eliminated the risk. In this case, Fortify SCA found an =20=
issue that would have been difficult to catch otherwise.
The other buffer overflow was found in the Blender implementation, =20
from Dr. Colin Bradbury. This issue was a classic typo:
DataLength sourceDataLength2[3]; // high order parts of data =20
length
...
if (ss.sourceDataLength < (bcount | databitlen)) // overflow
if (++ss.sourceDataLength2[0] =3D=3D 0) // increment higher =20=
order count
if (++ss.sourceDataLength2[1] =3D=3D 0) // and the next =20=
higher order
++ss.sourceDataLength2[3]; // and the next one, =20
etc.
The developer simply mistyped, using 3 instead of 2 for the array =20
access. This issue was probably not caught because it would not be =20
exposed without a very large input. The other issues we found were =20
memory leaks and null dereferences from memory allocation.
This just emphasizes what we already knew about C, even the most =20
careful, security conscious developer messes up memory management. =20
Some of you are saying, so what? These are reference implementations =20
and this is only Round 1. There are a few problems with that thought.
Reference implementations don't disappear, they serve as a starting =20
point for future implementations or are used directly. A bug in the =20
RSA reference implementation was responsible for vulnerabilities in =20
OpenSSL and two seperate SSH implementations. They can also be used to =20=
design hardware implementations, using buffer sizes to decide how much =20=
silicon should be used.
The other consideration is speed, which will be a factor in the choice =20=
of algorithm. The fix for the MD6 buffer issues was to double the size =20=
of a buffer, which could degrade the performance. On the other hand, =20
memory leaks could slow an implementation. A correct implementation is =20=
an accurate implementation.
We will put out a more detailed report on all the results soon.
Technorati Tags: sha-3 buffer overflow
Posted by jforsythe at 5:41 PM in crypto
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
