Skip to content

Instantly share code, notes, and snippets.

@seadog007
Last active August 25, 2024 16:18
Show Gist options
  • Save seadog007/b0f6f5038b333b8bbfa503705ed91dfe to your computer and use it in GitHub Desktop.
Save seadog007/b0f6f5038b333b8bbfa503705ed91dfe to your computer and use it in GitHub Desktop.
HITCON 2024 Badge Hash Bruteforcer
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <atomic>
#include <iostream>
#include <thread>
#include <vector>
// Original by Sciuridae
// Modified by seadog007
constexpr size_t SHA3_256_HASH_SIZE = 256 / 8;
#ifndef SHA3_H
#define SHA3_H
#define SHA3_KECCAK_SPONGE_WORDS \
(((1600) / 8 /*bits to byte*/) / sizeof(uint64_t))
typedef struct sha3_context_ {
uint64_t saved; /* the portion of the input message that we
* didn't consume yet */
union { /* Keccak's state */
uint64_t s[SHA3_KECCAK_SPONGE_WORDS];
uint8_t sb[SHA3_KECCAK_SPONGE_WORDS * 8];
} u;
unsigned byteIndex; /* 0..7--the next byte after the set one
* (starts from 0; 0--none are buffered) */
unsigned wordIndex; /* 0..24--the next word to integrate input
* (starts from 0) */
unsigned capacityWords; /* the double size of the hash output in
* words (e.g. 16 for Keccak 512) */
} sha3_context;
enum SHA3_FLAGS { SHA3_FLAGS_NONE = 0, SHA3_FLAGS_KECCAK = 1 };
enum SHA3_RETURN { SHA3_RETURN_OK = 0, SHA3_RETURN_BAD_PARAMS = 1 };
typedef enum SHA3_RETURN sha3_return_t;
/* For Init or Reset call these: */
sha3_return_t sha3_Init(void *priv, unsigned bitSize);
// Takes 16ms on STM32@12MHz, should be split.
void keccakf(uint64_t s[25]);
// Takes 0.7ms on STM32@12MHz, should only be called once per task.
// round should be sequentially called with [0, KECCAK_ROUNDS-1], for a total of
// KECCAK_ROUNDS times.
void keccakf_split(uint64_t s[25], int round);
void sha3_Init256(void *priv);
void sha3_Init384(void *priv);
void sha3_Init512(void *priv);
enum SHA3_FLAGS sha3_SetFlags(void *priv, enum SHA3_FLAGS);
// Takes up to 1 keccakf() call.
void sha3_UpdateWord(void *priv, void const *bufIn);
// Takes multiple keccakf() call and should not be used on STM32.
void sha3_Update(void *priv, void const *bufIn, size_t len);
// Takes 1 keccakf() call.
void const *sha3_Finalize(void *priv);
// This is exactly the same as sha3_Finalize() but the caller is expected
// to call this KECCAK_ROUNDS+2 times, each time giving round = 0 to
// KECCAK_ROUNDS+1.
// For round=0, it should handle anything before keccakf().
// For round=1 to KECCAK_ROUNDS, it should call keccakf(round-1).
// For round=KECCAK_ROUNDS+1, it should handle anything after keccakf().
void const *sha3_Finalize_split(void *priv, int round);
/* Single-call hashing */
sha3_return_t sha3_HashBuffer(
unsigned bitSize, /* 256, 384, 512 */
enum SHA3_FLAGS flags, /* SHA3_FLAGS_NONE or SHA3_FLAGS_KECCAK */
const void *in, unsigned inBytes, void *out,
unsigned outBytes); /* up to bitSize/8; truncation OK */
constexpr size_t KECCAK_ROUNDS = 24;
#endif
#define SHA3_ASSERT(x)
#define SHA3_TRACE(format, ...)
#define SHA3_TRACE_BUF(format, buf, l)
/*
* This flag is used to configure "pure" Keccak, as opposed to NIST SHA3.
*/
#define SHA3_USE_KECCAK_FLAG 0x80000000
#define SHA3_CW(x) ((x) & (~SHA3_USE_KECCAK_FLAG))
#if defined(_MSC_VER)
#define SHA3_CONST(x) x
#else
#define SHA3_CONST(x) x##L
#endif
#ifndef SHA3_ROTL64
#define SHA3_ROTL64(x, y) \
(((x) << (y)) | ((x) >> ((sizeof(uint64_t) * 8) - (y))))
#endif
static const uint64_t keccakf_rndc[24] = {
SHA3_CONST(0x0000000000000001UL), SHA3_CONST(0x0000000000008082UL),
SHA3_CONST(0x800000000000808aUL), SHA3_CONST(0x8000000080008000UL),
SHA3_CONST(0x000000000000808bUL), SHA3_CONST(0x0000000080000001UL),
SHA3_CONST(0x8000000080008081UL), SHA3_CONST(0x8000000000008009UL),
SHA3_CONST(0x000000000000008aUL), SHA3_CONST(0x0000000000000088UL),
SHA3_CONST(0x0000000080008009UL), SHA3_CONST(0x000000008000000aUL),
SHA3_CONST(0x000000008000808bUL), SHA3_CONST(0x800000000000008bUL),
SHA3_CONST(0x8000000000008089UL), SHA3_CONST(0x8000000000008003UL),
SHA3_CONST(0x8000000000008002UL), SHA3_CONST(0x8000000000000080UL),
SHA3_CONST(0x000000000000800aUL), SHA3_CONST(0x800000008000000aUL),
SHA3_CONST(0x8000000080008081UL), SHA3_CONST(0x8000000000008080UL),
SHA3_CONST(0x0000000080000001UL), SHA3_CONST(0x8000000080008008UL)};
static const unsigned keccakf_rotc[24] = {1, 3, 6, 10, 15, 21, 28, 36,
45, 55, 2, 14, 27, 41, 56, 8,
25, 43, 62, 18, 39, 61, 20, 44};
static const unsigned keccakf_piln[24] = {10, 7, 11, 17, 18, 3, 5, 16,
8, 21, 24, 4, 15, 23, 19, 13,
12, 2, 20, 14, 22, 9, 6, 1};
/* generally called after SHA3_KECCAK_SPONGE_WORDS-ctx->capacityWords words
* are XORed into the state s
*/
void keccakf(uint64_t s[25]) {
int i, j, round;
uint64_t t, bc[5];
for (round = 0; round < KECCAK_ROUNDS; round++) {
/* Theta */
for (i = 0; i < 5; i++)
bc[i] = s[i] ^ s[i + 5] ^ s[i + 10] ^ s[i + 15] ^ s[i + 20];
for (i = 0; i < 5; i++) {
t = bc[(i + 4) % 5] ^ SHA3_ROTL64(bc[(i + 1) % 5], 1);
for (j = 0; j < 25; j += 5) s[j + i] ^= t;
}
/* Rho Pi */
t = s[1];
for (i = 0; i < 24; i++) {
j = keccakf_piln[i];
bc[0] = s[j];
s[j] = SHA3_ROTL64(t, keccakf_rotc[i]);
t = bc[0];
}
/* Chi */
for (j = 0; j < 25; j += 5) {
for (i = 0; i < 5; i++) bc[i] = s[j + i];
for (i = 0; i < 5; i++) s[j + i] ^= (~bc[(i + 1) % 5]) & bc[(i + 2) % 5];
}
/* Iota */
s[0] ^= keccakf_rndc[round];
}
}
// This is exactly the same as keccakf except that the caller is expected to
// call keccakf_split() variant exactly KECCAK_ROUNDS time, with round = 0 to
// KECCAK_ROUNDS-1.
void keccakf_split(uint64_t s[25], int round) {
int i, j;
uint64_t t, bc[5];
/* Theta */
for (i = 0; i < 5; i++)
bc[i] = s[i] ^ s[i + 5] ^ s[i + 10] ^ s[i + 15] ^ s[i + 20];
for (i = 0; i < 5; i++) {
t = bc[(i + 4) % 5] ^ SHA3_ROTL64(bc[(i + 1) % 5], 1);
for (j = 0; j < 25; j += 5) s[j + i] ^= t;
}
/* Rho Pi */
t = s[1];
for (i = 0; i < 24; i++) {
j = keccakf_piln[i];
bc[0] = s[j];
s[j] = SHA3_ROTL64(t, keccakf_rotc[i]);
t = bc[0];
}
/* Chi */
for (j = 0; j < 25; j += 5) {
for (i = 0; i < 5; i++) bc[i] = s[j + i];
for (i = 0; i < 5; i++) s[j + i] ^= (~bc[(i + 1) % 5]) & bc[(i + 2) % 5];
}
/* Iota */
s[0] ^= keccakf_rndc[round];
}
/* *************************** Public Inteface ************************ */
/* For Init or Reset call these: */
sha3_return_t sha3_Init(void *priv, unsigned bitSize) {
sha3_context *ctx = (sha3_context *)priv;
if (bitSize != 256 && bitSize != 384 && bitSize != 512)
return SHA3_RETURN_BAD_PARAMS;
memset(ctx, 0, sizeof(*ctx));
ctx->capacityWords = 2 * bitSize / (8 * sizeof(uint64_t));
return SHA3_RETURN_OK;
}
void sha3_Init256(void *priv) { sha3_Init(priv, 256); }
void sha3_Init384(void *priv) { sha3_Init(priv, 384); }
void sha3_Init512(void *priv) { sha3_Init(priv, 512); }
enum SHA3_FLAGS sha3_SetFlags(void *priv, enum SHA3_FLAGS flags) {
sha3_context *ctx = (sha3_context *)priv;
flags = static_cast<enum SHA3_FLAGS>(flags & SHA3_FLAGS_KECCAK);
ctx->capacityWords |= (flags == SHA3_FLAGS_KECCAK ? SHA3_USE_KECCAK_FLAG : 0);
return flags;
}
void sha3_UpdateWord(void *priv, void const *bufIn) {
sha3_context *ctx = (sha3_context *)priv;
/* Ensure that byteIndex is reset to 0 (since we're processing a full word) */
if (ctx->byteIndex != 0) {
return; // Error: byteIndex should be 0 when updating a full word
}
const uint64_t *t = reinterpret_cast<const uint64_t *>(bufIn);
ctx->u.s[ctx->wordIndex] ^= *t;
if (++ctx->wordIndex ==
(SHA3_KECCAK_SPONGE_WORDS - SHA3_CW(ctx->capacityWords))) {
keccakf(ctx->u.s);
ctx->wordIndex = 0;
}
}
void sha3_Update(void *priv, void const *bufIn, size_t len) {
sha3_context *ctx = (sha3_context *)priv;
if (len % 8 == 0 && ctx->byteIndex == 0) {
// The input length is a multiple of 8 bytes and byteIndex is 0,
// which means we are processing complete words from bufIn.
size_t words = len / sizeof(uint64_t);
const uint64_t *buf = reinterpret_cast<const uint64_t *>(bufIn);
for (size_t i = 0; i < words; i++, buf++) {
sha3_UpdateWord(ctx, buf);
}
return;
}
/* 0...7 -- how much is needed to have a word */
unsigned old_tail = (8 - ctx->byteIndex) & 7;
size_t words;
unsigned tail;
size_t i;
const uint8_t *buf = reinterpret_cast<const uint8_t *>(bufIn);
SHA3_TRACE_BUF("called to update with:", buf, len);
SHA3_ASSERT(ctx->byteIndex < 8);
SHA3_ASSERT(ctx->wordIndex < sizeof(ctx->u.s) / sizeof(ctx->u.s[0]));
if (len < old_tail) { /* have no complete word or haven't started
* the word yet */
SHA3_TRACE("because %d<%d, store it and return", (unsigned)len,
(unsigned)old_tail);
/* endian-independent code follows: */
while (len--)
ctx->saved |= (uint64_t)(*(buf++)) << ((ctx->byteIndex++) * 8);
SHA3_ASSERT(ctx->byteIndex < 8);
return;
}
if (old_tail) { /* will have one word to process */
SHA3_TRACE("completing one word with %d bytes", (unsigned)old_tail);
/* endian-independent code follows: */
len -= old_tail;
while (old_tail--)
ctx->saved |= (uint64_t)(*(buf++)) << ((ctx->byteIndex++) * 8);
/* now ready to add saved to the sponge */
ctx->u.s[ctx->wordIndex] ^= ctx->saved;
SHA3_ASSERT(ctx->byteIndex == 8);
ctx->byteIndex = 0;
ctx->saved = 0;
if (++ctx->wordIndex ==
(SHA3_KECCAK_SPONGE_WORDS - SHA3_CW(ctx->capacityWords))) {
keccakf(ctx->u.s);
ctx->wordIndex = 0;
}
}
/* now work in full words directly from input */
SHA3_ASSERT(ctx->byteIndex == 0);
words = len / sizeof(uint64_t);
tail = len - words * sizeof(uint64_t);
SHA3_TRACE("have %d full words to process", (unsigned)words);
for (i = 0; i < words; i++, buf += sizeof(uint64_t)) {
const uint64_t t =
(uint64_t)(buf[0]) | ((uint64_t)(buf[1]) << 8 * 1) |
((uint64_t)(buf[2]) << 8 * 2) | ((uint64_t)(buf[3]) << 8 * 3) |
((uint64_t)(buf[4]) << 8 * 4) | ((uint64_t)(buf[5]) << 8 * 5) |
((uint64_t)(buf[6]) << 8 * 6) | ((uint64_t)(buf[7]) << 8 * 7);
#if defined(__x86_64__) || defined(__i386__)
SHA3_ASSERT(memcmp(&t, buf, 8) == 0);
#endif
ctx->u.s[ctx->wordIndex] ^= t;
if (++ctx->wordIndex ==
(SHA3_KECCAK_SPONGE_WORDS - SHA3_CW(ctx->capacityWords))) {
keccakf(ctx->u.s);
ctx->wordIndex = 0;
}
}
SHA3_TRACE("have %d bytes left to process, save them", (unsigned)tail);
/* finally, save the partial word */
SHA3_ASSERT(ctx->byteIndex == 0 && tail < 8);
while (tail--) {
SHA3_TRACE("Store byte %02x '%c'", *buf, *buf);
ctx->saved |= (uint64_t)(*(buf++)) << ((ctx->byteIndex++) * 8);
}
SHA3_ASSERT(ctx->byteIndex < 8);
SHA3_TRACE("Have saved=0x%016" PRIx64 " at the end", ctx->saved);
}
void const *sha3_Finalize_split(void *priv, int round) {
sha3_context *ctx = (sha3_context *)priv;
if (round == 0) {
/* Append 2-bit suffix 01, per SHA-3 spec. */
uint64_t t;
if (ctx->capacityWords & SHA3_USE_KECCAK_FLAG) {
/* Keccak version */
t = (uint64_t)(((uint64_t)1) << (ctx->byteIndex * 8));
} else {
/* SHA3 version */
t = (uint64_t)(((uint64_t)(0x02 | (1 << 2))) << ((ctx->byteIndex) * 8));
}
ctx->u.s[ctx->wordIndex] ^= ctx->saved ^ t;
/* Prepare for the final round */
ctx->u.s[SHA3_KECCAK_SPONGE_WORDS - SHA3_CW(ctx->capacityWords) - 1] ^=
SHA3_CONST(0x8000000000000000UL);
} else if (round <= KECCAK_ROUNDS) {
/* Perform KECCAK_ROUNDS of keccakf */
keccakf_split(ctx->u.s, round - 1);
} else { /* round = KECCAK_ROUNDS + 1 */
/* Convert the context state to bytes after the final round */
for (unsigned i = 0; i < SHA3_KECCAK_SPONGE_WORDS; i++) {
const unsigned t1 = (uint32_t)ctx->u.s[i];
const unsigned t2 = (uint32_t)((ctx->u.s[i] >> 16) >> 16);
ctx->u.sb[i * 8 + 0] = (uint8_t)(t1);
ctx->u.sb[i * 8 + 1] = (uint8_t)(t1 >> 8);
ctx->u.sb[i * 8 + 2] = (uint8_t)(t1 >> 16);
ctx->u.sb[i * 8 + 3] = (uint8_t)(t1 >> 24);
ctx->u.sb[i * 8 + 4] = (uint8_t)(t2);
ctx->u.sb[i * 8 + 5] = (uint8_t)(t2 >> 8);
ctx->u.sb[i * 8 + 6] = (uint8_t)(t2 >> 16);
ctx->u.sb[i * 8 + 7] = (uint8_t)(t2 >> 24);
}
}
return (round == KECCAK_ROUNDS + 1) ? ctx->u.sb : nullptr;
}
/* This is simply the 'update' with the padding block.
* The padding block is 0x01 || 0x00* || 0x80. First 0x01 and last 0x80
* bytes are always present, but they can be the same byte.
*/
void const *sha3_Finalize(void *priv) {
sha3_context *ctx = (sha3_context *)priv;
SHA3_TRACE("called with %d bytes in the buffer", ctx->byteIndex);
/* Append 2-bit suffix 01, per SHA-3 spec. Instead of 1 for padding we
* use 1<<2 below. The 0x02 below corresponds to the suffix 01.
* Overall, we feed 0, then 1, and finally 1 to start padding. Without
* M || 01, we would simply use 1 to start padding. */
uint64_t t;
if (ctx->capacityWords & SHA3_USE_KECCAK_FLAG) {
/* Keccak version */
t = (uint64_t)(((uint64_t)1) << (ctx->byteIndex * 8));
} else {
/* SHA3 version */
t = (uint64_t)(((uint64_t)(0x02 | (1 << 2))) << ((ctx->byteIndex) * 8));
}
ctx->u.s[ctx->wordIndex] ^= ctx->saved ^ t;
ctx->u.s[SHA3_KECCAK_SPONGE_WORDS - SHA3_CW(ctx->capacityWords) - 1] ^=
SHA3_CONST(0x8000000000000000UL);
keccakf(ctx->u.s);
/* Return first bytes of the ctx->s. This conversion is not needed for
* little-endian platforms e.g. wrap with #if !defined(__BYTE_ORDER__)
* || !defined(__ORDER_LITTLE_ENDIAN__) ||
* __BYTE_ORDER__!=__ORDER_LITTLE_ENDIAN__
* ... the conversion below ...
* #endif */
{
unsigned i;
for (i = 0; i < SHA3_KECCAK_SPONGE_WORDS; i++) {
const unsigned t1 = (uint32_t)ctx->u.s[i];
const unsigned t2 = (uint32_t)((ctx->u.s[i] >> 16) >> 16);
ctx->u.sb[i * 8 + 0] = (uint8_t)(t1);
ctx->u.sb[i * 8 + 1] = (uint8_t)(t1 >> 8);
ctx->u.sb[i * 8 + 2] = (uint8_t)(t1 >> 16);
ctx->u.sb[i * 8 + 3] = (uint8_t)(t1 >> 24);
ctx->u.sb[i * 8 + 4] = (uint8_t)(t2);
ctx->u.sb[i * 8 + 5] = (uint8_t)(t2 >> 8);
ctx->u.sb[i * 8 + 6] = (uint8_t)(t2 >> 16);
ctx->u.sb[i * 8 + 7] = (uint8_t)(t2 >> 24);
}
}
SHA3_TRACE_BUF("Hash: (first 32 bytes)", ctx->u.sb, 256 / 8);
return (ctx->u.sb);
}
sha3_return_t sha3_HashBuffer(unsigned bitSize, enum SHA3_FLAGS flags,
const void *in, unsigned inBytes, void *out,
unsigned outBytes) {
sha3_return_t err;
sha3_context c;
err = sha3_Init(&c, bitSize);
if (err != SHA3_RETURN_OK) return err;
if (sha3_SetFlags(&c, flags) != flags) {
return SHA3_RETURN_BAD_PARAMS;
}
sha3_Update(&c, in, inBytes);
const void *h = sha3_Finalize(&c);
if (outBytes > bitSize / 8) outBytes = bitSize / 8;
memcpy(out, h, outBytes);
return SHA3_RETURN_OK;
}
constexpr int LEADING_ZERO_BITS_LUT[16] = {4, 3, 2, 2, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0};
int ComputePrefixZero(const uint8_t *bin_hash) {
int count = 0;
for (int i = 0; i < SHA3_256_HASH_SIZE; i++) {
uint8_t byte = bin_hash[i];
uint8_t high_nibble = (byte & 0xF0) >> 4;
if (high_nibble != 0) {
return count + LEADING_ZERO_BITS_LUT[high_nibble];
}
count += 4;
uint8_t low_nibble = byte & 0x0F;
if (low_nibble != 0) {
return count + LEADING_ZERO_BITS_LUT[low_nibble];
}
count += 4;
}
return 0;
}
void SetColumnPrefix(uint8_t *out, int col) {
memcpy(out, "HITCON", 6);
uint16_t col_uint16 = static_cast<uint16_t>(col);
out[6] = (col_uint16 >> 8) & 0xFF;
out[7] = col_uint16 & 0xFF;
}
constexpr size_t kNumCols = 16;
constexpr size_t kDataSize = 8;
constexpr int kByteMax = 256;
constexpr int targetScore = 28;
int main(int argc, char* argv[]) {
//for (int col = 0; col < kNumCols; col++) {
int col = std::stoi(argv[1]);
int current_score = 0;
//std::cout << "Column " << col << ": " << std::endl;
uint8_t col_prefix[kDataSize];
SetColumnPrefix(col_prefix, col);
uint8_t cell_data[kDataSize] = {0};
//for (int byte8 = 0; byte8 < kByteMax; byte8++) {
//cell_data[7] = byte8;
cell_data[7] = std::stoi(argv[2]);
for (int byte7 = 0; byte7 < kByteMax; byte7++) {
cell_data[6] = byte7;
for (int byte6 = 0; byte6 < kByteMax; byte6++) {
cell_data[5] = byte6;
for (int byte5 = 0; byte5 < kByteMax; byte5++) {
cell_data[4] = byte5;
for (int byte4 = 0; byte4 < kByteMax; byte4++) {
cell_data[3] = byte4;
for (int byte3 = 0; byte3 < kByteMax; byte3++) {
cell_data[2] = byte3;
for (int byte2 = 0; byte2 < kByteMax; byte2++) {
cell_data[1] = byte2;
for (int byte1 = 0; byte1 < kByteMax; byte1++) {
cell_data[0] = byte1;
sha3_context routine_sha3_256_context_;
sha3_Init256(&routine_sha3_256_context_);
sha3_UpdateWord(&routine_sha3_256_context_, col_prefix);
sha3_UpdateWord(&routine_sha3_256_context_, cell_data);
int out_score =
ComputePrefixZero(reinterpret_cast<const uint8_t *>(
sha3_Finalize(&routine_sha3_256_context_)));
if (out_score >= targetScore) {
std::cout << col << ": "<< unsigned(cell_data[0]) << " "
<< unsigned(cell_data[1]) << " "
<< unsigned(cell_data[2]) << " "
<< unsigned(cell_data[3]) << " "
<< unsigned(cell_data[4]) << " "
<< unsigned(cell_data[5]) << " "
<< unsigned(cell_data[6]) << " "
<< unsigned(cell_data[7]) << " = "
<< out_score << std::endl;
//std::cout << "Column Target score reached!" << std::endl;
//goto next_column;
}
}
}
}
}
}
}
}
//}
//next_column:
// continue;
//}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment