Project Nayuki


Lowest SHA-512 value by brute force

Lowest SHA-512 program running screenshot

I encountered a competition to find an ASCII string with a SHA-512 hash value as low as possible (or the most number of leading zeros). So I accepted the challenge and built a brute-force search program in C, based on my fast SHA-512 implementation in x86-64 assembly. Additionally, I rewrote SHA-512 in vectorized form to do dual and quad SHA-512 hashing using x86 AVX instructions, and implemented multithreading with pthreads.

Source code

C + x86-64 AVX (dual SHA-512)

Download: lowest-sha512-dual-pthread.c, sha512-64-avx.S

Compile: gcc -pthread -O1 lowest-sha512-dual-pthread.c sha512-64-avx.S -o lowest-sha512-dual-pthread

This uses the 128-bit XMM registers to compute two simultaneous instances of the SHA-512 hash function per thread. The program prints abbreviated hashes to standard error and full hashes to standard output (intended for logging).

C + x86-64 AVX2 (quad SHA-512)

Download: lowest-sha512-quad-pthread.c, sha512-64-avx2.S

Compile: gcc -pthread -O1 lowest-sha512-quad-pthread.c sha512-64-avx2.S -o lowest-sha512-quad-pthread

This uses the 256-bit YMM registers to compute four simultaneous instances of the SHA-512 hash function per thread. The program prints abbreviated hashes to standard error and full hashes to standard output (intended for logging).

C (portable)

Download: lowest-sha512.c

Compile: gcc -O1 lowest-sha512.c -o lowest-sha512

This C code is portable, not depending on the x86 machine architecture and forgoes multithreading. Though it’s not very fast, the code illustrates my core ideas involed in this brute-force hashing program and contains fewer minute details than the optimized versions.

Python

Download: lowest-sha512.py

This highly simplified program demonstrates the core of what the C programs are doing. The program prints abbreviated hashes to standard output only. Compatible with Python 2 and 3.

Notes