Find a crc32 hash collision to embed in a file (requires zlib)

README.md

Purpose

To embed a CRC-32 hash collision within a script to make the file hash to that value.

Usage

1. Add exactly sum=00000000 with a newline anywhere in a script file /path/to/your/file

#!{{whatever}}
# ... your code

sum=00000000

## bash self-check example
[ "$(crc32 "$0")" = "$sum" ] || { echo >&2 "$0: Hash failed"; exit 1; }

# ... code to run

2. Run

$ git clone https://gist.github.com/c85d295cf9e6124dd7e90716dc7b7310 find-crc32-collision
$ cd find-crc32-collision
$ make
$ bash find-crc32-in-parallel /path/to/your/file
### wait a long time

3. Update the script with found CRC-32 value

Notes

1. More physical cores = more performance with linear speed-up.
2. The parallel script is wasteful once it has found a match. Just ^C it if you only care to find one rather than to brute force the entire hash range.
3. While it maybe possible to adapt a brute force search to find an MD-5, SHA-0, or SHA-1 on a many-core server, it's probably a waste of time and money. It would probably work better re-arranged to launch many multiple AWS micro instances similar to computing rainbow tables.

find-crc32-in-parallel

#!/usr/bin/env bash
set -Eeuo pipefail

n=$(nproc)
inc=$((4294967296 / n))
begin=0

pids=()
trap 'E=$?; trap - EXIT; kill "${pids[@]}" 2>/dev/null; exit $E' EXIT

for ((i = 0; i < n; i++)); do
  if (( i == n-1 )); then
    end=4294967295
  else
    end=$((begin + inc - 1))
  fi
  ./find-crc32-worker "$1" $(printf '%08x' "$begin") $(printf '%08x' "$end") &
  pids+=("$!")
  begin=$((end+1))
done

wait

find-crc32-worker.c

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

typedef uint32_t hash_t;
#define HASH_HEX_DIGITS 8
#define BUF_SZ 4096
#define MAGIC_VARIABLE "sum="

#define _STRINGIFY(x) #x
#define STRINGIFY(x) _STRINGIFY(x)

void *read_whole_file(const char *filename, size_t *size) {
  uint8_t *new_r, *r = NULL;
  size_t actual_read;
  FILE *f = fopen(filename, "rb");
  if (!f) goto err0;

  for (*size = 0;;) {
    new_r = realloc(r, *size + BUF_SZ);
    if (!new_r) goto err1;
    r = new_r;
    actual_read = fread(&r[*size], 1, BUF_SZ, f);
    if (actual_read == 0) break;
    *size += actual_read;
  }
  if (!feof(f)) goto err1;

  fclose(f);
  return (r);
err1:
  free(r);
  fclose(f);
err0:
  return (NULL);
}

char *find_mutant(const char *begins, char *buf) {
  for (char *walk = strstr(buf, begins); walk;
       walk = strstr(walk + 1, begins)) {
    if (walk == buf || walk[-1] == '\n')
      return (walk);
  }
  return (NULL);
}

int is_valid_mutant(hash_t crc, const char *buf, size_t buf_len, char *hex_loc) {
  char hex[HASH_HEX_DIGITS+1];
  sprintf(hex, "%0" STRINGIFY(HASH_HEX_DIGITS) PRIx32, crc);
  memcpy(hex_loc, hex, HASH_HEX_DIGITS);

  return (crc32_z(0, (void *)buf, buf_len) == crc);
}

int main(int argc, char **argv) {
  if (argc != 4) return EXIT_FAILURE;
  hash_t begin = 0;
  hash_t end = 0;

  sscanf(argv[2], "%0" STRINGIFY(HASH_HEX_DIGITS) SCNx32, &begin);
  sscanf(argv[3], "%0" STRINGIFY(HASH_HEX_DIGITS) SCNx32, &end);
  if (begin > end) return EXIT_FAILURE;

  size_t len = 0;

  char *const buf = (char *const)read_whole_file(argv[1], &len);
  if (!buf) return EXIT_FAILURE;

  char *const mutant = find_mutant(MAGIC_VARIABLE, buf);
  if (!mutant) {
    free(buf);
    return EXIT_FAILURE;
  }
  char *const hex_loc = &mutant[strlen(MAGIC_VARIABLE)];

  for (hash_t try_crc = begin; try_crc != end; ++try_crc) {
    if (is_valid_mutant(try_crc, buf, len, hex_loc)) {
      fprintf(stderr, "Valid hash collision for CRC-32 is %0" STRINGIFY(HASH_HEX_DIGITS) PRIx32 "\n", try_crc);
    }
  }

  free(buf);
  return EXIT_SUCCESS;
}

Makefile

CFLAGS ?= -std=c99 -D_FORTIFY_SOURCE=2 -Wall -Wextra -Wpedantic -Wformat=2 -flto -O3 -DNEBUG

build: find-crc32-worker

find-crc32-worker: find-crc32-worker.c Makefile
	$(CC) $(CFLAGS) -lz $< -o $@
  
clean:
	rm -f find-crc32-worker