README.md

   1 # sha1collisiondetection
   2 Library and command line tool to detect SHA-1 collisions in files
   3
   4 Copyright 2017 Marc Stevens <marc@marc-stevens.nl>
   5
   6 Distributed under the MIT Software License.
   7
   8 See accompanying file LICENSE.txt or copy at https://opensource.org/licenses/MIT.
   9
  10 ## Developers
  11
  12 - Marc Stevens, CWI Amsterdam (https://marc-stevens.nl)
  13 - Dan Shumow, Microsoft Research (https://www.microsoft.com/en-us/research/people/danshu/)
  14
  15 ## About
  16 This library and command line tool were designed as near drop-in replacements for common SHA-1 libraries and sha1sum.
  17 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.
  18
  19 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:
  20 ```
  21     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),
  22     I(46,2), I(47,2), I(48,2), I(49,2), I(50,2), I(51,2),
  23     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),
  24     II(46,2), II(49,2), II(50,2), II(51,2)
  25 ```
  26 The possibility of false positives can be neglected as the probability is smaller than 2^-90.
  27
  28 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.
  29 Colliding files will have the same SHA-1 hash, but will have different unpredictable safe-hashes.
  30 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.
  31
  32 For the theoretical explanation of collision detection see the award-winning paper on _Counter-Cryptanalysis_:
  33
  34 Counter-cryptanalysis, Marc Stevens, CRYPTO 2013, Lecture Notes in Computer Science, vol. 8042, Springer, 2013, pp. 129-146,
  35 https://marc-stevens.nl/research/papers/C13-S.pdf
  36
  37 ## Compiling
  38
  39 Run:
  40 ```
  41 make
  42 ```
  43
  44 ## Command-line usage
  45
  46 There are two programs `bin/sha1dcsum` and `bin/sha1dcsum_partialcoll`.
  47 The first program `bin/sha1dcsum` will detect and warn for files that were generated with a cryptanalytic SHA-1 collision attack,
  48 like the one documented at https://shattered.io/ as well as the later derived attack https://sha-mbles.github.io/.
  49 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).
  50
  51 Examples:
  52 ```
  53 bin/sha1dcsum test/sha1_reducedsha_coll.bin test/shattered-1.pdf
  54 bin/sha1dcsum_partialcoll test/sha1reducedsha_coll.bin test/shattered-1.pdf
  55 pipe_data | bin/sha1dcsum -
  56 ```
  57
  58 ## Library usage
  59
  60 See the documentation in `lib/sha1.h`. Here is a simple example code snippet:
  61 ```
  62 #include <sha1dc/sha1.h>
  63
  64 SHA1_CTX ctx;
  65 unsigned char hash[20];
  66 SHA1DCInit(&ctx);
  67
  68 /** disable safe-hash mode (safe-hash mode is enabled by default) **/
  69 // SHA1DCSetSafeHash(&ctx, 0);
  70 /** disable use of unavoidable attack conditions to speed up detection (enabled by default) **/
  71 // SHA1DCSetUseUBC(&ctx, 0);
  72
  73 SHA1DCUpdate(&ctx, buffer, (unsigned)(size));
  74
  75 int iscoll = SHA1DCFinal(hash,&ctx);
  76 if (iscoll)
  77     printf("collision detected");
  78 else
  79     printf("no collision detected");
  80 ```
  81
  82 ## Inclusion in other programs
  83
  84 In order to make it easier to include these sources in other project
  85 there are several preprocessor macros that the code uses. Rather than
  86 copy/pasting and customizing or specializing the code, first see if
  87 setting any of these defines appropriately will allow you to avoid
  88 modifying the code yourself.
  89
  90 - SHA1DC_NO_STANDARD_INCLUDES
  91
  92  Skips including standard headers. Use this if your project for
  93  whatever reason wishes to do its own header includes.
  94
  95 - SHA1DC_CUSTOM_INCLUDE_SHA1_C
  96
  97   Includes a custom header at the top of sha1.c. Usually this would be
  98   set in conjunction with SHA1DC_NO_STANDARD_INCLUDES to point to a
  99   header file which includes various standard headers.
 100
 101 - SHA1DC_INIT_SAFE_HASH_DEFAULT
 102
 103   Sets the default for safe_hash in SHA1DCInit(). Valid values are 0
 104   and 1. If unset 1 is the default.
 105
 106 - SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C
 107
 108   Includes a custom trailer in sha1.c. Useful for any extra utility
 109   functions that make use of the functions already defined in sha1.c.
 110
 111 - SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H
 112
 113   Includes a custom trailer in sha1.h. Useful for defining the
 114   prototypes of the functions or code included by
 115   SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C.
 116
 117 - SHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C
 118
 119   Includes a custom header at the top of ubc_check.c.
 120
 121 - SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_C
 122
 123   Includes a custom trailer in ubc_check.c.
 124
 125 - SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_H
 126
 127   Includes a custom trailer in ubc_check.H.
 128
 129 This code will try to auto-detect certain things based on
 130 CPU/platform. Unless you're running on some really obscure CPU or
 131 porting to a new platform you should not need to tweak this. If you do
 132 please open an issue at
 133 https://github.com/cr-marcstevens/sha1collisiondetection
 134
 135 - SHA1DC_FORCE_LITTLEENDIAN / SHA1DC_FORCE_BIGENDIAN
 136
 137   Override the check for processor endianenss and force either
 138   Little-Endian or Big-Endian.
 139
 140 - SHA1DC_FORCE_UNALIGNED_ACCESS
 141
 142   Permit unaligned access. This will fail on e.g. SPARC processors, so
 143   it's only permitted on a whitelist of processors. If your CPU isn't
 144   detected as allowing this, and allows unaligned access, setting this
 145   may improve performance (or make it worse, if the kernel has to
 146   catch and emulate such access on its own).