X-MAS CTF 2020 Writeup

X-MAS CTF 2020 に team "upper-village" のメンバとして参加してきました。自分が解いた問題をWriteupします。
問題を確認しながらやろうと思ったらWebサイトがもう閉鎖されてまして問題見れず…。思い出して書いてるので、ちょっと問題の設定は不正確なところがあるかもしれません。

# Conversation(Forensics 50pts)

チャットが社内ルールで禁止されているのだがルール違反でチャットをしてるのでそこからフラグを抜き出せ、という問題。

与えられるのはWireshark の.pcapngファイルひとつ。追跡->TCPストリームで中身を見てゆくとストリーム56で怪しいやりとりが出てくる。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/602379/34bb4d3b-d2ec-c232-b3fc-2a9e7b7810d7.png)
いかにもbase64なのだが、このままだとエラーになり戻せない…と思ったら下でrot13だと言ってるので、rot13で戻す。
<https://rot13.com/>
今度はbase64としてデコードできるのが出てくる。
`X-MAS{Anna_from_marketing_has_a_new_boyfriend-da817c7129916751}`

# The Cat(Forensics 500pts)
でかいモニタを買ったんだけどそこでnyancatを映してる云々…という問題。こちらも与えられるのは.pcapngファイルひとつ。
今回はhttpsが入ってる。

ファイル -> オブジェクトをエクスポート... すると、この7個のオブジェクトが出てくる。![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/602379/97626bdc-5ffd-4037-5a00-576e10d25eb4.png)
このうち、No.4173の中身が怪しい。見てみるとこんなフォーマット。
(テキストエディタがいまだに秀丸なの、許して…)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/602379/09f5a53e-3251-4480-bcc1-54f51566168a.png)
調べると、NSS Keylog format という形式で、Wiresharkが暗号通信を復号化できるようブラウザなどが設定により出力するファイルだそうだ。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/602379/69ee768d-403c-08b3-0632-ddaad34159e4.png)
Wiresharkの設定->プロトコル設定->TLS の、(Pre)-Master Secret log filename でこのファイルを指定してみると、ストリーム120が復号化できる。復号化がでてきてることが、ちまちまTCPのパケットを見てかないとわからないのだがほかに方法ないのかな。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/602379/c6b5eeec-1154-3426-5676-038000778193.png)
中身をバイナリで保存し、httpヘッダを切り取るとnyan.shというシェルスクリプトが得られる。実行するとただ猫が踊ってるだけ…とおもいきや、実は実行開始前にフラグが一瞬表示されている。Ctrl-Cで猫がフラグを隠す前に止めて、フラグをゲット。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/602379/455c4a71-5085-f3a0-6030-e70fda5d54f5.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/602379/f6e1748a-8200-1b40-13a1-dab0e32752a9.png)
実をいうと私はとろくてうまく止められず、チームメイトにやってもらいました…



`X-MAS{yeah_nyan_is_cool_but_have_you_ever_Y3VybCAtcyAtTCBiaXQubHkvMTBoQThpQyB8IGJhc2gK-ea8f6adb7605962d}`

# FORMULA TRANSLATION NOVICE (Reverse Engineering 500pts)

FORTRANのソースコードがあるから見てみてね、って問題。
FORTRANのソースがもらえる。

```fortran:PROGRAM.F
      REAL FUNCTION ANALYZER(M, I, B)
        INTEGER M(*), I
        INTEGER B, OP

        OP = I
        DO 10 I = 1, B
          B = B + 1
10      CONTINUE
        I = OP

        OP = XOR(B, 35)
        IF (OP .EQ. M(I)) THEN
          ANALYZER = 1.0
        ELSE
          ANALYZER = 0.0
        ENDIF

        RETURN
      END

      SUBROUTINE COMPUTE(A, I, B)
        INTEGER A, I, B
        INTEGER OPTIMIZE
        COMMON /PRAGMA/ OPTIMIZE

        DO 50 I = 0, B -1
          B = B + 1
50      CONTINUE
        I = I - 48

        IF (A .EQ. B) THEN
          OPTIMIZE = 1
        ELSE
          OPTIMIZE = 0
        ENDIF 

        RETURN
      END

      BLOCK DATA
        INTEGER PROGRESSIONMATRIX(12), CONVOLUTIONMATRIX(4,3)
        COMMON /PERFORMANTBLOCK/ CONVOLUTIONMATRIX, PROGRESSIONMATRIX
        INTEGER POSITIONMATRIX(2,2,5)
        COMMON /SLOWBLOCK/ POSITIONMATRIX
        DATA CONVOLUTIONMATRIX/7, 13, 15, 17, 19, 24, 30, 31, 34, 37
     +  , 39, 41/
        DATA PROGRESSIONMATRIX/241, 209, 201, 243, 207, 249, 231, 251
     +  , 235, 255, 209, 201/
        DATA POSITIONMATRIX/134, 36, 175, 63, 112, 163, 111, 37, 140, 73
     +  , 172, 83, 61, 65, 135, 53, 146, 43, 157, 58/
      END

      PROGRAM CHRISTMAS
        LOGICAL DECISION
        INTEGER INSTRUCTION
        INTEGER OPTIMIZE
        COMMON /PRAGMA/ OPTIMIZE
        CHARACTER I(42)
        INTEGER TT(-4:0), TT2(-4:0)
        INTEGER ANTIMONY(0:4)
        INTEGER PROGRESSIONMATRIX(12), CONVOLUTIONMATRIX(4,3)
        COMMON /PERFORMANTBLOCK/ PROGRESSIONMATRIX, CONVOLUTIONMATRIX
        INTEGER POSITIONMATRIX(2,2,5)
        INTEGER A, B
        PARAMETER(AX=28, AY=48)

        WRITE(*,*) "PLEASE INPUT FLAG."
        DECISION = .TRUE.
        READ(*,*) I
        DATA TT/85, 32, 64, 76, 94/
        DATA ANTIMONY/0, 4, 5, 8, 12/
        DATA POSITIONMATRIX/118, 53, 43, 51, 117, 51, 41, 53, 116, 51,
     +  40, 48, 113, 48, 38, 51, 109, 52, 36, 55/

        DO 20 J = 1, 5
          IF (XOR(ICHAR(I(J)), 13) .NE. TT(J - 5)) DECISION = .FALSE.
20      CONTINUE

        IF (I(6) .NE. CHAR(123)) DECISION = .FALSE.
        IF (I(42) .LT. CHAR(125)) DECISION = .FALSE.

        DATA TT2/8, 12, 16, 21, 26/

        DO 30 J = 0, -4, -1
          IF (ICHAR(I(TT2(J))) .NE. 95) DECISION = .FALSE.
30      CONTINUE
      
        DO 40 J = 1, 12, 1
          INSTRUCTION = ICHAR(I(PROGRESSIONMATRIX(J)))
          OPTIMIZE = J
          IF(ANALYZER(CONVOLUTIONMATRIX, OPTIMIZE, INSTRUCTION) 
     +    .LT. 0.5) DECISION = .FALSE.
40      CONTINUE

        IF (ICHAR(I(29)) .NE. 95) DECISION = .FALSE.
        IF (ICHAR(I(35)) .NE. 95) DECISION = .FALSE.
        IF (ICHAR(I(38)) .NE. 95) DECISION = .FALSE.

        INSTRUCTION = 5570010
        TT(0) = 0
        DO 60 J = 0, 7
          CALL COMPUTE(LSHIFT(ICHAR(I(INT(AX + ANTIMONY(4-TT(0))))), 1)
     #,J,              INT(AY + MOD(INSTRUCTION, 10)))

          INSTRUCTION = INSTRUCTION / 10
          TT = TT + 1
          IF (OPTIMIZE .NE. 1) GOTO 1000
60      CONTINUE
        
        DO 70 J = 1, 5
          IF (ICHAR(I(XOR(POSITIONMATRIX(1,1,J), 127))) .NE.
     +      POSITIONMATRIX(2,1,J)) DECISION = .FALSE.
          IF (ICHAR(I(XOR(POSITIONMATRIX(1,2,J), 63))) .NE.
     +      POSITIONMATRIX(2,2,J)) DECISION = .FALSE.
70      CONTINUE

        IF (.NOT. DECISION) GOTO 1000

        WRITE(*,*) "CORRECT."
        GOTO 1001
1000    WRITE(*,*) "WRONG FLAG."
1001    STOP
      END
```

フラグを入力して、合致してたらCORRECT というCTFあるあるなプログラム。Reverse Engineeringなんでソース読む問題なのかもしれないんですが実行したほうが楽そうなので実行環境を探すと、Windows10 では <a href="https://www.silverfrost.com/11/ftn95/ftn95_fortran_95_for_windows.aspx"> FTN95 </a> 一択だそうな。

単に2倍するコードを複雑にしたりとかしてるだけなので、照合対象の文字を地道に出力するとかやってフラグゲット。
`X-MAS{i_533_y0u_h4v3_50m3_77_bl00d_1n_y0u}`


# Bigglest Lowest (Program 50pts)

```
>
So you think you have what it takes to be a good programmer?
Then solve this super hardcore task:
Given an array print the first k1 smallest elements of the array in increasing order and then the first k2 elements of the array in decreasing order.
You have 50 tests that you'll gave to answer in maximum 90 seconds, GO!
Here's an example of the format in which a response should be provided:
1, 2, 3; 10, 9, 8
```

昇順に並べたときのk1個と、降順に並べたときのk2個を答えてね、という問題。単にソートするだけ? あまりに簡単すぎて悩んだ…。

単にソートして返せばよい。

```python
    array.sort()
    inc_ary = array[0:k1]
    array.reverse()
    dec_ary = array[0:k2]
    ans_string = ",".join(map(str, inc_ary)) + ';' + ",".join(map(str, dec_ary)) + '\n'
```

後ろN個を取るのもっと簡単にできたっけか…。
ちなみに回答はこれでいいんですが、別の障害が。当初時間制限は30秒、最初のうちはさくさく解けてるんだが進につれてサーバからの応答が遅くなってそもそも30秒以内に全部解けない。そういう問題?
やってるうちに時間制限は90秒に緩和されるが、それでもギリギリすぎて45問目とかで時間切れ。しかたないから自動で投稿をリトライするプログラムを書いてしばらく回してたら通りました。そういう問題?

# Least Greatest (Program 500pts)

```
>
Hey, you there! You look like you know your way with complex alogrithms.
There's this weird task that I can't get my head around. It goes something like this:
Given two numbers g and l, tell me how many pairs of numbers (x, y) exist such that gcd(x, y) = g and lcm(x, y) = l
Also, i have to answer 100 such questions in at most 90 seconds.
```

最小公倍数と最大公約数を与えるから、それを満たす2つの数の組み合わせが何通りあるか答えてね、という問題。
最小公倍数 ÷ 最大公約数 をやって、その素因数がN種類あると $ 2^N $ が答えとなる。

```python
    gcd = eval(lines[-3][12:])
    lcm = eval(lines[-2][12:])
    print(gcd, lcm)
    
    factors = sympy.factorint(lcm // gcd)
    print(factors)
    ans = 1
    for f in factors:
        ans = ans * (2)
```

相変わらずソースがショボいの許してくださいね…。
てかsympy.factorintすげー。でかい桁数を一瞬で素因数分解してきますね。
この問題、解いた時には460点くらいあったのですが1日経過したら50点まで落下してました。残念。。。

# Santa's Landing Pad (Hardware 500pts)

与えられるのはyoutubeの動画。マイコンにLEDが乱雑につながってて、ボリュームを回すとちかちかする。

LEDの数は7個なんでASCIIか?と思ったらあたりだった。
各LEDをビットに対応させる。左から順に並んでいるわけではないので、X-MAS{ のパターンでLEDを対応づけてあとはコマ送りしながら地道に文字コードを出してゆけばよい。

`X-MAS{W3lc0Me_To_E.E.}`



解いた問題は以上です。