4

Below is a complex pseudocode for a mathematical problem which attempts to check if a password entered is correct or not.

Previous Analysis Done: Data is arranged in the form of 3x3 Matrix with i,j as row, columns and k as a temporary variable to generate test conditions. Elements v6, v7, v8 .. etc are used in the k loop as an array. The end goal is to return 0 for successful completion of the code.

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
    Can you attach the binary too? I would like to make some changes in the data types in the decompiled code. – sudhackar Oct 26 '18 at 2:55
  • 2
    It looks like that 2 3x3 matrices are being multiplied and the product's diagonal should be all 1 in int8_t limits. I would write a proper answer once I have verified that in IDA. – sudhackar Oct 26 '18 at 3:11
  • 1
    @sudhackar The product is required to be the Identity matrix where n=3. Notice any other values except the diagonal are required to be precisely 0. Looking forward to reading your answer :) – NirIzr Oct 26 '18 at 5:04
  • 1
    @Nirlzr oh yes I missed all other being 0. Thanks. – sudhackar Oct 26 '18 at 5:10
  • @sudhackar Link to full binary drive.google.com/file/d/1GatqkD_6lUFdrxs_WYPYOrv6VQoE0tHj/…, (input pass needs to have length 9 as its matrix) – Sujith Sizon Oct 26 '18 at 10:57
12
+50

Since you've already mostly decoded the code, there are two things left: 1) understand what the code is doing and 2) understand how to compute the appropriate input.

The original code

First, here's a slightly modified bit of code based on what you already had:

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

The __attribute__ ((aligned (16))) can be ignored for our purposes. (I had included that to get gcc to use the same stack offset as your sample code.) What the code is doing is multiplying two 3x3 matrices, mod 127, and checking for the identity matrix.

The mathematics

Unfortunately, ReverseEngineering does not support MathJax, or I'd be able to write out pretty equations. Since I can't we'll do it the hard way. Let's say s = "ABCDEFGHI" is the input password and we treat it as a 3x3 matrix. For now, if we just assign uppercase letters to each letter in the password, expressed as a matrix, this is:

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

If you're familiar with matrix manipulation already, you may already recognize that this means that s must be the inverse of the fixed matrix. There are multiple ways of calculating this, such as by Gauss-Jordan elimination. Another way is to multiply the reciprocal of the determinant of the matrix by the transpose of its cofactor matrix. Note that all of the mathematics is done mod 127, as per the original code.

Worked example

To make things a bit more concrete, I'll use the latter method and show the step-by-step worked solution. First, we calculate the determinant using the Leibniz formula.

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)

To compute the reciprocal, of this we can't just use 1/34 because we're working with modular mathematics. So just in the way that we'd expect that 34 * 1/34 = 1 for regular mathematics, in modular mathematics, we're looking for something that satifies the equation 34 * x = 1 (mod 127). One way to do this is to use the extended Euclidean algorithm. I won't go through that algorithm here, but in this case, the answer is 71 (which we can verify by noting that 71 * 34 = 2414 = 1 (mod 127).

Next we calculate the cofactor matrix. Here again, we won't go through all of the steps, but the cofactor matrix of fixed is:

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

Since we're working with modular mathematics, we can reduce this:

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

Now all that's left is to multiply them together:

         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

Finally, we take the transpose:

 35    37    89
101    55   109
 52   103   126

If we then translate this matrix back into an ASCII string, we get "#%Ye7m4g~" which is the inverse of the given matrix and the solution to this reverse engineering problem.

Why this might matter

While it may be an interesting enough puzzle by itself, these kinds of transformations using discrete mathematics and modular arithmetic are fundamental to many areas of modern cryptography. Since you've already started looking into reverse engineering, you may find it useful and interesting to study these topics as well.

  • 1
    A great answer! – NirIzr Oct 29 '18 at 4:44
  • 1
    +1 for the matrix explanation. Tip: The matrix can be formatted with ASCII art. – Biswapriyo Oct 31 '18 at 6:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.