[Christmas CTF 2017] Simple_Bit

Christmas CTF 2017 Simple_Bit 문제이다

사람들은 꽤 많이 풀었지만 나한텐 약간 어려웠다.

__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  __int64 result; // rax@4
  __int64 v4; // rsi@4
  char buf[264]; // [sp+10h] [bp-110h]@1
  __int64 v6; // [sp+118h] [bp-8h]@1
 
  v6 = *MK_FP(__FS__, 40LL);
  memset(buf, 0, 0x100uLL);
  printf("Input : ", a2, buf);
  fflush(stdout);
  buf[(signed int)((unsigned __int64)read(0, buf, 0x100uLL) - 1)] = 0;
  if ( sub_925(buf, buf) )
    puts("Correct");
  else
    puts("Wrong");
  result = 0LL;
  v4 = *MK_FP(__FS__, 40LL) ^ v6;
  return result;
}
 
signed __int64 __fastcall sub_925(const char *a1)
{
  signed __int64 result; // rax@17
  __int64 v2; // rsi@21
  int v3; // [sp+14h] [bp-402Ch]@8
  int i; // [sp+18h] [bp-4028h]@1
  int j; // [sp+1Ch] [bp-4024h]@2
  signed int k; // [sp+20h] [bp-4020h]@7
  int l; // [sp+24h] [bp-401Ch]@8
  signed int m; // [sp+28h] [bp-4018h]@15
  int v9; // [sp+2Ch] [bp-4014h]@1
  int v10[2048]; // [sp+30h] [bp-4010h]@1
  int v11[2]; // [sp+2030h] [bp-2010h]@1
  int v12; // [sp+2038h] [bp-2008h]@1
  int v13; // [sp+203Ch] [bp-2004h]@1
  int v14; // [sp+2040h] [bp-2000h]@1
  int v15; // [sp+2050h] [bp-1FF0h]@1
  int v16; // [sp+2054h] [bp-1FECh]@1
  int v17; // [sp+205Ch] [bp-1FE4h]@1
  int v18; // [sp+2064h] [bp-1FDCh]@1
  int v19; // [sp+2070h] [bp-1FD0h]@1
  int v20; // [sp+2080h] [bp-1FC0h]@1
  int v21; // [sp+2084h] [bp-1FBCh]@1
  int v22; // [sp+2088h] [bp-1FB8h]@1
  int v23; // [sp+20A0h] [bp-1FA0h]@1
  int v24; // [sp+20A8h] [bp-1F98h]@1
  int v25; // [sp+20B4h] [bp-1F8Ch]@1
  int v26; // [sp+20BCh] [bp-1F84h]@1
  int v27; // [sp+20C0h] [bp-1F80h]@1
  int v28; // [sp+20C4h] [bp-1F7Ch]@1
  int v29; // [sp+20D0h] [bp-1F70h]@1
  int v30; // [sp+20D4h] [bp-1F6Ch]@1
  int v31; // [sp+20F0h] [bp-1F50h]@1
  int v32; // [sp+20F4h] [bp-1F4Ch]@1
  int v33; // [sp+20FCh] [bp-1F44h]@1
  int v34; // [sp+2104h] [bp-1F3Ch]@1
  int v35; // [sp+2108h] [bp-1F38h]@1
  int v36; // [sp+2120h] [bp-1F20h]@1
  int v37; // [sp+2124h] [bp-1F1Ch]@1
  int v38; // [sp+212Ch] [bp-1F14h]@1
  int v39; // [sp+2130h] [bp-1F10h]@1
  int v40; // [sp+2134h] [bp-1F0Ch]@1
  int v41; // [sp+213Ch] [bp-1F04h]@1
  int v42; // [sp+2140h] [bp-1F00h]@1
  int v43; // [sp+2154h] [bp-1EECh]@1
  int v44; // [sp+2160h] [bp-1EE0h]@1
  int v45; // [sp+2168h] [bp-1ED8h]@1
  int v46; // [sp+2170h] [bp-1ED0h]@1
  int v47; // [sp+2184h] [bp-1EBCh]@1
  int v48; // [sp+2188h] [bp-1EB8h]@1
  int v49; // [sp+218Ch] [bp-1EB4h]@1
  int v50; // [sp+2194h] [bp-1EACh]@1
  int v51; // [sp+2198h] [bp-1EA8h]@1
  int v52; // [sp+219Ch] [bp-1EA4h]@1
  int v53; // [sp+21ACh] [bp-1E94h]@1
  int v54; // [sp+21B0h] [bp-1E90h]@1
  int v55; // [sp+21BCh] [bp-1E84h]@1
  int v56; // [sp+21C0h] [bp-1E80h]@1
  int v57; // [sp+21C4h] [bp-1E7Ch]@1
  int v58; // [sp+21C8h] [bp-1E78h]@1
  int v59; // [sp+21D0h] [bp-1E70h]@1
  int v60; // [sp+21E8h] [bp-1E58h]@1
  int v61; // [sp+21ECh] [bp-1E54h]@1
  int v62; // [sp+2200h] [bp-1E40h]@1
  int v63; // [sp+2204h] [bp-1E3Ch]@1
  int v64; // [sp+2210h] [bp-1E30h]@1
  int v65; // [sp+2214h] [bp-1E2Ch]@1
  int v66; // [sp+2218h] [bp-1E28h]@1
  int v67; // [sp+2224h] [bp-1E1Ch]@1
  int v68; // [sp+2228h] [bp-1E18h]@1
  int v69; // [sp+2240h] [bp-1E00h]@1
  int v70; // [sp+224Ch] [bp-1DF4h]@1
  int v71; // [sp+2260h] [bp-1DE0h]@1
  int v72; // [sp+2268h] [bp-1DD8h]@1
  int v73; // [sp+2270h] [bp-1DD0h]@1
  int v74; // [sp+2274h] [bp-1DCCh]@1
  int v75; // [sp+2278h] [bp-1DC8h]@1
  int v76; // [sp+227Ch] [bp-1DC4h]@1
  int v77; // [sp+2284h] [bp-1DBCh]@1
  int v78; // [sp+2288h] [bp-1DB8h]@1
  int v79; // [sp+228Ch] [bp-1DB4h]@1
  int v80; // [sp+2298h] [bp-1DA8h]@1
  int v81; // [sp+22A4h] [bp-1D9Ch]@1
  int v82; // [sp+22B8h] [bp-1D88h]@1
  int v83; // [sp+22CCh] [bp-1D74h]@1
  int v84; // [sp+22DCh] [bp-1D64h]@1
  int v85; // [sp+22E4h] [bp-1D5Ch]@1
  int v86; // [sp+22E8h] [bp-1D58h]@1
  int v87; // [sp+22ECh] [bp-1D54h]@1
  int v88; // [sp+22F0h] [bp-1D50h]@1
  int v89; // [sp+22FCh] [bp-1D44h]@1
  int v90; // [sp+2300h] [bp-1D40h]@1
  int v91; // [sp+2308h] [bp-1D38h]@1
  int v92; // [sp+2310h] [bp-1D30h]@1
  int v93; // [sp+2314h] [bp-1D2Ch]@1
  int v94; // [sp+2318h] [bp-1D28h]@1
  int v95; // [sp+232Ch] [bp-1D14h]@1
  int v96; // [sp+2334h] [bp-1D0Ch]@1
  int v97; // [sp+2340h] [bp-1D00h]@1
  int v98; // [sp+2348h] [bp-1CF8h]@1
  int v99; // [sp+2354h] [bp-1CECh]@1
  int v100; // [sp+235Ch] [bp-1CE4h]@1
  int v101; // [sp+2360h] [bp-1CE0h]@1
  int v102; // [sp+2364h] [bp-1CDCh]@1
  int v103; // [sp+2368h] [bp-1CD8h]@1
  int v104; // [sp+2370h] [bp-1CD0h]@1
  int v105; // [sp+2374h] [bp-1CCCh]@1
  int v106; // [sp+2378h] [bp-1CC8h]@1
  int v107; // [sp+2390h] [bp-1CB0h]@1
  int v108; // [sp+2398h] [bp-1CA8h]@1
  int v109; // [sp+23A4h] [bp-1C9Ch]@1
  int v110; // [sp+23A8h] [bp-1C98h]@1
  int v111; // [sp+23B8h] [bp-1C88h]@1
  int v112; // [sp+23BCh] [bp-1C84h]@1
  int v113; // [sp+23C0h] [bp-1C80h]@1
  int v114; // [sp+23C4h] [bp-1C7Ch]@1
  int v115; // [sp+23C8h] [bp-1C78h]@1
  int v116; // [sp+23CCh] [bp-1C74h]@1
  int v117; // [sp+23D8h] [bp-1C68h]@1
  int v118; // [sp+23E4h] [bp-1C5Ch]@1
  int v119; // [sp+23ECh] [bp-1C54h]@1
  int v120; // [sp+23F0h] [bp-1C50h]@1
  int v121; // [sp+23F8h] [bp-1C48h]@1
  int v122; // [sp+2404h] [bp-1C3Ch]@1
  int v123; // [sp+240Ch] [bp-1C34h]@1
  int v124; // [sp+241Ch] [bp-1C24h]@1
  int v125; // [sp+2428h] [bp-1C18h]@1
  int v126; // [sp+243Ch] [bp-1C04h]@1
  int v127; // [sp+244Ch] [bp-1BF4h]@1
  int v128; // [sp+2450h] [bp-1BF0h]@1
  int v129; // [sp+2460h] [bp-1BE0h]@1
  int v130; // [sp+2464h] [bp-1BDCh]@1
  int v131; // [sp+246Ch] [bp-1BD4h]@1
  int v132; // [sp+2478h] [bp-1BC8h]@1
  int v133; // [sp+2480h] [bp-1BC0h]@1
  int v134; // [sp+2484h] [bp-1BBCh]@1
  int v135; // [sp+248Ch] [bp-1BB4h]@1
  int v136; // [sp+2490h] [bp-1BB0h]@1
  int v137; // [sp+2498h] [bp-1BA8h]@1
  int v138; // [sp+249Ch] [bp-1BA4h]@1
  int v139; // [sp+24A0h] [bp-1BA0h]@1
  int v140; // [sp+24ACh] [bp-1B94h]@1
  __int64 v141; // [sp+4038h] [bp-8h]@1
 
  v141 = *MK_FP(__FS__, 40LL);
  memset(v10, 0, sizeof(v10));
  memset(v11, 0, 0x2000uLL);
  v12 = 1;
  v13 = 1;
  v14 = 1;
  v15 = 1;
  v16 = 1;
  v17 = 1;
  v18 = 1;
  v19 = 1;
  v20 = 1;
  v21 = 1;
  v22 = 1;
  v23 = 1;
  v24 = 1;
  v25 = 1;
  v26 = 1;
  v27 = 1;
  v28 = 1;
  v29 = 1;
  v30 = 1;
  v31 = 1;
  v32 = 1;
  v33 = 1;
  v34 = 1;
  v35 = 1;
  v36 = 1;
  v37 = 1;
  v38 = 1;
  v39 = 1;
  v40 = 1;
  v41 = 1;
  v42 = 1;
  v43 = 1;
  v44 = 1;
  v45 = 1;
  v46 = 1;
  v47 = 1;
  v48 = 1;
  v49 = 1;
  v50 = 1;
  v51 = 1;
  v52 = 1;
  v53 = 1;
  v54 = 1;
  v55 = 1;
  v56 = 1;
  v57 = 1;
  v58 = 1;
  v59 = 1;
  v60 = 1;
  v61 = 1;
  v62 = 1;
  v63 = 1;
  v64 = 1;
  v65 = 1;
  v66 = 1;
  v67 = 1;
  v68 = 1;
  v69 = 1;
  v70 = 1;
  v71 = 1;
  v72 = 1;
  v73 = 1;
  v74 = 1;
  v75 = 1;
  v76 = 1;
  v77 = 1;
  v78 = 1;
  v79 = 1;
  v80 = 1;
  v81 = 1;
  v82 = 1;
  v83 = 1;
  v84 = 1;
  v85 = 1;
  v86 = 1;
  v87 = 1;
  v88 = 1;
  v89 = 1;
  v90 = 1;
  v91 = 1;
  v92 = 1;
  v93 = 1;
  v94 = 1;
  v95 = 1;
  v96 = 1;
  v97 = 1;
  v98 = 1;
  v99 = 1;
  v100 = 1;
  v101 = 1;
  v102 = 1;
  v103 = 1;
  v104 = 1;
  v105 = 1;
  v106 = 1;
  v107 = 1;
  v108 = 1;
  v109 = 1;
  v110 = 1;
  v111 = 1;
  v112 = 1;
  v113 = 1;
  v114 = 1;
  v115 = 1;
  v116 = 1;
  v117 = 1;
  v118 = 1;
  v119 = 1;
  v120 = 1;
  v121 = 1;
  v122 = 1;
  v123 = 1;
  v124 = 1;
  v125 = 1;
  v126 = 1;
  v127 = 1;
  v128 = 1;
  v129 = 1;
  v130 = 1;
  v131 = 1;
  v132 = 1;
  v133 = 1;
  v134 = 1;
  v135 = 1;
  v136 = 1;
  v137 = 1;
  v138 = 1;
  v139 = 1;
  v140 = 1;
  v9 = strlen(a1);
  for ( i = 0; i < v9; ++i )
  {
    for ( j = 8 * i; j < 8 * (i + 1); ++j )
    {
      v10[j] = a1[i] & 1;
      a1[i] >>= 1;
    }
  }
  for ( k = 0; k <= 15; ++k )
  {
    v3 = 1;
    for ( l = 0; l < 8 * v9; ++l )
    {
      if ( v10[l] )
        v3 ^= 1u;
      v10[l] = v3;
    }
    sub_104C(v10, (unsigned int)(8 * v9));
  }
  for ( m = 0; m <= 2047; ++m )
  {
    if ( v10[m] != v11[m] )
    {
      result = 0LL;
      goto LABEL_21;
    }
  }
  result = 1LL;
LABEL_21:
  v2 = *MK_FP(__FS__, 40LL) ^ v141;
  return result;
}
 
_DWORD *__fastcall sub_104C(__int64 a1, signed int a2)
{
  _DWORD *result; // rax@1
  int i; // [sp+18h] [bp-8h]@1
  int v4; // [sp+1Ch] [bp-4h]@2
 
  result = (_DWORD *)(unsigned int)(a2 - 1);
  for ( i = a2 - 1; i >= 0; --i )
  {
    v4 = rand() % a2;
    result = (_DWORD *)(unsigned int)i;
    if ( i != v4 )
    {
      *(_DWORD *)(4LL * i + a1) ^= *(_DWORD *)(4LL * v4 + a1);
      *(_DWORD *)(4LL * v4 + a1) ^= *(_DWORD *)(4LL * i + a1);
      result = (_DWORD *)(4LL * i + a1);
      *result ^= *(_DWORD *)(4LL * v4 + a1);
    }
  }
  return result;
}

 IDA로 디컴파일하여 해당 문제를 분석하였다.

먼저 input을 받고 여러 연산을 거친후에 값을 비교한다.

v11 값은 직접 동적디버깅 하여 hex view dump을 해주고 값을 추출했다.

전체적으로 보면 일단 입력받은 문자열을 2진수(8bit)로 바꾼 후에 이 바꾼 값들로 연산을 진행한다.

rand() 값이 srand로 초기화되지 않았기 때문에 규칙적인 숫자가 나와 역연산이 가능하다.

먼저 input_length 를 알아내야 하는데 이 부분은 v11 값을 보면 알 수 있다. 

v11도 2진수로 변환한 후에 나온 암호화 값이기 때문에 len(v11) == 288 이므로 288/8 = 36 글자가 input_length 이다. 

pseudo code를 짜준 후에 pseudo code를 바탕으로 역연산을 진행하였다.

[pseudo code]

from ctypes import *
 
libc = CDLL('libc.so.6')
bit = [0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1]
#flag_length == len(bit)/8 == 36
 
def sub_104c(string_bit, num):
    n = num - 1
    rand_data = 0
 
    while(n >= 0):
        rand_data = libc.rand() % num    
        if n != rand_data:
            tmp = string_bit[n]
            string_bit[n] = string_bit[rand_data]
            string_bit[rand_data] = tmp
        n -= 1
 
if __name__ == "__main__":
    for i in range(2048 - len(bit)): 
        bit.append(0)
    string_bit = [0 for i in range(2048)]
 
    string = bytearray(raw_input("> "))
 
    for i in range(len(string)):
        for j in range(i*8, (i+1) * 8):
            string_bit[j] = string[i] & 1
            string[i] >>= 1
    
    for i in range(16):
        v3 = 1
        for j in range(len(string) * 8):
            if string_bit[j]:
                v3 ^= 1
            string_bit[j] = v3
        sub_104c(string_bit, len(string) * 8)
    
    result = 1
    for i in range(2048):
        if string_bit[i] != bit[i]:
            result = 0
            break
    
    if result:
        print "Correct!"
    else:
    
        print "Incorrect.."
 

[Solve code]

from ctypes import *
 
libc = CDLL('libc.so.6')
bit = [0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1]
 
def sub_104c(bit, r):
    r = r[::-1]
    for i in range(len(r)):
        tmp = bit[i]
        bit[i] = bit[r[i]]
        bit[r[i]] = tmp
 
if __name__ == "__main__":
    length = 36
    for i in range(0x800 - len(bit)): 
        bit.append(0)
    
    rand_data = []
    for i in range(16):
        rand = []
        for j in range(length * 8):
            rand.append(libc.rand() % (length * 8))
        rand_data.append(rand)
    
    for i in range(16):
        v3 = 1
        sub_104c(bit, rand_data[15 - i])
        bit[0] ^= v3
        for j in range(1, length * 8):
            if bit[j - 1]:
                v3 ^= 1
            bit[j] ^= v3
    
    flag = ''
    for i in range(0, length * 8, 8):
        flag += chr(int(''.join(map(str, bit[i:i+8][::-1])), 2))
    print flag  #XMAS{S1mp1e_diff3r3nt1cal_c0d1ng_:p}