SECCON Beginners 2023 Writeup

1 : crypto

1-1 : CoughingFox2

圧縮ファイルをもらい、解凍するとpythonファイルとテキストファイルが。
pythonファイルが暗号化プログラム、テキストがその結果です。
暗号化は下記のようにされていました。

1. encodeメソッドでflagを文字コード化
2. c = ((flag[i] + flag[i+1]) ** 2 + i) で i 文字目について i+1 文字目との和を2乗し、iを足す
3. リスト cipher に暗号化した値(=c)を加える
4. random.shuffle(cipher) で暗号結果をシャッフル

とりあえずシャッフルは放置して(2)の復号だけを考えようとしました。
しかし、順番が絡む以上一発で復号とはいかないし、その順番を確定させる方法が思いつきません…
flagの長さはcipherから44文字　※(2)ではi文字目とi+1文字目で1つの値が出るため、得られる値の総数はflagの文字数より1小さくなっている
仮に総当たりで考えるとすると44!通りなのでバカみたいな数になり、現実的ではなさそうです。
頭の「ctf4b{」までは初期位置も文字も確定してるので、とりあえずここを足掛かりにすることでどうにかなるのかとも思ったのですが、一向に進展せず。
八方塞がりになってたところ、タイトル的にこれ多分去年も類題出てるなと思って去年のwriteupを調べてみました。
するとドンピシャなのが見つかります。
暗号化された値からiを引いたもの( c - i )はi文字目とi+1文字目の文字コードの和 = 整数を2乗したものです( (flag[i]+flag[i+1])^2 )
なので i は「 c - i の平方根を取った時、値が整数になるもの」となります。
これだけだとiが複数ある可能性も否めませんが、まあ
この条件を元に、以下のような手順で解いていきます。

1. cipher[n]からiを引き、その平方根をとる
2. (1)の結果が整数となるiが見つかるまで総当たりで行う(0≦i≦43)
3. (1),(2)をcipherの全ての値について行う -> 43個のflag[i]+flag[i+1]の値が順番とともに求まる
4. flagの一文字目は「c」で確定していることを利用し、(3)の結果からflag[i+1]を求める
5. chrメソッドを使って復号し、その結果を連結して最終的にflagを求める

下記はそのプログラムです。

solve_coughfox2.py

import math

cipher = [4396, 22819, 47998, 47995, 40007, 9235, 21625, 25006, 4397, 51534, 46680, 44129, 38055, 18513, 24368, 38451, 46240, 20758, 37257, 40830, 25293, 38845, 22503, 44535, 22210, 39632, 38046, 43687, 48413, 47525, 23718, 51567, 23115, 42461, 26272, 28933, 23726, 48845, 21924, 46225, 20488, 27579, 21636] 
sum=[0]*len(cipher) #平方根とった結果を入れる
encoded=[0]*len(cipher) #各flag[i](=encode化された文字)を入れる
ans="" #flag格納用

with open(path,mode='w') as f:
    #平方根求めた結果が正数になるiを探し、flag[i]+flag[i+1]を求める
    for n in cipher:        
        for i in range(len(cipher)):
            result=math.sqrt(n-i)
            if(result.is_integer()):
                f.write(f"{n} -> {i}:{result}\n")
                sum[i]=int(result)
                break
    
    #求めたsumを順番に並べてテキストファイルに出力
    f.write("\n")
    f.write("[sum]\n")
    [f.write(f"{i}:{sum[i]}\n") for i in range(len(sum))]

    #sum[i]=flag[i]+flag[i+1]からflag[i]を引き、flag[i+1]を求める
    f.write("\n")
    f.write("[encoded]\n")
    encoded[0]=99 #c
    for j in range(1,len(sum)):
        encoded[j]=int(sum[j-1]-encoded[j-1])
        f.write(f"{j+1}文字目:{encoded[j]}\n")

    #各文字を変換、連結してflagを求める
    for j in range(len(encoded)):
        ans=ans+chr(encoded[j])
    ans=ans+"}"

print("ans:"+ans)
print("[fin]")

これより、ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve_fun!!!} が求められました。

参考サイト
https://note.nkmk.me/python-random-shuffle/
https://grapebanana.com/python-encoding-utf-8-7161/
https://note.nkmk.me/python-bin-oct-hex-int-format/
https://hack.nikkei.com/blog/ctf4b202206/#chapter4-1
https://pg-chain.com/python-sqrt
https://note.nkmk.me/python-check-int-float/
https://engineerblog.mynavi.jp/technology/seccon-beginners-ctf2022-2/
https://www.whyit.work/entry/2018/08/14/235416
https://www.seiai.ed.jp/sys/text/java/utf8table.html
https://infoma-study.com/python-system-of-equations/