给定此哈希函数、预期输出和输入字符串的长度，如何找到 returns 给定结果的输入字符串？

Question

我下面有这个哈希函数。

我知道对于长度为 8 的输入字符串，我得到的哈希值为 16530092119764772

输入的字符串只能由字符"abcdefghijklmnop"

组成

查找输入字符串的最佳方法是什么？

有没有一种方法可以在不依赖蛮力查找字符串的情况下从数学上分解问题？

递归解决方案会溢出堆栈吗？

function hash(str) {

  let g = 8;
  let charset = "abcdefghijklmnop";

  for(let i = 0; i < str.length; i++) {
    g = (g * 82 + charset.indexOf(str[i]));
  }

  return g;

}

例如字符串 "agile" 它散列为 29662550362

Answer 1

您可以创建一个从 8 开始的递归函数，遍历字符集索引并在当前值超过传递的哈希值时停止 (returns)。

查看下面的评论了解更多详情：

const charset = 'abcdefghijklmnop';

function bruteforce(hash, base = 8, result = {value: ''}) {
  // Always multiply the previous value by 82
  base *= 82;

  for (let i = 0; i < charset.length; i++) {
    // Add the char index to the value
    value = base + i;
    // If we found the hash, append the current char and return
    if (value === hash) {
      result.value += charset[i];
      return base === 656 ? result.value : value;
    }
    // If we went past the hash, return null to mark this iteration as failed
    if (value > hash) {
      return null;
    }
    // Otherwise, attempt next level starting from current value
    value = bruteforce(hash, value, result);
    // If we found the hash from there, prepend the current char and return
    if (value === hash) {
      result.value = charset[i] + result.value;
      return base === 656 ? result.value : value;
    }
  }

  // We tried everything, no match found :(
  return null;
}

console.log(bruteforce(29662550362));

Answer 2

这甚至不是真正的哈希，因为 charset 中没有 82 个字符。这更像是将字符串解析为 base-82 数字，您只能使用前 16 个符号。如果它不使用浮点数，那将是完全可逆的，浮点数对于那么大的整数来说是不精确的。如果你不熟悉为什么，简化版本是循环内的操作：

g * 82 + d

只要 d 小于 82，

就会对 g 和 d 的每个可能值给出不同的结果，因为 g * 82 和 (g + 1) * 82 之间有足够的 space 来适应 82 个不同的结果ds（从 0 到 81）。通过除以 82，每个不同的结果都可逆回到 g 和 d；整数为g，余数为d。当循环内的每一个操作都是可逆的，你就可以逆转整个事情。

因此，就像您可以使用一次除掉一位数字的循环手动将数字转换为十进制一样，您可以将这个不精确的数字转换为基数 82：

const getDigits = (value, base) => {
    const result = [];
  
    while (value) {
        result.push(value % base);
        value /= base;
    }
  
    return result.reverse();
};

const getLetter = index =>
    String.fromCharCode(97 + index);

const getPreimage = value =>
    getDigits(value, 82n)
        .map(Number)
        .map(getLetter)
        .join('');

console.log(getPreimage(29662550362n));
console.log(getPreimage(16530092119764772n));

结果以“i”开头，因为 g 从 8 而不是 0 开始。第二个数字也足够大而不是唯一的（与 agile 的“哈希”相反，可以用 JavaScript 数字精确表示），但如果你只是想找到 any 原像，它就足够了。

function hash(str) {

  let g = 8;
  let charset = "abcdefghijklmnop";

  for(let i = 0; i < str.length; i++) {
    g = (g * 82 + charset.indexOf(str[i]));
  }

  return g;

}

for (const s of ['hijackec', 'hijacked', 'hijackee', 'hijackef', 'hijackeg']) {
    console.log(s, hash(s) === 16530092119764772);
}

给定此哈希函数、预期输出和输入字符串的长度，如何找到 returns 给定结果的输入字符串？

Given this hash function, an expected output, and the length of the input string, how do I find the input string that returns the given result?

javascript

reverse-engineering

hash-function

brute-force