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.