Zenn
🔑

【HackTheBox Crypto Challenge】TwoForOne Writeup

2023/07/30に公開
Security
#
rsa
#
暗号
#
暗号化
#
hackthebox
tech


前はマシーンだけでしたが、最近はhtbのチャレンジも始めました。

About This Challenge

challengeの説明
CHALLENGE DESCRIPTION
Alice sent two times the same message to Bob.

提供されたのは2つの公開鍵と2つのciphertext。説明文から、2つのciphertextは同じplaintextから暗号化されたものだとがわかります。

key1.pem
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAxqy430huZnHUpVZIA+HD
IUqOJ03grABD7CjIWJ83fH6NMIvD4wKFA4Q0S6eYiIViCkGOatlVV4KE/ATyifEm
s4oBgWJRzvmhT9TCSdlraQh/qRsuGtvcgMuW/wzLYSnY9nN9qFDEUfLtP2y2HDaJ
Hckk0Kso8mrfDtNXzoSNAv/gCRJxTM9jcsH0EIDoZ0egMD61zfbOkS8RRP1PVXQ8
eWh1oU/f+Pi2YhUMVr5YsJI5dx3ETZaQecStj9mTvGMLeFXS4C6L4Wgk3NWrOBMj
HBcxEQqL0CjXod+riS51KUVXuvxxrq9eSNsCZ6bbY9NQ+ZUGjuHK1tMt8RpJvSS6
lwIDAQAB
-----END PUBLIC KEY-----⏎
key2.pem
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAxqy430huZnHUpVZIA+HD
IUqOJ03grABD7CjIWJ83fH6NMIvD4wKFA4Q0S6eYiIViCkGOatlVV4KE/ATyifEm
s4oBgWJRzvmhT9TCSdlraQh/qRsuGtvcgMuW/wzLYSnY9nN9qFDEUfLtP2y2HDaJ
Hckk0Kso8mrfDtNXzoSNAv/gCRJxTM9jcsH0EIDoZ0egMD61zfbOkS8RRP1PVXQ8
eWh1oU/f+Pi2YhUMVr5YsJI5dx3ETZaQecStj9mTvGMLeFXS4C6L4Wgk3NWrOBMj
HBcxEQqL0CjXod+riS51KUVXuvxxrq9eSNsCZ6bbY9NQ+ZUGjuHK1tMt8RpJvSS6
lwIDBTy3
-----END PUBLIC KEY-----
message1
RBVdQw7Pllwb42GDYyRa6ByVOfzRrZHmxBkUPD393zxOcrNRZgfub1mqcrAgX4PAsvAOWptJSHbrHctFm6rJLzhBi/rAsKGboWqPAWYIu49Rt7Sc/5+LE2dvy5zriAKclchv9d+uUJ4/kU/vcpg2qlfTnyor6naBsZQvRze0VCMkPvqWPuE6iL6YEAjZmLWmb+bqO+unTLF4YtM1MkKTtiOEy+Bbd4LxlXIO1KSFVOoGjyLW2pVIgKzotB1/9BwJMKJV14/+MUEiP40ehH0U2zr8BeueeXp6NIZwS/9svmvmVi06Np74EbL+aeB4meaXH22fJU0eyL2FppeyvbVaYQ==
message2
TSHSOfFBkK/sSE4vWxy00EAnZXrIsBI/Y6mGv466baOsST+qyYXHdPsI33Kr6ovucDjgDw/VvQtsAuGhthLbLVdldt9OWDhK5lbM6e0CuhKSoJntnvCz7GtZvjgPM7JDHQkAU7Pcyall9UEqL+W6ZCkiSQnK+j6QB7ynwCsW1wAmnCM68fY2HaBvd8RP2+rPgWv9grcEBkXf7ewA+sxSw7hahMaW0LYhsMYUggrcKqhofGgl+4UR5pdSiFg4YKUSgdSw1Ic/tug9vfHuLSiiuhrtP38yVzazqOZPXGxG4tQ6btc1helH0cLfw1SCdua1ejyan9l1GLXsAyGOKSFdKw==

Investigation

key1.pemとkey2.pemの値がほぼ同じなので気になります。とりあえずpemをdecodeできるオンラインツールで中身を見てみます。https://8gwifi.org/PemParserFunctions.jsp

key1.pemのdecode結果
Algo RSA
Format X.509
 ASN1 Dump
RSA Public Key [a8:50:bd:91:69:2a:d6:c1:76:15:11:4a:0e:d8:62:7e:1d:28:93:8c]
            modulus: c6acb8df486e6671d4a5564803e1c3214a8e274de0ac0043ec28c8589f377c7e8d308bc3e302850384344ba7988885620a418e6ad955578284fc04f289f126b38a01816251cef9a14fd4c249d96b69087fa91b2e1adbdc80cb96ff0ccb6129d8f6737da850c451f2ed3f6cb61c36891dc924d0ab28f26adf0ed357ce848d02ffe00912714ccf6372c1f41080e86747a0303eb5cdf6ce912f1144fd4f55743c796875a14fdff8f8b662150c56be58b09239771dc44d969079c4ad8fd993bc630b7855d2e02e8be16824dcd5ab3813231c1731110a8bd028d7a1dfab892e75294557bafc71aeaf5e48db0267a6db63d350f995068ee1cad6d32df11a49bd24ba97
    public exponent: 10001
key2.pemのdecode結果
Algo RSA
Format X.509
 ASN1 Dump
RSA Public Key [ee:3d:fe:e7:ab:cd:14:a7:f4:1a:29:d3:d6:a8:8b:05:35:95:c2:23]
            modulus: c6acb8df486e6671d4a5564803e1c3214a8e274de0ac0043ec28c8589f377c7e8d308bc3e302850384344ba7988885620a418e6ad955578284fc04f289f126b38a01816251cef9a14fd4c249d96b69087fa91b2e1adbdc80cb96ff0ccb6129d8f6737da850c451f2ed3f6cb61c36891dc924d0ab28f26adf0ed357ce848d02ffe00912714ccf6372c1f41080e86747a0303eb5cdf6ce912f1144fd4f55743c796875a14fdff8f8b662150c56be58b09239771dc44d969079c4ad8fd993bc630b7855d2e02e8be16824dcd5ab3813231c1731110a8bd028d7a1dfab892e75294557bafc71aeaf5e48db0267a6db63d350f995068ee1cad6d32df11a49bd24ba97
    public exponent: 53cb7

RSAの公開鍵で、modulusが同じです。これはcommon modulus attackでいけるはずです。
plaintextにフラグが入っているでしょう。

Common Modulus Attack

RSAの暗号化と復号

あまり詳しくないのでちょっとだけ書いてみます。Cは暗号文、Mは平文の意味です。

暗号化

pとqは大きな素数で、n=p \cdot q
\phi(n)=(p-1)(q-1)
public exponent eはここから選ぶ： e \in \{1,2,....,\phi(n)-1\}

C \equiv M^e\ mod\ n

復号

この式が成立するdを求める：d \cdot e \equiv mod\ \phi(n)

dを使って復号する。

M \equiv C^d\ mod\ n

RSAの安全性の根拠
\phi(n) がわからないと復号に使う秘密鍵 d を計算できない。
\phi(n) を計算するために n の素因数分解をしないといけないが、n はとても大きい数字（2048 bitsとか）なので素因数分解が難しすぎる。n を公開しても \phi(n) が計算できない。

数式

今回のケースはこんな感じ。知らないのはMだけです。

\begin{cases} C_1 \equiv M^{e_1}\ mod\ n \\ C_2 \equiv M^{e_2}\ mod\ n \end{cases}

ベズーの等式(Bezout's identity)でこれがわかります。

ae_1+be_2 = gcd(e_1, e_2)

また、gcd(e_1, e_2)=1なので、こう書けます。

ae_1+be_2 = gcd(e_1, e_2)=1

aとbは拡張ユークリッドの互除法（Extended Euclidean algorithm）で計算できます。

整理すると平文Mはこれで導出できます。

C_1^{a}C_2^{b}= (M^{e_1})^{a}(M^{e_2})^{b}=M^{e_1a+e_2b} \equiv M\ mod\ n

数学が苦手なので間違ったらごめんなさい。

コード

solution.py
from base64 import b64decode
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
from gmpy2 import gcdext

# 公開鍵を読み込む
k1 = RSA.importKey(open("key1.pem").read())
k2 = RSA.importKey(open("key2.pem").read())

# 　暗号文を読み込む
c1 = bytes_to_long(b64decode(open("message1").read()))
c2 = bytes_to_long(b64decode(open("message2").read()))

# 公開鍵から情報を抽出
n1, n2 = k1.n, k2.n
e1, e2 = k1.e, k2.e

assert n1 == n2
assert e1 != e2

# common modulus attack
n = n1
gcd, a, b = gcdext(e1, e2)
m = pow(c1, a, n) * pow(c2, b, n) % n

print(long_to_bytes(m))

実行するとフラグが出てきました。

b'HTB{C0mmxxxxxxxxxxxxxxb4D}'

Discussion