橙になりたいaquarium

にゃーんにゃーんにゃにゃーん

Hack Festa 2023 (トヨタCTF) に参加しました！WriteUp

普段とは違った話をします。研究室からHack Festa 2023というトヨタ主催のCTFに参加してきました。日米で開催され、国内1位総合2位となりました！

自己紹介

  • 大阪大学のB4です。

  • 研究では画像処理とか機械学習とかやってて、セキュリティとは無縁です。

  • 趣味では競技プログラミングをやってて、AtCoder黄色です。今年のICPC 2023 Asia Yokohama Regionalにも参加します。

  • バイトでは量子コンピューティングの関係のことをやっています。

目次

これまで

CTFとのこれまで

CTFはCpawCTFを埋めたり、高専や大学内で団体が開催しているCTFに参加したくらいです。Cryptoは比較的得意で、Miscやreversingはまだできる方ですが、webとかnetは一切わからないです。

今回のHack Festaは実機を触る以外ではこの中ではreversingしかなかったのでそれをやってました。というのも先輩たちがセキュリティを専門に研究していたりハード方面のことを趣味にしていたからです。私としては「数学とかアルゴリズムとか使う問題こないかなー」くらいの気持ちを持ちながらまぁ予想通りの問題セットがきた感じです。

今回はM1, M2の先輩と参加しました。M1のぽよさんの writeup はこちらです。

www.maaaaa.net

トヨタとのこれまで

トヨタ様には競プロで毎度お世話になってます。今年に入ってからだけで7回くらいAtCoder上で競技プログラミングのコンテストを開いていて、我々にとっては強力は後ろ盾だなぁと思っています。トヨタ自動車だけでこれで、トヨタシステムズとかも別にあったと思います。すごすぎ。

この記事を書いてる11/7の前々日、11/5(日)にもありました。そして11/11にもあります。11/5のコンテストでは37位の好成績でした。そのとき書いた解説↓

atcoder.jp

3月と8月にはトヨタ主催のオンサイトコンテストがあり、予選を通過して参加することができました。今年だけでトヨタグループのお金で3回東京に行けてて頭が上がりません…。

atcoder.jp

atcoder.jp

そのときに書いた記事はこちら。

shinchankosen.hatenadiary.jp

shinchankosen.hatenadiary.jp

WriteUp

pitstop puzzle (100点)

まずncのアレとtxtファイルが与えられました。txtは以下の通りです。

Car Engine Error Diagnostic Manual
===============================

1. Caesar Cipher (CXXX):
Encoding Key: C
1st Digit: Direction (1: Forward shift, 2: Backward shift)
2nd & 3rd Digits: Shift value
Example: C127 means a Caesar cipher shifting each letter 27 places backward in the alphabet.
Procedure: Shift each character in the encrypted string 27 places back to decode.

2. Base64 Encoding (BXXX):
Encoding Key: B
1st Digit: Input Reversed (1: Normal, 2: Reversed)
2nd Digit: Output Reversed (1: Normal, 2: Reversed)
Example: B22 implies a standard Base64 decoding, where the base64 payload is reversed, and also contains reversed text.

3. Hexadecimal Encoding (HXXX):
Encoding Key: H
1st Digit: Input Reversed (1: Normal, 2: Reversed)
2nd Digit: Output Reversed (1: Normal, 2: Reversed)
Example: H212 means decoding a hexadecimal encoded string and reversing the result.

4. Morse Code (MXXX):
Encoding Key: M
1st Digit: Direction (1: Normal, 2: Reversed)
Example: M221 implies decoding Morse Code and then reversing the result.

5. ASCII Conversion (AXXX):
Encoding Key: A
1st Digit: Direction (1: Normal, 2: Reversed)
Example: A214 implies converting ASCII to characters and then reversing the result.

6. XOR Operation (XYYY):
Encoding Key: X
1st digit is reserved for future use.
2nd & 3rd Digits: Key for XOR operation
Example: X112 implies XORing the string with the key "12". The output will be base64 encoded.

7. AES ECB Encryption (EXXX):
Encoding Key: E
1st digit is the padding character.
2nd and 3rd Digits: AES ECB Key (key, which will be padded with the 1st digit to make it 32 characters long)
Example: E242 implies decrypting the message using AES ECB with the key 42, padded to 32 characters with 2 and base64 encoded.

YXXXって形式の文字列と暗号が与えられて、10回くらい連続で復号してねーっていう問題です。

以下のCyberChefが復号に役立ちました。

gchq.github.io

  1. Caesar Cipher (CXXX): シーザー暗号です。† C++ † で実装しました。
  2. Base64 Encoding (BXXX): Base64の暗号です。CyberChefで解きました。
  3. Hexadecimal Encoding (HXXX): Hexの暗号です。CyberChef。
  4. Morse Code (MXXX): モールス信号です。ググってでてきた適当なサイトに入れました。
  5. ASCII Conversion (AXXX): CyberChef。
  6. XOR Operation (XYYY): CyberChef。
  7. AES ECB Encryption (EXXX): CyberChefを2段階でやる。

また、reverseが必要なときは適宜 † C++ † で実装した文字列反転プログラムに入れました。

10回くらい連続で正解するとフラグがでてきました。

smartcode (300点)

この問題もファイルとncのアレが与えられました。

まず、先輩がファイルをデコンパイルしてくれてCのコードをもらいました。

int calculate(char *param_1)

{
  int iVar1;
  char *local_20;
  char local_11;
  int local_10;
  int local_c;
  
  local_c = 1;
  local_10 = 0x5ba0;
  if (*param_1 == '\0') {
    local_10 = 0;
  }
  else {
    local_11 = *param_1;
    local_20 = param_1;
    do {
      iVar1 = (int)local_11;
      local_20 = local_20 + 1;
      local_11 = *local_20;
      local_10 = local_10 + (iVar1 + local_c * local_10) * 2;
      local_c = local_c + 1;
    } while (local_11 != '\0');
  }
  return local_10;
}
undefined8 main(void)

{
  size_t sVar1;
  char local_28 [28];
  int local_c;
  
  printf("INPUT CODE: ");
  fflush(stdout);
  fgets(local_28,0x15,stdin);
  sVar1 = strcspn(local_28,"\n");
  local_28[sVar1] = '\0';
  local_c = calculate(local_28);
  if (local_c == -0x14f5e200) {
    puts("ACCESS GRANTED");
    system("cat flag.txt");
    fflush(stdout);
  }
  else {
    puts("ACCESS DENIED");
    fflush(stdout);
  }
  return 0;
}

解読して以下のようにメモ書きとC++で動く形式にしました。

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;


int calculate(char *param_1)

{
  int iVar1;
  char *local_20;
  char local_11;
  int local_10;
  int local_c;
  
  local_c = 1;
  local_10 = 0x5ba0; //23456
  if (*param_1 == '\0') { 
    local_10 = 0;
  }
  else {
    local_11 = *param_1; // 1文字目
    local_20 = param_1; // param_1
    do {
      iVar1 = (int)local_11; // 順番に
      local_20 = local_20 + 1; // 2文字目以降
      local_11 = *local_20; // 1文字目
      local_10 += (iVar1 + local_c * local_10) * 2;  // めんどくさい
      local_c = local_c + 1; // インクリメント
    } while (local_11 != '\0');
  }
  return local_10;
}

int main(void)

{
    for(int i = 1; i <= 1000000000; i ++) {
        size_t sVar1;
        char local_28 [28];
        int local_c;
        string s = to_string(i);
        reverse(all(s));
        int id = 0;
        foa(e, s) {
            local_28[id ++] = e;
        }
        sVar1 = strcspn(local_28,"\n"); // 文字数
        local_28[sVar1] = '\0'; //null
        local_c = calculate(local_28);
        if (local_c == -0x14f5e200) { // -351658496 //  6144が割ったあまり ivar1の効果は3072
            cout << i << endl;
            puts("ACCESS GRANTED");
            // system("cat flag.txt");
            // fflush(stdout);
            break;
        }
    }
    
  return 0;
}

どうやら、20桁以上許容していて全探索は厳しそうです。また、オーバーフローが前提となっており、単純に数学で解くのが難しいです。

とりあえず立式してみました。mod 232の合同式を用いました。二重階乗とかでてきて鬱でした。

modintとか使う意味もないしなーとなったり、拡張ユークリッドとかも使えないし…となっていたところ、合同式の右辺の定数部分を232の倍数を足して固定することを試みました。

すると、奇数のmodを順に考えることで、解が一意に定まっていきます。ただ、割り算がちゃんと行えるように † boost::multiprecision::cpp_int † で無限桁数を許容しました。

最終的に実装したものが以下です。


#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto& e : v)
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;

#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using ll = mp::cpp_int;
using i64 = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
        
    for(ll i = -351658496 + (1LL << 32); i < INF ; i += (1LL << 32)) {
        for(ll l =10; l <= 21; l ++) {
            ll sum = 0;
            for(int j = 1; j <= l; j ++) {
                sum *= (ll)(j * 2 + 1);
                sum += 96;
            }
            {
                ll sum1 = 23456;
                for(int j = 1; j <= l; j ++) {
                    sum1 *= (ll)(j * 2 + 1);
                }
                sum += sum1;
            }
            assert(sum >= 0);
            ll val = i - sum;
            if(val < 0) continue;
            val /= 2;
            string s = "";
            bool ng = false;
            for(ll j = l; j >= 5; j --) {
                bool f = false;
                for(int k = 0; k < 10; k ++) {
                    if((val - k) % (j * 2 + 1) == 0) {
                        val -= k;
                        val /= (j * 2 + 1);
                        s += char('0' + k);
                        f = true;
                        break;
                    }
                }
                if(!f) {
                    ng = true;
                    break;
                }
            }
            if(ng) continue;
            bool ok = false;
            rep(k1, 10) rep(k2, 10) rep(k3, 10) rep(k4, 10) {
                if(ok) break;
                if(ll(k1 * 315 + k2 * 63 + k3 * 9 + k4) == val) {
                    s += char('0' + k4);
                    s += char('0' + k3);
                    s += char('0' + k2);
                    s += char('0' + k1);
                    ok = true;
                    break;
                }
            }
            if(!ok) continue;
            reverse(all(s));
            cout << (i64)i << " " << l << " " << (i64)sum << endl;
            cout << s << endl;
            
            return 0;
        }
    }
    
    return 0;
}

10通りから対象の奇数で割り切れるかーを試すのに、奇数が大きいときは1通りで割り切れたら貪欲にそれを採用してよいです。しかし、残りの4桁は全探索しました。

実行すると、10秒で 00865208553 とでました。フラグ入手。ありがとう。