WeChall - MD5 Broken

MD5 Broken (Cracking, Coding) by gizmore 每个字节缺一个 nibble 的部分 MD5，暴力破解 7 位小写字母明文

Challenge

题面给出一串 16 个 hex 字符（= 16 字节 MD5，每字节只显示一个 nibble）， 明文是 7 位小写字母。显示的 hash "bound to your session"——每次新登录 session 会重新随机选择每个字节显示高/低哪个 nibble，但底层答案不变。

Solution

暴力破解 26^7 = 8,031,810,176 个组合，对每个候选算 MD5，检查 16 个 nibble 是否全部落在"高/低 nibble"集合内。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdatomic.h>
#include <pthread.h>
#include <openssl/evp.h>

#define LEN 7              /* 明文长度 */
#define BYTES 16           /* MD5 字节数 */
#define TOTAL 8031810176LL /* 26^7 */

static uint8_t partial[BYTES];  /* 每字节显示的高/低 nibble 值 */
static atomic_int found = 0;    /* 全局找到标志 */
static char answer[LEN + 1];    /* 找到的明文 */
static long nthreads = 1;       /* 线程数 */

/* 计算 MD5，结果写入 out[16] */
static void md5_digest(const unsigned char *msg, size_t len, unsigned char out[16])
{
    EVP_MD_CTX *ctx = EVP_MD_CTX_new();
    EVP_DigestInit_ex(ctx, EVP_md5(), NULL);
    EVP_DigestUpdate(ctx, msg, len);
    EVP_DigestFinal_ex(ctx, out, NULL);
    EVP_MD_CTX_free(ctx);
}

/* 检查一个候选明文：MD5 的每个字节，高或低 nibble 必须命中 partial */
static inline int matches(const unsigned char *digest)
{
    for (int i = 0; i < BYTES; i++) {
        uint8_t hi = digest[i] >> 4, lo = digest[i] & 0xF;
        if (partial[i] != hi && partial[i] != lo)
            return 0;
    }
    return 1;
}

static void *worker(void *arg)
{
    long tid = (long)arg;

    /* 范围均分: [start, end) */
    long long per = TOTAL / nthreads;
    long long start = tid * per;
    long long end = (tid == nthreads - 1) ? TOTAL : start + per;

    unsigned char cand[LEN], digest[BYTES];
    for (long long k = start; k < end; k++) {
        if (atomic_load(&found))
            break;
        /* 每 1 亿个打一次进度 */
        if ((k - start) % 100000000 == 0)
            printf("  Thread %ld: %lld / %lld (%.1f%%)\n",
                   tid, k - start, per, 100.0 * (k - start) / per);

        /* base-26 展开为 7 个小写字母 */
        long long v = k;
        for (int i = LEN - 1; i >= 0; i--) {
            cand[i] = 'a' + (v % 26);
            v /= 26;
        }

        md5_digest(cand, LEN, digest);
        if (matches(digest)) {
            memcpy(answer, cand, LEN);
            answer[LEN] = '\0';
            atomic_store(&found, 1);
            printf("FOUND: %s\n", answer);
            break;
        }
    }
    return NULL;
}

int main(int argc, char **argv)
{
    if (argc < 2) {
        fprintf(stderr, "usage: %s <partial_hex> [threads]\n", argv[0]);
        return 1;
    }
    if (strlen(argv[1]) != BYTES) {
        fprintf(stderr, "partial must be %d hex chars\n", BYTES);
        return 1;
    }
    for (int i = 0; i < BYTES; i++) {
        char c = argv[1][i];
        if (c >= '0' && c <= '9') partial[i] = c - '0';
        else if (c >= 'a' && c <= 'f') partial[i] = c - 'a' + 10;
        else if (c >= 'A' && c <= 'F') partial[i] = c - 'A' + 10;
        else { fprintf(stderr, "invalid hex char: %c\n", c); return 1; }
    }
    nthreads = argc > 2 ? atol(argv[2]) : 16;
    if (nthreads < 1) nthreads = 1;

    printf("Starting brute force: %lld combinations across %ld threads\n", TOTAL, nthreads);
    printf("Partial hash: %s\n", argv[1]);

    pthread_t *th = malloc(sizeof(pthread_t) * nthreads);
    for (long t = 0; t < nthreads; t++)
        pthread_create(&th[t], NULL, worker, (void *)t);
    for (long t = 0; t < nthreads; t++)
        pthread_join(th[t], NULL);

    if (atomic_load(&found))
        printf("ANSWER: %s\n", answer);
    else
        printf("NOT FOUND in range\n");
    return 0;
}

Python 参考实现

#!/usr/bin/env python3
import hashlib
import sys


def matches(md5_hex: str, partial: str) -> bool:
    """partial: 16 个 nibble，每字节显示高或低 nibble"""
    for i in range(16):
        bv = int(md5_hex[i * 2:i * 2 + 2], 16)
        pn = int(partial[i], 16)
        if pn != ((bv >> 4) & 0xF) and pn != (bv & 0xF):
            return False
    return True


def crack(start: int, end: int, partial: str):
    """按字典序索引 [start, end) 搜索 7 位小写字母明文"""
    for k in range(start, end):
        v = k
        chars = []
        for _ in range(7):
            chars.append(chr(ord('a') + v % 26))
            v //= 26
        cand = ''.join(reversed(chars))
        if matches(hashlib.md5(cand.encode()).hexdigest(), partial):
            return cand
    return None


if __name__ == '__main__':
    partial = sys.argv[1] if len(sys.argv) > 1 else "3a45b89f570f5527"
    start = int(sys.argv[2]) if len(sys.argv) > 2 else 0
    end = int(sys.argv[3]) if len(sys.argv) > 3 else 26 ** 7
    ans = crack(start, end, partial)
    print(f"ANSWER: {ans}")