Aww, p*sh! [Sgàil: trivial collision in original submission]

Sgàil, my submission to NIST’s SHA-3 competition, unfortunately has an error in it which makes finding a collision or second pre-image trivial.  The error crept in when I’d decided to change the key schedule late on from being a tree structure to a simple double block processing.

The measure which had originally protected the tree structure from block interchanges – the preliminary key – was unique for each 2048-bit block.  Unfortunately when redesigning the algorithm, I’d neglected to process a preliminary key for each 2048-bit block and instead processed a single preliminary key for each 4096-bit block.  The process where the 4096-bit block is reduced to the 2048-bit principle key uses the same preliminary key for both 2048-bit halves of the 4096-bit block, where they should have been different.  Hence the 2048-bit input pair is interchangable.

The resolution is to process a preliminary key for each 2048-bit input block and update the block counter at each 2048-bit input block rather than at each 4096-bit block.  The performance wouldn’t be significantly altered.  However since the submission deadline has now lapsed, I doubt any modifications will be accepted.

The following code generates a collision:

——-

int main() {

u8 data__a[ SGAIL__INPUT_BLOCK__SIZE * 2 ];
u8 data__b[ SGAIL__INPUT_BLOCK__SIZE * 2 ];
u8 result__a[ 64 ];
u8 result__b[ 64 ];

memset( data__a, 0, SGAIL__INPUT_BLOCK__SIZE * 2 );
memset( data__b, 0, SGAIL__INPUT_BLOCK__SIZE * 2 );

data__a[ 0 ] = 1;
data__a[ 256 ] = 2;

data__b[ 0 ] = 2;
data__b[ 256 ] = 1;

Hash( 512, data__a, ( SGAIL__INPUT_BLOCK__SIZE * 2 ) * 8, result__a );
Hash( 512, data__b, ( SGAIL__INPUT_BLOCK__SIZE * 2 ) * 8, result__b );

do__display_512_bit_hash__byte_wise( result__a );
do__display_512_bit_hash__byte_wise( result__b );

}
——–

I will post a revision of Sgàil in the next few days with the error fixed, although I don’t know of its applicability as concerns the SHA-3 competition.

UPDATED 21st November 2008: Ok, maybe a bit more than a few days, keep getting side-tracked. Will upload new revision once have fixed the specification document.

UPDATED 21st January 2009: Version 0.4 has been released here which corrects this error…. enjoy ;-)

UPDATED 12th April 2010: Added [] extra meaning in title.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>