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.