下面是一个针对数学问题的复杂伪代码,它试图检查输入的密码是否正确。 j作为行,列,k作为临时变量以生成测试条件。
元素v6,v7,v8等在k循环中用作数组。
最终目标是返回0用于成功完成代码。

signed __int64 __fastcall check_password(const char *a1)
{
  signed int i; // [rsp+10h] [rbp-30h]
  signed int j; // [rsp+14h] [rbp-2Ch]
  int v4; // [rsp+18h] [rbp-28h]
  signed int k; // [rsp+1Ch] [rbp-24h]
  char v6; // [rsp+20h] [rbp-20h]
  char v7; // [rsp+21h] [rbp-1Fh]
  char v8; // [rsp+22h] [rbp-1Eh]
  char v9; // [rsp+23h] [rbp-1Dh]
  char v10; // [rsp+24h] [rbp-1Ch]
  char v11; // [rsp+25h] [rbp-1Bh]
  char v12; // [rsp+26h] [rbp-1Ah]
  char v13; // [rsp+27h] [rbp-19h]
  char v14; // [rsp+28h] [rbp-18h]
  unsigned __int64 v15; // [rsp+38h] [rbp-8h]

  v15 = __readfsqword(0x28u);
  v6 = 79; 
  v7 = 8;
  v8 = 29;
  v9 = 58;
  v10 = 81;
  v11 = 21;
  v12 = 49;
  v13 = 123;
  v14 = 114;
  if ( strlen(a1) != 9 )
    return -1;
  for ( i = 0; i <= 2; ++i )
  {
    for ( j = 0; j <= 2; ++j )
    {
      v4 = 0;
      for ( k = 0; k <= 2; ++k )
        v4 = (a1[3 * k + j] * *(&v6 + 3 * i + k) + v4) % 127;
      if ( i == j )
      {
        if ( v4 != 1 )
          return -2;
      }
      else if ( v4 )
      {
        return -2;
      }
    }
  }
  return 0;
}


评论

您也可以附加二进制文件吗?我想对反编译代码中的数据类型进行一些更改。

看起来正在乘以2个3x3矩阵,并且乘积的对角线在int8_t限制内应全部为1。我在IDA中验证了答案后,就会写出正确的答案。

@sudhackar产品必须是身份矩阵,其中n = 3。请注意,除对角线外,其他所有值都必须精确为0。期待阅读您的答案:)

@Nirlzr哦,是的,我想念所有其他的零。谢谢。

@sudhackar链接到完整的二进制drive.google.com/file/d/1GatqkD_6lUFdrxs_WYPYOrv6VQoE0tHj/…,(输入传递的矩阵长度必须为9)

#1 楼

由于您已经对代码进行了大部分解码,所以剩下两件事了:1)了解代码在做什么,以及2)了解如何计算适当的输入。

原始代码

首先,这是根据您已有的内容略微修改的代码:

int check_password(const char *s) {
    char fixed[] __attribute__ ((aligned (16))) = { 79, 8, 29, 58, 81, 21, 49, 123, 114 };
    if (strlen(s) != 9)
        return -1;
    for (int i=0; i < 3; ++i) {
        for (int j=0; j < 3; ++j) {
            int sum = 0;
            for (int k=0; k < 3; ++k) {
                sum = (fixed[3 * i + k] * s[3 * k + j] + sum) % 127;
            }
            if (i == j) {
                if (sum != 1) {
                    return -2;
                }
            } else if (sum) {
                return -2;
            }
        }
    }
    return 0;
}


出于我们的目的,可以忽略__attribute__ ((aligned (16)))。 (我包括了让gcc使用与您的示例代码相同的堆栈偏移量。)代码正在执行的工作是将两个3x3矩阵mod 127相乘,并检查单位矩阵。

数学

不幸的是,ReverseEngineering不支持MathJax,或者我可以写出漂亮的方程式。既然我做不到,我们将尽全力。假设s = "ABCDEFGHI"是输入密码,我们将其视为3x3矩阵。现在,如果我们仅将每个大写字母分配给密码中的每个字母(以矩阵表示),则为:

,您可能已经意识到这意味着s必须是fixed矩阵的逆矩阵。有多种计算方法,例如通过高斯-乔丹消除法。另一种方法是将矩阵行列式的倒数乘以其辅助因子矩阵的转置。请注意,所有数学均按照原始代码在mod 127上完成。并显示逐步的解决方案。首先,我们使用Leibniz公式计算行列式。

A B C        79   8  29       1 0 0
D E F   x    58  81  21   =   0 1 0    (mod 127)
G H I        49 123 114       0 0 1


为了计算倒数,我们不能仅使用1/34,因为我们正在使用模块化数学。因此,就像我们期望正规数学34 * 1/34 = 1一样,在模块化数学中,我们正在寻找能够满足方程34 * x = 1 (mod 127)的事物。一种方法是使用扩展的欧几里得算法。在这里,我将不介绍该算法,但是在这种情况下,答案是71(我们可以通过注意71 * 34 = 2414 = 1 (mod 127)进行验证。 t完成所有步骤,但fixed的辅因子矩阵为:

D = 79*81*114 + 8*21*49 + 29*58*123 - 29*81*49 - 8*58*114 - 79*21*123   (mod 127)
D = 572550 (mod 127)
D = 34  (mod 127)


由于我们正在使用模块化数学,因此可以减少此:

 6651  -5583   3165
 2655   7585  -9325     (mod 127) 
-2181     23   5935


现在剩下的就是将它们相乘:

 47     5   117
115    92    73      (mod 127)
105    23    93


最后,我们进行转置:

         47     5   117
71   *  115    92    73      (mod 127)
        105    23    93


3337    355   8307
8165   6532   5183   (mod 127) 
7455   1633   6603

35   101    52
37    55   103    (mod 127)
89   109   126


如果再将此矩阵转换回ASCII字符串,则会得到"#%Ye7m4g~",它是给定矩阵的逆矩阵以及该逆向工程问题的解决方案。 >
为什么这很重要

虽然它本身可能是一个足够有趣的难题,但是使用离散数学和模块化算术进行的这类转换是现代密码学许多领域的基础。我已经开始寻找我在逆向工程中,您可能也会发现研究这些主题也很有用和有趣。

评论


一个很好的答案!

– NirIzr
18-10-29在4:44

+1用于矩阵说明。提示:可以使用ASCII格式对矩阵进行格式化。

– Biswapriyo
'18 -10-31在6:26