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]}}](https://s0.wp.com/latex.php?latex=0+%5Ctimes+10%5E%7B%5Ctexttt%7B%5Bdigits%5D%7D%7D&bg=ffffff&fg=000000&s=0 "0 \times 10^{\texttt{[digits]}}")
== 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 
0e..., we have
for an 
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 
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.
.
and weight 
, we create a 
. The 
must be unique for every item. This is done for every item in the knapsack. So, Problem 2 is NP-hard.
. Now assume that we want to represent the term 
. Define 
to be a product 
. 
is a prime number.![Q_1(x) = p(x) \cdot \left[(x-a_1)(x-a_2)(x-a_3)\right]^{-1}](https://s0.wp.com/latex.php?latex=Q_1%28x%29+%3D+p%28x%29+%5Ccdot+%5Cleft%5B%28x-a_1%29%28x-a_2%29%28x-a_3%29%5Cright%5D%5E%7B-1%7D&bg=ffffff&fg=000000&s=0 "Q_1(x) = p(x) \cdot \left[(x-a_1)(x-a_2)(x-a_3)\right]^{-1}")
. To consider all terms jointly, pick a number large number 
. Then, we create a polynomial using the terms ![Q_2(x) = p(x) \cdot \left[(x-a_2)(x-a_5)\right]^{-1}](https://s0.wp.com/latex.php?latex=Q_2%28x%29+%3D%C2%A0p%28x%29+%5Ccdot+%5Cleft%5B%28x-a_2%29%28x-a_5%29%5Cright%5D%5E%7B-1%7D&bg=ffffff&fg=000000&s=0 "Q_2(x) = p(x) \cdot \left[(x-a_2)(x-a_5)\right]^{-1}")
, ![Q_3(x) = p(x) \cdot \left[(x-a_4)(x-a_6)(x-a_7)\right]^{-1}](https://s0.wp.com/latex.php?latex=Q_3%28x%29+%3D%C2%A0p%28x%29+%5Ccdot+%5Cleft%5B%28x-a_4%29%28x-a_6%29%28x-a_7%29%5Cright%5D%5E%7B-1%7D&bg=ffffff&fg=000000&s=0 "Q_3(x) = p(x) \cdot \left[(x-a_4)(x-a_6)(x-a_7)\right]^{-1}")
and so on. We assume there are 
terms.
is constructed as 
. Since 
and 
will not interfere.
be the generator of a QC-MDPC code. Find a non-zero codeword with minimal weight, i.e., minimize 
.
generates a code as well. So, 
. This means that 
is of degree 
and that 
, i.e., 
has at most 
non-zero coefficients.
in a predefined prime-number basis. We are interested in unravel 
.
such that the factorization is 
-smooth.
, generate a corresponding vector
and check if they have the same property. The results are put into a matrix after which one performs Gaussian eliminiation over 
.
. Then compute 
to find 
.
such that the factorization of at least fraction of 
greater than 
is 
corresponds to the product of primes not represented in the chosen basis. In other words, 
for the vector above, or equivalently, 
.
and 
be the set of segments owned by 
be an abritrary segment and let 
denote the signature of 
.
of length 
is minimized.
over 
and the task is to find a minimum-weight codeword in 
. Then 
corresponds to the number of codewords in 
and 
. Then with high probability and for larger values of 
. For a perfect code, which has minimal size, we have 
. Therefore, the size of the code is 
, which is also the number of elements 
and 
that map to the same codeword 
and discard the point that is the farthest away from 
. For larger 
, we see that the upper bound for expected minimum distance approximates 
and 
.
Then, using the expression
segments with high probability. Using the lower bound, 
segments.
. Because all indices in the non-linear terms (
) are disjoint, we get
be the dimension of the state and 
such that
is governed by the non-linearity of 
. The expected Hamming weight of 
computation. Employing BKW will significantly reduce the complexity, by transforming the problem into a problem of smaller dimension at the expense of higher error rate.
such that 
, where 
. Turns out we can easily find the square root of it; by simply dividing every power with 
, we can find 
from 
.
and use a generalized birthday attack to find 
. There are several papers on it. This is not as difficult as it may be time consuming to write functional code.
, then 
. Since 
, 
will have weight 
