過ぎるだけの時間じゃ悔しい

CryptoHack

Properties1
tagsctf

16 min read

同期と隔週土曜に CryptoHack の問題を解いている。

分野別に問題が分かれている

  • 2024-09-14 登録

  • pem

    • from Crypto.PublicKey import RSA
    • key = RSA.import_key(key), key.d

  • pub keyは公開されていて検索できる, 使っているsub domainを検索

    • openssl rsa -in t.pem -pubin -outform der | openssl dgst -sha256
    • https://crt.sh?a=1 で SHA-256(SubjectPublicKeyInfo) で検索
    • https://thetransparencyflagishere.cryptohack.org/ がヒットする

Math

# x^a, x^(a+1), ... (mod p) の列から a, pを特定
ints = [588, 665, 216, 113, 642, 4, 836, 114, 851, 492, 819, 237]
 
# 以下 mod p
# x ^ a = 588
# x ^ a * x = 588 * x = 665 <=> x = 665 / 588
# x ^ a * x ^ 2 = 588 * x ^ 2 = 216 <=> x ^ 2 = 216 / 588
# よって, 216 / 588 = (665 / 588) ^ 2
 
for p in range(100, 999):
    try:
        if divmod(216, 588, p) == pow(divmod(665, 588, p), 2, p):
            ic(p)
            break
    except:
        pass
 
ic(divmod(665, 588, p))
  • Adrien’s Signs
    • 有限体の累乗根: Adleman-Manders-Miler algorithm
# c = 01100011
# [0]: n1 = a ^ e1
# n1 = -878604477115251
# [3]: n3 = a ^ e3
# n3 = -384763565929640
# n1 * n3 = a ^ (e1 + e3)
 
# 方針: e乗根を求める
for i in range(1, 8):
    for b in ["0", "1"]:
        # TODO: 主張: b が 1 か 0 かどちらかの場合のみ e乗根が存在する
        if b == "1":
            actual_n = actual_ints[i]
        else:
            actual_n = -actual_ints[i] % p
 
        # e乗根の存在を確認
        # a = actual_n ^ e mod p
        e = discrete_logarithm_arbitrary_mod(a, actual_n, p)
        ic(i, b, e)
        if e is None:
            continue
        ans.append(b)
 
ic(ans)
 
ic(long_to_bytes(int("".join([str(int(qr(i, p))) for i in c]), 2)))

# e1, e2, c1, c2, n given
e = e1 * e2
 
# c1^e2 = (2p)^e + (3q)^e
# c2^e1 = (5p)^e + (7q)^e
# p^e を消す, 5^e c1^e2 - 2^e c2^e1 = (q だけの式)
# よって q^e は (左辺) をNの約数に持つ
# q^e = q = gcd((左辺), N)
 
e = e1 * e2
q = gcd(pow(5, e, n) * pow(c1, e2, n) - pow(2, e, n) * pow(c2, e1, n), n)
p = n // q
assert n == p * q
print(f"crypto{{{p},{q}}}")
  • Broken RSA

Symmetric Ciphers

key <- md5(word.encode())
flag = "crypto{???}"
ct = aes.enc(key, flag)
{ word in words | aes.dec(key, ct) == "crypto{...}" }
  • ECB CBC WTF
[iv, ct] = aes.enc(key, flag, iv)
[iv: 16 | ct1: 16 | ct2: 16]
# inversion of CBC
p2 = dec(c2) ^ c1
p1 = dec(c1) ^ iv
p = p1 + p2
print(p)

  • ECB Oracle

    • AES-ECB Padding Attack | Exploit Notes
    • 31bytesのダミーで埋めると先頭1(=32-1)byteのみの暗号化となる
    • 総当りで1bytesを探す, 以降30byte + 見つけた1byte(=flag)に減らして同じことをする

  • Flipping Cookie

# p1_true = p1 ^ "admin=False;expi" ^ "admin=True ;expi"
# c1 = enc(p1 ^ iv)
# c2 = enc(p2 ^ c1)
# c3 = enc(p3 ^ c2)

RSA

2024-10-25

  • 素因数分解

    • ECM: Eliptic Curve Method
    • SIQS: 2次篩

  • Modular Exponentiation

  • Publis Keys

    • `n = p*q
    • ct = pow(pt, e, n)

  • Euler's Totient

    • 約数の個数
    • phi(N) = (p-1)(q-1)
    • p, q: 素数なので

  • Private Keys

    • pt = pow(ct, d, n)
    • d = pow(e, -1, phi)

  • RSA Decryption

  • RSA Signatures

    • 平文 m, `c = pow(m, e0, N0)
    • 署名 s = pow(h(m), d1, n1)
      • h() はSHA256
    • 検証 s == pow(s, e1, n1)

  • Factoring

  • Inferius Prime

  • Monoprime

    • n: 素数のとき phi = n - 1

  • Square Eyes

  • Manyprime

    • factordb

  • Salty

    • やるだけ

  • Modulus Inutilis

    • Low Public-Exponent Attack ctf - Qiita
    • gmpy2.iroot(v^k, k) -> (mpz(v), is_int)
    • pt^e < n の時, mod n の影響受けなくなるので pt = iroot(ct, e)

  • Everything is Big

    • factordb

  • Crossed Wires

    • factordb
    • 順番にdecするだけ

  • Everything is still Big

    • factordb

  • Endless Emails

def CRT(pairs):
    M = 1
    for a, m in pairs:
        M *= m
    result = 0
    for a, m in pairs:
        Mi = M // m
        s, _, _ = extgcd(Mi, m)
        result += a * Mi * s
    return result % M
 
def HBR(e: int, pairs: list[(int, int)]):
    r = CRT(pairs)
    return iroot(r, e)
 
for indices in combinations(range(len(cn_pairs)), 3):
    pairs = [cn_pairs[i] for i in indices]
    pt, is_int = HBR(e, pairs)
    if is_int:
        print(long_to_bytes(pt))

  • 日本62位

  • Infinite Descent

    • factordb

  • Marin's Secrets

    • factordb

  • Fast Primes

    • key = RSA.construct((n, e, d))
    • cipher = PKCS1_OAEP.new(key)

  • Ron was Wrong, Whit is Right

Diffie-Hellman

from Crypto.Util.number import *
 
 
def smooth_p():
    mul = 1
    i = 1
    while 1:
        mul *= i
        if (mul + 1).bit_length() >= p.bit_length() and isPrime(mul + 1):
            return mul + 1
        i += 1

Elliptic Curves

2024-11-16

def sha1(s: str):
    import hashlib
 
    sha1 = hashlib.sha1()
    sha1.update(s.encode("ascii"))
    hash = sha1.digest()
    return hash
  • ECDH
alice:
    n_A <- Z
    Q_A = [n_A]G
bob:
    n_B <- Z
    Q_B = [n_B]G
alice:
    [n_A]Q_B
bob:
    [n_B]Q_A

S = [n_A]Q_B = [n_B]Q_A
  • Efficient Exchange
from lib import fp, EllipticCurve, Point, decrypt_flag
 
ec = EllipticCurve(fp(497), fp(1768))
g = Point.new(1804, 5368)
 
x = fp(4726)
q_a = Point(False, x, ec.e(x))
n_b = 6534
s = ec.mul(q_a, n_b).x
print(decrypt_flag(s.value, iv, encrypted_flag))
sage: p = 310717010502520989590157367261876774703
sage: p
310717010502520989590157367261876774703
sage: a = 2
sage: b = 3
sage: g_x = 179210853392303317793440285562762725654
sage: g_y = 105268671499942631758568591033409611165
sage: E = EllipticCurve(GF(p), [a,b])
sage: G = E(g_x, g_y)
sage: G.order()
155358505251260494795103074529582338902
sage: n = G.order()
sage: n.factor()
2 * 3^7 * 139 * 165229 * 31850531 * 270778799 * 179317983307
sage: gn_x = 280810182131414898730378982766101210916
sage: gn_y = 291506490768054478159835604632710368904
sage: Gn = E(gn_x, gn_y)
sage: G.discrete_log(Gn)

  • Exceptional Curves

    • from sage.all import 出来ない

  • Micro Transmissions

Hash Functions

  • (1) Pre-image attacks

    • x = hash(m) があるときに, hash(m0) == x となる m0 を見つけることが難しい

  • (2) Second pre-image resistance

    • m1 があるときに hash(m1) == hash(m2) を探すのが難しい
    • (1) が出来るなら出来る

  • (3) Collision resistance

    • hash(m1) == hash(m2) な m1, m2 を見つけるのが難しい
    • (1) が出来るなら出来る
    • (3) が出来ても (1) が出来るとは限らない

  • Jack’s Birthday Hash

    • 11bit値 JACK(secret) = 01011001101 と衝突する確率が50%になる秘密鍵の個数は?
    • -> 誕生日攻撃は2つ用意できるので違う
    • 余事象をつかう
      • (1 - 2^-11)^n > 0.5 <=> n > 1420

  • Jack’s Birthday Confusion

    • 任意の2つが75%
    • k ~= sqrt(2n ln(1 / 1 - p)) = sqrt(2n ln 4)

  • Collider

    • self.documents[document_hash] != document だとflagわかる

  • Hash Stuffing

    • xorと巡回シフトが全単射な気がするので無理でない?
      • initial_state を普通に使いまわしていた
    • bitの流れを追う

  • Merkle Trees

    • やるだけ

  • WOTS Up

Web Security

RSA or HMAC2

https://blog.silentsignal.eu/2021/02/08/abusing-jwt-public-keys-without-the-public-key/

TLS

$ tshark -r ~/Downloads/cryptohack_6b3a90f7c585d399088758fda92fb9f6.org.pcapng
# DNS
    1   0.000000 172.16.112.134 → 172.16.112.2 DNS 74 Standard query 0x87f0 A cryptohack.or
    2   0.000117 172.16.112.134 → 172.16.112.2 DNS 74 Standard query 0x2bf6 AAAA cryptohack.org
# The "Safe Browsing" feature in Firefox reached out to a Google server
# to check that cryptohack.org was not a phishing or malicious domain.
    3   0.007451 172.16.112.134 → 216.58.213.3 TCP 54 56062 → 80 [ACK] Seq=1 Ack=1 Win=63791 Len=0
    4   0.008528 216.58.213.3 → 172.16.112.134 TCP 60 [TCP ACKed unseen segment] 80 → 56062 [ACK] Seq=1 Ack=2 Win
# DNS responses 
    5   0.170777 172.16.112.2 → 172.16.112.134 DNS 104 Standard query response 0x87f0 A cryptohack.org A 178.62.7
    6   0.172908 172.16.112.2 → 172.16.112.134 DNS 169 Standard query response 0x2bf6 AAAA cryptohack.org SOA ns1
# A TCP three-way handshake
    7   0.175626 172.16.112.134 → 178.62.74.206 TCP 74 54028 → 443 [SYN] Seq=0 Win=64240 Len=0 MSS=1460 SACK_PERM
    8   0.185694 178.62.74.206 → 172.16.112.134 TCP 60 443 → 54028 [SYN, ACK] Seq=0 Ack=1 Win=64240 Len=0 MSS=146
    9   0.186029 172.16.112.134 → 178.62.74.206 TCP 54 54028 → 443 [ACK] Seq=1 Ack=1 Win=64240 Len=0
# A TLS ClientHello 
   10   0.207390 172.16.112.134 → 178.62.74.206 TLSv1 571 Client Hello
   11   0.209439 178.62.74.206 → 172.16.112.134 TCP 60 443 → 54028 [ACK] Seq=1 Ack=518 Win=64240 Len=0
# The server sent TLS ServerHello
   12   0.217279 178.62.74.206 → 172.16.112.134 TLSv1.3 2934 Server Hello, Change Cipher Spec, Application Data
   13   0.217366 172.16.112.134 → 178.62.74.206 TCP 54 54028 → 443 [ACK] Seq=518 Ack=2881 Win=62780 Len=0
   14   0.217280 178.62.74.206 → 172.16.112.134 TCP 1270 443 → 54028 [PSH, ACK] Seq=2881 Ack=518 Win=64240 Len=12
   15   0.218063 172.16.112.134 → 178.62.74.206 TCP 54 54028 → 443 [ACK] Seq=518 Ack=4097 Win=61564 Len=0
   16   0.218534 178.62.74.206 → 172.16.112.134 TLSv1.3 582 Application Data, Application Data, Application Data
   17   0.218591 172.16.112.134 → 178.62.74.206 TCP 54 54028 → 443 [ACK] Seq=518 Ack=4625 Win=61036 Len=0
# An Online Certificate Status Protocol (OCSP) connection was made from our laptop to an OCSP server,
# to check that the TLS certificate presented by CryptoHack hadn't been revoked...
   18   0.255769 172.16.112.134 → 23.62.3.195  OCSP 467 Request
   19   0.256280  23.62.3.195 → 172.16.112.134 TCP 60 80 → 38256 [ACK] Seq=1 Ack=414 Win=64240 Len=0
   20   0.265894  23.62.3.195 → 172.16.112.134 OCSP 941 Response
   21   0.265949 172.16.112.134 → 23.62.3.195  TCP 54 38256 → 80 [ACK] Seq=414 Ack=888 Win=63936 Len=0
# Our laptop sent a Change Cipher Spec message to note that it is switching over to sending encrypted data
   22   0.278679 172.16.112.134 → 178.62.74.206 TLSv1.3 134 Change Cipher Spec, Application Data
   23   0.279032 178.62.74.206 → 172.16.112.134 TCP 60 443 → 54028 [ACK] Seq=4625 Ack=598 Win=64240 Len=0
   24   0.280042 172.16.112.134 → 178.62.74.206 TLSv1.3 224 Application Data
   25   0.280460 172.16.112.134 → 178.62.74.206 TLSv1.3 361 Application Data
   26   0.280537 178.62.74.206 → 172.16.112.134 TCP 60 443 → 54028 [ACK] Seq=4625 Ack=768 Win=64240 Len=0
   27   0.280658 178.62.74.206 → 172.16.112.134 TCP 60 443 → 54028 [ACK] Seq=4625 Ack=1075 Win=64240 Len=0
   28   0.288327 178.62.74.206 → 172.16.112.134 TLSv1.3 690 Application Data, Application Data, Application Data
# The server started sending the contents
   29   0.288356 172.16.112.134 → 178.62.74.206 TCP 54 54028 → 443 [ACK] Seq=1075 Ack=5261 Win=62780 Len=0
   30   0.288742 172.16.112.134 → 178.62.74.206 TLSv1.3 85 Application Data
   31   0.288994 178.62.74.206 → 172.16.112.134 TCP 60 443 → 54028 [ACK] Seq=5261 Ack=1106 Win=64240 Len=0
   32   0.296851 178.62.74.206 → 172.16.112.134 TLSv1.3 85 Application Data
   33   0.296881 172.16.112.134 → 178.62.74.206 TCP 54 54028 → 443 [ACK] Seq=1106 Ack=5292 Win=62780 Len=0
   34   0.347798 178.62.74.206 → 172.16.112.134 TCP 1494 [TCP segment of a reassembled PDU]
   35   0.347839 172.16.112.134 → 178.62.74.206 TCP 54 54028 → 443 [ACK] Seq=1106 Ack=6732 Win=62780 Len=0
   36   0.348229 178.62.74.206 → 172.16.112.134 TCP 1494 443 → 54028 [PSH, ACK] Seq=6732 Ack=1106 Win=64240 Len=1440 [TCP segment of a reassembled PDU]
   37   0.348266 172.16.112.134 → 178.62.74.206 TCP 54 54028 → 443 [ACK] Seq=1106 Ack=8172 Win=62780 Len=0
   38   0.349329 178.62.74.206 → 172.16.112.134 TLSv1.3 2556 Application Data
   39   0.349369 172.16.112.134 → 178.62.74.206 TCP 54 54028 → 443 [ACK] Seq=1106 Ack=10674 Win=62780 Len=0
# Firefox's HTML parser saw that it needed external resources from Content Delivery Networks
   40   0.622776 172.16.112.134 → 172.16.112.2 DNS 80 Standard query 0xe81a A cdnjs.cloudflare.com
   41   0.622859 172.16.112.134 → 172.16.112.2 DNS 80 Standard query 0xda07 AAAA cdnjs.cloudflare.com
   42   0.625105 172.16.112.134 → 172.16.112.2 DNS 74 Standard query 0x8b91 A cryptohack.org
   43   0.625316 172.16.112.134 → 172.16.112.2 DNS 74 Standard query 0x7c9d AAAA cryptohack.org
   44   0.635045 172.16.112.2 → 172.16.112.134 DNS 90 Standard query response 0x8b91 A cryptohack.org A 178.62.74.206
   45   0.637084 172.16.112.2 → 172.16.112.134 DNS 74 Standard query response 0x7c9d AAAA cryptohack.org
   46   0.643725 172.16.112.2 → 172.16.112.134 DNS 152 Standard query response 0xe81a A cdnjs.cloudflare.com A 104.16.19.94 A 104.16.18.94
   47   0.645859 172.16.112.2 → 172.16.112.134 DNS 176 Standard query response 0xda07 AAAA cdnjs.cloudflare.com AAAA 2606:4700::6810:135e AAAA 2606:4700::6810:125e
   48   0.669092 172.16.112.134 → 172.16.112.2 DNS 76 Standard query 0x296c A cdn.jsdelivr.net
   49   0.669156 172.16.112.134 → 172.16.112.2 DNS 76 Standard query 0x5669 AAAA cdn.jsdelivr.net
   50   0.686745 172.16.112.2 → 172.16.112.134 DNS 333 Standard query response 0x5669 AAAA cdn.jsdelivr.net CNAME jsdelivr.map.fastly.net AAAA 2a04:4e42:400::485 AAAA 2a04:4e42:200::485 AAAA 2a04:4e42:600::485 AAAA 2a04:4e42::485
   51   0.687751 172.16.112.2 → 172.16.112.134 DNS 285 Standard query response 0x296c A cdn.jsdelivr.net CNAME jsdelivr.map.fastly.net A 151.101.65.229 A 151.101.1.229 A 151.101.193.229 A 151.101.129.229

cipher suite name(OpenSSL format)

  • ECDHE-RSA-AES128-GCM-SHA256:
    • ECDHE: used for key exchange.
    • RSA: signature algorithms
    • AES-128: is used to symmetrically encrypt the application data.
      • GCM: is the mode of operation that will be used for AES.
    • SHA256 will be used for handshake authentication.

https://www.ssllabs.com/ssltest/analyze.html?d=tls1.cryptohack.org
ECDHE-RSA-AES256-GCM-SHA384

Decrypting TLS1.2

  • TLS1.2はハンドシェイクが平文で見える
    • Menu > Protocols > TLS > add private keys > 172.16.112.2:443

Decrypting TLS1.3

Authenticated Handshake

認証は

  • 証明書
  • 証明書の検証
  • FinishedMessage: 今までのTLSメッセージのどれかが改ざんされていないかの確認
    • HMAC(finished_key, Transcript-Hash(Handshake Context, Certificate*, CertificateVerify*))
      • HMAC(): cipher suiteで定義された関数, usually SHA256 or SHA384.
    • finished_key: is the relevant handshake_traffic_secret, the CLIENT_HANDSHAKE_TRAFFIC_SECRET seen in the keylogfile.txt in the case for the client’s Finished.
    • Transcript-Hash(): concatenating together TLS messages (not including record layer headers) and hashing the result using the hash algorithm in the cipher suite.

Graph View