我该如何获取匹配返回的哈希值的任何可能字符串值？
我不想获取使用的确切键，只是任何键当传递到函数中时，将返回未知键的相同哈希值。
uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
size_t i = 0;
uint32_t hash = 0;
while (i != length) {
hash += key[i++];
hash += hash << 10;
hash ^= hash >> 6;
}
hash += hash << 3;
hash ^= hash >> 11;
hash += hash << 15;
return hash;
}
虽然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]; // buffer for guessed input (and one more null byte at the end)
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;
// print the input with unprintable chars nicely quoted
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;
}
// increment buffer, starting from second byte
for (int i = 1; ++buf[i] == 0; i++) /* nothing */;
} 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]; // buffer for guessed input (and one more null byte at the end)
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;
}
// increment buffer, starting from second byte, while keeping bytes within the valid range
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;
}
#define TARGET_HASH 0xA7AF2FFE
#define MIN_INPUT_CHAR 'A'
#define MAX_INPUT_CHAR 'Z'
#define INPUT_LEN 7
几秒钟的计算后，生成预映像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) {
// first invert the hash mixing step
hash ^= (hash >> 6) ^ (hash >> 12) ^ (hash >> 18) ^ (hash >> 24) ^ (hash >> 30);
hash *= 0xC00FFC01; // inverse of hash += hash << 10;
// then check if we're down to the first byte
if (depth == 0) {
bool found = (hash >= MIN_INPUT_CHAR && hash <= MAX_INPUT_CHAR);
if (found) buf[0] = hash;
return found;
}
// otherwise try all possible values for this byte
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]; // buffer for results
for (int i = 0; i <= INPUT_LEN; i++) buf[INPUT_LEN] = 0;
// first undo the finalization step
uint32_t hash = TARGET_HASH;
hash *= 0x3FFF8001; // inverse of hash += hash << 15;
hash ^= (hash >> 11) ^ (hash >> 22);
hash *= 0x38E38E39; // inverse of hash += hash << 3;
// then search recursively until we find a matching input
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;
find_preimage()来扩展上述优化以涵盖搜索的最后三个阶段：static bool find_preimage(uint32_t hash, uint8_t *buf, int depth) {
// first invert the hash mixing step
hash ^= (hash >> 6) ^ (hash >> 12) ^ (hash >> 18) ^ (hash >> 24) ^ (hash >> 30);
hash *= 0xC00FFC01; // inverse of hash += hash << 10;
// for the lowest three levels, abort early if no solution is possible
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;
}
// otherwise try all possible values for this byte
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;
}
depth == 1快捷方式的0.148秒，没有快捷方式的递归搜索的2.456秒以及非递归搜索的15.489秒，由TIO计时）。int main() {
const char *key1 = "keynumber1";
uint32_t match = jenkins_one_at_a_time_hash(key1, strlen(key1));
printf("Target 0x%lX\n", (unsigned long) match);
uint32_t i = 0;
do {
uint32_t hash = jenkins_one_at_a_time_hash(&i, sizeof i);
if (hash == match) {
printf("0x%lX: 0x%lX\n", (unsigned long) i, (unsigned long) hash);
fflush(stdout);
}
} while (++i);
const char *key2 = "\x3C\xA0\x94\xB9";
uint32_t match2 = jenkins_one_at_a_time_hash(key2, strlen(key2));
printf("Match 0x%lX\n", (unsigned long) match2);
}
输出
Target 0xA7AF2FFE
0xB994A03C: 0xA7AF2FFE
Match 0xA7AF2FFE
PB3PT"!!. - chux - Reinstate Monica