SECCON2017

# 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を使って解いた

```py

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さんのブログ](http://73spica.tech/blog/sha1-collision/)を参考にさせていただいた。
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](https://factorable.net/weakkeys12.extended.pdf)
という論文がヒットする。どうやら2つの公開鍵の中で共通の素因数を持っている場合
(n1 = p1*q1, n2 = p2*q2 として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}