SECCON
Vigenere3d (Crypto, 100pt)
Vigenere3d
----- Vigenere3d.py
import sys
def l(idx, s):
return s[idx:] + s[:idx]
def main(p, k1, k2):
s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz{}"
t = [[_l((i+j) % len(s), s) for j in range(len(s))] for i in range(len(s))]
i1 = 0
i2 = 0
c = ""
for a in p:
c += t[s.find(a)][s.find(k1[i1])][s.find(k2[i2])]
i1 = (i1 + 1) % len(k1)
i2 = (i2 + 1) % len(k2)
return c
print main(sys.argv[1], sys.argv[2], sys.argv[2][::-1])$ python Vigenere3d.py SECCON{**************************} **************
POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9
3次元のビジュネル暗号。
SECCON2016のビジュネル暗号が懐かしい。
とりあえず、配列tのindexと値をひも付けて出力してみる。
t[f0][k0][k13] = P
t[f1][k1][k12] = O
t[f2][k2][k11] = R
t[f3][k3][k10] = 4
t[f4][k4][k9] = d
t[f5][k5][k8] = n
t[f6][k6][k7] = y
t[f7][k7][k6] = T
t[f8][k8][k5] = L
t[f9][k9][k4] = H
t[f10][k10][k3] = B
t[f11][k11][k2] = f
t[f12][k12][k1] = w
t[f13][k13][k0] = b
t[f14][k0][k13] = x
t[f15][k1][k12] = A
t[f16][k2][k11] = A
t[f17][k3][k10] = Z
t[f18][k4][k9] = h
t[f19][k5][k8] = e
t[f20][k6][k7] = }
t[f21][k7][k6] = }
t[f22][k8][k5] = o
t[f23][k9][k4] = c
t[f24][k10][k3] = Z
t[f25][k11][k2] = R
t[f26][k12][k1] = 3
t[f27][k13][k0] = C
t[f28][k0][k13] = x
t[f29][k1][k12] = c
t[f30][k2][k11] = f
t[f31][k3][k10] = t
t[f32][k4][k9] = w
t[f33][k5][k8] = 9
t[f0][k0][k13] = P
t[f14][k0][k13] = x
を見るとf0とf14のasciiコードの差はPとxの差になる。
またk2はk1の逆順になっているため、
t[x][k0][k13] = t[x][k13][k0]となる。
f0f1f2f3f4f5f6 = SECCON{
がわかっているため、f7 - f33が計算できる。(f33 = }として確認。)
z3を使って解いた
from z3 import *
def _l(idx, s):
return s[idx:] + s[:idx]
k1 = [BitVec('k%d' % i, 8) for i in range(len('**************'))]
k2 = k1[::-1]
flag_str = 'SECCON{**************************}'
flag = [BitVec('f%d' % i, 8) for i in range(len('SECCON{**************************}'))]
enc = 'POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9'
s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz_{}"
t = [[_l((i+j) % len(s), s) for j in range(len(s))] for i in range(len(s))]
i1 = 0
i2 = 0
resolve_table = []
for i in range(len(flag)):
res = [flag_str[i], flag[i], k1[i1], k2[i2], enc[i]]
resolve_table.append(res)
i1 = (i1 + 1) % len(k1)
i2 = (i2 + 1) % len(k2)
solver = Solver()
for l1 in resolve_table:
if l1[0] != '*':
solver.add(l1[1] == s.find(l1[0]))
else:
for l2 in resolve_table:
if l1[2] == l2[2] or l1[2] == l2[3]:
solver.add(l1[1] == (l2[1] + s.find(l1[4]) - s.find(l2[4])) % len(s))
break
m = solver.model()
print('flag: %s' % ''.join([s[m.evaluate(c).as_long()] for c in flag]))
flag: SECCON{Welc0me_to_SECCON_CTF_2017}
SHA-1 is dead (Crypto, 100pt)
SHA-1 is dead
http://sha1.pwn.seccon.jp/
Upload two files satisfy following conditions:file1 != file2
SHA1(file1) == SHA1(file2)
SHA256(file1) <> SHA256(file2)
2017KiB < sizeof(file1) < 2018KiB
2017KiB < sizeof(file2) < 2018KiB
- 1KiB = 1024 bytes
73spicaさんのブログを参考にさせていただいた。
sha1は先頭320バイトの部分で衝突が起きていて、
それ以降が同じ値ならsha1は衝突し続けるとのこと。
Googleの衝突pdf(shattered-1.pdf, shattered-2.pdf)を取得し、
それぞれの後ろに同じ値を2017KiB < size < 2018KiBとなるように書き込んで
送信すれば終了。
Ps and Qs (Crypto, 200pt)
Ps and Qs
Decrypt it.
update: we fixed the flag, please try to submit again.
添付のzipファイルを解凍したところ以下のファイルが入っている
pub1.pub
pub2.pub
cipher
opensslを使って公開鍵からn,eを取得
openssl rsa -text -modulus -pubin < pub1.pub
↓
Exponent: 65537 (0x10001)
Modulus=CFCFBBEEA7DF143A8AC208B1AA1D2F86545AC4CB588C94A3FB1C14AD91A4F0B936157C5A4B869C18A8B864F4726BF8FCDC020CB41042BAC96784AB7D03F9374947EFB0BC3D665831974340159FFC3DB7C8E74B6390FDA6EEC30B81C6FF624E8D3F5B17BFB7A5C7FFD8ECF4E6518B393ABEFDDD0FAEBA4308746BA63F8106B59D7E058943A00131A7D4E538C464B270577647EDBC478CC1CE9585EFE877305B3A7C2E7C44DB5475EDDADC345A2C90A946771CAC0A454CDBCB461F2840E7613C83E9CECC94037FA09BB9DAA3F180562C01DF0BE6C51F0C06E8F0E2D6E1A5E50D0A28C3881140770A9F45934146B7F359B939CE23F0FA507A6F4E454571430952003C20F1D97A67140B6E5FCBFB3B376E4E24969AEB1D489CFC72AF4F15A4788A1AA97C89756D1D4D94AA47E7CD3A81AECB92448CC92C77D2EF576AA0DBC1350862ACCDDADDBCE80357F0CD5B854DD0F8C4627FE4B718B24ECFE11ED24C3BE22F00643BBED4EE5E345AF176E5B76D23A2F80E0EC6F34E5718C62A70FE5570C28B807B44F22EADEBD9B5FF906F6A85BE88C0C8F6E5F880A51F17F84DB1C2EEFEA8AF34040444CED1A37DF0E4F5F72CC3F50B7E427C8C2D8B6186EAD762F0C444B3CA3A0103ED12A93BCE9CAE7479A229EBBC0A648EAA6F97E5051A66EB09EBD7348E92F75F125EBDC367E2A7D1DA7759D41FAE2E2635BF4B7A7F91BECAB3AC7D05BD
pub2.pubについても同様にn,eを取得する
またタイトルの「Ps and Qs」をググると
Mining Your Ps and Qs
という論文がヒットする。どうやら2つの公開鍵の中で共通の素因数を持っている場合
(n1 = p1q1, n2 = p2q2 としてp1 == p2 など)
ユークリッドの互除法で簡単に因数が求められてしまうから気をつけて、
とい内容っぽい。
その方針で計算すると秘密鍵が求められる
rsatool.pyを使用してpemファイルを作成
import gmpy
e1 = 65537
n1 = 0xCFCFBBEEA7DF143A8AC208B1AA1D2F86545AC4CB588C94A3FB1C14AD91A4F0B936157C5A4B869C18A8B864F4726BF8FCDC020CB41042BAC96784AB7D03F9374947EFB0BC3D665831974340159FFC3DB7C8E74B6390FDA6EEC30B81C6FF624E8D3F5B17BFB7A5C7FFD8ECF4E6518B393ABEFDDD0FAEBA4308746BA63F8106B59D7E058943A00131A7D4E538C464B270577647EDBC478CC1CE9585EFE877305B3A7C2E7C44DB5475EDDADC345A2C90A946771CAC0A454CDBCB461F2840E7613C83E9CECC94037FA09BB9DAA3F180562C01DF0BE6C51F0C06E8F0E2D6E1A5E50D0A28C3881140770A9F45934146B7F359B939CE23F0FA507A6F4E454571430952003C20F1D97A67140B6E5FCBFB3B376E4E24969AEB1D489CFC72AF4F15A4788A1AA97C89756D1D4D94AA47E7CD3A81AECB92448CC92C77D2EF576AA0DBC1350862ACCDDADDBCE80357F0CD5B854DD0F8C4627FE4B718B24ECFE11ED24C3BE22F00643BBED4EE5E345AF176E5B76D23A2F80E0EC6F34E5718C62A70FE5570C28B807B44F22EADEBD9B5FF906F6A85BE88C0C8F6E5F880A51F17F84DB1C2EEFEA8AF34040444CED1A37DF0E4F5F72CC3F50B7E427C8C2D8B6186EAD762F0C444B3CA3A0103ED12A93BCE9CAE7479A229EBBC0A648EAA6F97E5051A66EB09EBD7348E92F75F125EBDC367E2A7D1DA7759D41FAE2E2635BF4B7A7F91BECAB3AC7D05BD
e2 = 65537
n2 = 0xBB33CC7FCC8ECAF3BF9ED95C583792E1EC6B80EE875EC2064DBCF07595C8344923BF536524D4E0A75574C7798C73B197DD2B1B42054B1E49CB45FBF04E6F114CF8A365C3DF3645524F778268038A3FA26802E9D1EDBFBB5EDFB5A0C375370D7F10F57DABBD4F771DAD3632F01B9BCE10489966EE882DAB17A33B786AA5F73165A54051300B1DF9280392A3EDE9D3FC9C4D8A6A06351F6EF3598E8DE2B39D3B19AF64A1716CD15826C3F24CB13DEB722C3A03EF1D2BE2D0A5A6E210FF5D018367BE3BF99EA26BA006E5164A4DD55AABCD449DE5CE1864825DC160E50D509EB0E6FE723EF182681EDDB94084B83EC9E2E943E87CB87509AB0FD9B1CA22C1CEAFF39FCACF6729FC0E0578670D87D7F0F9CCBE09CB3E12CEB895572A9979D10BFDBFAFA260568D8DB184BE12B3E3193E07729CE3C1D9CD8283ED6983A06388036A0A70294F23392944778280E7DE9F60163A8150E30FF4A4EA02792CBE8305BAA2E99AFE51E17DAFC56BE0D384147BCD38E9D12934EC712622217773A4B3851A9B0C6C7C3E01F6111A1E1A557F4E2AE4A247CE9B75CCCCB1819825F3054AA1C055BD3E2340093AE2EF1D0FA5A176825EFDF79507027F5104080009142F0D43E2F10CFAD220813BBB9014D4F4325EDAC538FB5E82B753E2AD3B24607D7380AA64FCB98B59EA8B5A736B809383248CECE0B17255EA559E90127F778AF6D7E8A66DAD91
p1 = gmpy.gcd(n1,n2)
assert(n1 % p1 == 0)
q1 = n1 / p1
p2 = p1
assert(n2 % p2 == 0)
q2 = n2 / p2
phi1 = (p1-1) * (q1-1)
d1 = int(gmpy.invert(e1, phi1))
assert((e1*d1) % phi1 == 1)
import os
os.system('python rsatool.py -f PEM -o key.pem -n %d -d %d' % (n1,d1))
作成した秘密鍵を使用して復号を行う
openssl rsautl -decrypt -inkey key.pem -in cipher
無事、flagを取得できた。
SECCON{1234567890ABCDEF}