[Dreamhack] public

암호화 과정을 복호화해야 한다.

1. main

  stream = fopen("n.txt", "r");
  __isoc99_fscanf(stream, "%llu %llu", &v5, &v6);
  fclose(stream);
  while ( v10 <= 0xFCFCFCFC )
  {
    v8 = sub_12FE(v5);
    v9 = sub_12FE(v8 + 128);
    v10 = v9 * v8;
  }
  printf("n1 = %llu\n", v10);
  v11 = v6;
  v13 = (v8 - 1) * (v9 - 1);
  while ( v11 < v13 && gcd(v11, v13) != 1 )
    ++v11;
  printf("n2 = %llu\n", v11);
  *(_QWORD *)s = 0LL;
  
  v15~45 = 0 (요약)

  stream = fopen("flag.txt", "rb");
  __isoc99_fscanf(stream, "%255s", s);
  fclose(stream);
  if ( (strlen(s) & 3) != 0 )
  {
    puts("invalid length!");
    exit(-1);
  }
  stream = fopen("out.bin", "wb");
  for ( i = 0; i < strlen(s) >> 2; ++i )
  {
    ptr = encode(*(unsigned int *)&s[4 * i], v11, v10);
    fwrite(&ptr, 8uLL, 1uLL, stream);
  }
  fclose(stream);
  return 0LL;

v5와 v6을 n.txt를 통해 받아옴. sub_12FE를 통해 얻은 값을 곱해 v10을 생성. n1 = v10 (v5 바탕으로 생성)
n2는 v6 바탕으로 생성

flag를 s에 저장. encode 함수를 통해 변환 후 out.bin에 저장

2. encode

__int64 __fastcall sub_1289(__int64 a1, unsigned __int64 a2, unsigned __int64 a3)
{
  __int64 v4; // [rsp+20h] [rbp-10h]
  unsigned __int64 i; // [rsp+28h] [rbp-8h]

  if ( !a3 )
    exit(-1);
  v4 = 1LL;
  for ( i = 0LL; i < a2; ++i )
    v4 = a1 * v4 % a3;
  return v4;
}

a1: msg, a2: n2, a3: n1

v4 = v4 * a1 % a3를 a2번 반복
v4 = s[i] ^ (n2) mod(n1) -> s[i]를 알아내야 함.
discrete logarithm 문제다.

sage 써야 하나 고민 중이었는데 dh 댓글들을 살펴보니 RSA를 알면 쉽다고 해서 ida에서 변수명을 다 바꿔보았다.

  while ( n <= 0xFCFCFCFC )
  {
    p = find_prime(v5);
    q = find_prime(p + 128);
    n = q * p;
  }
  printf("n1 = %llu\n", n);
  e = v6;
  pi_n = (p - 1) * (q - 1);
  while ( e < pi_n && gcd(e, pi_n) != 1 )
    ++e;
  printf("n2 = %llu\n", e);

이렇게 바꾸니까 그냥 RSA 문제다.
s[i] ^ e (mod n)을 저장했으니 여기에 d제곱해주면 평문이 나온다.
d는 ed = 1 (mod pi_n)을 만족시키는 값이면 된다.

3. out.txt
   

n1 = 4271010253 (n)
n2 = 201326609 (e)

4. exploit.py

with open('D:\\code\\dh\\rev\\public\\out.bin', 'rb') as f:
    data = f.read()
    n = 4271010253
    p = 65287
    q = 65419
    pi_n = (p-1)*(q-1)
    e = 201326609
    d = pow(e, -1, pi_n)
    
    flag = b''

    for i in range(len(data) // 8):
        s = int.from_bytes(data[i*8:i*8+8], 'little')
        flag += (pow(s, d, n)).to_bytes(4, 'little')
        
    print(flag)

주의: byte 변환 기본값이 big endian임.