🔑

CTF Crypto まとめ

2024/07/01に公開

cryptography

CTF

tech

asusnがこれまで解いてきたCTFのCrypto問題をジャンルごとに分類してまとめていくページです

よく使うツール・テクニック

やること

GPTにコードを投げて以下のことを聞く
- 何の暗号に基づいているか or オリジナルの暗号かを聞く
- それぞれの関数が何をやっているか詳しく聞く
- 既存の暗号と違ってどこが違うかを聞く
それぞれの変数の値をprintして紐解いていく
部分的にわかっている暗号と復号文があれば、キーを推測できると考える
シード固定されている？毎回同じ結果にできる？
英語版のWikipediaを読む
ギリ総当たり厳しい場合(2^32ぐらい)は中間一致攻撃を疑う
- 乱数は、何度か実行することで都合の良い数になる可能性があるので、全ての数を網羅していなくてもいい
暗号文の状態でuser1->adminに書き換えられない？（ビットフリップ攻撃）
Merkle–Damgård構造を持つハッシュを使っている？（Length Extension Attack）

テクニック

全ての文字

全ての文字で結果を試したいときはstring.printableを使う
string --- 一般的な文字列操作 — Python 3.12.4 ドキュメント

import string
strings = string.printable

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#%&\'()*+,-./:;<=>?@[\\]^_{|}~ \t\n\r\x0b\x0c

ファイルのロード

output.txtにある変数をpythonとして読みたい場合

with open('output.txt') as f:
    exec(f.read())

バイナリを読みたい場合

with open('secret.enc', 'rb') as f:
    secret = f.read()

bytes ⇔ int

b'a'[0] # 97
b'\x20'[0] # 32
int.from_bytes(b'i') # 105
int.from_bytes(b'\x00i', 'big') # 105

i.to_bytes() # b'i'
i.to_bytes(2, 'big') # b'\x00i'

hex ⇔ int

int('ff', 16) # 255
'{:02x}'.format(255) # 'ff'

bytes ⇔ long

from Crypto.Util.number import *
bytes_to_long(b)
long_to_bytes(l)

bytes ⇔ str

'str'.encode()
b'bytes'.decode()

bytes ⇔ hex

bytes.fromhex('deadbeef')
b'\xde\xad\xbe\xef'.hex()

素数(Crypto.Util)

from Crypto.Util.number import *
getPrime(512) # 512bitのランダムな素数を取得
isPrime(n) # 素数かどうか

素数(sympy)

from sympy import *
factorint(n) # 素因数分解
nextprime(n) # 次の素数

n乗根

import math
math.isqrt(k) # 2048くらいの大きい数の2乗根(整数値・切り捨て)

import gmpy2
root, exact = gmpy2.iroot(gmpy2.mpz(k), 3) # 大きい数の3乗根

奇素数pを法としたn乗根

# 平方根
from sympy.ntheory import sqrt_mod
sqrt_mod(17, 32, True) # [7, 9, 23, 25]

# n乗根
from sympy.ntheory.residue_ntheory import nthroot_mod
nthroot_mod(11, 4, 19, True) # [8, 11]

計算

s = A / (1 + A) (mod p) の計算

s = A * pow(1 + A, -1 , p) % p

汎用ツール

何の暗号かを調べる

https://www.dcode.fr/cipher-identifier

素因数分解

p-1法のような特殊な素因数を持つ場合などに使える素因数分解ツール

https://sourceforge.net/projects/yafu/ (Windows/Linux)
https://pypi.org/project/primefac/

$ python -m primefac 123456789
123456789: 3 3 3803 3607

定理

中国の剰余定理

与えられた二つの整数 m1, m2 が互いに素ならば、任意に与えられる整数 a1, a2 に対し、連立合同式
x ≡ a1 (mod m1),
x ≡ a2 (mod m2)
を満たす整数 x が m1 m2 を法として一意的に存在する。

from sympy.ntheory.modular import solve_congruence
solve_congruence((a1, m1), (a2, m2), (a3, m3))

こっちの方がいいかも

from sympy.ntheory.modular import crt
moduli = [3, 5, 7]  # 各法 (m1, m2, m3, ...)
remainders = [2, 3, 2]  # 各剰余 (a1, a2, a3, ...)

x, lcm = crt(moduli, remainders)  # xが最小解、lcmが法の積

https://ja.wikipedia.org/wiki/中国の剰余定理

中間一致攻撃

4重のAES

RSAのメッセージが2^32の乱数

RSA

暗号化

from Crypto.Util.number import *

flag = b'asusn'
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
c = pow(m, e, n)

print(f"{m = }")
print(f"{p = }")
print(f"{q = }")
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

復号

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = long_to_bytes(m).decode()

print(f"{phi = }")
print(f"{d = }")
print(f"{flag = }")

eが小さい(Low Public-Exponent Attack)

i = 0
while True:
    m, ok = gmpy2.iroot(c + i * n, e)
    if ok:
        break
    i += 1
print(long_to_bytes(m))

eが大きい(Wiener's Attack)

すなわちdが小さいとき。picoCTF2021の「Dachshund Attacks」など。

https://github.com/pablocelayes/rsa-wiener-attack/tree/master にあるコードをcloneして以下を実行

from RSAwienerHacker import *
d = hack_RSA(e, n)

異なるe1, e2で暗号化(Common Modulus Attack)

from sympy import gcdex

x, y, _ = gcdex(e1, e2)
m = (pow(c1, int(x), n) * pow(c2, int(y), n)) % n
print(long_to_bytes(m))

ツール

使ったことないけど試しておきたい

これも(from tchen)
https://github.com/jvdsn/crypto-attacks

RSA参考

どんな脆弱さがあるかは以下を確認するとよい

AES

AESについて

ECBがブロックごとに独立して暗号化するやつで、
CBCがIVを使って前のブロックの暗号をXORするやつ。

CyberChefにAESがあり、雑に試すことができる

乱数予測系

Pythonのrandom(Mersenne Twister)

# Python uses the Mersenne Twister (MT19937) as the core generator.
# Setup Random Number Generator
rng = random.Random()
rng.seed(secrets.randbits(32))

secret = rng.getrandbits(32)

IERAE CTFのWeak PRNGで、以下の記事を参考に、624個の乱数を元にステートを求めて、過去の乱数624個を生成した