/* * DF-3111 — shared solver: find two distinct filenames with the IDENTICAL * HAMMER1 ALG1 namekey in the wrap zone. * * Name shape: "aa" + 3 alphabet bytes + 'q' + '.' + seg2 * seg1 = "aa"+XYZ+"q" (6 bytes), seg2 = 4 solver bytes. * seg2 is solved by inverting the STANDALONE 4-byte CRC-32 (a bijection, * self-checked) so that crc32(seg1) + crc32(seg2) == 0x7fffffff or * 0xffffffff (mod 2^32) => crcx & 0x7fffffff == 0x7fffffff. * The 3 alphabet bytes randomize the whole-name crc; names whose * (crc ^ crc<<16) & 0xffff0000 lands in [0xff010000, 0xffff0000] get a * namekey > INT64_MAX - max_iterations (wrap zone). Two distinct names * with the same whole-name crc share the same key => colliding pair. */ #ifndef DF3111_SOLVER_H #define DF3111_SOLVER_H #include #include #include #include static uint32_t df_crc_table[256]; static void df_crc_init(void) { for (uint32_t n = 0; n < 256; n++) { uint32_t c = n; for (int k = 0; k < 8; k++) c = (c & 1) ? 0xedb88320U ^ (c >> 1) : c >> 1; df_crc_table[n] = c; } } static uint32_t df_crc32(const unsigned char *buf, size_t len) { uint32_t c = 0xffffffffU; for (size_t i = 0; i < len; i++) c = df_crc_table[(c ^ buf[i]) & 0xff] ^ (c >> 8); return c ^ 0xffffffffU; } static uint32_t df_inv_rows[32]; /* invert m -> crc32(4-byte m) (standalone; bijection) */ static void df_build_inverse(void) { uint32_t img[32], pre[32]; for (int i = 0; i < 32; i++) { unsigned char m[4]; memset(m, 0, 4); m[i / 8] = (unsigned char)(1u << (i % 8)); img[i] = df_crc32(m, 4) ^ df_crc32((const unsigned char *)"\0\0\0\0", 4); pre[i] = 1u << i; } for (int col = 0; col < 32; col++) { int piv = -1; for (int r = col; r < 32; r++) if (img[r] & (1u << col)) { piv = r; break; } if (piv < 0) { fprintf(stderr, "crc32 not invertible\n"); exit(1); } uint32_t t; t = img[col]; img[col] = img[piv]; img[piv] = t; t = pre[col]; pre[col] = pre[piv]; pre[piv] = t; for (int r = 0; r < 32; r++) if (r != col && (img[r] & (1u << col))) { img[r] ^= img[col]; pre[r] ^= pre[col]; } } for (int col = 0; col < 32; col++) df_inv_rows[col] = pre[col]; } static void df_crc32_inverse4(uint32_t want, unsigned char out[4]) { uint32_t c0 = df_crc32((const unsigned char *)"\0\0\0\0", 4); uint32_t lin = want ^ c0, m = 0; for (int col = 0; col < 32; col++) if (lin & (1u << col)) m ^= df_inv_rows[col]; out[0] = m & 0xff; out[1] = (m >> 8) & 0xff; out[2] = (m >> 16) & 0xff; out[3] = (m >> 24) & 0xff; } /* exact replica of hammer_direntry_namekey() ALG1 (hammer_subs.c:963) */ static int64_t df_alg1_key(const char *aname, int len) { uint32_t crcx = 0; int i, j; int64_t key = 0; for (i = j = 0; i < len; ++i) { if (aname[i] == '.' || aname[i] == '-' || aname[i] == '_' || aname[i] == '~') { if (i != j) crcx += df_crc32((const unsigned char *)aname + j, i - j); j = i + 1; } } if (i != j) crcx += df_crc32((const unsigned char *)aname + j, i - j); crcx &= 0x7fffffffU; key |= (uint64_t)crcx << 32; crcx = df_crc32((const unsigned char *)aname, len); crcx = crcx ^ (crcx << 16); key |= (int64_t)(crcx & 0xffff0000U); if ((key & 0xffffffff00000000LL) == 0) key |= 0x100000000LL; return key; } static const char *df_alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; #define DF_PAIR_MAX 4096 static char df_names[DF_PAIR_MAX][16]; static int df_nlen[DF_PAIR_MAX]; static int64_t df_keys[DF_PAIR_MAX]; static int df_n; /* returns 0 and fills the FIRST identical-key pair found (deterministic) */ static int df_find_pair(char *outA, int *outlenA, char *outB, int *outlenB, int64_t *outKey) { df_crc_init(); df_build_inverse(); { unsigned char o[4]; df_crc32_inverse4(0xdeadbeefU, o); if (df_crc32(o, 4) != 0xdeadbeefU) { fprintf(stderr, "solver self-check FAILED\n"); return -1; } } df_n = 0; for (int a = 0; a < 62 && df_n < DF_PAIR_MAX; a++) { for (int b = 0; b < 62 && df_n < DF_PAIR_MAX; b++) { for (int c = 0; c < 62 && df_n < DF_PAIR_MAX; c++) { unsigned char seg1[7]; uint32_t c1; seg1[0] = 'a'; seg1[1] = 'a'; seg1[2] = (unsigned char)df_alphabet[a]; seg1[3] = (unsigned char)df_alphabet[b]; seg1[4] = (unsigned char)df_alphabet[c]; seg1[5] = 'q'; c1 = df_crc32(seg1, 6); for (int s = 0; s < 2; s++) { uint32_t target = (s ? 0xffffffffU : 0x7fffffffU) - c1; unsigned char o[4], name[16]; int n = 0, bad = 0; df_crc32_inverse4(target, o); name[n++] = seg1[0]; name[n++] = seg1[1]; name[n++] = seg1[2]; name[n++] = seg1[3]; name[n++] = seg1[4]; name[n++] = seg1[5]; name[n++] = '.'; name[n++] = o[0]; name[n++] = o[1]; name[n++] = o[2]; name[n++] = o[3]; for (int q = 0; q < n; q++) if (name[q] == '/' || name[q] == 0) bad = 1; for (int q = 0; q + 1 < n; q++) if (name[q] == '@' && name[q + 1] == '@') bad = 1; if (bad) continue; int64_t k = df_alg1_key((const char *)name, n); if ((uint64_t)k > 0x7fffffffff000000ULL && (uint32_t)(k & 0xffffffffU) != 0) { memcpy(df_names[df_n], name, n); df_names[df_n][n] = 0; df_nlen[df_n] = n; df_keys[df_n] = k; df_n++; if (df_n >= DF_PAIR_MAX) break; } } } } } for (int i = 0; i < df_n; i++) for (int j = i + 1; j < df_n; j++) if (df_keys[i] == df_keys[j]) { memcpy(outA, df_names[i], df_nlen[i] + 1); *outlenA = df_nlen[i]; memcpy(outB, df_names[j], df_nlen[j] + 1); *outlenB = df_nlen[j]; *outKey = df_keys[i]; return 0; } fprintf(stderr, "only %d wrap-zone names, no pair\n", df_n); return -1; } static void df_pr_name(const char *label, const char *n, int len, int64_t key) { printf("%s key=%016llx len=%d bytes=", label, (unsigned long long)(uint64_t)key, len); for (int i = 0; i < len; i++) printf("%02x", (unsigned char)n[i]); printf("\n"); } #endif /* DF3111_SOLVER_H */