如何强制执行有损 AND 例程？

Question

我想知道是否有任何标准方法可以通过蛮力逆转 AND 例程。例如，我有以下转换：

MOV(eax, 0x5b3e0be0)  <- Here we move 0x5b3e0be0 to EDX.
MOV(edx, eax)  # Here we copy 0x5b3e0be0 to EAX as well.
SHL(edx, 0x7)  # Bitshift 0x5b3e0be0 with 0x7 which results in 0x9f05f000
AND(edx, 0x9d2c5680)  # AND 0x9f05f000 with 0x9d2c5680 which results in 0x9d045000
XOR(edx, eax)  # XOR 0x9d045000 with original value 0x5b3e0be0 which results in 0xc63a5be0

我的问题是如何蛮力和反转这个例程（即将 0xc63a5be0 转换回 0x5b3e0be0）

我的一个想法（不起作用）是使用 PeachPy 实现：

#Input values
MOV(esi, 0xffffffff) < Initial value to AND with, which will be decreased by 1 in a loop.
MOV(cl, 0x1) < Initial value to SHR with which will be increased by 1 until 0x1f.
MOV(eax, 0xc63a5be0) < Target result which I'm looking to get using the below loop.
MOV(edx, 0x5b3e0be0) < Input value which will be transformed.

sub_esi = peachpy.x86_64.Label()
with loop:
    #End the loop if ESI = 0x0
    TEST(esi, esi)
    JZ(loop.end)
    #Test the routine and check if it matches end result.
    MOV(ebx, eax)
    SHR(ebx, cl)
    TEST(ebx, ebx)
    JZ(sub_esi)
    AND(ebx, esi)
    XOR(ebx, eax)
    CMP(ebx, edx)
    JZ(loop.end)
    #Add to the CL register which is used for SHR.
    #Also check if we've reached the last potential value of CL which is 0x1f
    ADD(cl, 0x1)
    CMP(cl, 0x1f)
    JNZ(loop.begin)

    #Decrement ESI by 1, reset CL and restart routine.
    peachpy.x86_64.LABEL(sub_esi)
    SUB(esi, 0x1)
    MOV(cl, 0x1)
    JMP(loop.begin)

#The ESI result here will either be 0x0 or a valid value to AND with and get the necessary result.
RETURN(esi)

也许您可以推荐专门针对此的文章或书籍？

Answer 1

它不是有损的，最终的操作是 XOR。
整个例程可以在 C 中建模为

#define K 0x9d2c5680
uint32_t hash(uint32_t num)
{
  return num ^ ( (num << 7) & K);
}

现在，如果我们有两个位x和y以及操作x XOR y，当y为零时，结果是x。
因此，给定两个数字n1和n2并考虑它们的异或，与n2 中的零配对的位或n1将使其结果不变（其他将被翻转）。

因此在考虑num ^ ( (num << 7) & K)，我们可以找出num与N1和(num << 7) & K用N2。
由于n2是 AND，我们可以看出它必须至少具有与K相同的零位。
这意味着它的每一位num对应于常数K 中的零位，将使其不变进入结果。
因此，通过从结果中提取这些位，我们已经有了一个部分反函数：

/*hash & ~K extracts the bits of hash that pair with a zero bit in K*/
partial_num = hash & ~K

从技术上讲，该因子num << 7还会在 AND 的结果中引入其他零。我们确信最低 7 位必须为零。
然而K已经有最低的 7 位零，所以我们不能利用这个信息。
所以我们在这里只使用K，但如果它的值不同，你需要考虑 AND （​​实际上，这意味着将K的低 7 位归零）。

这让我们有 13 位未知（对应于在K中设置的位）。如果我们暂时忘记AND，我们就会有这样的x ^ (x << 7)意思

h _i = num _i for i from 0 to 6 inclusive
h _i = num _i ^ num _i-7 for i from 7 to 31 inclusive
(第一行是因为右边的低7位为零)

由此，从 h ₇开始向上，我们可以将 num ₇检索为 h ₇ ^ num ₀ = h ₇ ^ h ₀。
从第 7 位开始，等式不起作用，我们需要使用 num _k（对于合适的k），但幸运的是我们已经在上一步计算了它的值（这就是我们从低到高开始的原因）。

AND 对此所做的只是限制索引i运行的值，特别是仅限制在K中设置的位。

因此，要填写剩下的 13 个位，您必须这样做：

part_num ₇ = h ₇ ^ part_num ₀
part_num ₉ = h ₉ ^ part_num ₂
part_num ₁₂ = h ₁₂ ^ part_num ₅
...
part_num ₃₁ = h ₃₁ ^ part_num ₂₄

请注意，我们利用了 part_num _0..6 = h _{0..6 的}事实。

这是一个反转函数的 C 程序：

#include <stdio.h>
#include <stdint.h>


#define BIT(i, hash, result) ( (((result >> i) ^ (hash >> (i+7))) & 0x1) << (i+7) )
#define K 0x9d2c5680

uint32_t base_candidate(uint32_t hash)
{
  uint32_t result = hash & ~K;

  result |= BIT(0, hash, result);
  result |= BIT(2, hash, result);
  result |= BIT(3, hash, result);
  result |= BIT(5, hash, result);
  result |= BIT(7, hash, result);
  result |= BIT(11, hash, result);
  result |= BIT(12, hash, result);
  result |= BIT(14, hash, result);
  result |= BIT(17, hash, result);
  result |= BIT(19, hash, result);
  result |= BIT(20, hash, result);
  result |= BIT(21, hash, result);
  result |= BIT(24, hash, result);

  return result;
}

uint32_t hash(uint32_t num)
{
  return num ^ ( (num << 7) & K);
}



int main()
{

  uint32_t tester = 0x5b3e0be0;
  uint32_t candidate = base_candidate(hash(tester));

  printf("candidate: %x, tester %x\n", candidate, tester);
  
  return 0;

}