部内向け解説資料 - SECCON Beginners CTF 2021 Crypto

SECCON Beginners CTF ���� Crypto 問題の解説 濵田幸希 (HK_ilohas)

文字列と数値の相互変換

str型とbytes型の変換 文字列（str型）を数値（int型）にする前に， str型をbytes型に変換する必要がある． encode str型 bytes型 decode

str型とbytes型の変換 >>> flag = "Hello, World!“ >>> flag.encode() b'Hello, World!' >>> flag = b"Hello, World!“ >>> flag.decode() 'Hello, World! str型 bytes型 bytes型 str型

bytes型とint型の変換 bytes型のままだと計算ができないのでint型に変換したい． そこで，pycryptodomeという暗号系のライブラリを使用する． https://pypi.org/project/pycryptodome/ $ pip3 install pycryptodome

• https://pypi.org/project/pycryptodome/

bytes型とint型の変換 bytes_to_long(): bytes型をint型に変換する関数 long_to_bytes(): int型をbytes型に変換する関数 bytes_to_long bytes型 int型 long_to_bytes

bytes型とint型の変換 >>> from Crypto.Util.number import * >>> flag = “Hello, World!” >>> bytes_to_long(flag.encode()) 5735816763073854918203775149089 >>> long_to_bytes(5735816763073854918203775149089) b'Hello, World!’

変換のまとめ bytes_to_long encode str型 bytes型 decode int型 long_to_bytes

RSA暗号の仕組み

共通鍵暗号 ブロック暗号 (AES, DES) やストリーム暗号 (RC4) など 鍵 平文 m 暗号化・復号 暗号化と復号で 同じ鍵を使う 暗号文 c

公開鍵暗号 RSA, ElGamal, 楕円ElGamalなど 公開鍵 平文 m 暗号化 復号 秘密鍵 暗号文 c 暗号化と復号で 異なる鍵を使う

RSA暗号 平文 𝑚𝑚，暗号文 𝑐𝑐，公開鍵 𝑒𝑒, 𝑛𝑛 ，秘密鍵 𝑑𝑑, 𝑛𝑛  暗号化  復号 𝑐𝑐 = 𝑚𝑚𝑒𝑒 mod 𝑛𝑛 𝑚𝑚 = 𝑐𝑐 𝑑𝑑 mod 𝑛𝑛

鍵の作り方 ① 大きな2つの素数 𝑝𝑝, 𝑞𝑞 を生成する 乱数生成＋素数判定（ミラーラビンテスト）を繰り返す． 具体的には 1024 ～ 2048 bit 程度． ② n = 𝑝𝑝𝑝𝑝 を計算する ③ 𝑙𝑙 を計算する 𝑎𝑎 と 𝑏𝑏 の最大公約数 (Greatest Common Divisor)， 最小公倍数 (Least Common Multiple) を gcd 𝑎𝑎, 𝑏𝑏 , lcm 𝑎𝑎, 𝑏𝑏 とする． (𝑝𝑝 − 1)(𝑞𝑞 − 1) 𝑙𝑙 = lcm 𝑝𝑝 − 1, 𝑞𝑞 − 1 = gcd 𝑝𝑝 − 1, 𝑞𝑞 − 1

鍵の作り方 • ③の補足 資料によっては，lcm 𝑝𝑝 − 1, 𝑞𝑞 − 1 を 𝜙𝜙 𝑛𝑛 = (𝑝𝑝 − 1)(𝑞𝑞 − 1) としている場合がある．しかし，どちらを採用してもRSA暗号は成立する． 一般には lcm 𝑝𝑝 − 1, 𝑞𝑞 − 1 のほうが 𝑝𝑝 − 1 𝑞𝑞 − 1 よりも小さくなるので， lcm 𝑝𝑝 − 1, 𝑞𝑞 − 1 が使われている． 詳しく知りたい人は「オイラーのトーシェント関数」で検索．

鍵の作り方 ④ 𝑒𝑒 を計算する 1 < 𝑒𝑒 < 𝑙𝑙 かつ gcd 𝑒𝑒, 𝑙𝑙 = 1 を満たす 𝑒𝑒 を求める． 大きすぎても小さすぎてもダメ． 𝑒𝑒 = 216 + 1 = 65537 が推奨されている． ⑤ 𝑑𝑑 を計算する 1 < 𝑑𝑑 < 𝑙𝑙 かつ 𝑒𝑒𝑒𝑒 ≡ 1 mod 𝑙𝑙 を満たす 𝑑𝑑 を求める． これは拡張ユークリッドの互除法で見つけられる．

RSA暗号の関連資料 • 結城浩，『暗号技術入門 第3版 秘密の国のアリス』 • IPUSIRON，『暗号技術のすべて』 • 光成滋生，『クラウドを支えるこれからの暗号技術』 https://herumi.github.io/ango/ • kurenaif， 【CTF入門】RSA暗号を実装/解読する 1 【Crypto】(訂正はコメント参照！) https://www.youtube.com/watch?v=HKDyUELFdXs • sonickun，RSA暗号運用でやってはいけない n のこと #ssmjp https://www.slideshare.net/sonickun/rsa-n-ssmjp • ふるつき，CTF crypto 逆引き https://furutsuki.hatenablog.com/entry/2021/03/16/095021

• https://herumi.github.io/ango/
• https://www.youtube.com/watch?v=HKDyUELFdXs
• https://www.slideshare.net/sonickun/rsa-n-ssmjp
• https://furutsuki.hatenablog.com/entry/2021/03/16/095021

RSA暗号の関連資料 • ももいろテクノロジー，plain RSAに対する攻撃手法を実装してみる http://inaz2.hatenablog.com/entry/2016/01/15/011138 • ももいろテクノロジー，SageMathを使ってCoppersmith's Attackをやってみる http://inaz2.hatenablog.com/entry/2016/01/20/022936 • A painter and a black cat，CTF Crypto https://raintrees.net/projects/a-painter-and-a-black-cat/wiki/CTF_Crypto • 0xDktb，Summary of Crypto in CTF(RSA) https://0xdktb.top/2020/02/28/Summary-of-Crypto-in-CTF-RSA/ • RsaCtfTool https://github.com/Ganapati/RsaCtfTool

• http://inaz2.hatenablog.com/entry/2016/01/15/011138
• http://inaz2.hatenablog.com/entry/2016/01/20/022936
• https://raintrees.net/projects/a-painter-and-a-black-cat/wiki/CTF_Crypto
• https://0xdktb.top/2020/02/28/Summary-of-Crypto-in-CTF-RSA/
• https://github.com/Ganapati/RsaCtfTool

[Beginner] simple_RSA

ファイル構成 • problem.py Pythonのプログラム • output.txt problem.pyの実行結果

output.txt 公開鍵と暗号文が書かれている． n = 1768667184240039357473051203420012852133691956973597279167660… e = 3 c = 2137917515300171115086910841683630246868780573379713198802569…

problem.py from Crypto.Util.number import * from flag import flag 実際には存在しない ダミーのライブラリ flag = bytes_to_long(flag.encode("utf-8")) p q n e = = = = getPrime(1024) getPrime(1024) p * q 3 assert 2046 < n.bit_length() assert 375 == flag.bit_length() print("n =", n) print("e =", e) print("c =", pow(flag, e, n)) 𝑒𝑒 が小さすぎる 𝑛𝑛 は 2046 bit より大きい flag は 375 bit

Low Public-Exponent Attack 𝑚𝑚𝑒𝑒 < 𝑛𝑛 のとき，𝑐𝑐 の 𝑒𝑒 乗根を取ることで 𝑚𝑚 が求まる．  理由 𝑚𝑚𝑒𝑒 < 𝑛𝑛 のとき， 𝑚𝑚𝑒𝑒 は mod 𝑛𝑛 の影響を受けず， となるから． 【例】7 mod 19 = 7 𝑐𝑐 = 𝑚𝑚𝑒𝑒 mod 𝑛𝑛 = 𝑚𝑚𝑒𝑒

Low Public-Exponent Attack この問題では 𝑒𝑒 = 3， 𝑛𝑛 は 2047 bit 以上，flag は 375 bit なので， だと予想できる． flag 𝑒𝑒 < 𝑛𝑛 Low Public-Exponent Attackでflagが出る！

方針 ① output.txtから 𝑒𝑒, 𝑛𝑛, 𝑐𝑐 の値を取ってくる ② 𝑐𝑐 の 𝑒𝑒 乗根を計算する ③ 出てきた数値を文字列に変換する

Pythonでe乗根を計算する方法 gmpy2というライブラリを使用する． インストールするためにはGMPの開発環境が必要． Ubuntuだとaptを使うと上手くやってくれる． $ sudo apt update $ sudo apt install python3-gmpy2

Windows ① pipが対応しているwhlのバージョンを確認する >>> from pip._internal.utils.compatibility_tags import get_supported >>> print(get_supported()) ② gmpy2のwhlファイルをダウンロードする https://www.lfd.uci.edu/~gohlke/pythonlibs/#gmpy $ pip install ./gmpy2-2.0.8-cp38-cp38-win_amd64.whl

• https://www.lfd.uci.edu/~gohlke/pythonlibs/#gmpy

iroot >>> import gmpy2 >>> gmpy2.iroot(1024, 2) (mpz(32), True) >>> gmpy2.iroot(1024, 2)[0] mpz(32) >>> gmpy2.root(1024, 2) mpfr('32.0') 返り値はタプルなので [0]を付けて取り出す． irootとrootは別物． rootは実数なので 精度が落ちる．

[Beginner] Logical_SEESAW

ファイル構成 • problem.py Pythonのプログラム • output.txt problem.pyの実行結果

output.txt 暗号文が16個書かれている． cipher = ['11000010111…', '11000110110…', '11000010110…’, … '11000110110…', '11000010101…', '11000110101…']

problem.py from Crypto.Util.number import * from random import random, getrandbits from flag import flag flag = bytes_to_long(flag.encode("utf-8")) length = flag.bit_length() key = getrandbits(length) while not length == key.bit_length(): key = getrandbits(length) flag = list(bin(flag)[2:]) key = list(bin(key)[2:]) flagのビット長 flagと同じビット長のkeyを生成 flagとkeyを2進数の リストに変換する

problem.py cipher_L = [] for _ in range(16): cipher = flag[:] m = 0.5 for i in range(length): n = random() if n > m: cipher[i] = str(eval(cipher[i] + "&" + key[i])) cipher_L.append("".join(cipher)) print("cipher =", cipher_L) 16個の暗号文を生成 50%の確率で flag[i] & key[i]

暗号文のパターン cipher[k][i] = flag[i] または flag[i] & key[i] flag[i] key[i] 0 0 0 0 1 0 1 0 0 1 1 1 0 ≤ 𝑘𝑘 ≤ 15 0 ≤ 𝑖𝑖 < length flag[i] & key[i] cipher[k][i]が“1”なら， flag[i]は”1”

暗号文のパターン cipher[k][i] = flag[i] または flag[i] & key[i] flag[i] key[i] flag[i] & key[i] 0 0 0 0 1 0 1 0 0 1 1 1 0 ≤ 𝑘𝑘 ≤ 15 0 ≤ 𝑖𝑖 < length すべてのkについて， cipher[k][i]が“0”なら， flag[i]は”0”

暗号文のパターン cipher[k][i] = flag[i] または flag[i] & key[i] flag[i] key[i] 0 0 0 0 1 0 1 0 0 1 1 1 0 ≤ 𝑘𝑘 ≤ 15 0 ≤ 𝑖𝑖 < length flag[i] & key[i] この場合もcipher[k][i]は“0” になるが，このパターンが16回 連続で発生する確率はほぼゼロ

16回すべてAND演算がされる確率 • 1回だけ判定してAND演算がされる確率 1 2 • 16回すべてAND演算がされる確率 1 2 16 1 = ≅ 0.0015 % 65536 滅多に起こらないから， この場合は考えなくてもいい

方針 ① output.txtからcipherを取ってくる ② 16個の暗号文の各ビットについて 一つでも“1”があれば，flagの対応するビットを”1” すべて”0”なら，flagの対応するビットを”0” ③ flagを10進数に変換する ④ flagを文字列に変換する

[Easy] GFM

ファイル構成 • problem.sage SageMathのプログラム • output.txt problem.sageの実行結果

SageMathとは 「Sageは，代数学，幾何学，数論，暗号理論，数値解析，および関連 諸分野の研究と教育を支援する，フリーなオープンソース数学ソフト ウェアである．」（公式ページより） Pythonをベースに開発されているので，文法はPythonと大体同じ． • オンラインの実行環境 https://sagecell.sagemath.org/ • 公式ページ https://www.sagemath.org/ • 公式チュートリアル https://doc.sagemath.org/html/ja/tutorial/index.html

• https://sagecell.sagemath.org/
• https://www.sagemath.org/
• https://doc.sagemath.org/html/ja/tutorial/index.html

problem.sage
FLAG = b'<censored>'
SIZE = 8
p = random_prime(2 ^ 128)
MS = MatrixSpace(GF(p), SIZE)
key = MS.random_element()
while key.rank() != SIZE:
key = MS.random_element()

位数 𝑝𝑝 の有限体上の数を
要素に持つ 8 × 8 の行列空間 𝑀𝑀𝑀𝑀

rank 𝑘𝑘𝑘𝑘𝑘𝑘 = 8
→ 𝑘𝑘𝑘𝑘𝑘𝑘 は正則行列（逆行列を持つ）

有限体 加算・減算・乗算・除算の四則演算が定義され， 閉じている有限集合を有限体といい，𝐺𝐺𝐺𝐺 𝑝𝑝 と表す． 発見者のガロアにちなんで，ガロア体 (Galois Field) とも呼ぶ． ※「閉じている」… すべての演算結果が集合内に存在すること． 𝑝𝑝 は有限体に含まれる要素の数であり，位数と呼ばれる． 0, 1, 2, … , 𝑝𝑝 − 2, 𝑝𝑝 − 1 𝑝𝑝 個

problem.sage M = copy(MS.zero()) for i in range(SIZE): for j in range(SIZE): n = i * SIZE + j if n < len(FLAG): M[i, j] = FLAG[n] else: M[i, j] = GF(p).random_element() enc = key * M * key print('p:', p) print('key:', key) print('enc:', enc) 行列 𝑀𝑀 にFLAGを1文字ずつ格納する 行列 𝑀𝑀 の空部分には乱数を格納する output.txtに出力されている値

Mを取り出す FLAGは 𝑀𝑀 に格納されているので，𝑒𝑒𝑒𝑒𝑒𝑒 から 𝑀𝑀 を取り出したい． 𝑘𝑘𝑘𝑘𝑘𝑘 は逆行列 𝑘𝑘𝑘𝑘𝑦𝑦 −1 を持つので， 𝑒𝑒𝑒𝑒𝑒𝑒 = 𝑘𝑘𝑘𝑘𝑘𝑘 × 𝑀𝑀 × 𝑘𝑘𝑘𝑘𝑘𝑘 𝑀𝑀 = 𝑘𝑘𝑘𝑘𝑦𝑦 −1 × 𝑒𝑒𝑒𝑒𝑒𝑒 × 𝑘𝑘𝑘𝑘𝑦𝑦 −1 SageMathで逆行列を求めるためには，inverse()を使えばいい． key_inv = key.inverse()

方針 ① output.txtから 𝑝𝑝, 𝑘𝑘𝑘𝑘𝑘𝑘, 𝑒𝑒𝑒𝑒𝑒𝑒 の値を取ってくる ② 𝑘𝑘𝑘𝑘𝑘𝑘 の逆行列 𝑘𝑘𝑘𝑘𝑦𝑦 −1 を計算する ③ 𝑒𝑒𝑒𝑒𝑒𝑒 の左右に 𝑘𝑘𝑘𝑘𝑦𝑦 −1 をかけて 𝑀𝑀 を取り出す ④ 𝑀𝑀 からFLAGを取り出す

[Medium] Imaginary

ファイル構成 • app.py サーバ側のプログラム • test.py 配布されたapp.pyをローカル環境で動かせるように 勝手に改造したプログラム ※ フラグを書いているので，中身は見ない方がいいかも

ローカル環境でサーバを動かす方法 test.pyを実行するだけ． 止めるときは”ctrl+c”を押す． $ python3 test.py Start server at localhost:1337

アプリの動作 ncで接続すると，コマンド一覧が表示される． $ nc localhost 1337 Welcome to Secret IMAGINARY NUMBER Store! 1. Save a number 2. Show numbers 3. Import numbers 4. Export numbers 0. Exit >

アプリの動作 1. 複素数を保存する > 1 Real part> 1 Imaginary part> 3 2. 保存した複素数を表示する > 2 -------------------------------------------------1 + 3i: (1, 3) --------------------------------------------------

アプリの動作

4. 保存した複素数のデータをjsonに変換し，
それをAESのECBモードで暗号化する
> 4
{"1 + 3i": [1, 3]}
Exported:
0b63e3e740430cb46bf2a51f4cb29edf273788035f227f77074feb3fc52d6717

アプリの動作 3. AESのECBモードで暗号化されたjsonを受け取り， それを復号して変数に代入する > 3 Exported String> 0b63e3e740430cb46bf2a51f4cb29edf273788035f227f77074feb3fc52d6717 Imported. -------------------------------------------------1 + 3i: (1, 3) --------------------------------------------------

app.py while True: num = self._menu() if num == 1: self._save() elif num == 2: self._show() elif num == 3: self._import() elif num == 4: self._export() elif num == 5: self._secret() else: break 表示されていないコマンド5

FLAGの出力条件 self.numbersに’1337i’が含まれていたらFLAGを出力する． def _secret(self): if '1337i' in self.numbers: self.request.sendall(b'Congratulations!¥n') self.request.sendall(f'The flag is {flag}¥n'.encode())

self.numbers

keyに複素数，valueに実部・虚部のリストを持つ辞書．
self.numbers = {}
name = f'{re} + {im}i'
self.numbers[name] = [re, im]

>>>
>>>
>>>
>>>
>>>
>>>
{'1

numbers = {}
re = 1
im = 2
name = f'{re} + {im}i'
numbers[name] = [re, im]
numbers
+ 2i': [1, 2]}

self.numbers 実部に0を入れても，0 + 1337iと保存されてしまう． > 1 Real part> 0 Imaginary part> 1337 1. Save a number 2. Show numbers 3. Import numbers 4. Export numbers 0. Exit > 2 -------------------------------------------------0 + 1337i: (0, 1337) --------------------------------------------------

データの改ざん そこで，Import / Export の機能に注目する． ① Exportでデータを出力する． このデータはAESのECBモードで暗号化されている． ② データを改ざんして，keyを’1337i’にする． ③ Importで改ざんしたデータを入力する．

AES ブロック暗号（共通鍵暗号）の一種． 平文を1ブロック128ビットで分割し，それを暗号化する． 平文を128ビットで割り切れない場合は，乱数を追加して 対応する (Padding)． 平文 １ 2 3 4 ・・・ 暗号化 暗号文 n-1 n pad

ECBモード 複数のブロックがある場合は暗号化を繰り返して行うことになる． このときの繰り返し方をモードという． 最も単純な方法は，平文のブロックをそのまま暗号化することである． これをECBモードという． 平文 ブロック1 暗号化 暗号文 ブロック1 平文 ブロック2 暗号化 暗号文 ブロック2 平文 ブロック3 暗号化 暗号文 ブロック3 平文 ブロック4 暗号化 暗号文 ブロック4

ECBモードの問題点 ECBモードでは，暗号文のブロックを入れ替えたり，削除したりしても 復号ができてしまう． Aさん 暗号化 に100万貸した Bさん は 暗号化 入れ替える 暗号化 「BさんはAさんに100万貸した」に改ざんできる 暗号化

改ざんの方針 半角文字は8ビットなので，1ブロックは128÷8で16文字となる． データのkeyに’1337i’が出てくるように上手く調整する． {“a␣+␣bi”:␣[a,␣b],␣” c␣+␣ ～ブロック 1ブロック 1337i”:␣[c,␣1337]} ↑ 消す {“a␣+␣bi”:␣[a,␣b],␣”1337i”:␣[c,␣1337]}

改ざん用データの作成 {“a␣+␣bi”:␣[a,␣b],␣”とc␣+␣を作る． $ python3 data_1.py {'1000 + 1000i': [1000, 1000], ' x: 1000 bytes: 32 $ python3 data_2.py 1000000000000 + y: 1000000000000 bytes: 16

暗号文の入手 Exportを使って，暗号文を入手する． > 4 {"1000 + 1000i": [1000, 1000], "1000000000000 + 1337i": [1000000000000, 1337]} Exported: 71295e3edd417b3a18be48eb67b129508c7a47ce644b2402003bdd4e8c50510167d8 c505c310236544b96267806d5fed097af578edba148ead016696be713cff95c68a47 aabef5095c32c686008db357

不要なブロックの削除 1000000000000␣+␣のブロックを削除し， 必要なブロックだけを取り出す． $ python3 clip.py 71295e3edd417b3a18be48eb67b129508c7a47ce644b2402003bdd4e8c505101097a f578edba148ead016696be713cff95c68a47aabef5095c32c686008db357

FLAG 改ざんしたデータをImportし，5でFLAGを表示する． > 5 Congratulations! The flag is ctf4b{yeah_you_are_a_member_of_imaginary_number_club}

Cryptoの作問者Writeup • @ushigai_sub，SECCON Beginners CTF2021 作問者Writeup https://qiita.com/ushigai_sub/items/8c63fb566f19ac097bc5 • rex.gs，SECCON Beginners CTF 2021 Crypto 解説 https://rex.gs/2021/05/seccon-beginners-ctf-2021-crypto-%E8%A7%A3%E8%AA%AC/

• https://qiita.com/ushigai_sub/items/8c63fb566f19ac097bc5
• https://rex.gs/2021/05/seccon-beginners-ctf-2021-crypto-解説/

LLLの関連資料 • 自作のノート https://github.com/HK-ilohas/hkdocuments/blob/main/Knapsack_CLOS/Knapsack_CLOS.pdf • 國廣 昇，格子理論を用いた暗号解読の最近の研究動向 https://www.jstage.jst.go.jp/article/essfr/5/1/5_1_42/_pdf • うさぎ小屋，PlaidCTF CTF 2015: Lazy https://kimiyuki.net/writeups/ctf-2015-plaidctf-2015-lazy/ • katagaitai workshop #7 crypto ナップサック暗号と低密度攻撃 https://www.slideshare.net/trmr105/katagaitai-workshop-7-crypto • Xornet，LLLでCrypto問題を解く https://project-euphoria.dev/blog/10-lll-for-crypto/

• https://github.com/HK-ilohas/hk-documents/blob/main/Knapsack_CLOS/Knapsack_CLOS.pdf
• https://www.jstage.jst.go.jp/article/essfr/5/1/5_1_42/_pdf
• https://kimiyuki.net/writeups/ctf-2015-plaidctf-2015-lazy/
• https://www.slideshare.net/trmr105/katagaitai-workshop-7-crypto
• https://project-euphoria.dev/blog/10-lll-for-crypto/

p-8RSAの関連資料 • y011d4.log，p - 1 ≡ 0 (mod e) のときの RSA 復号方法 https://y011d4.netlify.app/20201026-not-coprime-e-phi/ • How to compute m value from RSA if phi(n) is not relative prime with the e? https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-fromrsa-if-phin-is-not-relative-prime-with-the-e • 0xDktb，Summary of Crypto in CTF(RSA) https://0xdktb.top/2020/02/28/Summary-of-Crypto-in-CTF-RSA/ • RSA Risk: When e and PHI share the same factor (and are not co-prime) https://asecuritysite.com/encryption/rsa_prob

• https://y011d4.netlify.app/20201026-not-coprime-e-phi/
• https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e
• https://0xdktb.top/2020/02/28/Summary-of-Crypto-in-CTF-RSA/
• https://asecuritysite.com/encryption/rsa_prob