11
\$\begingroup\$

I've been working on a byte-oriented SHA-256 implementation for educational purposes. I then tested it using the NIST CAVP tests found here.

All tests pass but I would appreciate some feedback from a third party (especially regarding things I may be too involved to see like pointer errors or performance improvements that may have slipped my mind).

sha256.h

#ifndef SHA256_H
#define SHA256_H

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "utils.h"

void sha256(uint8_t* message, size_t message_length);

#endif

sha256.c

#include "sha256.h"

const uint32_t round_constants[64] = {
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};

uint32_t right_rotate(uint32_t x, size_t k) {
    return ((x >> k) | (x << (32 - k)));
}

uint32_t choice(uint32_t x, uint32_t y, uint32_t z) {
    return ((x & y) ^ (~x & z));
}

uint32_t majority(uint32_t x, uint32_t y, uint32_t z) {
    return ((x & y) ^ (x & z) ^ (y & z));
}

uint32_t delta0(uint32_t x) {
    return (right_rotate(x, 2) ^ right_rotate(x, 13) ^ right_rotate(x, 22));
}

uint32_t delta1(uint32_t x) {
    return (right_rotate(x, 6) ^ right_rotate(x, 11) ^ right_rotate(x, 25));
}

uint32_t sigma0(uint32_t x) {
    return (right_rotate(x, 7) ^ right_rotate(x, 18) ^ (x >> 3));
}

uint32_t sigma1(uint32_t x) {
    return (right_rotate(x, 17) ^ right_rotate(x, 19) ^ (x >> 10));
}

void sha256_padding(uint8_t* message, uint8_t** buffer, size_t message_length, size_t* buffer_length) {
    size_t total_zeros = 0;
    uint64_t bit_length = 0;

    // When the message is 9 bytes short of a block multiple there is no additional block added.
    if ((message_length + 9) % 64 == 0) {
        *buffer_length = message_length + 9;
    } else {
        *buffer_length = ((message_length + 9 + 64) / 64) * 64;
    }
    *buffer = safe_malloc((*buffer_length * sizeof **buffer));
    memcpy((*buffer), message, message_length);

    // Add the 1 bit as big-endian using the byte 0x80 = 0b10000000.
    (*buffer)[message_length] = 0x80;
    // Compute and add the needed amount of 0 bits to reach congruence modulo 512.
    total_zeros = *buffer_length - message_length - 9;
    memset((*buffer + message_length + 1), 0x00, total_zeros);

    // Add the length of the message as a big-endian 64-bit value.
    bit_length = (uint64_t)message_length * 8;
    for (size_t i = 0; i < 8; i++) {
        (*buffer)[*buffer_length - 8 + i] = (uint8_t)(bit_length >> (56 - i * 8));
    }
}

void sha256_compression(const uint8_t* block, uint32_t* hash) {
    uint32_t a = hash[0];
    uint32_t b = hash[1];
    uint32_t c = hash[2];
    uint32_t d = hash[3];
    uint32_t e = hash[4];
    uint32_t f = hash[5];
    uint32_t g = hash[6];
    uint32_t h = hash[7];
    uint32_t temp1, temp2;
    uint32_t msg_schedule[64];

    for (size_t i = 0, j = 0; i < 16; i++, j += 4) {
        msg_schedule[i] = (block[j] << 24) | (block[j + 1] << 16) | (block[j + 2] << 8) | (block[j + 3]);
    }

    for (size_t i = 16; i < 64; i++) {
        msg_schedule[i] = sigma1(msg_schedule[i - 2]) + msg_schedule[i - 7] + sigma0(msg_schedule[i - 15]) + msg_schedule[i - 16];
    }

    for (size_t i = 0; i < 64; i++) {
        temp1 = h + delta1(e) + choice(e, f, g) + round_constants[i] + msg_schedule[i];
        temp2 = delta0(a) + majority(a, b, c);
        h = g;
        g = f;
        f = e;
        e = d + temp1;
        d = c;
        c = b;
        b = a;
        a = temp1 + temp2;
    }

    hash[0] += a;
    hash[1] += b;
    hash[2] += c;
    hash[3] += d;
    hash[4] += e;
    hash[5] += f;
    hash[6] += g;
    hash[7] += h;
}

void sha256(uint8_t* message, size_t message_length) {
    uint8_t* padded_message = NULL;
    size_t padded_length = 0;
    uint32_t hash[8] = {
        0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
    };

    sha256_padding(message, &padded_message, message_length, &padded_length);

    // Apply the compression function on every block.
    for (size_t i = 0; i < padded_length / 64; i++) {
        sha256_compression((padded_message + i * 64), hash);
    }

    for (size_t i = 0; i < 8; i++) {
        printf("%08x", hash[i]);
    }
    printf("\n");

    free(padded_message);
}

utils.h

#ifndef UTILS_H
#define UTILS_H

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

void* safe_malloc(size_t size);
FILE* safe_fopen(const char* file_path, const char* mode);
void read_file_bytes(const char* file_path, uint8_t** buffer, size_t* file_length);

#endif

utils.c

#include "utils.h"

void* safe_malloc(size_t size) {
    void* ptr = malloc(size);
    if (ptr == NULL) {
        printf("Unable to allocate enough memory!!\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

FILE* safe_fopen(const char* file_path, const char* mode) {
    FILE* file_ptr = fopen(file_path, mode);
    if (file_ptr == NULL) {
        printf("Unable to open the file!!\n");
        exit(EXIT_FAILURE);
    }

    return file_ptr;
}

// Returns the size of a file in bytes (max 2GiB due to ftell()).
size_t file_size(FILE* file_ptr) {
    size_t file_length = 0;
    fseek(file_ptr, 0, SEEK_END);
    file_length = ftell(file_ptr);
    rewind(file_ptr);
    return file_length;
}

// Reads a file into a byte array passed by reference.
// Freeing the buffer is the callers responsibility.
void read_file_bytes(const char* file_path, uint8_t** buffer, size_t* file_length) {
    FILE* file_ptr = safe_fopen(file_path, "rb");
    size_t bytes_read = 0;

    *file_length = file_size(file_ptr);
    *buffer = safe_malloc(*file_length * sizeof **buffer);

    bytes_read = fread(*buffer, 1, *file_length, file_ptr);
    if (bytes_read != *file_length) {
        printf("An error occurred while trying to read from the file!!\n");
        exit(EXIT_FAILURE);
    }

    fclose(file_ptr);
}

driver.c

#include "sha256.h"

int main(int argc, char* argv[]) {
    uint8_t* message = NULL;
    size_t message_length = 0;
    read_file_bytes(argv[1], &message, &message_length);
    sha256(message, message_length);
    free(message);
    return 0;
}

Hope I didn't break any rules when writing the question :)) Thanks in advance

\$\endgroup\$
4
  • \$\begingroup\$ Any specific reason you handle only SHA-256, and not any other hashes in the SHA-2 family (SHA-224, SHA-384, SHA-512, SHA-512/224, SHA-512/256)? \$\endgroup\$ Commented Dec 16, 2023 at 13:18
  • \$\begingroup\$ No specific reason. I just decided to pick one from different categories so that I can learn more about cryptography in general. Like this one for hashing / hmac, AES for symmetric encryption, DLP for DH and some CSPRNGs. \$\endgroup\$ Commented Dec 16, 2023 at 14:40
  • \$\begingroup\$ Re: right_rotate - Best practices for circular shift (rotate) operations in C++ shows a version that's safe for any rotate count, including 0 or 32. But your code only uses it with counts between 1 and 31, so this is fine. Either way, compilers recognize it and use a rotate instruction on hardware that supports it. \$\endgroup\$ Commented Dec 16, 2023 at 19:20
  • \$\begingroup\$ minor issue in your safe_malloc: it's perfectly acceptable for malloc to return NULL if size is 0 \$\endgroup\$ Commented Dec 17, 2023 at 23:45

3 Answers 3

Reset to default
16
\$\begingroup\$

The functions that are not used outside of a translation unit should be defined as having internal linkage:

Everything except sha256() should be defined with the static keyword.

#if 0
uint32_t right_rotate(uint32_t x, size_t k) {
    return ((x >> k) | (x << (32 - k)));
}
#else
static uint32_t right_rotate(uint32_t x, size_t k) {
    return ((x >> k) | (x << (32 - k)));
}
#endif

// And so on...

Error messages go to stderr:

I suggest:

#if 0
if (ptr == NULL) {
    printf("Unable to allocate enough memory!!\n");
    exit(EXIT_FAILURE);
}
#else

#include <errno.h>

errno = 0;
...
if (ptr == NULL) {
    if (errno) {
        perror("malloc()");
    } else {
        fputs("Unable to allocate enough memory!!\n", stderr);
    }
    exit(EXIT_FAILURE);
}
#endif

See: Why use stderr when printf works fine?

file_size() risks invoking undefined behavior:

From the C Standard: (footnote 234 on p. 267 of the linked Standard)

Setting the file position indicator to end-of-file, as with fseek(file, 0, SEEK_END),has undefined behavior for a binary stream (because of possible trailing null characters) or for anystream with state-dependent encoding that does not assuredly end in the initial shift state.

If the file was opened in binary mode, fseek(file_ptr, 0, SEEK_END); would invoke undefined behavior.

Don't include unnecessary header files:

sha256.h doesn't require anything but stdint.h and stddef.h.

#if 0
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#else
#include <stdint.h>
#include <stddef.h>  /* This suffices for the definition of size_t. */
#endif

sha256.c should not depend on sha256.h. Use the headers you need per file, no more, no less.

Minor:

You don't need the extra parenthesis in the calls to memcpy(). You can safely drop them:

#if 0
memcpy((*buffer), message, message_length);
#else 
memcpy(*buffer, message, message_length);
#endif
\$\endgroup\$
11
  • 1
    \$\begingroup\$ See: stackoverflow.com/a/75034411/20017547 \$\endgroup\$ Commented Dec 15, 2023 at 17:07
  • 1
    \$\begingroup\$ @dRevan25 There's no reason for an SHA function to know the file size in advance. You're just adding unnecessary restrictions. \$\endgroup\$ Commented Dec 16, 2023 at 3:24
  • 2
    \$\begingroup\$ @Harith I would think it a good idea to include sha256.h in sha256.c so that the compiler can complain if one changes the declaration or definition in incompatible ways, don't you think? It is quite common practice I believe. \$\endgroup\$ Commented Dec 16, 2023 at 13:13
  • 6
    \$\begingroup\$ sha256.c should include "sha256.h" - that's how we ensure that the implementation provides a function signature consistent with how the client code calls it. (It's always a good idea to make this the first include from the implementation file, to verify that the header is self-contained). \$\endgroup\$ Commented Dec 16, 2023 at 15:40
  • 1
    \$\begingroup\$ @Toby Of course, sha256.c should include "sha256.h", but it should not depend on "sha256.h" to include the standard header files. Do you believe this part of my answer lacks clarity? \$\endgroup\$ Commented Dec 16, 2023 at 17:02
15
\$\begingroup\$

On top of what Harith has already posted:

Your program isn't scalable

Hashing files is intended to work on files of any size. Your program implicitly assumes it will only be used with files that fit completely into the available memory (RAM + page/swap file), and only performs well if the file fits into RAM.

Don't do that. If someone needs to compute a hash for a single file complete download of Wikipedia (on the order of 100 GB), the only limitation should be the speed and capacity of their disk drive, not their available memory.

There are two obvious solutions here:

Piecemeal hashing

Typically the solution to this is to offer four API functions:

  1. To allocate/initialize state for a hashing run
  2. To update the state for a block of data
  3. To finalize the state to compute the digest
  4. To free the state

You can still provide an all-in-one function like your sha256 function for the simple case when you're writing a library, but you don't want to limit your program to smallish files.

Don't slurp the file into memory

Alternatively, if this code is purely for use on 64 bit systems, and you don't want to add the complexity of updatable hashing, you can keep what you have, and write your program to avoid the use of fread in favor of OS-specific memory mapping facilities, e.g. mmap on most POSIX systems, and CreateFileMapping/MapViewOfFile on Windows. While it still relies on having adequate address space (thus the "64 bit only" requirement), a read-only mapping can page in from disk on demand and simply drop data under memory pressure (unlike freading into malloced storage, which must read eagerly initially, and as memory runs out, must page to the page/swap file, effectively quadrupling the load on the hard disk as data is read, paged out as new data is read, then read in again when it's actually hashed, then paged out again as new data must be paged in), and for typical 64 bit systems it ups your maximum file size to the hundred TB range or so, not just "RAM+swap file size".

Yes, it will run slower for these larger files, that's unavoidable. But the lazily paged in data means your program can start hashing immediately (instead of waiting for the complete data of a 100 GB file to be read in before it hashes a single byte), and you'll be loading new data as you need it, with the OS handling dropping the old data as needed; your program doesn't gain much complexity, because it offloads all that complexity to the memory manager.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Thank you for the adivce. I already knew it won't be able to handle files larger than 2Gib because of ftell() but didn't think of the RAM / speed aspect of things. I'll look into your proposed solutions and try to update my code accordingly. \$\endgroup\$ Commented Dec 16, 2023 at 12:00
  • \$\begingroup\$ @dRevan25: long is a 64-bit type on most 64-bit platforms other than Windows. So long ftell(FILE*) should work on large files on Linux / Mac / *BSD and other 64-bit Unix systems. But yes, this answer makes a good point; memory-mapped I/O will let the OS read ahead in parallel with computation, and the pauses in computation will just be page-faults to map in pages from disk cache that have hopefully already been read ahead, rather than read or ReadFile system calls that have to copy the data. With fault-around to map multiple pages per page-fault, overhead should be low. \$\endgroup\$ Commented Dec 16, 2023 at 19:16
  • \$\begingroup\$ @dRevan25: I guess Windows doesn't have ftello that returns and off_t. The Linux man page say it's part of POSIX 2001. fseeko, fseeko64; ftello, ftello64 Visual C equivalents - apparently there are equivalents, but not with the same name. So for fully portable code without #ifdef for specific platforms, yeah, just ftell. Or keep reading in fixed-size chunks to end of file; you don't want to allocate a > 2GiB buffer anyway. Probably 128 KiB to 256 KiB is good, about half of L2 cache size so you can get hits after the copy. \$\endgroup\$ Commented Dec 16, 2023 at 19:25
  • \$\begingroup\$ Thanks for the advice @PeterCordes. Now I switched to using the stat() function to get the file details. I'll look into this as well along with using the cpu extensions for sha256 but I'll first have to brush up on my architecture skills :)). \$\endgroup\$ Commented Dec 17, 2023 at 16:36
  • \$\begingroup\$ @dRevan25: If you're going to mmap, use fstat on the already-open file descriptor to avoid TOCTOU races (although the file length could still change after you open and map it, if it's still being appended; that's the user's problem. But you do want to stat the file you opened.) But keep in mind that will prevent your program from reading from a pipe or something, only regular files. The sha256sum shell command can handle non-seekable input, that's a good model for a command-line wrapper around your SHA function. So you might want mmap for seekable files but normal read otherwise. \$\endgroup\$ Commented Dec 17, 2023 at 16:58
7
\$\begingroup\$

especially regarding things I may be too involved to see like pointer errors or performance improvements that may have slipped my mind

Various processors today offer instructions that directly implement parts of SHA-256, in a way that is much more efficient than any "manual" calculations.

Modern x64 processors (from both Intel and AMD) have SHA256RNDS2, SHA256MSG1, and SHA256MSG2 which implement various parts of the algorithm: both the "rounds" (2 rounds in one instruction!) and the message scheduling. Intel has a technical paper describing the instructions and how to use them. It is not completely trivial to build a fully working SHA-256 implementation out of those instructions, you need some additional things as described in Intels technical paper. Integration in C code however is not the problem, you can simply use the corresponding intrinsic functions.

ARMv8 has its own SHA-acceleration operations.

See also Are there in x86 any instructions to accelerate SHA (SHA1/2/256/512) encoding? (mostly x86-oriented but there is some mention of ARM as well).

Of course not all processors have these special instructions, so you can keep your original code for them. Generic SIMD (as opposed to specialized SHA instructions) can also be used.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you, I'll take a look see what I can learn about this. \$\endgroup\$ Commented Dec 16, 2023 at 14:42

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.