Program to find crc32 collision, generates output like: `Hello, my hash is: 1A745BD7! :)`

crc32_quine.cpp

// To compile:
// nvcc -O3 -Xcompiler -openmp crc32_quine.cpp -o crc32_quine

// Inspired by: https://gist.github.com/praetoriansentry/03b6dc2e68e174ffd8168aef7d85f910
// (Can be timed with: http://www.pc-tools.net/win32/ptime/)
// (Was not able to make it faster than the insiration, golang is impressive.)

#include <stdio.h>  // printf, sprintf
#include "Crc32.cpp" // From: https://github.com/stbrumme/crc32

#if defined(_WIN32) || defined(_WIN64)
#include <windows.h>
#else
#include <ctime>
#endif

// timing
static double seconds() {
#if defined(_WIN32) || defined(_WIN64)
  LARGE_INTEGER frequency, now;
  QueryPerformanceFrequency(&frequency);
  QueryPerformanceCounter  (&now);
  return now.QuadPart / double(frequency.QuadPart);
#else
  timespec now;
  clock_gettime(CLOCK_REALTIME, &now);
  return now.tv_sec + now.tv_nsec / 1000000000.0;
#endif
}

// Based on: https://stackoverflow.com/questions/63471522/how-to-replace-a-substring-in-a-string
char *replaceAll(char *source_str, const char *pattern, const char *replacement) {
  const size_t n3 = 8;
  char *match = strstr(source_str, pattern);
  char *result;
  bool found = false;
  while (match != NULL) {
    size_t len = strlen(source_str);
    size_t n1 = match - source_str;   // # bytes before the match
    size_t n2 = strlen(pattern);      // # bytes in the pattern string
    //size_t n3 = strlen(replacement);  // # bytes in the replacement string
    size_t n4 = len - n1 - n2;        // # bytes after the pattern in the source string
    result = (char*)malloc(n1 + n3 + n4 + 1);
    if (result != NULL) {
      memcpy(result, source_str, n1);               // copy the initial portion
      memcpy(result + n1, replacement, n3);         // copy the replacement string
      memcpy(result + n1 + n3, match + n2, n4 + 1); // copy the trailing bytes, including the null terminator
    }
    if (found) { // don't free the original input string
      free(source_str);
    }
    source_str = result;
    match = strstr(source_str + n1 + n3, pattern); // skip looking at parts of the string we already checked (no meta-templating)
    found = true;
  }
  if (!found) {
    return strdup(source_str); // always return an allocated string
  }
  return result;
}

int main(int argc, char* argv[]) {
  char *str = "Hello, my hash is: {{crc32}}! :)";
  char *out = NULL;
  unsigned int out_crc = 0;
  bool done = false;
  double startTime = seconds();

  if (argc > 1)
    str = argv[1];

#pragma omp parallel default(none) firstprivate(str, startTime) shared(done, out, out_crc)
{
  uint32_t crc;
  char *str_crc = new char[8];
  char *str_crc2 = new char[8];
// Using all cores actually slows it down!
#pragma omp for schedule(dynamic, 8)
  for (long long i = 0; i <= 4294967295; i++) {
    if (done) {
      break;
    }
    sprintf(str_crc, "%08X", (unsigned int)i);
    char *ret = replaceAll(str, "{{crc32}}", str_crc);
    crc = crc32_16bytes(ret, strlen(ret));
    sprintf(str_crc2, "%08X", crc);
    if (i == crc) {
      done = true;
      out = ret;
      out_crc = crc;
      break;
    }
    if (i % (long long)1e7 == 0) {
      double dur = seconds() - startTime;
      printf("str=%s, CRC=%s, %u, %.2fs, %.2f Mhashes/s\n", ret, str_crc2, (unsigned int)i, dur, (unsigned int)i / dur / 1e6);
    }
    free(ret);
  }
}

  double duration = seconds() - startTime;
  if (out != NULL) {
    printf("str=%s, CRC=%08X, iter=%u, %.2fs, %.2f Mhashes/s\n", out, out_crc, out_crc, duration, out_crc / duration / 1e6);
  } else
    printf("Finished without finding a collision in %.2fs. %.2f Mhashes/s\n", duration, out_crc / duration / 1e6);

  return 0;
}

crc32_quine.js

// CRC32 hashing and hex conversion based on: https://create.stephan-brumme.com/crc32/
function hex(what)
{
  // adjust negative numbers
  if (what < 0)
    what = 0xFFFFFFFF + what + 1;
  // convert to hexadecimal string
  var result = what.toString(16).toUpperCase();
  // add leading zeros
  return ('0000000' + result).slice(-8);
}

function crc32_bitwise(text)
{
  // CRC32b polynomial
  var Polynomial = 0xEDB88320;
  // start value
  var crc = 0xFFFFFFFF;

  for (var i = 0; i < text.length; i++)
  {
    // XOR next byte into state
    crc ^= text.charCodeAt(i);

    // process 8 bits
    for (var bit = 0; bit < 8; bit++)
    {
      // look at lowest bit
      if ((crc & 1) != 0)
        crc = (crc >>> 1) ^ Polynomial;
      else
        crc =  crc >>> 1;
    }
  }

  // return hex string
  return hex(~crc);
}

// Based on: https://www.tutorialspoint.com/split-a-range-of-number-to-a-specific-number-of-intervals-javascript
function getIntervals(interval, n)
{
  const size = Math.floor(interval / n) || 1;
  const res = [];
  for (let i = 0; i <= interval; i += size) {
    const a = (i == 0) ? i : (i += 1);
    const b = ((i + size) > interval) ? interval : (i + size);
    if (a < interval)
      res.push([a, b]);
  }
  return res;
}

// Based on: https://gist.github.com/praetoriansentry/03b6dc2e68e174ffd8168aef7d85f910#file-main-go
// and: https://github.com/hdf/clusters/blob/master/www/static/func.js
function hash_quine(str, placeholder = "{{crc32}}", hasher = crc32_bitwise, hash_bits = 32)
{
  const keyspace = Math.pow(2, hash_bits) - 1;
  var msg = "";
  //const cores = ((typeof(os) != 'undefined')?os.cpus().length:navigator.hardwareConcurrency || 2);
  const cores = 4; // On a 6 core, 12 thread Ryzen, using only 4 workers gives twice the performance as using 12 for some reason...
  const intervals = getIntervals(keyspace, cores);
  var start = performance.now();
  var workers = [];
  var checked = [];

  function func() {
    var id = Math.floor(Math.random() * 9999); // Random worker id if not specified
    if (typeof(asmjs) == 'function') asmjs();
    onmessage = function(e) {
      if (typeof(e.data.id) == 'number') // Assign worker id
        id = e.data.id;
      if (typeof(e.data.from) == 'number' && typeof(e.data.to) == 'number') {
        for (let i = e.data.to; i >= e.data.from; i--) {
          let hash = hex(i);
          let ret = e.data.str.replaceAll(e.data.placeholder, hash);
          if (hashers[e.data.hasher](ret) == hash) {
            postMessage({id: id, found: true, checked: (e.data.to - i), done: true, res: ret});
            return;
          }
          if ((i % 1e6) == 0)
            postMessage({id: id, found: false, checked: (e.data.to - i), done: false});
        }
        postMessage({id: id, found: false, checked: (e.data.to - e.data.from), done: true});
      }
    };
  }

  function stopWorkers() {
    for (let i = 0, n = workers.length; i < n; i++)
      workers[i].terminate();
    workers = [];
    checked = [];
  }

  stopWorkers();
  // Create worker content as blob
  var blob = new Blob(
    [
      hex.toString() + '\n\n' +
      'var hashers = {\n  crc32_bitwise: ' + crc32_bitwise.toString() + '\n};\n\n' +
      func.toString() + '\nfunc();'
    ], {type: 'text/javascript'});
  var code = URL.createObjectURL(blob);
  for (let i = 0; i < cores; i++) {
    checked[i] = 0;
    workers[i] = new Worker(code);
    workers[i].onmessage = function(e) {
      checked[e.data.id] = e.data.checked;
      const total_checked = checked.reduce((partialSum, a) => partialSum + a, 0);
      if (e.data.done && e.data.found) {
        console.log("Found a solution after " + total_checked + ' tries.');
        console.log(e.data.res);
        stopWorkers();
      }
      if (e.data.done && (!e.data.found) && total_checked == keyspace) {
        console.log("Finished without finding a collision.");
        stopWorkers();
      }
      if (!e.data.done) {
        let new_msg = "Processing at " + (total_checked / keyspace * 100).toFixed(2) + "%...";
        if (new_msg != msg){
          msg = new_msg;
          console.log(msg);
		  let elapsed = performance.now() - start;
          console.log("(Already tried " + total_checked.toString() + " hashes (" + (total_checked / (elapsed / 1000)).toFixed(0) + " hashes/sec).)");
        }
      }
    };
    workers[i].postMessage({
      id: i,
      from: intervals[i][0],
      to: intervals[i][1],
      str: str,
      placeholder: placeholder,
      hasher: hasher.name
    }); // Assign worker an id
  }
  return "Started search on " + cores + " cores...";

  // Single thread version (unreachable code):
  for (let i = keyspace; i >= 0; i--) {
    let hash = hex(i);
    let ret = str.replaceAll(placeholder, hash);
    if (hasher(ret) == hash)
      return ret;

    let new_msg = "Processing at " + ((keyspace - i) / keyspace * 100).toFixed(2) + "%...";
    if ((i % 1000000) == 0 && new_msg != msg){
      msg = new_msg;
      console.log(msg);
	  let elapsed = performance.now() - start;
      console.log("(Already tried " + (keyspace - i).toString() + " hashes (" + ((keyspace - i) / (elapsed / 1000)).toFixed(0) + " hashes/sec).)");
    }
  }
  return "Finished without finding a collision.";
}

console.log(hash_quine("Hello, my hash is: {{crc32}}! :)"));

crc32_quine_go.go

package main

import (
	"encoding/binary"
	"fmt"
	"hash/crc32"
	"os"
	"runtime"
	"strconv"
	"strings"
	"sync"
)

var routines uint32 = 8

func isPrint(s []byte) bool {
	for i := 0; i < len(s); i++ {
		if s[i] < 32 || s[i] > 126 {
			return false
		}
	}
	return true
}

func main() {
	runtime.GOMAXPROCS(int(routines))

	var wg sync.WaitGroup

	var i uint32
	old_status := 0.0
	for i = 0; i < routines; i = i + 1 {
		wg.Add(1)
		go func(buc uint32) {
			baseTemplateString := "Hello, my hash is: {{crc32}}! :)"
			desiredCRC := ""
			var desiredDEC uint64
			var cmp uint32
			if len(os.Args) > 1 {
				baseTemplateString = os.Args[1]
			}
			if len(os.Args) > 2 {
				desiredCRC = os.Args[2]
				desiredDEC, _ = strconv.ParseUint(desiredCRC, 16, 32)
			}
			parts := strings.Split(baseTemplateString, "{{crc32}}")
			var pad uint32 = 0
			pad_bytes := make([]byte, 4)
			for {
				pad += 1
				if pad == 0 {
					wg.Done()
					break
				}
				if pad%routines != buc {
					continue
				}
				cmp = pad
				var curQuine string
				if desiredCRC != "" { // We are looking for a forced hash!
					binary.LittleEndian.PutUint32(pad_bytes, pad)
					/*if !isPrint(pad_bytes) {
						continue
					}*/
					cmp = uint32(desiredDEC)
					if len(os.Args) > 3 {
						curQuine = strings.Join(parts, fmt.Sprintf("%08X", pad))
					} else {
						curQuine = strings.Join(parts, string(pad_bytes))
					}
				} else {
					curQuine = strings.Join(parts, fmt.Sprintf("%08X", pad))
				}
				cksum := crc32.ChecksumIEEE([]byte(curQuine))
				if cksum == cmp {
					fmt.Printf("Found dec: %d hex: %08X quine: %s\n", cmp, cmp, curQuine)
					//break
				}

				if len(os.Args) != 3 { // Repeat for lower case if we are not looking for a 4 byte solution.
					if desiredCRC != "" {
						if len(os.Args) > 3 {
							curQuine = strings.Join(parts, fmt.Sprintf("%08x", pad))
						}
					} else {
						curQuine = strings.Join(parts, fmt.Sprintf("%08x", pad))
					}
					cksum = crc32.ChecksumIEEE([]byte(curQuine))
					if cksum == cmp {
						fmt.Printf("Found dec: %d hex: %08X quine: %s\n", cmp, cmp, curQuine)
					}
				}

				new_status := float64(pad) / 4294967294 * 100
				if new_status >= old_status+0.1 || pad >= 4294967294 {
					old_status = new_status
					fmt.Printf("\r%.1f%% ", new_status)
				}
				/*if pad%1e7 == 0 {
					fmt.Printf("%d: %s", pad, curQuine)
				}*/
			}
		}(i)
	}
	wg.Wait()
	fmt.Println("Finished searching for collisions.")
}

Output:

crc32_quine_go "{{crc32}}"
19.9% Found dec: 854832951 hex: 32F3B737 quine: 32F3B737
100.0% Finished searching for collisions.

crc32_quine_go "{{crc32}}" "deadbeef"
2.4% Found dec: 3735928559 hex: DEADBEEF quine: ��$♠
100.0% Finished searching for collisions.

crc32_quine_go "{{crc32}}" "deadbeef" 1
10.4% Found dec: 3735928559 hex: DEADBEEF quine: 1ABCAB53
56.0% Found dec: 3735928559 hex: DEADBEEF quine: 8f88fd8a
78.7% Found dec: 3735928559 hex: DEADBEEF quine: C99606ED
82.7% Found dec: 3735928559 hex: DEADBEEF quine: d3e6969b
90.9% Found dec: 3735928559 hex: DEADBEEF quine: E8B1E6C2
100.0% Finished searching for collisions.

crc32_quine_go
10.3% Found dec: 443833303 hex: 1A745BD7 quine: Hello, my hash is: 1A745BD7! :)
21.6% Found dec: 925562677 hex: 372AF735 quine: Hello, my hash is: 372af735! :)
55.6% Found dec: 2389256129 hex: 8E6927C1 quine: Hello, my hash is: 8e6927c1! :)
61.3% Found dec: 2624772843 hex: 9C72DAEB quine: Hello, my hash is: 9C72DAEB! :)
85.9% Found dec: 3687246397 hex: DBC6EA3D quine: Hello, my hash is: DBC6EA3D! :)
100.0% Finished searching for collisions.

crc32_quine_go "Hello, my hash is: {{crc32}}! :)" "deadbeef" 1
0.1% Found dec: 3735928559 hex: DEADBEEF quine: Hello, my hash is: 0052670a! :)
84.0% Found dec: 3735928559 hex: DEADBEEF quine: Hello, my hash is: D70D463D! :)
100.0% Finished searching for collisions.

Related:

https://blog.stalkr.net/2011/03/crc-32-forging.html
https://www.nayuki.io/page/forcing-a-files-crc-to-any-value
https://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art008