vsCTF 2022 - NIST Finalist: Revisited (Intended solution: https://github.com/sahuang/my-ctf-challenges/tree/main/vsctf-2022/Crypto/NIST%20Finalist%20Revisited/Solution)

collision1.cpp

#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define rotr(val, r) ((val >> r) | ((val & (1L << r) - 1) << (64 - r)))
typedef unsigned long uint64;

void printhex(char *buf, size_t len) {
	for (size_t i = 0; i < len; i++)
		printf("%02hhx", buf[i]);
	printf("\n");
}
void printstate(uint64 *S) {
	printf("[");
	for (int i = 0; i < 4; i++) {
		printf("%lu, ", S[i]);
	}
	printf("%lu]\n", S[4]);
}
void ascon_permutation(uint64 *S, int rounds) {
	for (uint64 r = 12 - rounds; r < 12; r++) {
		S[2] ^= (0xf0 - r * 0x10 + r * 0x1);
		S[0] ^= S[4];
		S[4] ^= S[3];
		S[2] ^= S[1];
		uint64 T[5];
		for (int i = 0; i < 5; i++)
			T[i] = (S[i] ^ 0xFFFFFFFFFFFFFFFF) & S[(i + 1) % 5];
		for (int i = 0; i < 5; i++)
			S[i] ^= T[(i + 1) % 5];
		S[1] ^= S[0];
		S[0] ^= S[4];
		S[3] ^= S[2];
		S[2] ^= 0XFFFFFFFFFFFFFFFF;
		S[0] ^= rotr(S[0], 19) ^ rotr(S[0], 28);
		S[1] ^= rotr(S[1], 61) ^ rotr(S[1], 39);
		S[2] ^= rotr(S[2], 1) ^ rotr(S[2], 6);
		S[3] ^= rotr(S[3], 10) ^ rotr(S[3], 17);
		S[4] ^= rotr(S[4], 7) ^ rotr(S[4], 41);
	}
}
char tmpbuf[1024];
void ascon_xor(char *out, char *message, int len) {
	int a = 2;
	int b = 2;
	int rate = 8;
	int hashlength = 8;
	char buf[40] = {};
	buf[1] = rate * 8;
	buf[2] = a;
	buf[3] = a - b;
	uint64 *S = (uint64 *)buf;
	S[0] = __builtin_bswap64(S[0]);

	ascon_permutation(S, a);

	memset(tmpbuf, 0, 1024);
	memcpy(tmpbuf, message, len);
	tmpbuf[len] = 0x80;
	int pad = 8 - len % 8;
	int padded_len = len + pad;

	int block = 0;
	for (; block < padded_len - rate; block += rate) {
		S[0] ^= __builtin_bswap64(*(uint64 *)(&tmpbuf[block]));
		ascon_permutation(S, b);
	}
	block = padded_len - rate;
	S[0] ^= __builtin_bswap64(*(uint64 *)(&tmpbuf[block]));

	ascon_permutation(S, a);
	int lenh = 0;
	while (lenh < hashlength) {
		long x = __builtin_bswap64(S[0]);
		memcpy(out, &x, 8);
		ascon_permutation(S, b);
		out += 8;
		lenh += 8;
	}
}
int main(int argc, char **argv) {
	if (argc < 2) {
		return 1;
	}
	uint64 init = atol(argv[1]);
	uint64 x = init, y = init, i = 0;
	do {
		i += 1;
		ascon_xor((char *)&x, (char *)&x, 8);
		ascon_xor((char *)&y, (char *)&y, 8);
		ascon_xor((char *)&y, (char *)&y, 8);
	} while (x != y);
	printf("Cycle found: %lu\n", i);
	// x is H^{i}(0), y is H^{2i}(0)
	// lets reset y back to initial value 0
	// using the algorithm from https://crypto.stackexchange.com/questions/3295/how-does-a-birthday-attack-on-a-hashing-algorithm-work
	y = init;
	uint64 nx = 0, ny = 0;
	for (int j = 0; j < i; j++) {
		ascon_xor((char *)&nx, (char *)&x, 8);
		ascon_xor((char *)&ny, (char *)&y, 8);
		if (nx == ny) {
			// small endian
			printf("Collision H(%lu)=H(%lu)=%lu\n", x, y, nx);
			break;
		}
		x = nx;
		y = ny;
	}
	return 0;
}
// core idea: https://sasdf.github.io/ctf/tasks/2021/BalsnCTF/crypto/trinity/
// g++ collision1.cpp -o collision1 -Ofast -march=native
// for i in $(seq 1234 1237); do ./collision1 $i & ; done
// H(8456266087073398779)=H(109564132703872653)=10938621401135978759
// H(337177861726909608)=H(8818851373910443600)=12688908957086049150

collision2.cpp

#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define rotr(val, r) ((val >> r) | ((val & (1L << r) - 1) << (64 - r)))
typedef unsigned long uint64;

void printhex(char *buf, size_t len) {
	for (size_t i = 0; i < len; i++)
		printf("%02hhx", buf[i]);
	printf("\n");
}
void printstate(uint64 *S) {
	printf("[");
	for (int i = 0; i < 4; i++) {
		printf("%lu, ", S[i]);
	}
	printf("%lu]\n", S[4]);
}
void ascon_permutation(uint64 *S, int rounds) {
	for (uint64 r = 12 - rounds; r < 12; r++) {
		S[2] ^= (0xf0 - r * 0x10 + r * 0x1);
		S[0] ^= S[4];
		S[4] ^= S[3];
		S[2] ^= S[1];
		uint64 T[5];
		for (int i = 0; i < 5; i++)
			T[i] = (S[i] ^ 0xFFFFFFFFFFFFFFFF) & S[(i + 1) % 5];
		for (int i = 0; i < 5; i++)
			S[i] ^= T[(i + 1) % 5];
		S[1] ^= S[0];
		S[0] ^= S[4];
		S[3] ^= S[2];
		S[2] ^= 0XFFFFFFFFFFFFFFFF;
		S[0] ^= rotr(S[0], 19) ^ rotr(S[0], 28);
		S[1] ^= rotr(S[1], 61) ^ rotr(S[1], 39);
		S[2] ^= rotr(S[2], 1) ^ rotr(S[2], 6);
		S[3] ^= rotr(S[3], 10) ^ rotr(S[3], 17);
		S[4] ^= rotr(S[4], 7) ^ rotr(S[4], 41);
	}
}
char tmpbuf[1024];
void ascon_xor(char *out, char *message, int len) {
	int a = 2;
	int b = 2;
	int rate = 8;
	int hashlength = 8;
	char buf[40] = {};
	buf[1] = rate * 8;
	buf[2] = a;
	buf[3] = a - b;
	uint64 *S = (uint64 *)buf;
	S[0] = __builtin_bswap64(S[0]);

	ascon_permutation(S, a);

	memset(tmpbuf, 0, 1024);
	memcpy(tmpbuf, message, len);
	tmpbuf[len] = 0x80;
	int pad = 8 - len % 8;
	int padded_len = len + pad;

	int block = 0;
	for (; block < padded_len - rate; block += rate) {
		S[0] ^= __builtin_bswap64(*(uint64 *)(&tmpbuf[block]));
		ascon_permutation(S, b);
	}
	block = padded_len - rate;
	S[0] ^= __builtin_bswap64(*(uint64 *)(&tmpbuf[block]));

	ascon_permutation(S, a);
	int lenh = 0;
	while (lenh < hashlength) {
		long x = __builtin_bswap64(S[0]);
		memcpy(out, &x, 8);
		ascon_permutation(S, b);
		out += 8;
		lenh += 8;
	}
}
int main(int argc, char **argv) {
	if (argc < 2) {
		return 1;
	}
	const uint64 suffix = 0x6e696d6461;  // 0x61646d696eL;
	uint64 init = atol(argv[1]);
	uint64 x[2] = {init, suffix};
	uint64 y[2] = {init, suffix}, i = 0;
	do {
		i += 1;
		ascon_xor((char *)&x[0], (char *)x, 13);
		ascon_xor((char *)&y[0], (char *)y, 13);
		ascon_xor((char *)&y[0], (char *)y, 13);
	} while (x[0] != y[0]);
	printf("Cycle found: %lu\n", i);
	// x is H^{i}(0), y is H^{2i}(0)
	// lets reset y back to initial value 0
	// using the algorithm from https://crypto.stackexchange.com/questions/3295/how-does-a-birthday-attack-on-a-hashing-algorithm-work
	y[0] = init;
	uint64 nx = 0, ny = 0;
	for (int j = 0; j < i; j++) {
		ascon_xor((char *)&nx, (char *)&x, 13);
		ascon_xor((char *)&ny, (char *)&y, 13);
		if (nx == ny) {
			// small endian
			printf("Collision H(%lu|suffix)=H(%lu|suffix)=%lu\n", x[0], y[0],
			       nx);
			break;
		}
		x[0] = nx;
		y[0] = ny;
	}
	return 0;
}
// core idea: https://sasdf.github.io/ctf/tasks/2021/BalsnCTF/crypto/trinity/
// g++ collision2.cpp -o collision2 -Ofast -march=native
// for i in $(seq 1234 1237); do ./collision1 $i & ; done

solution

{"m1": "fb3f31f633b15a75", "m2": "8d26f089ff3f8501"}
{"m1": "a9e30a0e524c931661646d696e", "m2": "41f388042af21a4061646d696e"}