diff --git a/clib/sha1.h b/clib/sha1.h --- a/clib/sha1.h +++ b/clib/sha1.h @@ -25,7 +25,7 @@ static inline int fbhg_sha1_update(fbhg_sha1_ctx_t* ctx, const void* data, unsigned long length) { - SHA1DCUpdate(ctx, (const unsigned char*)data, length); + SHA1DCUpdate(ctx, (const char*)data, length); return 0; } diff --git a/third-party/sha1dc/README.md b/third-party/sha1dc/README.md new file mode 100644 --- /dev/null +++ b/third-party/sha1dc/README.md @@ -0,0 +1,79 @@ +# sha1collisiondetection +Library and command line tool to detect SHA-1 collisions in files + +Copyright 2017 Marc Stevens + +Distributed under the MIT Software License. + +See accompanying file LICENSE.txt or copy at https://opensource.org/licenses/MIT. + +## Developers + +- Marc Stevens, CWI Amsterdam (https://marc-stevens.nl) +- Dan Shumow, Microsoft Research (https://www.microsoft.com/en-us/research/people/danshu/) + +## About +This library and command line tool were designed as near drop-in replacements for common SHA-1 libraries and sha1sum. +They will compute the SHA-1 hash of any given file and additionally will detect cryptanalytic collision attacks against SHA-1 present in each file. It is very fast and takes less than twice the amount of time as regular SHA-1. + +More specifically they will detect any cryptanalytic collision attack against SHA-1 using any of the top 32 SHA-1 disturbance vectors with probability 1: +``` + I(43,0), I(44,0), I(45,0), I(46,0), I(47,0), I(48,0), I(49,0), I(50,0), I(51,0), I(52,0), + I(46,2), I(47,2), I(48,2), I(49,2), I(50,2), I(51,2), + II(45,0), II(46,0), II(47,0), II(48,0), II(49,0), II(50,0), II(51,0), II(52,0), II(53,0), II(54,0), II(55,0), II(56,0), + II(46,2), II(49,2), II(50,2), II(51,2) +``` +The possibility of false positives can be neglected as the probability is smaller than 2^-90. + +The library supports both an indicator flag that applications can check and act on, as well as a special _safe-hash_ mode that returns the real SHA-1 hash when no collision was detected and a different _safe_ hash when a collision was detected. +Colliding files will have the same SHA-1 hash, but will have different unpredictable safe-hashes. +This essentially enables protection of applications against SHA-1 collisions with no further changes in the application, e.g., digital signature forgeries based on SHA-1 collisions automatically become invalid. + +For the theoretical explanation of collision detection see the award-winning paper on _Counter-Cryptanalysis_: + +Counter-cryptanalysis, Marc Stevens, CRYPTO 2013, Lecture Notes in Computer Science, vol. 8042, Springer, 2013, pp. 129-146, +https://marc-stevens.nl/research/papers/C13-S.pdf + +## Compiling + +Run: +``` +make +``` + +## Command-line usage + +There are two programs `bin/sha1dcsum` and `bin/sha1dcsum_partialcoll`. +The first program `bin/sha1dcsum` will detect and warn for files that were generated with a cryptanalytic SHA-1 collision attack like the one documented at https://shattered.io/. +The second program `bin/sha1dcsum_partialcoll` will detect and warn for files that were generated with a cryptanalytic collision attack against reduced-round SHA-1 (of which there are a few examples so far). + +Examples: +``` +bin/sha1dcsum test/sha1_reducedsha_coll.bin test/shattered-1.pdf +bin/sha1dcsum_partialcoll test/sha1reducedsha_coll.bin test/shattered-1.pdf +``` + +## Library usage + +See the documentation in `lib/sha1.h`. Here is a simple example code snippet: +``` +#include + +SHA1_CTX ctx; +unsigned char hash[20]; +SHA1DCInit(&ctx); + +/** disable safe-hash mode (safe-hash mode is enabled by default) **/ +// SHA1DCSetSafeHash(&ctx, 0); +/** disable use of unavoidable attack conditions to speed up detection (enabled by default) **/ +// SHA1DCSetUseUBC(&ctx, 0); + +SHA1DCUpdate(&ctx, buffer, (unsigned)(size)); + +int iscoll = SHA1DCFinal(hash,&ctx); +if (iscoll) + printf("collision detected"); +else + printf("no collision detected"); +``` + diff --git a/third-party/sha1dc/sha1.h b/third-party/sha1dc/sha1.h --- a/third-party/sha1dc/sha1.h +++ b/third-party/sha1dc/sha1.h @@ -12,29 +12,38 @@ extern "C" { #endif -#include // size_t #include -/* sha-1 compression function that takes an already expanded message, and additionally store intermediate states */ +/* uses SHA-1 message expansion to expand the first 16 words of W[] to 80 words */ +/* void sha1_message_expansion(uint32_t W[80]); */ + +/* sha-1 compression function; first version takes a message block pre-parsed as 16 32-bit integers, second version takes an already expanded message) */ +/* void sha1_compression(uint32_t ihv[5], const uint32_t m[16]); +void sha1_compression_W(uint32_t ihv[5], const uint32_t W[80]); */ + +/* same as sha1_compression_W, but additionally store intermediate states */ /* only stores states ii (the state between step ii-1 and step ii) when DOSTORESTATEii is defined in ubc_check.h */ void sha1_compression_states(uint32_t[5], const uint32_t[16], uint32_t[80], uint32_t[80][5]); /* -// Function type for sha1_recompression_step_T (uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5]). -// Where 0 <= T < 80 -// me2 is an expanded message (the expansion of an original message block XOR'ed with a disturbance vector's message block difference.) -// state is the internal state (a,b,c,d,e) before step T of the SHA-1 compression function while processing the original message block. -// The function will return: -// ihvin: The reconstructed input chaining value. -// ihvout: The reconstructed output chaining value. +// function type for sha1_recompression_step_T (uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5]) +// where 0 <= T < 80 +// me2 is an expanded message (the expansion of an original message block XOR'ed with a disturbance vector's message block difference) +// state is the internal state (a,b,c,d,e) before step T of the SHA-1 compression function while processing the original message block +// the function will return: +// ihvin: the reconstructed input chaining value +// ihvout: the reconstructed output chaining value */ typedef void(*sha1_recompression_type)(uint32_t*, uint32_t*, const uint32_t*, const uint32_t*); -/* A callback function type that can be set to be called when a collision block has been found: */ +/* table of sha1_recompression_step_0, ... , sha1_recompression_step_79 */ +/* extern sha1_recompression_type sha1_recompression_step[80];*/ + +/* a callback function type that can be set to be called when a collision block has been found: */ /* void collision_block_callback(uint64_t byteoffset, const uint32_t ihvin1[5], const uint32_t ihvin2[5], const uint32_t m1[80], const uint32_t m2[80]) */ typedef void(*collision_block_callback)(uint64_t, const uint32_t*, const uint32_t*, const uint32_t*, const uint32_t*); -/* The SHA-1 context. */ +/* the SHA-1 context */ typedef struct { uint64_t total; uint32_t ihv[5]; @@ -53,34 +62,30 @@ uint32_t states[80][5]; } SHA1_CTX; -/* Initialize SHA-1 context. */ +/* initialize SHA-1 context */ void SHA1DCInit(SHA1_CTX*); /* - Function to enable safe SHA-1 hashing: - Collision attacks are thwarted by hashing a detected near-collision block 3 times. - Think of it as extending SHA-1 from 80-steps to 240-steps for such blocks: - The best collision attacks against SHA-1 have complexity about 2^60, - thus for 240-steps an immediate lower-bound for the best cryptanalytic attacks would be 2^180. - An attacker would be better off using a generic birthday search of complexity 2^80. - - Enabling safe SHA-1 hashing will result in the correct SHA-1 hash for messages where no collision attack was detected, - but it will result in a different SHA-1 hash for messages where a collision attack was detected. - This will automatically invalidate SHA-1 based digital signature forgeries. - Enabled by default. +// function to enable safe SHA-1 hashing: +// collision attacks are thwarted by hashing a detected near-collision block 3 times +// think of it as extending SHA-1 from 80-steps to 240-steps for such blocks: +// the best collision attacks against SHA-1 have complexity about 2^60, +// thus for 240-steps an immediate lower-bound for the best cryptanalytic attacks would 2^180 +// an attacker would be better off using a generic birthday search of complexity 2^80 +// +// enabling safe SHA-1 hashing will result in the correct SHA-1 hash for messages where no collision attack was detected +// but it will result in a different SHA-1 hash for messages where a collision attack was detected +// this will automatically invalidate SHA-1 based digital signature forgeries +// enabled by default */ void SHA1DCSetSafeHash(SHA1_CTX*, int); -/* - Function to disable or enable the use of Unavoidable Bitconditions (provides a significant speed up). - Enabled by default - */ +/* function to disable or enable the use of Unavoidable Bitconditions (provides a significant speed up) */ +/* enabled by default */ void SHA1DCSetUseUBC(SHA1_CTX*, int); -/* - Function to disable or enable the use of Collision Detection. - Enabled by default. - */ +/* function to disable or enable the use of Collision Detection */ +/* enabled by default */ void SHA1DCSetUseDetectColl(SHA1_CTX*, int); /* function to disable or enable the detection of reduced-round SHA-1 collisions */ @@ -92,11 +97,11 @@ void SHA1DCSetCallback(SHA1_CTX*, collision_block_callback); /* update SHA-1 context with buffer contents */ -void SHA1DCUpdate(SHA1_CTX*, const unsigned char*, size_t); +void SHA1DCUpdate(SHA1_CTX*, const char*, size_t); /* obtain SHA-1 hash from SHA-1 context */ /* returns: 0 = no collision detected, otherwise = collision found => warn user for active attack */ -int SHA1DCFinal(unsigned char[20], SHA1_CTX*); +int SHA1DCFinal(unsigned char[20], SHA1_CTX*); #if defined(__cplusplus) } diff --git a/third-party/sha1dc/sha1.c b/third-party/sha1dc/sha1.c --- a/third-party/sha1dc/sha1.c +++ b/third-party/sha1dc/sha1.c @@ -14,7 +14,7 @@ #include "ubc_check.h" -/* +/* Because Little-Endian architectures are most common, we only set SHA1DC_BIGENDIAN if one of these conditions is met. Note that all MSFT platforms are little endian, @@ -876,11 +876,6 @@ ihvout[0] = ihvin[0] + a; ihvout[1] = ihvin[1] + b; ihvout[2] = ihvin[2] + c; ihvout[3] = ihvin[3] + d; ihvout[4] = ihvin[4] + e; \ } -#ifdef _MSC_VER -#pragma warning(push) -#pragma warning(disable: 4127) /* Complier complains about the checks in the above macro being constant. */ -#endif - #ifdef DOSTORESTATE0 SHA1_RECOMPRESS(0) #endif @@ -1201,10 +1196,6 @@ SHA1_RECOMPRESS(79) #endif -#ifdef _MSC_VER -#pragma warning(pop) -#endif - static void sha1_recompression_step(uint32_t step, uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5]) { switch (step) @@ -1622,7 +1613,7 @@ unsigned i, j; uint32_t ubc_dv_mask[DVMASKSIZE] = { 0xFFFFFFFF }; uint32_t ihvtmp[5]; - + ctx->ihv1[0] = ctx->ihv[0]; ctx->ihv1[1] = ctx->ihv[1]; ctx->ihv1[2] = ctx->ihv[2]; @@ -1723,7 +1714,7 @@ ctx->callback = callback; } -void SHA1DCUpdate(SHA1_CTX* ctx, const unsigned char* buf, size_t len) +void SHA1DCUpdate(SHA1_CTX* ctx, const char* buf, size_t len) { unsigned left, fill; if (len == 0) @@ -1768,7 +1759,7 @@ uint32_t last = ctx->total & 63; uint32_t padn = (last < 56) ? (56 - last) : (120 - last); uint64_t total; - SHA1DCUpdate(ctx, sha1_padding, padn); + SHA1DCUpdate(ctx, (const char*)(sha1_padding), padn); total = ctx->total - padn; total <<= 3;