生き恥

生きるは恥だが役に立つ

SECCON2017 writeup

今回はぼっち参加だった。

とりあえず興味のあるCryptoを解いて行こうというお気持ちでスタートした。

解いたのはVigenere3dとSHA-1 is deadとPs and Qsの3問のみ。

Vigenere3d

プログラムの以下の箇所より、暗号文は平文の文字と鍵kのi番目と鍵kのlen(k)-i番目の文字によって決まることがわかる。

c += t[s.find(a)][s.find(k1[i1])][s.find(k2[i2])]

鍵kの長さが14で、わかっている平文がSECCON{の7文字あるので、ヴィジュネル方陣を固定してしまえば鍵がわかる。 (鍵kはi番目のの文字とlen(k)-i番目の文字の差が一定であればなんでもよい)

$ python Vigenere3d.py SECCON{AAAAAAAAAAAAAAAAAAAAAAAAAA} AAAAAAA_aZ2PK_
POR4dny_aZ2PK__KP2Za__aZ2PK__KP2Z9

この状態でPOR4dny_aZ2PK__KP2Za__aZ2PK__KP2Z9 → POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9になるような残りの平文を探して行く。

s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz_{}"
c1 = "TLHBfwbxAAZhe}}ocZR3Cxcftw"
c2 = "_aZ2PK__KP2Za__aZ2PK__KP2Z"
flag = ""

for i in range(len(c1)):
    num = s.find(c1[i]) - s.find(c2[i])
    if num < 0 : 
        num = len(s) + num 
    flag += s[num]
print flag

FLAGはWelc0me_to_SECCON_CTF_2017 おわり

SHA-1 is dead

以下より、SHA-1が衝突した2つのpdfを取ってくる。しかし、このままではファイルサイズが条件に合わない。
https://shattered.io/
どうやら、先頭320バイトの部分で衝突が起きていてそれ以降が同じ値ならずっと衝突し続けるらしい。
巷で話題のGoogleのSHA-1衝突やってみた | 73spica's Blog
ddコマンドでそれっぽいサイズのファイルを作って、Googleのpdfをバイナリエディタでコピペして終わり。
FLAGはSECCON{SHA-1_1995-2017?}

Ps and Qs

公開鍵が二つと暗号文が一つが渡される。 この時点で、「二つのnが共通の因数を持っているときは簡単に素因数分解できるよね!」問題であるとわかる。 http://www2.nict.go.jp/csri/plan/H26-symposium/files/3-2.pdf
以下のコマンドで公開鍵の中身を表示。

openssl rsa -text -noout -pubin -in pub1.pub 

適当に:を取り除いて、intに直して復号する。

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

def gcd(x, y):
    r = modlog(x, y)
    while r != 0:
        x = y 
        y = r 
        r = modlog(x, y)
    return y

def modlog(x, y): 
    r = x % y 
    return r

def main():
    u1 = 847796795638781450678718708664542960446354226336422534142899480441478781747168340722544245493739168125415291376063352480076469305992008517388366298914970810765149321160596112226917023146371080685458239747986992197343482255681414590678694753885521068656675164266739274608505094927725285868801825144058835115051061857233824816176186349372737400492228548130718029270482313906040935333159681273527671359469173939861889228505791626525994180917670701909816457560622922219797109618405842358250940062127841301193206255543580550667149741357342408703680375118252445296600962244008043713708516004025217199954286478272550961283413053789743740774140439284662596273452124779590753836094450154459078034659421366584354005421566290862244000178569163732971816333961711759000171156293724203334889496589376907683142167883476184246287660764821622298961378903818077158234683927321823293466245584486980446609569799420950073036635602004293246754252079757527610246223280774592566063422181158810677919909523144033543195999214800559998598003329294711989868113423468536273984117507008756542731210465222475943122324672467669623079721727526348599823126409108190030551584092950358235465140166515452377475799157617227362838246912839086733412861436353117994501342653
    u2 = 763718912475160487902804749669814117361530270298225094625871588939939773892509348006077810445741086683427253000695920011673348476297973798322806091336777405584801442639626925406721932533140226556519019440300864340670199686368307155860493615065198319490060598587202051942638792919648596288576294804549738135969737494734307362891313864027749187674251692407867312885251279302785352318725391842117065840058358065676707016006124478822206302825992616559261930620693061673348139416033418864269248381876692676529410115745518353146254670349865568255213560376368953292931958006941630719304442332912813624543600126197554727832190226632919876204677667384620275620336951964833888599634720101911051166398907898747710391394105753614253527704990658698844796442515669670816004761855554187277637871343595647487793209271354240148469085627742503649786300484610102224828274384484809539697728008552925590472129497180290668277790132130824141651399551803499770513576176720509094833332201946177880267399933460994496277590932311628302240154240967341858152145815276163397709272690500041597393678630136932574450837982593210399370333578887450410911663220219423601973078501237709613593311133945501455828164291429228495931943107997137587307522565029820756690578833
    q = gcd(u1, u2) 
    p1 = u1 / q 
    p2 = u2 / q 
    p = p1
    e = 65537
    n = p*q 
    d = inverse(e, (p-1)*(q-1))
    c = 658063702174492170630737837355589886583067761650983363941909994400817849856699417146067253546506602278075708984235030629800257348531833245813500290774620305460892522597019439353562154791548732158611776887029731801160549012269973218438385289683478390258807883040582486877315287316434659387503441900781236184660059984452592862372092943601918214678188098699869456828712213889111037574260127805370442774040527872243053566674392335408758655125255348375903482668216482987543268073626349429427137502888363903952006288982053867518114220684218204451432796538994848617443448310129521661643038060029344993848959815504667821131473020187375309009206832679656996752407442812626820517856712301473172939393077581041096102765300236211230880310865997117134702580037421149475552478616188956436553987824362086889555205262619209905351934963104086266912820024692280089431479663058370757076811911498591955722977726204374289841309901648701195859400837279037103456926577158547907968290437097309522419677174364683467262506453282619330543399466280395015485412557434129628605096528473160112582078299169455676557687825433899041475427962227421628101522052945742591131895830805488509689551017396730038834596064101206291844830276746407286995621109990490886816777237


    key = RSA.construct(map(long, (n,e,d)))
#  print  binascii.unhexlify(hex(key.decrypt(c))[2:]).decode()
    print  hex(key.decrypt(c))[2:]

if __name__=="__main__":
    main()

binascii.unhexlify(hex(key.decrypt(c))[2:]).decode()でいい感じにFLAGが表示されなかったので、hex(key.decrypt(c))[2:]で表示をみてみると、それっぽいものを見つけた。
534543434f4e7b313233343536373839304142434445467d
この部分だけ何が書いてあるのかみてみると、

>>> import binascii
>>> binascii.unhexlify("534543434f4e7b313233343536373839304142434445467d")
b'SECCON{1234567890ABCDEF}'

FLAGはSECCON{1234567890ABCDEF}

おわりに

文章力の無さは許してくだい。
サイコロ出たい...