During the last months, the problem of finding magic hashes for various hash functions has had a renaissance. After this tweet, the over-a-decade-old problem received new attention from a few people in the security community and, as a consequence, a flurry of new magical hashes were found.
Magical hashes have their roots in PHP. In particular, it all revolves around the improper use of the equality operator ==
. PHP uses implicit typing, e.g., if a string has the format 0e[digits]
, then it is interpreted as the scientific notation for . This has some undesired side effects: when comparing hashes from password input it causes a small but non-negligible subset of elements that are all equal under the
==
operation.
The probability of a hash being magical is easy to compute if we can assume that the hash function behaves completely at random. Let the be a hash function with
-hexdigit long output. If we disregard all but the ones starting with
0e...
, we have
for an randomly selected over all strings of any length.
The inverse probability amounts to the number of trials (or hash-function oracle calls) required on average to find a magic hash. For instance, SHA-256, which has an output length corresponds to about calls.
Modifying hashcat kernels
We will take SHA-224 as an example, since it is a bit easier to find magic hashes for. First, we are going to define two masks:
The first one returns 0 if the hex representation contains nothing but decimal digits:
#define IS_MAGIC(x) ((x & 0x88888888) & (((x & 0x22222222) >> 1 | (x & 0x44444444) >> 2) & ((x & 0x88888888) >> 3)) << 3)
The second one does the same as the first, but it forces the first two hex digits to 0e
.
#define IS_MAGIC_H(x) ((x & 0x00888888) & (((x & 0x00222222) >> 1 | (x & 0x00444444) >> 2) & ((x & 0x00888888) >> 3)) << 3) | ((x & 0xff000000) ^ 0x0e000000)
We add these lines to inc_hash_sha224.h
. Then, we locate the function sha224_final_vector
in inc_hash_sha224.cl
.
DECLSPEC void sha224_final_vector (sha224_ctx_vector_t *ctx) { MAYBE_VOLATILE const int pos = ctx->len & 63; append_0x80_4x4 (ctx->w0, ctx->w1, ctx->w2, ctx->w3, pos ^ 3); if (pos >= 56) { sha224_transform_vector (ctx->w0, ctx->w1, ctx->w2, ctx->w3, ctx->h); ctx->w0[0] = 0; ctx->w0[1] = 0; ctx->w0[2] = 0; ctx->w0[3] = 0; ctx->w1[0] = 0; ctx->w1[1] = 0; ctx->w1[2] = 0; ctx->w1[3] = 0; ctx->w2[0] = 0; ctx->w2[1] = 0; ctx->w2[2] = 0; ctx->w2[3] = 0; ctx->w3[0] = 0; ctx->w3[1] = 0; ctx->w3[2] = 0; ctx->w3[3] = 0; } ctx->w3[2] = 0; ctx->w3[3] = ctx->len * 8; sha224_transform_vector (ctx->w0, ctx->w1, ctx->w2, ctx->w3, ctx->h); // Add these lines ctx->h[0] = IS_MAGIC_H(ctx->h[0]); // first block starts with 0e ctx->h[1] = IS_MAGIC(ctx->h[1]); ctx->h[2] = IS_MAGIC(ctx->h[2]); ctx->h[3] = IS_MAGIC(ctx->h[3]); ctx->h[4] = IS_MAGIC(ctx->h[4]); ctx->h[5] = IS_MAGIC(ctx->h[5]); ctx->h[6] = IS_MAGIC(ctx->h[6]); }
Finally, we need to modify the corresponding module m01300_a3_pure.cl
. More specifically, we modify the following function:
KERNEL_FQ void m01300_sxx (KERN_ATTR_VECTOR ()) { /** * modifier */ const u64 lid = get_local_id (0); const u64 gid = get_global_id (0); if (gid >= gid_max) return; /** * digest */ const u32 search[4] = { digests_buf[digests_offset].digest_buf[DGST_R0], digests_buf[digests_offset].digest_buf[DGST_R1], digests_buf[digests_offset].digest_buf[DGST_R2], digests_buf[digests_offset].digest_buf[DGST_R3] }; /** * base */ const u32 pw_len = pws[gid].pw_len; u32x w[64] = { 0 }; for (u32 i = 0, idx = 0; i < pw_len; i += 4, idx += 1) { w[idx] = pws[gid].i[idx]; } /** * loop */ u32x w0l = w[0]; for (u32 il_pos = 0; il_pos < il_cnt; il_pos += VECT_SIZE) { const u32x w0r = words_buf_r[il_pos / VECT_SIZE]; const u32x w0 = w0l | w0r; w[0] = w0; sha224_ctx_vector_t ctx; sha224_init_vector (&ctx); sha224_update_vector (&ctx, w, pw_len); sha224_final_vector (&ctx); const u32x r0 = ctx.h[0]; const u32x r1 = ctx.h[1]; const u32x r2 = ctx.h[2]; const u32x r3 = ctx.h[3]; const u32x r4 = ctx.h[4]; const u32x r5 = ctx.h[5]; const u32x r6 = ctx.h[6]; // this is one hacky solution if ((r4 == 0) && (r5 == 0) && (r6 == 0)) { COMPARE_S_SIMD (r0, r1, r2, r3); } } }
This assumes no vectorization. Now build hashcat. Since all magic hashes will be mapped to the all-zero sequence, we run it as follows:
$ ./hashcat.bin -m 1300 00000000000000000000000000000000000000000000000000000000 -a 3 --self-test-disable --keep-guessing
--keep-guessing
causes hashcat to continue looking for hashes, even after one has been found. The --self-test-disable
is needed, since we have modified how SHA-224 functions, and the testcases defined in hashcat will consequently fail.
Running it on AWS
TBA?
Results
Relatively quickly, we found several magic hashes using this modification for SHA-224:
noskba6h0:0e615700362721473273572994672194243561543298826708511055 Ssrodxcm0:0e490606683681835610577024835460055379837761934700306599 i04i19pjb:0e487547019477070898434358527128478302010609538219168998 Fuq0guvec:0e469685182044169758492939426426028878580665828076076227 Sjv2n8fjg:0e353928003962053988403389507631422927454987073208369549 L0gg4bvt5:0e730381844465899091531741380493299916620289188395999379 7v2k2to5o:0e676632093970918870688436761599383423043605011248525140
For SHA-256:
Sol7trnk00:0e57289584033733351592613162328254589214408593566331187698889096
For a more comprehensive list of hashes, refer to this Github repo.
Thanks to @0xb0bb for providing crucial help with computational resources.