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 20091211: 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 21/11/08: Ok, maybe a bit more than a few days, keep getting side-tracked. Will upload new revision once have fixed the specification document.

UPDATED 21/01/09: Version 0.4 has been released here which corrects this error…. enjoy

NIST hasn’t even published the complete and proper candidates, but there’s already a full break (second pre-image) of one of the candidate hash algorithms in the SHA-3 competition, pretty exciting, huh?  The “WaMM” hash algorithm is the first to fall, see here for more info.  There’s also been an attack on another of the submissions, EnRUPT.  A list of some (I say some, there’s quite a lot on the list) of the candidates can be found at the SHA-3 zoo.

In this type of process, such a complete break so early on is certainly a good indicator that the process is working as intended – and getting good involvement.  It also serves as a stark warning to those who would use a home-grown crypto scheme in a commercial product without full peer-review of their algorithm, the consequences of which are no less apparent than the failure of the ubiqutous Mifare classic, used for example in the Oyster card in London.