虽然chux建议的暴力方法已经可以正常工作,但实际上我们可以通过下面所描述的优化使其加速256倍以上(事实上,如果使用以下所有优化,速度会更快)。
关键在于这里的所有用于计算哈希的操作都是可逆的。(这是设计上的考虑,因为它确保例如将相同后缀附加到所有输入字符串不会增加哈希冲突的数量。)具体来说:
The operation hash += hash << n
is, of course, equivalent to hash *= (1 << n) + 1
. We're working with 32-bit unsigned integers, so all these calculations are done modulo 232. To undo this operation, all we need to do is find the modular multiplicative inverse of (1 << n) + 1
= 2n + 1 modulo 232 and multiply hash
by it.
We can do this pretty easily e.g. with this Python script, based on this answer here on SO. As it turns out, the multiplicative inverses of 210 + 1, 23 + 1 and 215 + 1 are, in hex, 0xC00FFC01, 0x38E38E39 and 0x3FFF8001 respectively.
To find the inverse of hash ^= hash >> n
for some constant n
, first note that this operation leaves the highest n
bits of hash
entirely unchanged. The next lower n
bits are simply XORed with the highest n
bits, so for those, simply repeating the operation undoes it. Looks pretty simple so far, right?
To recover the original values of the third highest group of n
bits, we need to XOR them with the original values of the second highest n
bits, which we can of course calculate by XORing the two highest groups of n
bits as describe above. And so on.
What this all boils down to is that the inverse operation to hash ^= hash >> n
is:
hash ^= (hash >> n) ^ (hash >> 2*n) ^ (hash >> 3*n) ^ (hash >> 4*n) ^ ...
where, of course, we can cut off the series once the shift amount is equal or greater to the number of bits in the integers we're working with (i.e. 32, in this case). Alternatively, we could achieve the same result in multiple steps, doubling the shift amount each time until it exceeds the bitlength of the numbers we're working with, like this:
hash ^= hash >> n;
hash ^= hash >> 2*n;
hash ^= hash >> 4*n;
hash ^= hash >> 8*n;
// etc.
(The multiple step method scales better when n
is small compared to the integer size, but for moderately large n
, the single step method may suffer from fewer pipeline stalls on modern CPUs. It's hard to say which one is actually more efficient in any given situation without benchmarking them both, and the results may vary between compilers and CPU models. In any case, such micro-optimizations are mostly not worth worrying too much about.)
Finally, of course, the inverse of hash += key[i++]
is simply hash -= key[--i]
.
所有这一切意味着,如果我们愿意,我们可以像这样反向运行哈希:
uint32_t reverse_one_at_a_time_hash(const uint8_t* key, size_t length, uint32_t hash) {
hash *= 0x3FFF8001; // inverse of hash += hash << 15;
hash ^= (hash >> 11) ^ (hash >> 22);
hash *= 0x38E38E39; // inverse of hash += hash << 3;
size_t i = length;
while (i > 0) {
hash ^= (hash >> 6) ^ (hash >> 12) ^ (hash >> 18) ^ (hash >> 24) ^ (hash >> 30);
hash *= 0xC00FFC01; // inverse of hash += hash << 10;
hash -= key[--i];
}
return hash; // this should return 0 if the original hash was correct
}
然后调用reverse_one_at_a_time_hash("keynumber1", 10, 0xA7AF2FFE)
,应该返回零,确实如此。
好的,很酷。但是这对于查找预映像有什么好处呢?
首先,如果我们猜测输入的除第一个字节外的所有内容,那么我们可以将第一个字节设置为零,并在此输入上向后运行哈希。此时,有两种可能的结果:
如果像这样向后运行哈希会产生一个有效的输入字节(即不大于255,并且可能具有其他限制,例如如果您想要所有输入字节都是可打印的ASCII),那么我们可以将输入的第一个字节设置为该值,然后完成!
相反,如果向后运行哈希的结果不是有效的输入字节(例如,如果它大于255),那么我们知道没有第一个字节可以使其余的输入哈希到我们想要的输出,因此我们需要尝试另一个猜测。
这里是一个示例, 它找到与chux代码相同的输入(但将其打印为引用字符串,而不是按照小端整数):
#define TARGET_HASH 0xA7AF2FFE
#define INPUT_LEN 4
int main() {
uint8_t buf[INPUT_LEN+1];
for (int i = 0; i <= INPUT_LEN; i++) buf[i] = 0;
do {
uint32_t ch = reverse_one_at_a_time_hash(buf, INPUT_LEN, TARGET_HASH);
if (ch <= 255) {
buf[0] = ch;
printf("hash(\"");
for (int i = 0; i < INPUT_LEN; i++) {
if (buf[i] < 32 || buf[i] > 126 || buf[i] == '"' || buf[i] == '\\') printf("\\x%02X", buf[i]);
else putchar(buf[i]);
}
printf("\") = 0x%08X\n", TARGET_HASH);
return 0;
}
for (int i = 1; ++buf[i] == 0; i++) ;
} while (buf[INPUT_LEN] == 0);
printf("No matching input of %d bytes found for hash 0x%08X. :(", INPUT_LEN, TARGET_HASH);
return 1;
}
这里有一个限制输入为可打印ASCII字符的版本(并输出五字节字符串^U_N.
):
#define TARGET_HASH 0xA7AF2FFE
#define MIN_INPUT_CHAR ' '
#define MAX_INPUT_CHAR '~'
#define INPUT_LEN 5
int main() {
uint8_t buf[INPUT_LEN+1];
buf[0] = buf[INPUT_LEN] = 0;
for (int i = 1; i < INPUT_LEN; i++) buf[i] = MIN_INPUT_CHAR;
do {
uint32_t ch = reverse_one_at_a_time_hash(buf, INPUT_LEN, TARGET_HASH);
if (ch >= MIN_INPUT_CHAR && ch <= MAX_INPUT_CHAR) {
buf[0] = ch;
printf("hash(\"%s\") = 0x%08X\n", buf, TARGET_HASH);
return 0;
}
int i = 1;
while (buf[i] >= MAX_INPUT_CHAR) buf[i++] = MIN_INPUT_CHAR;
buf[i]++;
} while (buf[INPUT_LEN] == 0);
printf("No matching input of %d bytes found for hash 0x%08X. :(", INPUT_LEN, TARGET_HASH);
return 1;
}
当然,很容易修改这段代码以限制接受哪些输入字节。例如,
使用以下设置:
几秒钟的计算后,生成预映像KQEJZVS
。
限制输入范围确实会使代码运行变慢,因为反向哈希计算结果是有效输入字节的概率当然与可能的有效字节数成比例。
有多种方法可以使这段代码运行得更快。例如,我们可以将反向哈希与递归搜索结合起来, 这样即使只有一个字节发生变化,我们也不必重复哈希整个输入字符串:
#define TARGET_HASH 0xA7AF2FFE
#define MIN_INPUT_CHAR 'A'
#define MAX_INPUT_CHAR 'Z'
#define INPUT_LEN 7
static bool find_preimage(uint32_t hash, uint8_t *buf, int depth) {
hash ^= (hash >> 6) ^ (hash >> 12) ^ (hash >> 18) ^ (hash >> 24) ^ (hash >> 30);
hash *= 0xC00FFC01;
if (depth == 0) {
bool found = (hash >= MIN_INPUT_CHAR && hash <= MAX_INPUT_CHAR);
if (found) buf[0] = hash;
return found;
}
for (uint32_t ch = MIN_INPUT_CHAR; ch <= MAX_INPUT_CHAR; ch++) {
bool found = find_preimage(hash - ch, buf, depth - 1);
if (found) { buf[depth] = ch; return true; }
}
return false;
}
int main() {
uint8_t buf[INPUT_LEN+1];
for (int i = 0; i <= INPUT_LEN; i++) buf[INPUT_LEN] = 0;
uint32_t hash = TARGET_HASH;
hash *= 0x3FFF8001;
hash ^= (hash >> 11) ^ (hash >> 22);
hash *= 0x38E38E39;
bool found = find_preimage(hash, buf, INPUT_LEN - 1);
if (found) {
printf("hash(\"%s\") = 0x%08X\n", buf, TARGET_HASH);
} else {
printf("No matching input of %d bytes found for hash 0x%08X. :(", INPUT_LEN, TARGET_HASH);
}
return !found;
}
但是,我们还没有完成!观察一次性哈希的原始代码,我们可以看到,在循环的第一次迭代之后,
hash
的值将为
((c << 10) + c) ^ ((c << 4) + (c >> 6))
,其中
c
是输入的第一个字节。由于
c
是一个8位字节,这意味着在第一次迭代之后只能设置
hash
的最低18个字节。
事实上,如果我们对于第一个字节的每个可能值,
计算第一次迭代后hash
的值,我们可以看到
hash
从未超过
1042*c
。(实际上,比值
hash/c
的最大值仅为1041.015625 = 1041 + 2
-6。)这意味着,如果
M
是有效输入字节的最大可能值,则第一次迭代后
hash
的值不能超过
1042*M
。而添加下一个输入字节只会使
hash
增加至多
M
。
因此,我们可以通过在find_preimage()
中添加以下快捷检查来显著加速上面的代码:
// optimization: return early if no first two bytes can possibly match
if (depth == 1 && hash > MAX_INPUT_CHAR * 1043) return false;
事实上,类似的论点可以用来表明,在处理了前两个字节后,最多只能设置
哈希的最低28个字节(更准确地说,
哈希与最大输入字节值的比率最多为1084744.46667)。因此,我们可以通过像这样重写
find_preimage()
来扩展上述优化以涵盖搜索的最后三个阶段:
static bool find_preimage(uint32_t hash, uint8_t *buf, int depth) {
hash ^= (hash >> 6) ^ (hash >> 12) ^ (hash >> 18) ^ (hash >> 24) ^ (hash >> 30);
hash *= 0xC00FFC01;
switch (depth) {
case 0:
if (hash < MIN_INPUT_CHAR || hash > MAX_INPUT_CHAR) return false;
buf[0] = hash;
return true;
case 1:
if (hash > MAX_INPUT_CHAR * 1043) return false;
else break;
case 2:
if (hash > MAX_INPUT_CHAR * 1084746) return false;
else break;
}
for (uint32_t ch = MIN_INPUT_CHAR; ch <= MAX_INPUT_CHAR; ch++) {
bool found = find_preimage(hash - ch, buf, depth - 1);
if (found) { buf[depth] = ch; return true; }
}
return false;
}
对于寻找哈希值为0xA7AF2FFE的七字节全大写前像的示例,这种进一步优化将运行时间缩短到仅为0.075秒(相比仅使用
depth == 1
快捷方式的0.148秒,没有快捷方式的递归搜索的2.456秒以及非递归搜索的15.489秒,由TIO计时)。