Allicient

Well, its finally been done – Sgàil has been updated to fix the error described in this post which allowed second pre-image and collision attacks. An error in the reference implementation has been remedied, and a number of typographical corrections have been made to the specification. The known answer tests and intermediate value results have also been regenerated.

Although version 0.4 is considered to be immune to the previous design error and was submitted to NIST, it has not yet been approved/rejected as an official change. Updates will be posted as they happen.

Changelogs have been included in the Supporting_Documentation directory.

The performance of the reference implementation has dropped from 62 cycles/byte to 71 cycles/byte in asymptopic behaviour due to the corrections made to the key schedule. It is expected that an optimised version can improve this to at least 40 cycles/byte; I’m looking at coding this in the near future.

UPDATED 11th December 2009: I really should have updated this about six months ago; the corrections were not accepted by NIST and Sgàil did not progress to Round 2.

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.