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.

inverse_prob_hashfunction

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);

  // 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s