From 656ead1fb7db0afc4927446e5b604491efbba08c Mon Sep 17 00:00:00 2001 From: cynecx Date: Sun, 14 Feb 2021 17:31:44 +0000 Subject: [PATCH] [llvm/Support] Add SHA256 implementation Adds an *unaudited* SHA-256 implementation to `llvm/Support`. The ongoing lld-macho effort needs this to emit an adhoc code signature for macho files on macOS Big Sur. Reviewed By: mehdi_amini Differential Revision: https://reviews.llvm.org/D96540 --- llvm/include/llvm/Support/SHA256.h | 90 +++++++++++ llvm/lib/Support/CMakeLists.txt | 1 + llvm/lib/Support/SHA256.cpp | 291 ++++++++++++++++++++++++++++++++++ llvm/unittests/Support/CMakeLists.txt | 1 + llvm/unittests/Support/SHA256.cpp | 80 ++++++++++ 5 files changed, 463 insertions(+) create mode 100644 llvm/include/llvm/Support/SHA256.h create mode 100644 llvm/lib/Support/SHA256.cpp create mode 100644 llvm/unittests/Support/SHA256.cpp diff --git a/llvm/include/llvm/Support/SHA256.h b/llvm/include/llvm/Support/SHA256.h new file mode 100644 index 0000000..29270e1 --- /dev/null +++ b/llvm/include/llvm/Support/SHA256.h @@ -0,0 +1,90 @@ +//====- SHA256.cpp - SHA256 implementation ---*- C++ -* ======// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/* + * The SHA-256 Secure Hash Standard was published by NIST in 2002. + * + * http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf + * + * The implementation is based on nacl's sha256 implementation [0] and LLVM's + * pre-exsiting SHA1 code [1]. + * + * [0] https://hyperelliptic.org/nacl/nacl-20110221.tar.bz2 (public domain + * code) + * [1] llvm/lib/Support/SHA1.{h,cpp} + */ +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_SHA2_H +#define LLVM_SUPPORT_SHA2_H + +#include +#include + +namespace llvm { + +template class ArrayRef; +class StringRef; + +class SHA256 { +public: + explicit SHA256() { init(); } + + /// Reinitialize the internal state + void init(); + + /// Digest more data. + void update(ArrayRef Data); + + /// Digest more data. + void update(StringRef Str); + + /// Return a reference to the current raw 256-bits SHA256 for the digested + /// data since the last call to init(). This call will add data to the + /// internal state and as such is not suited for getting an intermediate + /// result (see result()). + StringRef final(); + + /// Return a reference to the current raw 256-bits SHA256 for the digested + /// data since the last call to init(). This is suitable for getting the + /// SHA256 at any time without invalidating the internal state so that more + /// calls can be made into update. + StringRef result(); + + /// Returns a raw 256-bit SHA256 hash for the given data. + static std::array hash(ArrayRef Data); + +private: + /// Define some constants. + /// "static constexpr" would be cleaner but MSVC does not support it yet. + enum { BLOCK_LENGTH = 64 }; + enum { HASH_LENGTH = 32 }; + + // Internal State + struct { + union { + uint8_t C[BLOCK_LENGTH]; + uint32_t L[BLOCK_LENGTH / 4]; + } Buffer; + uint32_t State[HASH_LENGTH / 4]; + uint32_t ByteCount; + uint8_t BufferOffset; + } InternalState; + + // Internal copy of the hash, populated and accessed on calls to result() + uint32_t HashResult[HASH_LENGTH / 4]; + + // Helper + void writebyte(uint8_t data); + void hashBlock(); + void addUncounted(uint8_t data); + void pad(); +}; + +} // namespace llvm + +#endif // LLVM_SUPPORT_SHA2_H diff --git a/llvm/lib/Support/CMakeLists.txt b/llvm/lib/Support/CMakeLists.txt index 1c805e3..33caf58 100644 --- a/llvm/lib/Support/CMakeLists.txt +++ b/llvm/lib/Support/CMakeLists.txt @@ -162,6 +162,7 @@ add_llvm_component_library(LLVMSupport ScaledNumber.cpp ScopedPrinter.cpp SHA1.cpp + SHA256.cpp Signposts.cpp SmallPtrSet.cpp SmallVector.cpp diff --git a/llvm/lib/Support/SHA256.cpp b/llvm/lib/Support/SHA256.cpp new file mode 100644 index 0000000..a75a7b8 --- /dev/null +++ b/llvm/lib/Support/SHA256.cpp @@ -0,0 +1,291 @@ +//====- SHA256.cpp - SHA256 implementation ---*- C++ -* ======// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/* + * The SHA-256 Secure Hash Standard was published by NIST in 2002. + * + * http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf + * + * The implementation is based on nacl's sha256 implementation [0] and LLVM's + * pre-exsiting SHA1 code [1]. + * + * [0] https://hyperelliptic.org/nacl/nacl-20110221.tar.bz2 (public domain + * code) + * [1] llvm/lib/Support/SHA1.{h,cpp} + */ +//===----------------------------------------------------------------------===// + +#include "llvm/Support/SHA256.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Endian.h" +#include "llvm/Support/Host.h" +#include + +namespace llvm { + +#if defined(BYTE_ORDER) && defined(BIG_ENDIAN) && BYTE_ORDER == BIG_ENDIAN +#define SHA_BIG_ENDIAN +#endif + +#define SHR(x, c) ((x) >> (c)) +#define ROTR(x, n) (((x) >> n) | ((x) << (32 - (n)))) + +#define CH(x, y, z) (((x) & (y)) ^ (~(x) & (z))) +#define MAJ(x, y, z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z))) + +#define SIGMA_0(x) (ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22)) +#define SIGMA_1(x) (ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25)) + +#define SIGMA_2(x) (ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10)) +#define SIGMA_3(x) (ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3)) + +#define F_EXPAND(A, B, C, D, E, F, G, H, M1, M2, M3, M4, k) \ + do { \ + H += SIGMA_1(E) + CH(E, F, G) + M1 + k; \ + D += H; \ + H += SIGMA_0(A) + MAJ(A, B, C); \ + M1 += SIGMA_2(M2) + M3 + SIGMA_3(M4); \ + } while (0); + +void SHA256::init() { + InternalState.State[0] = 0x6A09E667; + InternalState.State[1] = 0xBB67AE85; + InternalState.State[2] = 0x3C6EF372; + InternalState.State[3] = 0xA54FF53A; + InternalState.State[4] = 0x510E527F; + InternalState.State[5] = 0x9B05688C; + InternalState.State[6] = 0x1F83D9AB; + InternalState.State[7] = 0x5BE0CD19; + InternalState.ByteCount = 0; + InternalState.BufferOffset = 0; +} + +void SHA256::hashBlock() { + uint32_t A = InternalState.State[0]; + uint32_t B = InternalState.State[1]; + uint32_t C = InternalState.State[2]; + uint32_t D = InternalState.State[3]; + uint32_t E = InternalState.State[4]; + uint32_t F = InternalState.State[5]; + uint32_t G = InternalState.State[6]; + uint32_t H = InternalState.State[7]; + + uint32_t W00 = InternalState.Buffer.L[0]; + uint32_t W01 = InternalState.Buffer.L[1]; + uint32_t W02 = InternalState.Buffer.L[2]; + uint32_t W03 = InternalState.Buffer.L[3]; + uint32_t W04 = InternalState.Buffer.L[4]; + uint32_t W05 = InternalState.Buffer.L[5]; + uint32_t W06 = InternalState.Buffer.L[6]; + uint32_t W07 = InternalState.Buffer.L[7]; + uint32_t W08 = InternalState.Buffer.L[8]; + uint32_t W09 = InternalState.Buffer.L[9]; + uint32_t W10 = InternalState.Buffer.L[10]; + uint32_t W11 = InternalState.Buffer.L[11]; + uint32_t W12 = InternalState.Buffer.L[12]; + uint32_t W13 = InternalState.Buffer.L[13]; + uint32_t W14 = InternalState.Buffer.L[14]; + uint32_t W15 = InternalState.Buffer.L[15]; + + F_EXPAND(A, B, C, D, E, F, G, H, W00, W14, W09, W01, 0x428A2F98); + F_EXPAND(H, A, B, C, D, E, F, G, W01, W15, W10, W02, 0x71374491); + F_EXPAND(G, H, A, B, C, D, E, F, W02, W00, W11, W03, 0xB5C0FBCF); + F_EXPAND(F, G, H, A, B, C, D, E, W03, W01, W12, W04, 0xE9B5DBA5); + F_EXPAND(E, F, G, H, A, B, C, D, W04, W02, W13, W05, 0x3956C25B); + F_EXPAND(D, E, F, G, H, A, B, C, W05, W03, W14, W06, 0x59F111F1); + F_EXPAND(C, D, E, F, G, H, A, B, W06, W04, W15, W07, 0x923F82A4); + F_EXPAND(B, C, D, E, F, G, H, A, W07, W05, W00, W08, 0xAB1C5ED5); + F_EXPAND(A, B, C, D, E, F, G, H, W08, W06, W01, W09, 0xD807AA98); + F_EXPAND(H, A, B, C, D, E, F, G, W09, W07, W02, W10, 0x12835B01); + F_EXPAND(G, H, A, B, C, D, E, F, W10, W08, W03, W11, 0x243185BE); + F_EXPAND(F, G, H, A, B, C, D, E, W11, W09, W04, W12, 0x550C7DC3); + F_EXPAND(E, F, G, H, A, B, C, D, W12, W10, W05, W13, 0x72BE5D74); + F_EXPAND(D, E, F, G, H, A, B, C, W13, W11, W06, W14, 0x80DEB1FE); + F_EXPAND(C, D, E, F, G, H, A, B, W14, W12, W07, W15, 0x9BDC06A7); + F_EXPAND(B, C, D, E, F, G, H, A, W15, W13, W08, W00, 0xC19BF174); + + F_EXPAND(A, B, C, D, E, F, G, H, W00, W14, W09, W01, 0xE49B69C1); + F_EXPAND(H, A, B, C, D, E, F, G, W01, W15, W10, W02, 0xEFBE4786); + F_EXPAND(G, H, A, B, C, D, E, F, W02, W00, W11, W03, 0x0FC19DC6); + F_EXPAND(F, G, H, A, B, C, D, E, W03, W01, W12, W04, 0x240CA1CC); + F_EXPAND(E, F, G, H, A, B, C, D, W04, W02, W13, W05, 0x2DE92C6F); + F_EXPAND(D, E, F, G, H, A, B, C, W05, W03, W14, W06, 0x4A7484AA); + F_EXPAND(C, D, E, F, G, H, A, B, W06, W04, W15, W07, 0x5CB0A9DC); + F_EXPAND(B, C, D, E, F, G, H, A, W07, W05, W00, W08, 0x76F988DA); + F_EXPAND(A, B, C, D, E, F, G, H, W08, W06, W01, W09, 0x983E5152); + F_EXPAND(H, A, B, C, D, E, F, G, W09, W07, W02, W10, 0xA831C66D); + F_EXPAND(G, H, A, B, C, D, E, F, W10, W08, W03, W11, 0xB00327C8); + F_EXPAND(F, G, H, A, B, C, D, E, W11, W09, W04, W12, 0xBF597FC7); + F_EXPAND(E, F, G, H, A, B, C, D, W12, W10, W05, W13, 0xC6E00BF3); + F_EXPAND(D, E, F, G, H, A, B, C, W13, W11, W06, W14, 0xD5A79147); + F_EXPAND(C, D, E, F, G, H, A, B, W14, W12, W07, W15, 0x06CA6351); + F_EXPAND(B, C, D, E, F, G, H, A, W15, W13, W08, W00, 0x14292967); + + F_EXPAND(A, B, C, D, E, F, G, H, W00, W14, W09, W01, 0x27B70A85); + F_EXPAND(H, A, B, C, D, E, F, G, W01, W15, W10, W02, 0x2E1B2138); + F_EXPAND(G, H, A, B, C, D, E, F, W02, W00, W11, W03, 0x4D2C6DFC); + F_EXPAND(F, G, H, A, B, C, D, E, W03, W01, W12, W04, 0x53380D13); + F_EXPAND(E, F, G, H, A, B, C, D, W04, W02, W13, W05, 0x650A7354); + F_EXPAND(D, E, F, G, H, A, B, C, W05, W03, W14, W06, 0x766A0ABB); + F_EXPAND(C, D, E, F, G, H, A, B, W06, W04, W15, W07, 0x81C2C92E); + F_EXPAND(B, C, D, E, F, G, H, A, W07, W05, W00, W08, 0x92722C85); + F_EXPAND(A, B, C, D, E, F, G, H, W08, W06, W01, W09, 0xA2BFE8A1); + F_EXPAND(H, A, B, C, D, E, F, G, W09, W07, W02, W10, 0xA81A664B); + F_EXPAND(G, H, A, B, C, D, E, F, W10, W08, W03, W11, 0xC24B8B70); + F_EXPAND(F, G, H, A, B, C, D, E, W11, W09, W04, W12, 0xC76C51A3); + F_EXPAND(E, F, G, H, A, B, C, D, W12, W10, W05, W13, 0xD192E819); + F_EXPAND(D, E, F, G, H, A, B, C, W13, W11, W06, W14, 0xD6990624); + F_EXPAND(C, D, E, F, G, H, A, B, W14, W12, W07, W15, 0xF40E3585); + F_EXPAND(B, C, D, E, F, G, H, A, W15, W13, W08, W00, 0x106AA070); + + F_EXPAND(A, B, C, D, E, F, G, H, W00, W14, W09, W01, 0x19A4C116); + F_EXPAND(H, A, B, C, D, E, F, G, W01, W15, W10, W02, 0x1E376C08); + F_EXPAND(G, H, A, B, C, D, E, F, W02, W00, W11, W03, 0x2748774C); + F_EXPAND(F, G, H, A, B, C, D, E, W03, W01, W12, W04, 0x34B0BCB5); + F_EXPAND(E, F, G, H, A, B, C, D, W04, W02, W13, W05, 0x391C0CB3); + F_EXPAND(D, E, F, G, H, A, B, C, W05, W03, W14, W06, 0x4ED8AA4A); + F_EXPAND(C, D, E, F, G, H, A, B, W06, W04, W15, W07, 0x5B9CCA4F); + F_EXPAND(B, C, D, E, F, G, H, A, W07, W05, W00, W08, 0x682E6FF3); + F_EXPAND(A, B, C, D, E, F, G, H, W08, W06, W01, W09, 0x748F82EE); + F_EXPAND(H, A, B, C, D, E, F, G, W09, W07, W02, W10, 0x78A5636F); + F_EXPAND(G, H, A, B, C, D, E, F, W10, W08, W03, W11, 0x84C87814); + F_EXPAND(F, G, H, A, B, C, D, E, W11, W09, W04, W12, 0x8CC70208); + F_EXPAND(E, F, G, H, A, B, C, D, W12, W10, W05, W13, 0x90BEFFFA); + F_EXPAND(D, E, F, G, H, A, B, C, W13, W11, W06, W14, 0xA4506CEB); + F_EXPAND(C, D, E, F, G, H, A, B, W14, W12, W07, W15, 0xBEF9A3F7); + F_EXPAND(B, C, D, E, F, G, H, A, W15, W13, W08, W00, 0xC67178F2); + + InternalState.State[0] += A; + InternalState.State[1] += B; + InternalState.State[2] += C; + InternalState.State[3] += D; + InternalState.State[4] += E; + InternalState.State[5] += F; + InternalState.State[6] += G; + InternalState.State[7] += H; +} + +void SHA256::addUncounted(uint8_t Data) { +#ifdef SHA_BIG_ENDIAN + InternalState.Buffer.C[InternalState.BufferOffset] = Data; +#else + InternalState.Buffer.C[InternalState.BufferOffset ^ 3] = Data; +#endif + + InternalState.BufferOffset++; + if (InternalState.BufferOffset == BLOCK_LENGTH) { + hashBlock(); + InternalState.BufferOffset = 0; + } +} + +void SHA256::writebyte(uint8_t Data) { + ++InternalState.ByteCount; + addUncounted(Data); +} + +void SHA256::update(ArrayRef Data) { + InternalState.ByteCount += Data.size(); + + // Finish the current block. + if (InternalState.BufferOffset > 0) { + const size_t Remainder = std::min( + Data.size(), BLOCK_LENGTH - InternalState.BufferOffset); + for (size_t I = 0; I < Remainder; ++I) + addUncounted(Data[I]); + Data = Data.drop_front(Remainder); + } + + // Fast buffer filling for large inputs. + while (Data.size() >= BLOCK_LENGTH) { + assert(InternalState.BufferOffset == 0); + assert(BLOCK_LENGTH % 4 == 0); + constexpr size_t BLOCK_LENGTH_32 = BLOCK_LENGTH / 4; + for (size_t I = 0; I < BLOCK_LENGTH_32; ++I) + InternalState.Buffer.L[I] = support::endian::read32be(&Data[I * 4]); + hashBlock(); + Data = Data.drop_front(BLOCK_LENGTH); + } + + // Finish the remainder. + for (uint8_t C : Data) + addUncounted(C); +} + +void SHA256::update(StringRef Str) { + update( + ArrayRef((uint8_t *)const_cast(Str.data()), Str.size())); +} + +void SHA256::pad() { + // Implement SHA-2 padding (fips180-2 5.1.1) + + // Pad with 0x80 followed by 0x00 until the end of the block + addUncounted(0x80); + while (InternalState.BufferOffset != 56) + addUncounted(0x00); + + uint64_t len = InternalState.ByteCount << 3; // bit size + + // Append length in the last 8 bytes big edian encoded + addUncounted(len >> 56); + addUncounted(len >> 48); + addUncounted(len >> 40); + addUncounted(len >> 32); + addUncounted(len >> 24); + addUncounted(len >> 16); + addUncounted(len >> 8); + addUncounted(len); +} + +StringRef SHA256::final() { + // Pad to complete the last block + pad(); + +#ifdef SHA_BIG_ENDIAN + // Just copy the current state + for (int i = 0; i < 8; i++) { + HashResult[i] = InternalState.State[i]; + } +#else + // Swap byte order back + for (int i = 0; i < 8; i++) { + HashResult[i] = (((InternalState.State[i]) << 24) & 0xff000000) | + (((InternalState.State[i]) << 8) & 0x00ff0000) | + (((InternalState.State[i]) >> 8) & 0x0000ff00) | + (((InternalState.State[i]) >> 24) & 0x000000ff); + } +#endif + + // Return pointer to hash (32 characters) + return StringRef((char *)HashResult, HASH_LENGTH); +} + +StringRef SHA256::result() { + auto StateToRestore = InternalState; + + auto Hash = final(); + + // Restore the state + InternalState = StateToRestore; + + // Return pointer to hash (32 characters) + return Hash; +} + +std::array SHA256::hash(ArrayRef Data) { + SHA256 Hash; + Hash.update(Data); + StringRef S = Hash.final(); + + std::array Arr; + memcpy(Arr.data(), S.data(), S.size()); + return Arr; +} + +} // namespace llvm \ No newline at end of file diff --git a/llvm/unittests/Support/CMakeLists.txt b/llvm/unittests/Support/CMakeLists.txt index 72d4987..f03f12e 100644 --- a/llvm/unittests/Support/CMakeLists.txt +++ b/llvm/unittests/Support/CMakeLists.txt @@ -67,6 +67,7 @@ add_llvm_unittest(SupportTests ReplaceFileTest.cpp RISCVAttributeParserTest.cpp ScaledNumberTest.cpp + SHA256.cpp SourceMgrTest.cpp SpecialCaseListTest.cpp SuffixTreeTest.cpp diff --git a/llvm/unittests/Support/SHA256.cpp b/llvm/unittests/Support/SHA256.cpp new file mode 100644 index 0000000..82359a71 --- /dev/null +++ b/llvm/unittests/Support/SHA256.cpp @@ -0,0 +1,80 @@ +//===- llvm/unittest/Support/SHA256Test.cpp - SHA256 tests +//----------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements unit tests for the SHA256 functions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Support/SHA256.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallString.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { + +static std::string toHex(StringRef Input) { + static const char *const LUT = "0123456789abcdef"; + size_t Length = Input.size(); + + std::string Output; + Output.reserve(2 * Length); + for (size_t i = 0; i < Length; ++i) { + const unsigned char c = Input[i]; + Output.push_back(LUT[c >> 4]); + Output.push_back(LUT[c & 15]); + } + return Output; +} + +/// Tests an arbitrary set of bytes passed as \p Input. +void TestSHA256Sum(ArrayRef Input, StringRef Final) { + SHA256 Hash; + Hash.update(Input); + auto hash = Hash.final(); + auto hashStr = toHex(hash); + EXPECT_EQ(hashStr, Final); +} + +using KV = std::pair; + +TEST(SHA256Test, SHA256) { + std::array testvectors{ + KV{"", + "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"}, + KV{"a", + "ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb"}, + KV{"abc", + "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"}, + KV{"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", + "248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1"}, + KV{"abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklm" + "nopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu", + "cf5b16a778af8380036ce59e7b0492370b249b11e8f07a51afac45037afee9d1"}}; + + for (auto input_expected : testvectors) { + auto str = std::get<0>(input_expected); + auto expected = std::get<1>(input_expected); + TestSHA256Sum({reinterpret_cast(str), strlen(str)}, + expected); + } + + std::string rep(1000, 'a'); + SHA256 Hash; + for (int i = 0; i < 1000; ++i) { + Hash.update({reinterpret_cast(rep.data()), rep.size()}); + } + auto hash = Hash.final(); + auto hashStr = toHex(hash); + EXPECT_EQ(hashStr, + "cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0"); +} + +} // namespace -- 2.7.4