BKPCTFのRSA暗号問題を解く
2016年3月4日に開催されたBoston Key Party CTFにチームm1z0r3として少しだけ参加した．大会からかなり日が経ってしまって今更感があるが，今回はbob's hatというRSA暗号の問題のWrite-upを書こうと思う．
http://bostonkey.party/
bob's hat - Crypto 4
問題概要
Task:
bob’s hat — 4 : crypto : Alice and Bob are close together, likely because they have a lot of things in common.This is why Alice asked him a small *q*uestion, about something cooler than a wiener.
File: bkpctf_crypto_bobhat_task.zip
zipファイルを解凍すると，以下のファイルが得られる．
- almost_almost_almost_almost_there.pub - 公開鍵
- almost_almost_almost_almost_there.encrypted - 公開鍵で暗号化された暗号文
- almost_almost_almost_almost_there.zip - パスワード付きzipファイル
暗号文を解読し，得られた平文がzipファイルのパスワードとなる．このzipファイルを解凍するとまた同じような構成のファイルが抽出され，暗号を繰り返し解いていくと最後にフラグが得られる．いつぞやに見かけたエクストリームCTFと似たような形式である．
Stage 1
まず，公開鍵の情報を確認する．
# openssl rsa -text -modulus -pubin < almost_almost_almost_almost_there.pub
Public-Key: (1024 bit)
Modulus:
00:86:e9:96:01:3e:77:c4:16:99:00:0e:09:41:d4:
80:c0:46:b2:f7:1a:4f:95:b3:50:ac:1a:4d:42:63:
72:92:3d:8a:45:61:d9:6f:bf:b0:24:05:95:90:72:
01:ad:32:25:cf:6e:de:d7:de:02:d9:1c:38:6f:fa:
c2:80:b7:2d:0f:95:ca:e7:1f:42:eb:e0:d3:ed:ae:
ac:e7:ce:a3:19:5f:a3:2c:1c:60:80:d9:0e:f8:53:
d0:6d:d4:57:2c:92:b9:f8:31:0b:bc:0c:63:5a:5e:
26:95:25:11:75:10:30:a6:59:08:16:55:4e:76:30:
31:bc:bb:31:e3:f1:19:c6:5f
Exponent: 65537 (0x10001)
Modulus=86E996013E77C41699000E0941D480C046B2F71A4F95B350AC1A4D426372923D8A4561D96FBFB0240595907201AD3225CF6EDED7DE02D91C386FFAC280B72D0F95CAE71F42EBE0D3EDAEACE7CEA3195FA32C1C6080D90EF853D06DD4572C92B9F8310BBC0C635A5E26952511751030A6590816554E763031BCBB31E3F119C65F
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCG6ZYBPnfEFpkADglB1IDARrL3
Gk+Vs1CsGk1CY3KSPYpFYdlvv7AkBZWQcgGtMiXPbt7X3gLZHDhv+sKAty0Plcrn
H0Lr4NPtrqznzqMZX6MsHGCA2Q74U9Bt1Fcskrn4MQu8DGNaXiaVJRF1EDCmWQgW
VU52MDG8uzHj8RnGXwIDAQAB
-----END PUBLIC KEY-----鍵長は十分な長さがあり，ModulusやExponentの値も特に怪しい点はない．このようなケースの場合，各種素因数分解アルゴリズムを用いてModulusの素因数分解を試みると良い．
今回はFermat法によって素因数分解に成功した．
参考
Fermat法は素数同士の積からなる合成数において、二つの素数の差が小さい場合に有効なアルゴリズムである。 具体的には、合成数nの平方根周辺のある値をxとしたとき、(x-k)*(x+k) == nとなるkを小さいものから求める。
Solver
実行結果
p= 9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987246769 q= 9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987245583 pass: XtCgoEKksjKFWlqOSxqsEhK/+tsr1k5c
pとqの値が非常に近いことが分かる．
なお，今回rsatool.pyを使って秘密鍵を生成して復号する手法を取ろうとしたが，なぜかopensslコマンドでうまく復号できず，結局復号の処理をpythonで実装した．他にも同様の現象に陥った人もいたようなので，この原因について暗号のプロに教えを請いたいところ．
Stage 2
公開鍵の情報を確認．
# openssl rsa -text -modulus -pubin < almost_almost_almost_there.pub
Public-Key: (1024 bit)
Modulus:
00:ab:e6:33:ce:c2:e7:ec:10:a8:51:92:79:05:a6:
57:df:4e:10:41:60:23:c0:c3:4f:c6:4d:64:bd:8b:
82:57:b7:bf:20:7a:dd:04:7b:0a:df:21:c5:25:b0:
52:06:8c:70:29:5c:74:6c:3b:1b:e1:43:6f:39:ed:
8b:f7:a8:13:e4:b8:45:ce:0c:a8:9c:a8:28:b4:57:
63:d4:6b:18:98:c7:a2:fa:5f:8f:e7:84:28:ca:b6:
cd:f7:0e:f8:71:db:97:1b:32:32:84:1a:1c:e2:45:
9c:e6:50:a1:54:36:2f:80:cf:b6:41:63:c3:ca:63:
ad:72:bc:fb:db:f0:15:4f:f7
Exponent: 65537 (0x10001)
Modulus=ABE633CEC2E7EC10A851927905A657DF4E10416023C0C34FC64D64BD8B8257B7BF207ADD047B0ADF21C525B052068C70295C746C3B1BE1436F39ED8BF7A813E4B845CE0CA89CA828B45763D46B1898C7A2FA5F8FE78428CAB6CDF70EF871DB971B3232841A1CE2459CE650A154362F80CFB64163C3CA63AD72BCFBDBF0154FF7
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCr5jPOwufsEKhRknkFplffThBB
YCPAw0/GTWS9i4JXt78get0EewrfIcUlsFIGjHApXHRsOxvhQ2857Yv3qBPkuEXO
DKicqCi0V2PUaxiYx6L6X4/nhCjKts33Dvhx25cbMjKEGhziRZzmUKFUNi+Az7ZB
Y8PKY61yvPvb8BVP9wIDAQABこちらも鍵長，Modulus・Exponentの値ともに怪しいところはない．
ところが，今回のModulusとStage 1のModulusのGCDをとったところ，1ではない公約数が存在することが判明した．要は，鍵生成において「素数の使い回し」をしていたことになる．これによりModulusの素因数分解が可能となる．
Solver
実行結果
p= 9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987246769 q= 12401828372292379853813876769631673931562555174641979554254424458038243058638417065284301266881242433017828663818811606556559256084249679274024474025282343 pass: rlSpJ6HbP+cZXaOuSPOe4pgfevGnXtLt
Stage 3
公開鍵の情報を確認する．
# openssl rsa -text -modulus -pubin < almost_almost_there.pub
Public-Key: (1040 bit)
Modulus:
00:ba:d2:0c:f9:7e:d5:04:2d:f6:96:ce:4d:f3:e5:
a6:78:cf:4f:b3:69:3d:3d:f1:2d:fe:9f:d3:fd:8c:
c8:aa:b8:b9:55:33:e4:14:e3:fc:0c:37:7f:4e:e5:
48:27:11:8b:1d:30:56:1a:3c:74:1b:ea:7c:76:89:
97:89:b5:17:43:e0:76:09:2d:f9:eb:05:dc:97:eb:
15:05:ce:9e:b1:2b:5a:b9:e1:0a:bf:56:f9:20:a5:
8e:7e:00:ec:f0:59:77:e8:72:83:4d:d8:58:4c:f4:
ac:87:cb:7d:c5:01:59:bd:96:2c:75:cb:ef:b6:c6:
ac:3a:31:a7:4e:7d:8f:1e:4c:10:d5
Exponent: 65537 (0x10001)
Modulus=BAD20CF97ED5042DF696CE4DF3E5A678CF4FB3693D3DF12DFE9FD3FD8CC8AAB8B95533E414E3FC0C377F4EE54827118B1D30561A3C741BEA7C76899789B51743E076092DF9EB05DC97EB1505CE9EB12B5AB9E10ABF56F920A58E7E00ECF05977E872834DD8584CF4AC87CB7DC50159BD962C75CBEFB6C6AC3A31A74E7D8F1E4C10D5
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGhMA0GCSqGSIb3DQEBAQUAA4GPADCBiwKBgwC60gz5ftUELfaWzk3z5aZ4z0+z
aT098S3+n9P9jMiquLlVM+QU4/wMN39O5UgnEYsdMFYaPHQb6nx2iZeJtRdD4HYJ
LfnrBdyX6xUFzp6xK1q54Qq/VvkgpY5+AOzwWXfocoNN2FhM9KyHy33FAVm9lix1
y++2xqw6MadOfY8eTBDVAgMBAAE=
-----END PUBLIC KEY-----こちらも鍵長，Modulus・Exponentの値ともに怪しいところはない．
各種素因数分解アルゴリズムを適用したところ，片方の素数の値が非常に小さいことが判明し，Modulusを小さい素数から順に除算していくことにより素因数分解に成功した．
Solver
実行結果
p= 54311 q= 158304142767773473275973624083670689370769915077762416888835511454118432478825486829242855992134819928313346652550326171670356302948444602468194484069516892927291240140200374848857608566129161693687407393820501709299228594296583862100570595789385365606706350802643746830710894411204232176703046334374939501731 pass: hQdK+dKleMJqth/dofWyFaiWp3PW7jil
Stage 4
これが最後の問題．公開鍵の情報を確認する．
# openssl rsa -text -modulus -pubin < almost_there.pub
Public-Key: (1024 bit)
Modulus:
00:9c:2f:65:05:89:91:20:90:6e:5a:fb:d7:55:c9:
2f:ec:42:9f:ba:19:44:66:f0:6a:ae:48:4f:a3:3c:
ab:a7:20:20:5e:94:ce:9b:f5:aa:52:72:24:91:6d:
18:52:ae:07:91:5f:bc:6a:3a:52:04:58:57:e0:a1:
22:4c:72:a3:60:c0:1c:0c:ef:38:8f:16:93:a7:46:
d5:af:bf:31:8c:0a:bf:02:76:61:ac:ab:54:e0:29:
0d:fa:21:c3:61:6a:49:82:10:e2:57:81:21:d7:c2:
38:77:42:93:31:d4:28:d7:56:b9:57:eb:41:ec:ab:
1e:aa:d8:70:18:c6:ea:34:45
Exponent:
46:6a:16:9e:8c:14:ac:89:f3:9b:5b:03:57:ef:fc:
3e:21:39:f9:b1:9e:28:c1:e2:99:f1:8b:54:95:2a:
07:a9:32:ba:5c:a9:f4:b9:3b:3e:aa:5a:12:c4:85:
69:81:ee:1a:31:a5:b4:7a:00:68:ff:08:1f:a3:c8:
c2:c5:46:fe:aa:36:19:fd:6e:c7:dd:71:c9:a2:e7:
5f:13:01:ec:93:5f:7a:5b:74:4a:73:df:34:d2:1c:
47:59:2e:14:90:74:a3:cc:ef:74:9e:ce:47:5e:3b:
6b:0c:8e:ec:ac:7c:55:29:0f:f1:48:e9:a2:9d:b8:
48:0c:fe:2a:57:80:12:75
Modulus=9C2F6505899120906E5AFBD755C92FEC429FBA194466F06AAE484FA33CABA720205E94CE9BF5AA527224916D1852AE07915FBC6A3A52045857E0A1224C72A360C01C0CEF388F1693A746D5AFBF318C0ABF027661ACAB54E0290DFA21C3616A498210E2578121D7C23877429331D428D756B957EB41ECAB1EAAD87018C6EA3445
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKBgQCcL2UFiZEgkG5a+9dVyS/s
Qp+6GURm8GquSE+jPKunICBelM6b9apSciSRbRhSrgeRX7xqOlIEWFfgoSJMcqNg
wBwM7ziPFpOnRtWvvzGMCr8CdmGsq1TgKQ36IcNhakmCEOJXgSHXwjh3QpMx1CjX
VrlX60Hsqx6q2HAYxuo0RQKBgEZqFp6MFKyJ85tbA1fv/D4hOfmxnijB4pnxi1SV
KgepMrpcqfS5Oz6qWhLEhWmB7hoxpbR6AGj/CB+jyMLFRv6qNhn9bsfdccmi518T
AeyTX3pbdEpz3zTSHEdZLhSQdKPM73SezkdeO2sMjuysfFUpD/FI6aKduEgM/ipX
gBJ1
-----END PUBLIC KEY-----これは明らかにExponentの値があやしい．通常は65537などの値が多用されるが，今回は値が大きすぎる．このような場合，Wiener's Attackが成立する可能性が高い．Exponentの値が大きいと，相対的に秘密鍵dが小さくなり，公開鍵からdを復元することができる．素数をp, q，秘密鍵をd，Modulusの値をNとしたとき，Wiener's Attackの成立条件は以下のとおりである．
Wiener's Attackの詳細なアルゴリズムは以下の記事によくまとまっている．
Exponentの値を見た瞬間の弊チームslackの様子（途中バイナリアンが混じっている）．
Solver
実行結果
p= 10843221374140991753173625949764386011485161421520044246309105053489500519257941272796681417497061734054081478280518835582353321569961722963922828311576983 q= 10114792273660656874618568712406420344176220457790563178092222929337786916374923318745284718351487926620784106195715878875311958793629905453919697155685507 pass: /3aAP5dF2zmrPh9K6A4AqMLsIiYDk2C2
最後のzipファイルを解凍すると，FLAGという名前のファイルが抽出される．
# cat FLAG
BKPCTF{Its_not_you,_its_rsa_(that_is_broken)}というわけで，フラグはBKPCTF{Its_not_you,_its_rsa_(that_is_broken)}
問題の考察
改めて，問題文を振り返ってみる．
Alice and Bob are close together, likely because they have a lot of things in common.This is why Alice asked him a small *q*uestion, about something cooler than a wiener.
これを分解・分析してみると．
- "Alice and Bob are close together,": pとqの値が近い（Stage 1）
- "likely because they have a lot of things in common.": 素数の使い回し（Stage 2）
- "This is why Alice asked him a small *q*uestion,": 小さな素数q（Stage 3）
- "about something cooler than a wiener": Wiener's Attack（Stage 4）
このように，問題文が解答の大きなヒントになっていたということが分かる．
