Finding magic hashes with hashcat

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 $0 \times 10^{\texttt{[digits]}}$. 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 $H : A \rightarrow B$ be a hash function with $l$-hexdigit long output. If we disregard all but the ones starting with 0e..., we have

$\mathbb{P}(H(x) \text{ is magical}) = \left(\frac{1}{10}\right)^2 \cdot \left(\frac{10}{16}\right)^l$

for an $x$ 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 $2^{50}$ 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);

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.