0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

SECCON2017

Posted at

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}

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?