1nzag

[Python] gmpy invert, divm (rctf 2018 babyre2)

rev

오늘은 파이썬 툴인 gmpy 에 대해서 써보려고 한다. 이 툴은 여러 분야에서 많이 사용될 수 있지만, 리버싱에서도 역연산을 할때 좋은 툴이기 때문에 간간히 쓰면 좋을 듯 하다.


이 툴을 모를때는 역연산을 구할때, 특히 정수론적인 부분에서 역연산을 구할때 어려움을 많이 겪었었다. 


(기억에 남는 것은 mod n 에 대한 곱셈의 역원을 구해야 하는 상황일때 였던 것 같다.)


gmpy 툴은 이러한 연산을 할때나, 역연산을 할때나 매우 유용하게 쓸 수 있다. 


사용법이나 함수, 메소드에 관한 백서는 아래 링크에 있다.


https://media.readthedocs.org/pdf/gmpy2/latest/gmpy2.pdf


이 툴에 대해서 많이 사용해 보진 않았지만 좋게 썼던 두 가지 함수에 대해서 소개하려고 한다. 


1. invert

invert 함수는 위에서 말한 것 처럼 mod n 에 대한 곱셈의 역원을 구할 때 쓸 수 있는 함수이다. 백서에 나와있는 설명을 보면 다음과 같이 설명이 되어있다. 


 invert(...) invert(x, m) returns y such that x * y == 1 modulo m, or 0 if no such y exists


역원이 존재하지 않을때는 0을 리턴한다.

invert 함수를 응용하면 모듈러 제곱에 대한 역연산도 구할 수 있다.


2. divm 


divm 함수는 모듈러 곱에 대한 역연산을 계산해준다. 

 divm(...) divm(a, b, m) returns x such that b * x == a modulo m. Raises a ZeroDivisionError exception if no such value x exists.


a 값에 1을 넣어주면 invert 함수처럼 사용할 수 도 있을것이다.


이러한 모듈러 연산에 대한 계산은 관련 역연산을 계산할때 아주 편리했다. z3 solver 같은경우도 해답을 찾는데에 무리가 많이 가는데, gmpy는 이러한 문제를 해결하는데 도움을 준다. 

 

예시로 rctf  2018에 나왔던 babyre2 문제를 풀어보겠다.


__int64 __fastcall main(__int64 a1, char **a2, char **a3)

{

  unsigned __int64 v3; // rax

  __m128i v4; // xmm1

  __m128i v5; // xmm0

  unsigned __int64 v7; // [rsp+0h] [rbp-198h]

  unsigned __int64 v8; // [rsp+8h] [rbp-190h]

  unsigned __int64 v9; // [rsp+10h] [rbp-188h]

  unsigned __int64 v10; // [rsp+18h] [rbp-180h]

  unsigned __int64 v11; // [rsp+20h] [rbp-178h]

  unsigned __int64 v12; // [rsp+28h] [rbp-170h]

  unsigned __int64 v13; // [rsp+30h] [rbp-168h]

  unsigned __int64 v14; // [rsp+38h] [rbp-160h]

  unsigned __int64 v15; // [rsp+40h] [rbp-158h]

  unsigned __int64 v16; // [rsp+48h] [rbp-150h]

  unsigned __int64 v17; // [rsp+50h] [rbp-148h]

  unsigned __int64 v18; // [rsp+58h] [rbp-140h]

  unsigned __int64 v19; // [rsp+60h] [rbp-138h]

  unsigned __int64 v20; // [rsp+68h] [rbp-130h]

  unsigned __int64 v21; // [rsp+70h] [rbp-128h]

  unsigned __int64 v22; // [rsp+78h] [rbp-120h]

  char s[8]; // [rsp+80h] [rbp-118h]

  unsigned __int64 v24; // [rsp+88h] [rbp-110h]

  unsigned __int64 v25; // [rsp+90h] [rbp-108h]

  unsigned __int64 v26; // [rsp+98h] [rbp-100h]

  unsigned __int64 v27; // [rsp+A0h] [rbp-F8h]

  unsigned __int64 v28; // [rsp+A8h] [rbp-F0h]

  unsigned __int64 v29; // [rsp+B0h] [rbp-E8h]

  unsigned __int64 v30; // [rsp+B8h] [rbp-E0h]

  unsigned __int64 v31; // [rsp+C0h] [rbp-D8h]

  unsigned __int64 v32; // [rsp+C8h] [rbp-D0h]

  unsigned __int64 v33; // [rsp+D0h] [rbp-C8h]

  unsigned __int64 v34; // [rsp+D8h] [rbp-C0h]

  unsigned __int64 v35; // [rsp+E0h] [rbp-B8h]

  unsigned __int64 v36; // [rsp+E8h] [rbp-B0h]

  unsigned __int64 v37; // [rsp+F0h] [rbp-A8h]

  unsigned __int64 v38; // [rsp+F8h] [rbp-A0h]

  __int128 v39; // [rsp+100h] [rbp-98h]

  __m128i v40; // [rsp+110h] [rbp-88h]

  __int128 v41; // [rsp+120h] [rbp-78h]

  __int128 v42; // [rsp+130h] [rbp-68h]

  __int128 v43; // [rsp+140h] [rbp-58h]

  __int128 v44; // [rsp+150h] [rbp-48h]

  __int128 v45; // [rsp+160h] [rbp-38h]

  __m128i v46; // [rsp+170h] [rbp-28h]

  unsigned __int64 v47; // [rsp+188h] [rbp-10h]


  v47 = __readfsqword(0x28u);

  v30 = -1LL;

  v31 = -1LL;

  v7 = 6148914691236517205LL;

  v8 = 6148914691236517205LL;

  v9 = 6148914691236517205LL;

  v10 = 6148914691236517205LL;

  v11 = 6148914691236517205LL;

  v12 = 6148914691236517205LL;

  v13 = 6148914691236517205LL;

  v14 = 6148914691236517205LL;

  v15 = 6148914691236517205LL;

  v16 = 6148914691236517205LL;

  v17 = 6148914691236517205LL;

  v18 = 6148914691236517205LL;

  v19 = 6148914691236517205LL;

  v20 = 6148914691236517205LL;

  v21 = 6148914691236517205LL;

  v22 = 6148914691236517205LL;

  strcpy(s, "Welcome to RCTF 2018! Here is a BabyRE challenge for you.");

  v32 = -1LL;

  v33 = -1LL;

  v34 = -1LL;

  v35 = -1LL;

  v36 = -1LL;

  v37 = -1LL;

  v38 = -1LL;

  puts(s);

  __printf_chk(1LL, "Give me your flag: ");

  __isoc99_scanf("%127s", &v7);

  *(_QWORD *)&v39 = sub_400BA0(v7 * (unsigned __int128)*(unsigned __int64 *)s, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *((_QWORD *)&v39 + 1) = sub_400BA0(v8 * (unsigned __int128)v24, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  v40.m128i_i64[0] = sub_400BA0(v9 * (unsigned __int128)v25, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  v40.m128i_i64[1] = sub_400BA0(v10 * (unsigned __int128)v26, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *(_QWORD *)&v41 = sub_400BA0(v11 * (unsigned __int128)v27, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *((_QWORD *)&v41 + 1) = sub_400BA0(v12 * (unsigned __int128)v28, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *(_QWORD *)&v42 = sub_400BA0(v13 * (unsigned __int128)v29, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *((_QWORD *)&v42 + 1) = sub_400BA0(v14 * (unsigned __int128)v30, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *(_QWORD *)&v43 = sub_400BA0(v15 * (unsigned __int128)v31, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *((_QWORD *)&v43 + 1) = sub_400BA0(v16 * (unsigned __int128)v32, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *(_QWORD *)&v44 = sub_400BA0(v17 * (unsigned __int128)v33, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *((_QWORD *)&v44 + 1) = sub_400BA0(v18 * (unsigned __int128)v34, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *(_QWORD *)&v45 = sub_400BA0(v19 * (unsigned __int128)v35, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  *((_QWORD *)&v45 + 1) = sub_400BA0(v20 * (unsigned __int128)v36, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  v46.m128i_i64[0] = sub_400BA0(v21 * (unsigned __int128)v37, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  v3 = sub_400BA0(v22 * (unsigned __int128)v38, 0xFFFFFFFFFFFFFFC5LL, 0LL);

  v4 = _mm_load_si128((const __m128i *)&v39);

  v46.m128i_i64[1] = v3;

  v5 = _mm_or_si128(

         _mm_xor_si128(_mm_load_si128((const __m128i *)&xmmword_6020D0), v46),

         _mm_or_si128(

           _mm_xor_si128(_mm_load_si128((const __m128i *)&v45), (__m128i)xmmword_6020C0),

           _mm_or_si128(

             _mm_xor_si128(_mm_load_si128((const __m128i *)&v44), (__m128i)xmmword_6020B0),

             _mm_or_si128(

               _mm_xor_si128(_mm_load_si128((const __m128i *)&v43), (__m128i)xmmword_6020A0),

               _mm_or_si128(

                 _mm_xor_si128(_mm_load_si128((const __m128i *)&v42), (__m128i)xmmword_602090),

                 _mm_or_si128(

                   _mm_xor_si128(_mm_load_si128((const __m128i *)&v41), (__m128i)xmmword_602080),

                   _mm_or_si128(

                     _mm_xor_si128(v4, (__m128i)xmmword_602060),

                     _mm_xor_si128(_mm_load_si128((const __m128i *)&xmmword_602070), v40))))))));

  if ( (unsigned __int64)*(_OWORD *)&_mm_or_si128(v5, _mm_srli_si128(v5, 8)) )

    puts("Incorrect.");

  else

    puts("Correct. Congratulations!");

  return 0LL;

}

다음과 같이 함수에 나오는 값이 모두 만족이 되면 통과가 된다. 


이때 해당 함수의 내용을 보면 이상한 코드들이 많지만 대부분 쓸모없는 코드라는 것을 알 수 있다. 

unsigned __int64 __fastcall sub_400BA0(unsigned __int128 a1, unsigned __int64 a2, unsigned __int64 zero)

{

  unsigned __int64 v3; // r10

  unsigned __int64 result; // rax

  unsigned __int64 v5; // rdx

  __int64 v6; // rbp

  int v7; // ebp

  unsigned __int64 v8; // rbx

  unsigned __int64 v9; // r10

  unsigned __int64 v10; // r8

  unsigned __int128 v11; // tt

  unsigned __int64 v12; // rsi

  unsigned __int128 v13; // ax

  unsigned __int64 v14; // rcx

  unsigned __int64 v15; // rdi

  unsigned __int128 v16; // ax

  unsigned __int128 v17; // tt


  v3 = a2;

  result = a1;

  if ( zero )

  {

    if ( zero > *((_QWORD *)&a1 + 1) )

    {

      result = a1;

    }

    else

    {

      _BitScanReverse64((unsigned __int64 *)&v6, zero);

      v7 = v6 ^ 0x3F;

      if ( v7 )

      {

        v8 = a2 << v7;

        v9 = (zero << v7) | (a2 >> (64 - (unsigned __int8)v7));

        v10 = (_QWORD)a1 << v7;

        *(_QWORD *)&v11 = ((unsigned __int64)a1 >> (64 - (unsigned __int8)v7)) | (*((_QWORD *)&a1 + 1) << v7);

        *((_QWORD *)&v11 + 1) = *((_QWORD *)&a1 + 1) >> (64 - (unsigned __int8)v7);

        v12 = v11 % v9;

        v13 = (a2 << v7) * (unsigned __int128)(unsigned __int64)(v11 / v9);

        v14 = v8 * (unsigned __int128)(unsigned __int64)(v11 / v9) >> 64;

        v15 = v8 * (v11 / v9);

        if ( v12 < *((_QWORD *)&v13 + 1) || v12 == *((_QWORD *)&v13 + 1) && v10 < (unsigned __int64)v13 )

        {

          v16 = v13 - __PAIR__(v9, v8);

          v14 = *((_QWORD *)&v16 + 1);

          v15 = v16;

        }

        result = ((v10 - v15) >> v7) | ((__PAIR__(v12, v10) - __PAIR__(v14, v15)) >> 64 << (64 - (unsigned __int8)v7));

      }

      else if ( zero < *((_QWORD *)&a1 + 1) || a2 <= (unsigned __int64)a1 )

      {

        result = a1 - a2;

      }

    }

  }

  else

  {

    if ( a2 <= *((_QWORD *)&a1 + 1) )

    {

      if ( !a2 )

        v3 = 1 / 0uLL;

      *(_QWORD *)&v17 = a1;

      *((_QWORD *)&v17 + 1) = *((_QWORD *)&a1 + 1) % v3;

      v5 = v17 % v3;

    }

    else

    {

      v5 = a1 % a2;

    }

    result = v5;

  }

  return result;

}

 3번째 인자에 따라서 루틴이 다른데, 세번째 인자에는 무조건 0 값이 들어가고 그에 따라 해당루틴에서는 빨간색으로 표시된 부분만 의미가 있다. 

따라서 이 함수는 나머지 연산을 하는 함수라 볼 수 있다. 

즉, 내가 입력한 값의 특정 키값에 대한 모듈러 곱연산이 바이너리 내에 들어있는 값과 일치하면 통과가 되는 프로그램이다.

따라서 모듈러 곱에 대한 역연산이 필요한데, 이때 gmpy 의 divm 함수를 통해 해결했다. 


from pwn import *

import gmpy2

keyli = ''.join(['\xfb', '\xe8', '\x05', ')', 'E', '\x92', 'q', '+', '5', '\x80', '\x89', '\xbd', '\x82', '\x8f', '\xa5', '{', '4', '\x14', '.', 'X', 'F', "'", '\x11', '\xa3', '\xb0', '\x1a', '"', '\xcc', 'o', 'u', '?', '\x16', '\xfe', '\xa1', '\xcb', '\xb9', 'o', '\x8e', '\xc7', '\xec', '\x14', '~', ']', '\xea', 'I', '\x8b', '\xdd', '\xdc', '\x8e', 'o', '\t', '\xb3', '\xe0', '_', '\x84', '\xa2', '\x1c', ']', '\x97', '\xaa', '\xaa', '\xaa', '\xaa', '\xaa', '\xa3', 'Y', 'U', 'U', 'U', 'U', 'U', 'U', '\xa3', 'Y', 'U', 'U', 'U', 'U', 'U', 'U', '\xa3', 'Y', 'U', 'U', 'U', 'U', 'U', 'U', '\xa3', 'Y', 'U', 'U', 'U', 'U', 'U', 'U', '\xa3', 'Y', 'U', 'U', 'U', 'U', 'U', 'U', '\xa3', 'Y', 'U', 'U', 'U', 'U', 'U', 'U', '\xa3', 'Y', 'U', 'U', 'U', 'U', 'U', 'U', '\xa3', 'Y', 'U', 'U', 'U', 'U', 'U', 'U'])



key = []




for i in range(len(keyli) / 8):

key.append(u64(keyli[(i * 8):(i * 8) + 8]))



def bitmax(num , bit):

if bit == 64:

return num & 0xffffffffffffffff

elif bit == 128:

return num & 0xffffffffffffffffffffffffffffffff

else:

print "bitmax error"

exit()



input_ = [0 for i in range(16)]

xor_table = [0 for i in range(16)]


xor_table[7] = 0xFFFFFFFFFFFFFFFF

xor_table[8] = 0xFFFFFFFFFFFFFFFF

input_[0] = 0x5555555555555555

input_[1] = 0x5555555555555555

input_[2] = 0x5555555555555555

input_[3] = 0x5555555555555555

input_[4] = 0x5555555555555555

input_[5] = 0x5555555555555555

input_[6] = 0x5555555555555555

input_[7] = 0x5555555555555555

input_[8] = 0x5555555555555555

input_[9] = 0x5555555555555555

input_[10] = 0x5555555555555555

input_[11] = 0x5555555555555555

input_[12] = 0x5555555555555555

input_[13] = 0x5555555555555555

input_[14] = 0x5555555555555555

input_[15] = 0x5555555555555555

xor_table[0] = 0x20656D6F636C6557

xor_table[9] = 0xFFFFFFFFFFFFFFFF

xor_table[1] = 0x2046544352206F74

xor_table[10] = 0xFFFFFFFFFFFFFFFF

xor_table[2] = 0x6548202138313032

xor_table[11] = 0xFFFFFFFFFFFFFFFF

xor_table[3] = 0x2061207369206572

xor_table[12] = 0xFFFFFFFFFFFFFFFF

xor_table[13] = 0xFFFFFFFFFFFFFFFF

xor_table[14] = 0xFFFFFFFFFFFFFFFF

xor_table[15] = 0xFFFFFFFFFFFFFFFF

xor_table[4] = 0x6320455279626142

xor_table[5] = 0x65676E656C6C6168

xor_table[6] = 0x756F7920726F6620


q = 0xFFFFFFFFFFFFFFC5


res = ""

for i in range(16):

#print "gmpy.invert(" + hex(xor_table[i]) + ", " + hex(key[i]) + ", " + hex(q) + ")"

res += p64(gmpy2.divm(key[i],xor_table[i] ,q))

print res

 


이 문제 외에도 rctf 리버싱문제에 simplere 라는 문제에서도 gmpy를 쓰면 좋은 문제가 있었다. 모듈러 제곱에 대한 역연산을 구해야 되는 문제였는데, 이역시도 invert 함수를 쓰면 쉽게 풀 수 있다.

'rev' 카테고리의 다른 글

PDF 자바스크립트 추출  (0) 2018.09.10
[IDA] C++ decompile failure : call analysis failed  (0) 2018.09.03
[IDA] 자주쓰는 IDA 단축키  (0) 2018.08.01
,

티스토리툴바