https://blog.lixtelnis.com/weakhash/

weakhash.cpp

//-O2 -std=c++17 -lpthread -lcrypto
// 4 GB - 1 hour
#include <openssl/des.h>
#include <iostream>
#include <vector>
#include <cstring>
#include <thread>

constexpr uint64_t flip_endian(uint64_t x) {
	return __builtin_bswap64(x);
}

uint64_t start = flip_endian(0x7765616B68617368);
uint64_t end = flip_endian(0xda99d1ea64144f3e);

#define N_TARGET (1ul << 32)
#define N_TOT (N_TARGET << 2)
#define N_BYTE (N_TOT >> 2)
#define MAX_DEPTH 30
#define MASK_FULL (N_TOT - 1)
#define MASK_2 0x3
std::vector<uint8_t> targets(N_BYTE,0);
std::vector<uint64_t> key_set(3);

// Usage:
// SpeedMeasurer speed;
// // ...
// speed.measure(items_processed);
// // ...
// cout << speed;
struct SpeedMeasurer {
	std::chrono::high_resolution_clock::time_point start;
	uint64_t items;
	SpeedMeasurer() : start{std::chrono::high_resolution_clock::now()}, items{0} {}
	void measure(uint64_t items_processed) { items += items_processed; }
	double items_per_second() const {
		const auto stop = std::chrono::high_resolution_clock::now();
		using seconds_t = std::chrono::duration<double, std::chrono::seconds::period>;
		const seconds_t seconds = stop - start;
		return static_cast<double>(items) / seconds.count();
	}
};
std::ostream& operator<<(std::ostream& os, const SpeedMeasurer& speed) {
	os << speed.items_per_second() << "/s";
	return os;
}

uint64_t encrypt(uint64_t hash, uint64_t key) {
	DES_key_schedule ks;
	uint64_t output;
	DES_set_key_unchecked((DES_cblock*)&key, &ks);
	DES_ecb_encrypt((DES_cblock*)&hash, (DES_cblock*)&output, &ks, 1);
	return output;
}

uint64_t decrypt(uint64_t hash, uint64_t key) {
	DES_key_schedule ks;
	uint64_t output;
	DES_set_key_unchecked((DES_cblock*)&key, &ks);
	DES_ecb_encrypt((DES_cblock*)&hash, (DES_cblock*)&output, &ks, 0);
	return output;
}

uint64_t get(uint64_t t) {
	uint64_t ind = t&MASK_FULL;
	return (targets[ind>>2]>>((ind&MASK_2)<<1))&MASK_2;
}

void add(uint64_t t, uint64_t i) {
	uint64_t ind = t&MASK_FULL;
	targets[ind>>2] |= i<<((ind&MASK_2)<<1);
}

uint64_t counter_to_key(uint64_t n) {
	constexpr int INPUT_BYTES = 7;
	constexpr int INPUT_BYTE_BITS = 7;
	constexpr int BITS_MASK = (1 << INPUT_BYTE_BITS) - 1;
	constexpr int BYTE_BITS = 8;
	uint64_t key = 0;
	for (uint64_t i = 0; i < INPUT_BYTES; ++i) {
		const uint64_t input_shift = i * INPUT_BYTE_BITS;
		const uint64_t byte_mask = BITS_MASK << input_shift;
		const uint64_t input_byte = (n & byte_mask) >> input_shift;
		const uint64_t output_byte = input_byte << 1; // ignore last bit
		const uint64_t output_shift = i * BYTE_BITS;
		key |= output_byte << output_shift;
	}
	return key;
}

uint64_t rand64() {
	return ((uint64_t)rand() << 32) | rand();
}

void expand() {
	struct entry_t {uint64_t val; uint64_t lvl;};
	std::vector<struct entry_t> to_expand;
	uint64_t ctr = 0;
	while (ctr < N_TARGET) {
		for (uint64_t ki = 0; ki < key_set.size(); ++ki) {
			key_set[ki] = rand64();
		}

		to_expand.push_back({.val = end, .lvl = 0});
		while (to_expand.size() != 0 and ctr < N_TARGET) {
			struct entry_t target = to_expand.back();
			to_expand.pop_back();
			if (target.lvl == MAX_DEPTH) {
				continue;
			}
			for (uint64_t ki = 0; ki < key_set.size(); ++ki) {
				uint64_t key = key_set[ki];
				uint64_t new_target = decrypt(target.val, key);

				if (get(new_target) == 0) {
					add(new_target, ki + 1);
					to_expand.push_back({.val = new_target, .lvl = target.lvl + 1});
					ctr += 1;
				}
			}
		}
		if (ctr < N_TARGET) {
			std::cout << "only got " << ctr << " targets of " << N_TARGET << std::endl
			<< "restarting with new keys" << std::endl;
			std::fill(targets.begin(), targets.end(), 0);
			ctr = 0;
		}
	}
}

uint64_t is_valid_path(uint64_t k1, std::vector<uint64_t>& sol) {
	uint64_t cur = encrypt(start, k1);
	for (uint64_t i = 0; i < MAX_DEPTH; ++i) {
		uint64_t entry = get(cur);
		if (entry == 0) {
			break;
		}
		sol[i] = entry - 1;
		uint64_t k = key_set[entry - 1];
		cur = encrypt(cur, k);
		if (cur == end) {
			return i + 1;
		}
	}
	return 0;
}

void search_collision(uint64_t start, uint64_t steps) {
	std::vector<uint64_t> sol(MAX_DEPTH);
	for (uint64_t counter = start; counter < start + steps; ++counter) {
		uint64_t key = counter_to_key(counter);
		uint64_t len = is_valid_path(key, sol);
		if (len != 0) {
			std::cout << "done. first key is " << key << std::endl;
			for (uint64_t j = 0; j < len; ++j) {
				std::cout << sol[j] << ","; 
			}
			std::cout << std::endl;
			exit(0);
		}
	}
}

void find_collision(const int num_threads, const int show_progress_every) {
	const uint64_t steps = show_progress_every / num_threads;
	uint64_t counter = 0;
	while (true) {
		SpeedMeasurer speed;
		std::vector<std::thread> threads;
		for (int thread = 0; thread < num_threads; ++thread) {
			auto search_thread = [counter, steps]() {
				search_collision(counter, steps);
			};
			threads.emplace_back(search_thread);
			counter += steps;
			speed.measure(steps);
		}
		for (auto& thread : threads) {
			thread.join();
		}
		std::cout << "    processed " << counter << " " << speed << std::endl;
	}
}

int main() {
	srand(time(0));

	std::cout << "forward step" << std::endl;
	expand();

	std::cout << "keys are" << std::endl;
	for (uint64_t ki = 0; ki < key_set.size(); ++ki) {
		std::cout << key_set[ki] << std::endl;
	}

	std::cout << "backward step" << std::endl;
	find_collision(1,50000000);

	return 1;
}

weakhash2.cpp

//-O2 -std=c++17 -lpthread -lcrypto
// 4 GB - 1 hour
#include <openssl/des.h>
#include <iostream>
#include <vector>
#include <cstring>
#include <thread>

constexpr uint64_t flip_endian(uint64_t x) {
	return __builtin_bswap64(x);
}

uint64_t start = flip_endian(0x7765616B68617368);
uint64_t end = flip_endian(0xda99d1ea64144f3e);

#define N_TARGET (1ul << 32)
#define N_TOT (N_TARGET << 3)
#define N_BYTE (N_TOT >> 3)
#define MAX_DEPTH 30
#define MASK_FULL (N_TOT - 1)
#define MASK_3 0x7
std::vector<uint8_t> targets(N_BYTE,0);
std::vector<uint64_t> key_set(3);

// Usage:
// SpeedMeasurer speed;
// // ...
// speed.measure(items_processed);
// // ...
// cout << speed;
struct SpeedMeasurer {
	std::chrono::high_resolution_clock::time_point start;
	uint64_t items;
	SpeedMeasurer() : start{std::chrono::high_resolution_clock::now()}, items{0} {}
	void measure(uint64_t items_processed) { items += items_processed; }
	double items_per_second() const {
		const auto stop = std::chrono::high_resolution_clock::now();
		using seconds_t = std::chrono::duration<double, std::chrono::seconds::period>;
		const seconds_t seconds = stop - start;
		return static_cast<double>(items) / seconds.count();
	}
};
std::ostream& operator<<(std::ostream& os, const SpeedMeasurer& speed) {
	os << speed.items_per_second() << "/s";
	return os;
}

uint64_t encrypt(uint64_t hash, uint64_t key) {
	DES_key_schedule ks;
	uint64_t output;
	DES_set_key_unchecked((DES_cblock*)&key, &ks);
	DES_ecb_encrypt((DES_cblock*)&hash, (DES_cblock*)&output, &ks, 1);
	return output;
}

uint64_t decrypt(uint64_t hash, uint64_t key) {
	DES_key_schedule ks;
	uint64_t output;
	DES_set_key_unchecked((DES_cblock*)&key, &ks);
	DES_ecb_encrypt((DES_cblock*)&hash, (DES_cblock*)&output, &ks, 0);
	return output;
}

uint64_t get(uint64_t t) {
	uint64_t ind = t&MASK_FULL;
	return (targets[ind>>3]>>(ind&MASK_3))&1;
}

void add(uint64_t t) {
	uint64_t ind = t&MASK_FULL;
	targets[ind>>3] |= 1<<(ind&MASK_3);
}

uint64_t counter_to_key(uint64_t n) {
	constexpr int INPUT_BYTES = 7;
	constexpr int INPUT_BYTE_BITS = 7;
	constexpr int BITS_MASK = (1 << INPUT_BYTE_BITS) - 1;
	constexpr int BYTE_BITS = 8;
	uint64_t key = 0;
	for (uint64_t i = 0; i < INPUT_BYTES; ++i) {
		const uint64_t input_shift = i * INPUT_BYTE_BITS;
		const uint64_t byte_mask = BITS_MASK << input_shift;
		const uint64_t input_byte = (n & byte_mask) >> input_shift;
		const uint64_t output_byte = input_byte << 1; // ignore last bit
		const uint64_t output_shift = i * BYTE_BITS;
		key |= output_byte << output_shift;
	}
	return key;
}

uint64_t rand64() {
	return ((uint64_t)rand() << 32) | rand();
}

void expand() {
	struct entry_t {uint64_t val; uint64_t lvl;};
	std::vector<struct entry_t> to_expand;
	uint64_t ctr = 0;
	while (ctr < N_TARGET) {
		for (uint64_t ki = 0; ki < key_set.size(); ++ki) {
			key_set[ki] = rand64();
		}

		to_expand.push_back({.val = end, .lvl = 0});
		while (to_expand.size() != 0 and ctr < N_TARGET) {
			struct entry_t target = to_expand.back();
			to_expand.pop_back();
			if (target.lvl == MAX_DEPTH) {
				continue;
			}
			for (uint64_t ki = 0; ki < key_set.size(); ++ki) {
				uint64_t key = key_set[ki];
				uint64_t new_target = decrypt(target.val, key);

				if (get(new_target) == 0) {
					add(new_target);
					to_expand.push_back({.val = new_target, .lvl = target.lvl + 1});
					ctr += 1;
				}
			}
		}
		if (ctr < N_TARGET) {
			std::cout << "only got " << ctr << " targets of " << N_TARGET << std::endl
			<< "restarting with new keys" << std::endl;
			std::fill(targets.begin(), targets.end(), 0);
			ctr = 0;
		}
	}
}

std::vector<uint64_t> is_valid_path(uint64_t k1) {
	struct entry_t {uint64_t val; uint64_t lvl; std::vector<uint64_t> path;};

	std::vector<uint64_t> empty;
	uint64_t cur = encrypt(start, k1);
	if (get(cur) == 0) {
		return empty;
	}

	std::vector<struct entry_t> to_expand;
	to_expand.push_back({.val = cur, .lvl = 0});
	while (to_expand.size() != 0) {
		struct entry_t target = to_expand.back();
		to_expand.pop_back();
		if (target.lvl == MAX_DEPTH) {
			continue;
		}
		for (uint64_t ki = 0; ki < key_set.size(); ++ki) {
			uint64_t key = key_set[ki];
			uint64_t new_target = encrypt(target.val, key);
			if (new_target == end) {
				target.path.push_back(ki);
				return target.path;
			}

			if (get(new_target) == 1) {
				to_expand.push_back({.val = new_target, .lvl = target.lvl + 1, .path = target.path});
				to_expand.back().path.push_back(ki);
			}
		}
	}
	return empty;
}

void search_collision(uint64_t start, uint64_t steps) {
	for (uint64_t counter = start; counter < start + steps; ++counter) {
		uint64_t key = counter_to_key(counter);
		std::vector<uint64_t> sol = is_valid_path(key);
		if (sol.size() != 0) {
			std::cout << "done. first key is " << key << std::endl;
			for (uint64_t j = 0; j < sol.size(); ++j) {
				std::cout << sol[j] << ","; 
			}
			std::cout << std::endl;
			exit(0);
		}
	}
}

void find_collision(const int num_threads, const int show_progress_every) {
	const uint64_t steps = show_progress_every / num_threads;
	uint64_t counter = 0;
	while (true) {
		SpeedMeasurer speed;
		std::vector<std::thread> threads;
		for (int thread = 0; thread < num_threads; ++thread) {
			auto search_thread = [counter, steps]() {
				search_collision(counter, steps);
			};
			threads.emplace_back(search_thread);
			counter += steps;
			speed.measure(steps);
		}
		for (auto& thread : threads) {
			thread.join();
		}
		std::cout << "    processed " << counter << " " << speed << std::endl;
	}
}

int main() {
	srand(time(0));

	std::cout << "forward step" << std::endl;
	expand();

	std::cout << "keys are" << std::endl;
	for (uint64_t ki = 0; ki < key_set.size(); ++ki) {
		std::cout << key_set[ki] << std::endl;
	}

	std::cout << "backward step" << std::endl;
	find_collision(1,50000000);

	return 1;
}