SECCON online CTF2017-WriteUp-

自分が解いたの

Team:Bluemermaidで参加して100pts入れました。

Simon and Speck Block Ciphers[100pts]

Simon and Speck Block Ciphers

https://eprint.iacr.org/2013/404.pdf
Simon_96_64, ECB, key="SECCON{xxxx}", plain=0x6d564d37426e6e71, cipher=0xbb5d12ba422834b5 

ggrと実装されたコードがみつかる

test.pyに書いてあるのを参考にしてkeyxxxxを総当たり

from speck import SpeckCipher
from simon import SimonCipher
from itertools import product
import sys


def solve():
    keyf = "SECCON{"
    s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz_'
    plaintxt =0x6d564d37426e6e71
    ciphertxt=0xbb5d12ba422834b5
    block_size=64
    key_size=96
    # blute force
    pws = product(s, repeat=4)
    for pw in pws:
        key = keyf+''.join(pw)+"}"
        print key
        c = SimonCipher(int(key.encode('hex'),16),key_size, block_size, 'ECB')
        if c.encrypt(plaintxt) == ciphertxt:
            print key
            sys.exit()

solve()

SECCON{6Pz0}

チームの人が解いたけど自分も解いたの

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次元になってる。key1はkey2の逆である。そして鍵の長さが14文字、さらにわかってる平文が7文字

暗号文の7文字がSECCON{になるような鍵を見つけてしまえばあとはその逆をくっつければおしまいかなとフィーリングで組む

import sys

def _l(idx, s):
    return s[idx:] + s[:idx]

def e(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

def main():
    c ="POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9"
    s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz_{}"
    head="SECCON{"
    key="AAAAAAAAAAAAAA"
    for i in range(len(head)):
        j=1
        while(e(c,key,key[::-1])[i] != head[i]):
            key=key[:i]+s[j]+key[i+1:]
            j+=1
    bac = key[::-1]
    key = key[:7]+bac[:7]
    print e(c,key,key[::-1])
main()

SECCON{Welc0me_to_SECCON_CTF_2017}

Ps and Qs

Ps and Qs

Decrypt it.
update: we fixed the flag, please try to submit again.

psqs1-0dd2921c9fbdb738e51639801f64164dd144d0771011a1dc3d55da6fbcb0fa02.zip (pass:seccon2017)

展開すると二つの公開鍵と暗号文が出てくる。そしてggrとBoston Key Partyに似たような問題があったっぽい

ということで適当にコードを組むとpとqが復号できる

#!python
import gmpy
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA

E=65537

def get_key_n(filename):
    pubkey = RSA.importKey(open(filename).read())
    assert pubkey.e == E
    return gmpy.mpz(pubkey.n)

def load_keys():
    keys = []
    keys.append(get_key_n('pub1.pub'))
    keys.append(get_key_n('pub2.pub'))
    return keys

def factor_keys(keys):
    factors = [None]*len(keys)
    for i, k1 in enumerate(keys):
        for k, k2 in enumerate(keys):
            if factors[i] and factors[k]:
                continue
            common = gmpy.gcd(k1,k2)
            if common > 1:
                factors[i] = (common,k1/common)
                factors[k] = (common,k2/common)

    return factors

def form_priv_keys(pubkeys, factors):
    privkeys=[]
    for n, (p,q) in zip(pubkeys, factors):
        assert p*q == n
        phi = (p-1) * (q-1)
        d = gmpy.invert(E,phi)
        key = RSA.construct((long(n), long(E), long(d),long(p), long(q)))
        privkeys.append(key)
    return privkeys

if __name__ == '__main__':
    pubkeys = load_keys()
    factors = factor_keys(pubkeys)
    privkeys = form_priv_keys(pubkeys,factors)
    print privkeys[0].p
    print privkeys[1].p
    print privkeys[0].q
    print privkeys[1].q

一応出力したがpとqが同じものを使われているときに復号できる手法(確か)である。今回はpが同じ出力だった

なのであとは秘密鍵を作ります。

from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse

p =28491351268021265385526651386538607807309659986276688343064670073891013400825164415230601338782473025742402049394830630675805725885088430112149497869242346184436501498250656252478654366186925359496427622140658107345546543257713919694302487049954761322101254188444207888427451979864984635323522901072705782835553010119115529960199616134426518090324707055730908978182075401070044276443957929403874512391698813306139691898167549756758189122432373003019206630611377319244160315312008084214038516008026804548925876733577843139353697227433645926176332422253880445694249081777712571005410284034477749618735562684652311433029
q1=29756285957217824990174038832451778402099067307810847648290595785058431646976908322304147959112427140159792888914923236200167490011201811250432742134955076467161512399957077313964630071141735504154569672191460389697633956438555548934921730829103416692214221897316036431719854727062122070711252924237859981650839082127947619246716311728507350521260831762017879211408671194883521699107885995227760052190268561172377288494647487407578357795768368061699760835305355222313206649747987980403480055830409354654506995090037005532480704961830183236922268938782515705140754745094708066416483123932606937140087049605071066540057
q2=26805289271497618288824957409840900087921737364247062017954653095350605996401170903273670545713193946727301443779225655009185442124301303618802469003843741958147267024677868793805932449329658920982848063484688700333399204106733149230481527426171610107889681875992617647315539302047794058437648908212645971211176786957517731494723729889354075435764097658602139780143569337636457452893386690938522392609685556109416233805154149262663416050814684714850213550063231110089787491540944945712297710844735930977234970373826519042470046867137186054740672979017101637673890382547484646195101031561338945685511605286410830656477

E=65537

N = p*q1
d=inverse(E,(p-1)*(q1-1))

key = RSA.construct(map(long, (N,E,d)))
print "q1"
print key.exportKey()

N = p*q2
d=inverse(E,(p-1)*(q2-1))

key = RSA.construct(map(long, (N,E,d)))
print "q2"
print key.exportKey()

でそれを適当にq1.keyとq2.keyに保存、opensslコマンドで復号しました。q1.keyで復号完了

$ openssl rsautl -decrypt -inkey q1.key -in cipher
SECCON{1234567890ABCDEF}

感想

SHA1のやつは過去に衝突させたことあるので、ひたすら伸ばすだけだったけどチームの人がsubmitしたのでそれ以上にやるきがしなかった

解けるんだけどこれ解けても強い人も解けるしあんまり貢献してない感じがある。つらい