cr-marcstevens / sha1collisiondetection Goto Github PK

As far as I understand, if two files were created to collide as git-objects, this program will mark them safe.

Because in this case, the chosen-prefix attack will be selected to include the git header, but that header won't be there when checking the file.

It would be nice to detect collision attack on git, without the user having to create the git-object manually.
Either by checking the "headered" version of files automatically, or by providing a command-line switch to do so.

I downloaded the sample PDFs and uploaded them to the file checker at https://shattered.io/ and it says that they're safe. Tesed on Chrome and Firefox. Wasn't sure where to post about the issue, so hopefully this works.

I just wanted to mention that there exists a "workaround" for git called git-evtag which only relies on the cryptographically strong(er) hash function SHA2-512 and includes that into a (OpenPGP signed) git tag. Maybe you will consider using git-evtag to provide a strong checksum over your tags/releases 😉

Which brings us to OpenPGP. As mentioned by @nbraud in this comment:

Note that OpenPGP signatures are also vulnerable to SHA1 second-preimage attacks (the adversary can forge keys with specific keyids at that point).

(RFC4880, 12.2. Key IDs and Fingerprints)

Does anyone know if someone is working on solving these issues for git and OpenPGP?

These files contain the following note:

// this file was generated by the 'parse_bitrel' program in the tools section
// using the data files from directory 'tools/data/3565'

However, that directory does not exist.

The URL http://www.oracle.com/technetwork/server-storage/solaris/portingtosolaris-138514.html in code comment at:

appears to be dead. I tried to find it on oracle.com or an archived version of it, but nothing came up. The closest related URL that I could find is Sun Studio 12: C User's Guide > Chapter 2 C-Compiler Information Specific to Sun’s Implementation > 2.9 Predefined Names, which has the following:

Predefinitions (not valid in -Xc mode):

• sun
• unix
• sparc (SPARC)
• i386 (x86)

The following predefinitions are valid in all modes:

• __sun
• __unix
• __SUNPRO_C=0x580
• __”uname -s”_”uname -r” (example: __SunOS_5_7)
• __sparc (SPARC)
• __i386 (x86)
• __BUILTIN_VA_ARG_INCR
• __SVR4
• __sparcv9 (-Xarch=v9, v9a)

Hi Marc,

awesome work. One small comment: the target install is missing in the Makefile.
Also, could you add a version number to the release, so one can refer to it?

It looks like the block where the collision is detected is re-compressed in some way, but I'm not enough of a C developer to be sure I understand what I'm reading. Is this documented anywhere?

The example commands don't work anymore since the binary has been renamed and there seems to be a single binary now (2nd one is a symlink)

I noticed that on some older PPC systems I have, the SHA1 hashes created in git were failing since this code was included. When built with newer gcc compilers (e.g. gcc6) git would generate properly working binaries.

The stock Apple compilers are gcc-4.2 and less, and they don't generate the #defines needed to succeed in the current big endian tests. Forcing big endian with -DSHA1DC_FORCE_BIGENDIAN does work to create a working git.

Perhaps the big endian detection might be tweaked to add support for these older stock Apple compilers, and that would fix git on these systems.

Here's the output:

$ ./gcc-apple-4.2 -E -dM  - < /dev/null
#define __DBL_MIN_EXP__ (-1021)
#define __FLT_MIN__ 1.17549435e-38F
#define __DEC64_DEN__ 0.000000000000001E-383DD
#define __CHAR_BIT__ 8
#define _ARCH_PPCGR 1
#define __WCHAR_MAX__ 2147483647
#define __DBL_DENORM_MIN__ 4.9406564584124654e-324
#define __FLT_EVAL_METHOD__ 0
#define __DBL_MIN_10_EXP__ (-307)
#define __FINITE_MATH_ONLY__ 0
#define __GNUC_PATCHLEVEL__ 1
#define __DEC64_MAX_EXP__ 384
#define __SHRT_MAX__ 32767
#define __LDBL_MAX__ 1.79769313486231580793728971405301e+308L
#define __APPLE_CC__ 5666
#define __UINTMAX_TYPE__ long long unsigned int
#define __DEC32_EPSILON__ 1E-6DF
#define __block __attribute__((__blocks__(byref)))
#define __LDBL_MAX_EXP__ 1024
#define __SCHAR_MAX__ 127
#define __USER_LABEL_PREFIX__ _
#define __STDC_HOSTED__ 1
#define __LDBL_HAS_INFINITY__ 1
#define __DEC64_MIN_EXP__ (-383)
#define __DBL_DIG__ 15
#define __FLT_EPSILON__ 1.19209290e-7F
#define __LDBL_MIN__ 2.00416836000897277799610805135016e-292L
#define __DEC32_MAX__ 9.999999E96DF
#define __ppc__ 1
#define __strong 
#define __APPLE__ 1
#define __DECIMAL_DIG__ 33
#define __LDBL_HAS_QUIET_NAN__ 1
#define __DYNAMIC__ 1
#define __GNUC__ 4
#define __FLT_HAS_DENORM__ 1
#define __DBL_MAX__ 1.7976931348623157e+308
#define __DBL_HAS_INFINITY__ 1
#define __DEC32_MIN_EXP__ (-95)
#define OBJC_NEW_PROPERTIES 1
#define __LDBL_HAS_DENORM__ 1
#define __DEC128_MAX__ 9.999999999999999999999999999999999E6144DL
#define __DEC32_MIN__ 1E-95DF
#define __weak __attribute__((objc_gc(weak)))
#define __DBL_MAX_EXP__ 1024
#define __DEC128_EPSILON__ 1E-33DL
#define __LONG_LONG_MAX__ 9223372036854775807LL
#define __GXX_ABI_VERSION 1002
#define __FLT_MIN_EXP__ (-125)
#define __DBL_MIN__ 2.2250738585072014e-308
#define __DBL_HAS_QUIET_NAN__ 1
#define __DEC128_MIN__ 1E-6143DL
#define __REGISTER_PREFIX__ 
#define __DBL_HAS_DENORM__ 1
#define __NO_INLINE__ 1
#define __DEC_EVAL_METHOD__ 2
#define _ARCH_PPC 1
#define __FLT_MANT_DIG__ 24
#define __VERSION__ "4.2.1 (Apple Inc. build 5666) (dot 3) (MacPorts apple-gcc42 5666.3_15)"
#define __BIG_ENDIAN__ 1
#define __DEC64_EPSILON__ 1E-15DD
#define __DEC128_MIN_EXP__ (-6143)
#define __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__ 1040
#define __SIZE_TYPE__ long unsigned int
#define __DEC32_DEN__ 0.000001E-95DF
#define __FLT_RADIX__ 2
#define __LDBL_EPSILON__ 4.94065645841246544176568792868221e-324L
#define __NATURAL_ALIGNMENT__ 1
#define __LDBL_DIG__ 31
#define __FLT_HAS_QUIET_NAN__ 1
#define __FLT_MAX_10_EXP__ 38
#define __LONG_MAX__ 2147483647L
#define __FLT_HAS_INFINITY__ 1
#define __DEC64_MAX__ 9.999999999999999E384DD
#define __DEC64_MANT_DIG__ 16
#define __DEC32_MAX_EXP__ 96
#define _BIG_ENDIAN 1
#define __DEC128_DEN__ 0.000000000000000000000000000000001E-6143DL
#define __LDBL_MANT_DIG__ 106
#define __CONSTANT_CFSTRINGS__ 1
#define __WCHAR_TYPE__ int
#define __pic__ 2
#define __FLT_DIG__ 6
#define __INT_MAX__ 2147483647
#define __LONG_DOUBLE_128__ 1
#define __FLT_MAX_EXP__ 128
#define __BLOCKS__ 1
#define __DBL_MANT_DIG__ 53
#define __DEC64_MIN__ 1E-383DD
#define __WINT_TYPE__ int
#define __LDBL_MIN_EXP__ (-968)
#define __MACH__ 1
#define __LDBL_MAX_10_EXP__ 308
#define __DBL_EPSILON__ 2.2204460492503131e-16
#define __INTMAX_MAX__ 9223372036854775807LL
#define __FLT_DENORM_MIN__ 1.40129846e-45F
#define __PIC__ 2
#define __FLT_MAX__ 3.40282347e+38F
#define __FLT_MIN_10_EXP__ (-37)
#define __INTMAX_TYPE__ long long int
#define __DEC128_MAX_EXP__ 6144
#define __GNUC_MINOR__ 2
#define __DEC32_MANT_DIG__ 7
#define __DBL_MAX_10_EXP__ 308
#define __LDBL_DENORM_MIN__ 4.94065645841246544176568792868221e-324L
#define __STDC__ 1
#define __PTRDIFF_TYPE__ int
#define __DEC128_MANT_DIG__ 34
#define __LDBL_MIN_10_EXP__ (-291)
#define __POWERPC__ 1
#define __GNUC_GNU_INLINE__ 1

perhaps checking for __APPLE__ and __BIG_ENDIAN__ would do it?

Per a discussion on Git mailing list at One failed self test on Fedora 29 and assorted follow-ups. The discussion concerns itself with a failed audit due to unaligned accesses in sha1dc/sha1.c (using CFLAGS += -fsanitize=undefined).

And in particular, from Jeff King at disabling sha1dc unaligned access:

Unfortunately, I don't think sha1dc currently supports #defines in that
direction. The only logic is "if we are on intel, do unaligned loads"
and "even if we are not on intel, do it anyway". There is no "even if we
are on intel, do not do unaligned loads".

I think you'd need something like this:

diff --git a/Makefile b/Makefile
index 148668368b..705c54dcd8 100644
--- a/Makefile
+++ b/Makefile
@@ -1194,6 +1194,7 @@ BASIC_CFLAGS += -fsanitize=$(SANITIZE) -fno-sanitize-recover=$(SANITIZE)
BASIC_CFLAGS += -fno-omit-frame-pointer
ifneq ($(filter undefined,$(SANITIZERS)),)
BASIC_CFLAGS += -DNO_UNALIGNED_LOADS
+BASIC_CFLAGS += -DSHA1DC_DISALLOW_UNALIGNED_ACCESS
endif
ifneq ($(filter leak,$(SANITIZERS)),)
BASIC_CFLAGS += -DSUPPRESS_ANNOTATED_LEAKS
diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index df0630bc6d..0bdf80d778 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -124,9 +124,11 @@
#endif
/ENDIANNESS SELECTION/

+#ifndef SHA1DC_DISALLOW_UNALIGNED_ACCESS
#if defined(SHA1DC_FORCE_UNALIGNED_ACCESS) || defined(SHA1DC_ON_INTEL_LIKE_PROCESSOR)
#define SHA1DC_ALLOW_UNALIGNED_ACCESS
#endif /UNALIGNMENT DETECTION/
+#endif

#define rotate_right(x,n) (((x)>>(n))|((x)<<(32-(n))))

but of course we cannot touch sha1dc/*, because we might actually be
using the submodule copy instead. And AFAIK there is no good way to
modify the submodule-provided content as part of the build. Why do we
even have the submodule again? ;P

I guess the same would be true for DC_SHA1_EXTERNAL, too, though.

So anyway, I think this needs a patch to the upstream sha1dc project.

Please provide an option to disable unaligned accesses.

The default make that ships with the latest Xcode or Mac OS Yosemite does not honor the president going to the most specialized suffix rule: as a result the SIMD compile time flags don't get added and clang chokes trying to compile some of the avx356 code because -mavx2 doesn't get passed. See #4 for additional discussion.

Checkinstall does not give any installation erros, but runnig the samples results in:

error while loading shared libraries: libsha1detectcoll.so.0: cannot open shared object file: No such file or directory

The homebrew folks (MacOS package manager) would like a git tag for a release (be it stable or development). Can you please create a tag?

Thanks.

cf. https://github.com/Homebrew/homebrew-core/pull/10431/files/f74798d7662c777d29b9cabce1ebb0cbf1bb93b5

Added to Blackarch: BlackArch/blackarch#1726
Feel free to change or inform me if any changes are needed.

Kudos for the impressive results and this very interesting project! Also, let me apologize in advance for reporting the obvious, as well as in case I am missing something about the below; I only looked at the code and didn't actually trigger any of the issues described here. I just felt these concerns needed to be brought up somewhere in here, as people might start actually using this code very soon.

As far as I can tell, the current implementation of the collision detector is not timing-safe, containing conditional branches based on data (and not only when a collision attack is fully detected, which could be acceptable). If this code is meant for actual use rather than just as a proof-of-concept perhaps this should be fixed - or at least it should be documented.

Specifically, there are many "if (mask & DV_...)" in ubc_check.c (coming from sha1collisiondetection-tools/parse_bitrel/parse_bitrel.cpp, so that one should be enhanced and the file regenerated), as well as some relevant if's in sha1.c: sha1_process(). There are also some in ubc_check_verify.c, but since this file is only needed for testing (right?), I guess they're OK to stay as-is (but maybe this is best to document in a comment).

ubc_check_simd.cinc got this right (I mean timing-safe) as it is, so I think parse_bitrel.cpp simply needs to have its SIMD logic replicated for its scalar code generation as well. And sha1.c needs to be edited manually.

For a conceptually similar yet much simpler example (almost trivial), here's my crypt_blowfish bug workaround from 2011, where it deviates from computing the correct hash only when a would-be-collision is detected and does so in a timing-safe manner:

http://cvsweb.openwall.com/cgi/cvsweb.cgi/Owl/packages/glibc/crypt_blowfish/crypt_blowfish.c.diff?r1=1.19;r2=1.20

How many dev hours did you put into finding something that has never actually happened in the wild and has an astronomically low chance of happening?

Upon code review, @cr-marcstevens and I noticed that the ihv2 buffers and m2 buffers on the context are unnecessary for the struct. And hence can be removed to simplify the code.

https://sha-mbles.github.io/

Dear Marc Stevens and Dan Shumow,
There are a variety of tools to calculate SHA1 that could benefit from including your library.
But what’s the proper argumentation to move its authors to do that?
For example, I asked RHash’s author to “reinforce SHA1 against collisions” which led to confusion.

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.

Please clarify strength of the "safe hash"? Why it's not vulnerable to SHA-1 weaknesses?

Besides the gcc flags (see PR #41) there is also the issue that dependent files are not generated.

root@x066:[/data/prj/aixtools/git]git clone https://github.com/cr-marcstevens/sha1collisiondetection.git sha1test
Cloning into 'sha1test'...
remote: Counting objects: 864, done.
remote: Total 864 (delta 0), reused 0 (delta 0), pack-reused 864
Receiving objects: 100% (864/864), 602.00 KiB | 552.00 KiB/s, done.
Resolving deltas: 100% (560/560), done.
root@x066:[/data/prj/aixtools/git]cd sha1test
root@x066:[/data/prj/aixtools/git/sha1test]ls -l
total 96
drwxr-sr-x 8 root felt 4096 Jul 30 06:38 .git
-rw-r--r-- 1 root felt 422 Jul 30 06:38 .gitignore
-rw-r--r-- 1 root felt 396 Jul 30 06:38 .travis.yml
-rw-r--r-- 1 root felt 1270 Jul 30 06:38 LICENSE.txt
-rw-r--r-- 1 root felt 5215 Jul 30 06:38 Makefile
-rw-r--r-- 1 root felt 5786 Jul 30 06:38 README.md
drwxr-sr-x 2 root felt 4096 Jul 30 06:38 lib
drwxr-sr-x 2 root felt 4096 Jul 30 06:38 src
drwxr-sr-x 2 root felt 4096 Jul 30 06:38 test
drwxr-sr-x 4 root felt 4096 Jul 30 06:38 vs2015
root@x066:[/data/prj/aixtools/git/sha1test]make
mkdir -p dep_lib && cc -O2 -Wall -Werror -Wextra -pedantic -std=c90 -Ilib -M -MF dep_lib/sha1.d lib/sha1.c
cc: 1501-210 (S) command option Wall contains an incorrect subargument
mkdir -p dep_lib && cc -O2 -Wall -Werror -Wextra -pedantic -std=c90 -Ilib -M -MF dep_lib/ubc_check.d lib/ubc_check.c
cc: 1501-210 (S) command option Wall contains an incorrect subargument
mkdir -p dep_src && cc -O2 -Wall -Werror -Wextra -pedantic -std=c90 -Ilib -M -MF dep_src/main.d src/main.c
cc: 1501-210 (S) command option Wall contains an incorrect subargument
make: *** No rule to make target 'dep_lib/ubc_check.d', needed by 'obj_lib/ubc_check.lo'. Stop.