SECCON Beginners CTF 2022: recursive

[roaris]

https://github.com/SECCON/Beginners_CTF_2022/tree/main/reversing/recursive

[roaris]

$ ./recursive 

   ▄▀▀▄▀▀▀▄  ▄▀▀█▄▄▄▄  ▄▀▄▄▄▄   ▄▀▀▄ ▄▀▀▄  ▄▀▀▄▀▀▀▄  ▄▀▀▀▀▄  ▄▀▀█▀▄   ▄▀▀▄ ▄▀▀▄  ▄▀▀█▄▄▄▄ 
  █   █   █ ▐  ▄▀   ▐ █ █    ▌ █   █    █ █   █   █ █ █   ▐ █   █  █ █   █    █ ▐  ▄▀   ▐ 
  ▐  █▀▀█▀    █▄▄▄▄▄  ▐ █      ▐  █    █  ▐  █▀▀█▀     ▀▄   ▐   █  ▐ ▐  █    █    █▄▄▄▄▄  
   ▄▀    █    █    ▌    █        █    █    ▄▀    █  ▀▄   █      █       █   ▄▀    █    ▌  
  █     █    ▄▀▄▄▄▄    ▄▀▄▄▄▄▀    ▀▄▄▄▄▀  █     █    █▀▀▀    ▄▀▀▀▀▀▄     ▀▄▀     ▄▀▄▄▄▄   
  ▐     ▐    █    ▐   █     ▐             ▐     ▐    ▐      █       █            █    ▐   
             ▐        ▐                                     ▐       ▐            ▐        

FLAG: test
Incorrect.

[roaris]

IDAでmain関数を確認する

rbp+sがscanfの第2引数に渡されており、入力文字列はrbp+sに格納される その後、rbp+sはstrlenの第1引数に渡される 長さが0x26(=38)じゃないと、"Incorrect."に移動してしまうので、入力文字列が長さ38であることは確定である

長さが38の場合、rbp+sを第1引数、0を第2引数として、checkという関数が呼ばれている check関数の戻り値はrbp+var_54に格納される 戻り値が0なら、cmp [rbp+var_54], 1でZF=0になり、jnz命令で"Correct!"に移動する

[roaris]

次にcheck関数を確認した 分かったことは

• check関数の中でcheck関数が呼ばれている(問題名通り、再帰関数になっている)
• 第1引数で渡す文字列の長さが1かどうかで場合分けしており、長さが1の場合は再帰が終わる

ということである

[roaris]

check関数の処理はアセンブリを見ているだけでは理解できなかったので、Ghidraでデコンパイルした 以下のような結果が得られた

undefined8 check(char *param_1,int param_2)

{
  int iVar1;
  int iVar2;
  int iVar3;
  size_t sVar4;
  char *pcVar5;

  sVar4 = strlen(param_1);
  iVar3 = (int)sVar4;
  if (iVar3 == 1) {
    if (table[param_2] != *param_1) {
      return 1;
    }
  }
  else {
    iVar1 = iVar3 / 2;
    pcVar5 = (char *)malloc((long)iVar1);
    strncpy(pcVar5,param_1,(long)iVar1);
    iVar2 = check(pcVar5,param_2);
    if (iVar2 == 1) {
      return 1;
    }
    pcVar5 = (char *)malloc((long)(iVar3 - iVar1));
    strncpy(pcVar5,param_1 + iVar1,(long)(iVar3 - iVar1));
    iVar3 = check(pcVar5,iVar1 * iVar1 + param_2);
    if (iVar3 == 1) {
      return 1;
    }
  }
  return 0;
}

[roaris]

if (table[param_2] != *param_1)のtableは.dataに確保されている変数である Ghidraでtableをダブルクリックすると、以下のように確認出来る

しかし、IDAの方がASCII文字に直してくれて分かりやすい

stringsコマンドでも出てくる

$ strings recursive | grep "ct"
Incorrect.
Correct!
ct`*f4(+bc95".81b{hmr3c/}r@:{&;514od*<h,n'dmxw?leg(yo)ne+j-{(`q/rr3|($0+5s.z{_ncaur${s1v5%!p)h!q't<=l@_8h93_woc4ld%>?cba<dagx|l<b/y,y`k-7{=;{&8,8u5$kkc}@7q@<tm03:&,f1vyb'8%dyl2(g?717q#u>fw()voo$6g):)_c_+8v.gbm(%$w(<h:1!c'ruv}@3`ya!r5&;5z_ogm0a9c23smw-.i#|w{8kepfvw:3|3f5<e@:}*,q>sg!bdkr0x7@>h/5*hi<749'|{)sj1;0,$ig&v)=t0fnk|03j"}7r{}ti}?_<swxju1k!l&db!j:}!z}6*`1_{f1s@3d,vio45<_4vc_v3>hu3>+byvq##@f+)lc91w+9i7#v<r;rr$u@(at>vn:7b`jsmg6my{+9m_-rypp_u5n*6.}f8ppg<m-&qq5k3f?=u1}m_?n9<|et*-/%fgh.1m(@_3vf4i(n)s2jvg0m4GCC: (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

以下がtableである

ct`*f4(+bc95".81b{hmr3c/}r@:{&;514od*<h,n'dmxw?leg(yo)ne+j-{(`q/rr3|($0+5s.z{_ncaur${s1v5%!p)h!q't<=l@_8h93_woc4ld%>?cba<dagx|l<b/y,y`k-7{=;{&8,8u5$kkc}@7q@<tm03:&,f1vyb'8%dyl2(g?717q#u>fw()voo$6g):)_c_+8v.gbm(%$w(<h:1!c'ruv}@3`ya!r5&;5z_ogm0a9c23smw-.i#|w{8kepfvw:3|3f5<e@:}*,q>sg!bdkr0x7@>h/5*hi<749'|{)sj1;0,$ig&v)=t0fnk|03j"}7r{}ti}?_<swxju1k!l&db!j:}!z}6*`1_{f1s@3d,vio45<_4vc_v3>hu3>+byvq##@f+)lc91w+9i7#v<r;rr$u@(at>vn:7b`jsmg6my{+9m_-rypp_u5n*6.}f8ppg<m-&qq5k3f?=u1}m_?n9<|et*-/%fgh.1m(@_3vf4i(n)s2jvg0m4

[roaris]

check関数を模擬したプログラムを作成し、フラグを出力した if (table[param_2] != *param_1)のチェックは入力文字列の先頭から順にされていくため、table[i]を順に繋げたものがフラグになる

table = 'ct`*f4(+bc95".81b{hmr3c/}r@:{&;514od*<h,n\'dmxw?leg(yo)ne+j-{(`q/rr3|($0+5s.z{_ncaur${s1v5%!p)h!q\'t<=l@_8h93_woc4ld%>?cba<dagx|l<b/y,y`k-7{=;{&8,8u5$kkc}@7q@<tm03:&,f1vyb\'8%dyl2(g?717q#u>fw()voo$6g):)_c_+8v.gbm(%$w(<h:1!c\'ruv}@3`ya!r5&;5z_ogm0a9c23smw-.i#|w{8kepfvw:3|3f5<e@:}*,q>sg!bdkr0x7@>h/5*hi<749\'|{)sj1;0,$ig&v)=t0fnk|03j"}7r{}ti}?_<swxju1k!l&db!j:}!z}6*`1_{f1s@3d,vio45<_4vc_v3>hu3>+byvq##@f+)lc91w+9i7#v<r;rr$u@(at>vn:7b`jsmg6my{+9m_-rypp_u5n*6.}f8ppg<m-&qq5k3f?=u1}m_?n9<|et*-/%fgh.1m(@_3vf4i(n)s2jvg0m4'

def check(s, i):
    if len(s) == 1:
        print(table[i], end='')
        return

    t = len(s) // 2
    check(s[:t], i)
    check(s[t:], t*t+i)

check('a'*38, 0)