反向 Jenkins 的一次一个哈希

Question

反向 Jenkins 的一次一个哈希

我将如何获取与返回的哈希匹配的任何可能的字符串值？

我不想获得所使用的确切密钥，只是在传递给函数时将返回与未知密钥相同的哈希值的任何密钥。

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

Run Code Online (Sandbox Code Playgroud)

例如，我将密钥作为“keynumber1”传递，该函数返回 0xA7AF2FFE。我如何找到任何也可以散列到 0xA7AF2FFE 的字符串。

Answer 1

Ilm*_*nen 8

虽然chux 建议的蛮力方法可以正常工作，但实际上我们可以将其加速至 256 左右（事实上，如果我们使用下面描述的所有优化，则速度会更快）。

这里的关键实现是用于计算散列的所有操作都是可逆的。（这是设计使然，因为它确保例如将相同的后缀附加到所有输入字符串不会增加哈希冲突的数量。）具体来说：

hash += hash << n当然，该操作等效于hash *= (1 << n) + 1。我们正在使用 32 位无符号整数，因此所有这些计算都是以2 ³²为模完成的。要撤消此操作，我们需要做的就是找到= 2 ⁿ + 1 modulo 2 ³²的模乘法逆并乘以它。^{(1 << n) + 1^hash}

我们可以很容易地做到这一点，例如使用这个 Python 脚本，基于SO上的这个答案。事实证明，2 ¹⁰ + 1、2 ³ + 1 和2 ¹⁵ + 1的乘法倒数在十六进制中分别为0xC00FFC01、0x38E38E39 和0x3FFF8001。

要找到hash ^= hash >> n某个常量的倒数n，首先要注意此操作使的最高n位hash完全不变。下一个较低的n位与最高n位简单地进行异或，因此对于那些，只需重复操作即可撤消它。到目前为止看起来很简单，对吧？

为了恢复第三高位组的原始值n，我们需要将它们与第二高位的原始值进行异或n，我们当然可以通过n如上所述对两个最高位组进行异或来计算。等等。

这一切归结为逆运算hash ^= hash >> n是：

hash ^= (hash >> n) ^ (hash >> 2*n) ^ (hash >> 3*n) ^ (hash >> 4*n) ^ ...
Run Code Online (Sandbox Code Playgroud)
当然，一旦移位量等于或大于我们正在处理的整数中的位数（即在这种情况下为 32），我们就可以切断序列。或者，我们可以在多个步骤中获得相同的结果，每次将移位量加倍，直到超过我们正在处理的数字的位长，如下所示：

hash ^= hash >> n; hash ^= hash >> 2*n; hash ^= hash >> 4*n; hash ^= hash >> 8*n; // etc.
Run Code Online (Sandbox Code Playgroud)
（n与整数大小相比，多步方法在较小时可以更好地扩展，但对于中等大小的n，单步方法可能会在现代 CPU 上遭受更少的管道停顿。很难说在任何给定情况下，哪一个实际上更有效，没有两者都进行基准测试，结果可能因编译器和 CPU 模型而异。无论如何，这种微优化大多不值得太担心。）

最后，当然，的倒数hash += key[i++]很简单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 }
Run Code Online (Sandbox Code Playgroud)
然后调用，比如说，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; }
Run Code Online (Sandbox Code Playgroud)
而且这里有一个限制输入可打印的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; }
Run Code Online (Sandbox Code Playgroud)
当然，很容易修改此代码以更加严格地限制接受哪些输入字节。例如，使用以下设置：

#define TARGET_HASH 0xA7AF2FFE #define MIN_INPUT_CHAR 'A' #define MAX_INPUT_CHAR 'Z' #define INPUT_LEN 7
Run Code Online (Sandbox Code Playgroud)
产生（经过几秒钟的计算）原像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; }
Run Code Online (Sandbox Code Playgroud)
但是等等，我们还没有完成！查看一次一次散列的原始代码，我们可以看到hash循环第一次迭代后的值将是((c << 10) + c) ^ ((c << 4) + (c >> 6))，其中c是输入的第一个字节。由于c是一个八位字节，这意味着hash在第一次迭代后只能设置最低的 18 个字节。

事实上，如果我们为第一个字节的每个可能值计算hash第一次迭代后的值c，我们可以看到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;
Run Code Online (Sandbox Code Playgroud)
实际上，可以使用类似的参数来表明，在处理前两个字节后，最多hash可以设置的最低 28 个字节（更准确地说，的hash与最大输入字节值的比率最多为 1084744.46667 ）。因此，我们可以通过如下重写来扩展上面的优化以涵盖搜索的最后三个阶段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; }
Run Code Online (Sandbox Code Playgroud)
对于哈希 0xA7AF2FFE 的七字节全大写原像的示例搜索，这种进一步的优化将运行时间减少到仅 0.075 秒（而depth == 1单独的快捷方式为 0.148 秒，没有快捷方式的递归搜索为 2.456 秒，非递归搜索为 15.489 秒，由 TIO 计时）。

归档时间：	6 年，9 月前
查看次数：	1400 次
最近记录：	6 年，9 月前