[lib/Fuzzer] Add SHA1 implementation from public domain.

[kcc]

Summary

This adds a SHA1 implementation taken from public domain code.
The change is trivial, but as it involves third-party code I'd like
a second pair of eyes before commit.

LibFuzzer can not use SHA1 from openssl because openssl may not be available
and because we may be fuzzing openssl itself.
Using sha1sum via a pipe is too slow.

[majnemer]

I guess it would be nice if this lived in support alongside MD5.h

[kcc]

Not at all nice. I want to keep libFuzzer independent from the rest of LLVM.
It does *rely* on the rest of LLVM (because it needs instrumentation) but it can be compiled w/o
the rest of LLVM code. This is a very important trait for me.

[chandlerc]

lib/Fuzzer/CMakeLists.txt

13

This should be spelled FuzzerSHA1.cpp

lib/Fuzzer/FuzzerInternal.h

47–49

The comment isn't helping here. Again, please spell it 'SHA1' instead of 'Sha1'.

Also, array arguments with a size doesn't really make sense. They're just pointers in C++. I would either use a pointer or use a reference to an array of the given size.

lib/Fuzzer/FuzzerSha1.cpp

1–9 ↗

(On Diff #25659)

Please use a normal LLVM style header and formatting. In particular please explain why this is here and not in lib/Support, etc.

14 ↗

(On Diff #25659)

It would seem better to put this in an anonymous namespace and include the FuzzerInternal.h to define the ComputeSHA1 function in the fuzzer namespace.

221–225 ↗

(On Diff #25659)

I really don't like this approach. Why not just write a normal LLVM unittest for this (or other parts of the Fuzzer library)?

[kcc]

addressed comments

[kcc]

done all, PTAL

lib/Fuzzer/CMakeLists.txt

13

done

lib/Fuzzer/FuzzerInternal.h

47–49

Improved the comment, spelling and types.

lib/Fuzzer/FuzzerSha1.cpp

1–9 ↗

(On Diff #25659)

done

14 ↗

(On Diff #25659)

done

221–225 ↗

(On Diff #25659)

This is from the original code.
I've removed this part and added a unit test to test/FuzzerUnittest.cpp

[kcc]

fix comment

[chandlerc]

Looks good. Minor comment below.

lib/Fuzzer/FuzzerSHA1.cpp

10–13

I'd go ahead and say its been placed in the public domain so no one panics when reading it.

198–199

You can just define it:

void fuzzer::ComputeSHA1(...) {

Saves you namespace boilerplate. Not a big deal either way though.

[kcc]

addressed last comments

lib/Fuzzer/CMakeLists.txt

 set(LIBFUZZER_FLAGS_BASE "${CMAKE_CXX_FLAGS_RELEASE}")
 # Disable the coverage and sanitizer instrumentation for the fuzzer itself.
 set(CMAKE_CXX_FLAGS_RELEASE "${LIBFUZZER_FLAGS_BASE} -O2 -fno-sanitize=all")
 if( LLVM_USE_SANITIZE_COVERAGE )
   add_library(LLVMFuzzerNoMain OBJECT
     FuzzerCrossOver.cpp
     FuzzerTraceState.cpp
     FuzzerDriver.cpp
     FuzzerIO.cpp
     FuzzerLoop.cpp
     FuzzerMutate.cpp
     FuzzerSanitizerOptions.cpp
+    FuzzerSHA1.cpp
     FuzzerUtil.cpp
     )
   add_library(LLVMFuzzer STATIC
     FuzzerMain.cpp
     $<TARGET_OBJECTS:LLVMFuzzerNoMain>
     )
 
   if( LLVM_INCLUDE_TESTS )
     add_subdirectory(test)
   endif()
 endif()

lib/Fuzzer/FuzzerInternal.h

 void CrossOver(const Unit &A, const Unit &B, Unit *U, size_t MaxLen);
 
 void Print(const Unit &U, const char *PrintAfter = "");
 void PrintASCII(const Unit &U, const char *PrintAfter = "");
 std::string Hash(const Unit &U);
 void SetTimer(int Seconds);
 void PrintFileAsBase64(const std::string &Path);
 
+// Private copy of SHA1 implementation.
+static const int kSHA1NumBytes = 20;
+// Computes SHA1 hash of 'Len' bytes in 'Data', writes kSHA1NumBytes to 'Out'.
+void ComputeSHA1(const uint8_t *Data, size_t Len, uint8_t *Out);
+
 int NumberOfCpuCores();
 
 class Fuzzer {
  public:
   struct FuzzingOptions {
     int Verbosity = 1;
     int MaxLen = 0;
     bool DoCrossOver = true;

lib/Fuzzer/FuzzerSHA1.cpp

+//===- FuzzerSHA1.h - Private copy of the SHA1 implementation ---*- C++ -* ===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This code is taken from public domain
+// (http://oauth.googlecode.com/svn/code/c/liboauth/src/sha1.c)
+// and modified by adding anonymous namespace, adding an interface
+// function fuzzer::ComputeSHA1() and removing unnecessary code.
+//
+// lib/Fuzzer can not use SHA1 implementation from openssl because
+// openssl may not be available and because we may be fuzzing openssl itself.
+// For the same reason we do not want to depend on SHA1 from LLVM tree.
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerInternal.h"
+
+/* This code is public-domain - it is based on libcrypt
+ * placed in the public domain by Wei Dai and other contributors.
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+namespace {  // Added for LibFuzzer
+
+#ifdef __BIG_ENDIAN__
+# define SHA_BIG_ENDIAN
+#elif defined __LITTLE_ENDIAN__
+/* override */
+#elif defined __BYTE_ORDER
+# if __BYTE_ORDER__ ==  __ORDER_BIG_ENDIAN__
+# define SHA_BIG_ENDIAN
+# endif
+#else // ! defined __LITTLE_ENDIAN__
+# include <endian.h> // machine/endian.h
+# if __BYTE_ORDER__ ==  __ORDER_BIG_ENDIAN__
+#  define SHA_BIG_ENDIAN
+# endif
+#endif
+
+
+/* header */
+
+#define HASH_LENGTH 20
+#define BLOCK_LENGTH 64
+
+typedef struct sha1nfo {
+  uint32_t buffer[BLOCK_LENGTH/4];
+  uint32_t state[HASH_LENGTH/4];
+  uint32_t byteCount;
+  uint8_t bufferOffset;
+  uint8_t keyBuffer[BLOCK_LENGTH];
+  uint8_t innerHash[HASH_LENGTH];
+} sha1nfo;
+
+/* public API - prototypes - TODO: doxygen*/
+
+/**
+ */
+void sha1_init(sha1nfo *s);
+/**
+ */
+void sha1_writebyte(sha1nfo *s, uint8_t data);
+/**
+ */
+void sha1_write(sha1nfo *s, const char *data, size_t len);
+/**
+ */
+uint8_t* sha1_result(sha1nfo *s);
+
+
+/* code */
+#define SHA1_K0  0x5a827999
+#define SHA1_K20 0x6ed9eba1
+#define SHA1_K40 0x8f1bbcdc
+#define SHA1_K60 0xca62c1d6
+
+void sha1_init(sha1nfo *s) {
+  s->state[0] = 0x67452301;
+  s->state[1] = 0xefcdab89;
+  s->state[2] = 0x98badcfe;
+  s->state[3] = 0x10325476;
+  s->state[4] = 0xc3d2e1f0;
+  s->byteCount = 0;
+  s->bufferOffset = 0;
+}
+
+uint32_t sha1_rol32(uint32_t number, uint8_t bits) {
+  return ((number << bits) | (number >> (32-bits)));
+}
+
+void sha1_hashBlock(sha1nfo *s) {
+  uint8_t i;
+  uint32_t a,b,c,d,e,t;
+
+  a=s->state[0];
+  b=s->state[1];
+  c=s->state[2];
+  d=s->state[3];
+  e=s->state[4];
+  for (i=0; i<80; i++) {
+    if (i>=16) {
+      t = s->buffer[(i+13)&15] ^ s->buffer[(i+8)&15] ^ s->buffer[(i+2)&15] ^ s->buffer[i&15];
+      s->buffer[i&15] = sha1_rol32(t,1);
+    }
+    if (i<20) {
+      t = (d ^ (b & (c ^ d))) + SHA1_K0;
+    } else if (i<40) {
+      t = (b ^ c ^ d) + SHA1_K20;
+    } else if (i<60) {
+      t = ((b & c) | (d & (b | c))) + SHA1_K40;
+    } else {
+      t = (b ^ c ^ d) + SHA1_K60;
+    }
+    t+=sha1_rol32(a,5) + e + s->buffer[i&15];
+    e=d;
+    d=c;
+    c=sha1_rol32(b,30);
+    b=a;
+    a=t;
+  }
+  s->state[0] += a;
+  s->state[1] += b;
+  s->state[2] += c;
+  s->state[3] += d;
+  s->state[4] += e;
+}
+
+void sha1_addUncounted(sha1nfo *s, uint8_t data) {
+  uint8_t * const b = (uint8_t*) s->buffer;
+#ifdef SHA_BIG_ENDIAN
+  b[s->bufferOffset] = data;
+#else
+  b[s->bufferOffset ^ 3] = data;
+#endif
+  s->bufferOffset++;
+  if (s->bufferOffset == BLOCK_LENGTH) {
+    sha1_hashBlock(s);
+    s->bufferOffset = 0;
+  }
+}
+
+void sha1_writebyte(sha1nfo *s, uint8_t data) {
+  ++s->byteCount;
+  sha1_addUncounted(s, data);
+}
+
+void sha1_write(sha1nfo *s, const char *data, size_t len) {
+  for (;len--;) sha1_writebyte(s, (uint8_t) *data++);
+}
+
+void sha1_pad(sha1nfo *s) {
+  // Implement SHA-1 padding (fips180-2 §5.1.1)
+
+  // Pad with 0x80 followed by 0x00 until the end of the block
+  sha1_addUncounted(s, 0x80);
+  while (s->bufferOffset != 56) sha1_addUncounted(s, 0x00);
+
+  // Append length in the last 8 bytes
+  sha1_addUncounted(s, 0); // We're only using 32 bit lengths
+  sha1_addUncounted(s, 0); // But SHA-1 supports 64 bit lengths
+  sha1_addUncounted(s, 0); // So zero pad the top bits
+  sha1_addUncounted(s, s->byteCount >> 29); // Shifting to multiply by 8
+  sha1_addUncounted(s, s->byteCount >> 21); // as SHA-1 supports bitstreams as well as
+  sha1_addUncounted(s, s->byteCount >> 13); // byte.
+  sha1_addUncounted(s, s->byteCount >> 5);
+  sha1_addUncounted(s, s->byteCount << 3);
+}
+
+uint8_t* sha1_result(sha1nfo *s) {
+  // Pad to complete the last block
+  sha1_pad(s);
+
+#ifndef SHA_BIG_ENDIAN
+  // Swap byte order back
+  int i;
+  for (i=0; i<5; i++) {
+    s->state[i]=
+        (((s->state[i])<<24)& 0xff000000)
+      | (((s->state[i])<<8) & 0x00ff0000)
+      | (((s->state[i])>>8) & 0x0000ff00)
+      | (((s->state[i])>>24)& 0x000000ff);
+  }
+#endif
+
+  // Return pointer to hash (20 characters)
+  return (uint8_t*) s->state;
+}
+
+}  // namespace; Added for LibFuzzer
+
+// The rest is added for LibFuzzer
+void fuzzer::ComputeSHA1(const uint8_t *Data, size_t Len, uint8_t *Out) {
+  sha1nfo s;
+  sha1_init(&s);
+  sha1_write(&s, (const char*)Data, Len);
+  memcpy(Out, sha1_result(&s), HASH_LENGTH);
+}

lib/Fuzzer/FuzzerUtil.cpp

 //===- FuzzerUtil.cpp - Misc utils ----------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 // Misc utils.
 //===----------------------------------------------------------------------===//
 
 #include "FuzzerInternal.h"
+#include <sstream>
+#include <iomanip>
 #include <iostream>
 #include <sys/time.h>
 #include <cassert>
 #include <cstring>
 #include <signal.h>
 #include <unistd.h>
 
 namespace fuzzer {
for (auto X : U) {
     if (isprint(X))
       std::cerr << X;
     else
       std::cerr << "\\x" << std::hex << (int)(unsigned)X << std::dec;
   }
   std::cerr << PrintAfter;
 }
 
-// Try to compute a SHA1 sum of this Unit using an external 'sha1sum' command.
-// We can not use the SHA1 function from openssl directly because
-//  a) openssl may not be available,
-//  b) we may be fuzzing openssl itself.
-// This is all very sad, suggestions are welcome.
-static std::string TrySha1(const Unit &in) {
-  char TempPath[] = "/tmp/fuzzer-tmp-XXXXXX";
-  int FD = mkstemp(TempPath);
-  if (FD < 0) return "";
-  ssize_t Written = write(FD, in.data(), in.size());
-  close(FD);
-  if (static_cast<size_t>(Written) != in.size()) return "";
-
-  std::string Cmd = "sha1sum < ";
-  Cmd += TempPath;
-  FILE *F = popen(Cmd.c_str(), "r");
-  if (!F) return "";
-  char Sha1[41];
-  fgets(Sha1, sizeof(Sha1), F);
-  fclose(F);
-
-  unlink(TempPath);
-  return Sha1;
-}
-
-std::string Hash(const Unit &in) {
-  std::string Sha1 = TrySha1(in);
-  if (!Sha1.empty())
-    return Sha1;
-
-  size_t h1 = 0, h2 = 0;
-  for (auto x : in) {
-    h1 += x;
-    h1 *= 5;
-    h2 += x;
-    h2 *= 7;
-  }
-  return std::to_string(h1) + std::to_string(h2);
+std::string Hash(const Unit &U) {
+  uint8_t Hash[kSHA1NumBytes];
+  ComputeSHA1(U.data(), U.size(), Hash);
+  std::stringstream SS;
+  for (int i = 0; i < kSHA1NumBytes; i++)
+    SS << std::hex << std::setfill('0') << std::setw(2) << (unsigned)Hash[i];
+  return SS.str();
 }
 
 static void AlarmHandler(int, siginfo_t *, void *) {
   Fuzzer::StaticAlarmCallback();
 }
 
 void SetTimer(int Seconds) {
   struct itimerval T {{Seconds, 0}, {Seconds, 0}};

lib/Fuzzer/test/FuzzerUnittest.cpp

for (int Iter = 0; Iter < 3000; Iter++) {
       FoundUnits.insert(C);
     }
     for (const Unit &U : Expected)
       if (U.size() <= Len)
         ExpectedUnitsWitThisLength.insert(U);
     EXPECT_EQ(ExpectedUnitsWitThisLength, FoundUnits);
   }
 }
+
+TEST(Fuzzer, Hash) {
+  uint8_t A[] = {'a', 'b', 'c'};
+  fuzzer::Unit U(A, A + sizeof(A));
+  EXPECT_EQ("a9993e364706816aba3e25717850c26c9cd0d89d", fuzzer::Hash(U));
+  U.push_back('d');
+  EXPECT_EQ("81fe8bfe87576c3ecb22426f8e57847382917acf", fuzzer::Hash(U));
+}