【HackTheBox Crypto Challenge】TwoForOne Writeup
前はマシーンだけでしたが、最近はhtbのチャレンジも始めました。
About This Challenge
CHALLENGE DESCRIPTION
Alice sent two times the same message to Bob.
提供されたのは2つの公開鍵と2つのciphertext。説明文から、2つのciphertextは同じplaintextから暗号化されたものだとがわかります。
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAxqy430huZnHUpVZIA+HD
IUqOJ03grABD7CjIWJ83fH6NMIvD4wKFA4Q0S6eYiIViCkGOatlVV4KE/ATyifEm
s4oBgWJRzvmhT9TCSdlraQh/qRsuGtvcgMuW/wzLYSnY9nN9qFDEUfLtP2y2HDaJ
Hckk0Kso8mrfDtNXzoSNAv/gCRJxTM9jcsH0EIDoZ0egMD61zfbOkS8RRP1PVXQ8
eWh1oU/f+Pi2YhUMVr5YsJI5dx3ETZaQecStj9mTvGMLeFXS4C6L4Wgk3NWrOBMj
HBcxEQqL0CjXod+riS51KUVXuvxxrq9eSNsCZ6bbY9NQ+ZUGjuHK1tMt8RpJvSS6
lwIDAQAB
-----END PUBLIC KEY-----⏎
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAxqy430huZnHUpVZIA+HD
IUqOJ03grABD7CjIWJ83fH6NMIvD4wKFA4Q0S6eYiIViCkGOatlVV4KE/ATyifEm
s4oBgWJRzvmhT9TCSdlraQh/qRsuGtvcgMuW/wzLYSnY9nN9qFDEUfLtP2y2HDaJ
Hckk0Kso8mrfDtNXzoSNAv/gCRJxTM9jcsH0EIDoZ0egMD61zfbOkS8RRP1PVXQ8
eWh1oU/f+Pi2YhUMVr5YsJI5dx3ETZaQecStj9mTvGMLeFXS4C6L4Wgk3NWrOBMj
HBcxEQqL0CjXod+riS51KUVXuvxxrq9eSNsCZ6bbY9NQ+ZUGjuHK1tMt8RpJvSS6
lwIDBTy3
-----END PUBLIC KEY-----
RBVdQw7Pllwb42GDYyRa6ByVOfzRrZHmxBkUPD393zxOcrNRZgfub1mqcrAgX4PAsvAOWptJSHbrHctFm6rJLzhBi/rAsKGboWqPAWYIu49Rt7Sc/5+LE2dvy5zriAKclchv9d+uUJ4/kU/vcpg2qlfTnyor6naBsZQvRze0VCMkPvqWPuE6iL6YEAjZmLWmb+bqO+unTLF4YtM1MkKTtiOEy+Bbd4LxlXIO1KSFVOoGjyLW2pVIgKzotB1/9BwJMKJV14/+MUEiP40ehH0U2zr8BeueeXp6NIZwS/9svmvmVi06Np74EbL+aeB4meaXH22fJU0eyL2FppeyvbVaYQ==
TSHSOfFBkK/sSE4vWxy00EAnZXrIsBI/Y6mGv466baOsST+qyYXHdPsI33Kr6ovucDjgDw/VvQtsAuGhthLbLVdldt9OWDhK5lbM6e0CuhKSoJntnvCz7GtZvjgPM7JDHQkAU7Pcyall9UEqL+W6ZCkiSQnK+j6QB7ynwCsW1wAmnCM68fY2HaBvd8RP2+rPgWv9grcEBkXf7ewA+sxSw7hahMaW0LYhsMYUggrcKqhofGgl+4UR5pdSiFg4YKUSgdSw1Ic/tug9vfHuLSiiuhrtP38yVzazqOZPXGxG4tQ6btc1helH0cLfw1SCdua1ejyan9l1GLXsAyGOKSFdKw==
Investigation
key1.pemとkey2.pemの値がほぼ同じなので気になります。とりあえずpemをdecodeできるオンラインツールで中身を見てみます。https://8gwifi.org/PemParserFunctions.jsp
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
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は大きな素数で、
public exponent
復号
この式が成立する
RSAの安全性の根拠
数式
今回のケースはこんな感じ。知らないのは
ベズーの等式(Bezout's identity)でこれがわかります。
また、
整理すると平文
数学が苦手なので間違ったらごめんなさい。
コード
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