神のミソ汁のセカイ

大学生活のことや技術的な備忘録を残してます

EasyCTF 2015: Cave Johnson Write-up

問題

EasyCTF 2015: Cave Johnson

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題文のヒントにあるように単純なVigenere暗号である。Vigenere暗号はメッセージが長いと鍵が繰り返し使われるので、鍵長ごとにメッセージをグループ化すると単純なシーザー暗号になる。そこで頻度分析を行って鍵を推定して復号化すればよい。 以下が解読プログラム。暗号文はcave-johnson.txtに保存してある。

#! /usr/bin/env python3
# encoding: utf-8

def grouping(cipertext, keylength):
    group = [None] * keylength
    for i in range(len(cipertext)):
        if group[i % keylength] == None:
            group[i % keylength] = []
        group[i % keylength].append(cipertext[i])
    return group

def frequency_analysis(text):
    count_list = [0] * 26
    for i in range(len(text)):
        count_list[ord(text[i]) - ord('a')] += 1
    s = float(sum(count_list))
    occurences = [float(n)/s for n in count_list]
    return occurences

def frequency(group, i):
    alphabet_freq = [0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074]
    plain = [chr((ord(n) - ord('a') - i) % 26 + ord('a')) for n in group]
    occurences = frequency_analysis(plain)
    f = 0.0
    for j in range(26):
        f += pow(alphabet_freq[j] - occurences[j], 2) / alphabet_freq[j] # Chi-squared value
    return f

def get_key_letter(group):
    freq = [frequency(group, i) for i in range(26)]
    return freq.index(min(freq))

def decrypt(ciphertext, key):
    plaintext = ""
    index = 0
    for c in ciphertext:
        if c != '_':
            c = ord(c) - ord('a')
            k = ord(key[index % len(key)]) - ord('a')
            p = (c - k) % 26
            plaintext += chr(p + ord('a'))
            index += 1
        else:
            plaintext += '_'
    return plaintext

with open('cave-johnson.txt','r') as f:
    ciphertext = f.read().strip()

for keylength in range(1,31):
    group = grouping(ciphertext, keylength)
    key = ''
    for i in range(keylength):
        key += chr(get_key_letter(group[i]) + ord('a'))
    print('length : '+str(keylength)+' key : ' + key)
    plaintext = decrypt(ciphertext, key)
    print('plaintext : ' + plaintext)

このプログラムを実行すると鍵長を1から30として鍵を探索し、復号した結果を出力する。

実行結果は

$ ./solver.py
---省略---
length : 12 key : iammoroncore
plaintext : helloandagainwelcometotheaperturesciencecomputeraidedenrichmentcenterehopeyourbriefdetentionintherelaxationvaulthasbeenapleasantoneyourspecimenhasbeenprocessedandwearenowreadytobeginthetestproperbeforewestarthoweverkeepinmindthatalthoughfunandlearningaretheprimarygoalsofallenrichmentcenteractivitiesseriousinjuriesmayoccurforyourownsafetyandthesafetyofotherspleaserefrainfromturningintheflagwrappedinthestandardformatthis_is_aperture_and_we_talk_too_much
---省略---

出力結果を目視で確認すると鍵長12で意味のある英文が出現している。よってflagはthis_is_aperture_and_we_talk_too_much

感想

Vigenere暗号関連の問題(0CTF 2015 Quals CTF: oldcrypto)を最近解いていたので簡単だった。頻度分析での分布の評価をカイ二乗値を使うように修正したのでより正確に鍵推定ができるようになったと思う。

今週末のGoogle CTF 2017頑張るぞ

EasyCTF 2015: Matrices Write-up

問題

EasyCTF 2015: Matrices

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題文を見るとoutput2を復元すればいいようだ。 Zobがオリジナルの暗号化アルゴリズム(matrix.java)に共通の鍵を使ってmessage1を暗号化したという。プログラムを見るとoutput1に結果を出力しているので、message1output1を使って鍵を復元すればoutput2を復元できる。

matrix.javaを見るとブロック暗号のCBCモードに似た暗号化を行っている。 CBCモードについては暗号利用モード - Wikipediaを参照。

メッセージは長さ16のブロックに分割されている。また暗号化アルゴリズムは行列の積であり、鍵は$16 \times 16$の正方行列である。メッセージを$m=m_1||m_2||\dots||m_n$、暗号文を$c=c_1||c_2||\dots||c_n$、鍵を $\text{K}$ とするとmatrix.javaで行われている暗号化は

$$c_i^\text{T} = \text{K}(c_{i-1} \oplus m_i)^\text{T}\quad(i=1,2,\dots)\ ただしc_0 = \bf{0}$$

である。$m_i$と$c_i$を16個集めると逆行列の計算によって鍵を手に入れることができる。

$$\text{C} = (c_1^\text{T}, c_2^\text{T}, \dots c_{16}^\text{T})$$

$$\text{M} = ((c_0 \oplus m_1)^\text{T}, (c_1 \oplus m_2)^\text{T}, \dots, (c_{15} \oplus m_{16})^\text{T})$$

とすると

$$\text{C} = \text{KM}\\ \text{K} = \text{C}\text{M}^{-1}$$

鍵$\text{K}$が手に入ったら鍵の逆行列$\text{K}^{-1}$を求めてoutput2を復号すればよい。復号アルゴリズムCBCモードと同じ。

これらを踏まえてmessage1output1から暗号化鍵を取り出してoutput2を復号するプログラムを作った。

#! /usr/bin/env python3
# -*- coding : utf-8 -*-

import numpy as np
import gmpy2 as gp2

def inv_mod(matrix, modulo):
    A = np.copy(matrix)
    n = A.shape[0]
    inv_A = np.identity(n, dtype=int)
    for i in range(n):
        tmp = int(gp2.invert(int(A[i][i]), modulo))
        for j in range(n):
            A[i][j] = (A[i][j] * tmp) % modulo
            inv_A[i][j] = (inv_A[i][j] * tmp) % modulo

        for j in range(n):
            if i != j:
                tmp = A[j][i]
                for k in range(n):
                    A[j][k] = (A[j][k] - A[i][k] * tmp) % modulo
                    inv_A[j][k] = (inv_A[j][k] - inv_A[i][k] * tmp) % modulo

    return np.copy(inv_A)

def get_key(message, ciphertext, n):
    M = [message[i:i+n] for i in range(0, n*n, n)]
    C = [list(ciphertext[i:i+n]) for i in range(0, n*n, n)]
    iv = [(b'\0'*n + ciphertext)[i:i+n] for i in range(0, n*n, n)]
    for i in range(n):
        M[i] = list(map(lambda a,b : a ^ b, M[i], iv[i]))

    M = np.array(M).transpose()
    C = np.array(C).transpose()
    M_inv = inv_mod(M, 251)
    key = C.dot(M_inv) % 251
    return key

def decrypt(ciphertext, key):
    n = len(key)
    inv_key = inv_mod(key, 251)
    C = [list(ciphertext[i:i+n]) for i in range(0, len(ciphertext), n)]
    iv = [(b'\0'*n + ciphertext)[i:i+n] for i in range(0, len(ciphertext), n)]
    message = b''
    for i in range(len(C)):
        c = np.array(C[i]).transpose()
        message += bytes(map(lambda a,b : a^b, inv_key.dot(c) % 251, iv[i]))
    return message

N = 16
with open('message1', 'rb') as f:
    message1 = f.read()

with open('output1', 'rb') as f:
    output1 = f.read()

with open('output2', 'rb') as f:
    output2 = f.read()

key = get_key(message1, output1, N)
message = decrypt(output2, key)
print(message)

inv_mod関数内の逆行列を求めるアルゴリズム行列式の値の求め方、逆行列の作り方の C 言語プログラム - Blue Sky Labを参考にした。ただし今回は実数の範囲でなく $GF(251)$ であるので通常の割り算の代わりに逆元の計算を行っている。

プログラムの実行結果は

$ ./solver.py
b'the flag: easyctf{4b5+r4C+10N}\xc6\xc0'

よってflagはeasyctf{4b5+r4C+10N}

感想

numpyを初めて使ったけど行列の計算が簡単にできて便利そう。数値計算系のアルゴリズムはそらで書けるようにしたい。 また、線形代数の知識の抜けを実感したので復習したい。

(githubに載ってたWrite-upではSageを使っていたけどSageって有限体とか環を扱えるのね)

Backdoor CTF 2015: Rsanne Write-up

問題

Backdoor CTF 2015: Rsanne

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題ファイルは暗号文ファイルflag.encと公開鍵id_rsa.pubflag.encはRSALOT同様暗号文をbase64エンコードしたものみたいだ。

公開鍵をopensslで覗いてみた。

$ openssl rsa -pubin -in id_rsa.pub -text -noout
Modulus (4484 bit):
    0f:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:fd:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    f8:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:01
Exponent: 65537 (0x10001)

exponentは初期値だけど法が不思議な値になってる。ということは特徴的な素数を使っているに違いない。 RSAの法について調べていると次のスライドを発見した。

RSA暗号運用でやってはいけない n のこと #ssmjp

スライドによると「メルセンヌ素数(2p-1の形をした素数)を元に鍵を作るとメルセンヌ素数は49個しかないので簡単に因数分解できてしまう」ということなのでメルセンヌ素数について調べて因数分解するプログラムを書いた。

# -*- coding : utf-8 -*-

import math

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDFFFFFFFFFFFFFFFFFFF80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

Mersenne_prime = list(map( lambda p: pow(2,p)-1, [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667]))

for p in Mersenne_prime:
    q = math.gcd(n, p)
    if q != 1:
        print (p)
        print ('')
        print (n // q)
        print ('-'*40)

実行結果

$ python3 factorization.py
1475979915214180235084898622737381736312066145333169775147771216478570297878078949377407337049389289382748507531496480477281264838760259191814463365330269540496961201113430156902396093989090226259326935025281409614983499388222831448598601834318536230923772641390209490231836446899608210795482963763094236630945410832793769905399982457186322944729636418890623372171723742105636440368218459649632948538696905872650486914434637457507280441823676813517852099348660847172579408422316678097670224011990280170474894487426924742108823536808485072502240519452587542875349976558572670229633962575212637477897785501552646522609988869914013540483809865681250419497686697771007

446087557183758429571151706402101809886208632412859901111991219963404685792820473369112545269003989026153245931124316702395758705693679364790903497461147071065254193353938124978226307947312410798874869040070279328428810311754844108094878252494866760969586998128982645877596028979171536962503068429617331702184750324583009171832104916050157628886606372145501702225925125224076829605427173573964812995250569412480720738476855293681666712844831190877620606786663862190240118570736831901886479225810414714078935386562497968178729127629594924411960961386713946279899275006954917139758796061223803393537381034666494402951052059047968693255388647930440925104186817009640171764133172418132836351
----------------------------------------
446087557183758429571151706402101809886208632412859901111991219963404685792820473369112545269003989026153245931124316702395758705693679364790903497461147071065254193353938124978226307947312410798874869040070279328428810311754844108094878252494866760969586998128982645877596028979171536962503068429617331702184750324583009171832104916050157628886606372145501702225925125224076829605427173573964812995250569412480720738476855293681666712844831190877620606786663862190240118570736831901886479225810414714078935386562497968178729127629594924411960961386713946279899275006954917139758796061223803393537381034666494402951052059047968693255388647930440925104186817009640171764133172418132836351

1475979915214180235084898622737381736312066145333169775147771216478570297878078949377407337049389289382748507531496480477281264838760259191814463365330269540496961201113430156902396093989090226259326935025281409614983499388222831448598601834318536230923772641390209490231836446899608210795482963763094236630945410832793769905399982457186322944729636418890623372171723742105636440368218459649632948538696905872650486914434637457507280441823676813517852099348660847172579408422316678097670224011990280170474894487426924742108823536808485072502240519452587542875349976558572670229633962575212637477897785501552646522609988869914013540483809865681250419497686697771007
----------------------------------------

この鍵の法は2つのメルセンヌ素数の積だった。あとはrsatoolを使って秘密鍵を生成して復号すればいい。復号にはRSALOTで使ったスクリプトを利用した。

$ python3 decrypt_RSA.py
b'the_flag_is_e4972e14a8bd2430bd52d41bad8060368c2fa4f56ef6deddf1b377773a761b1a'

よってflagはe4972e14a8bd2430bd52d41bad8060368c2fa4f56ef6deddf1b377773a761b1a

感想

RSA関係は情報が多いし自分が学んでいるのでぱっと解きたい

backdoor CTF 2015: RSALOT Write-up

問題

backdoor CTF 2015: RSALOT

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題ファイルを解凍すると100個のRSA公開鍵(1.pem100.pem)とflag.encが入っていた。 flag.encの中身はflagを暗号化してbase64エンコードしたものみたいだ。これをデコードしてRSA暗号で復号すればflagが手に入りそう。

opensslで公開鍵の中身を覗くとprivate exponentはどの公開鍵も65537だが法は全て異なっていた。 もし、この中に共通の素数を持つ法があればgcdを計算することで法を因数分解できる。 法同士のgcdを計算するために、まずは次のシェルスクリプトを使って法をファイルに1つずつ取り出した。

#!/bin/sh
for var in `ls -1 *.pem`
do
    openssl rsa -pubin -in "$var" -noout -modulus | sed "s/Modulus=//g" > "modulus/$var.mod.txt"
done

法を抜きだしたら全ての法の組み合わせでgcdを計算してgcd≠1であるファイルを探し出す。 今度はpythonでプログラムを書いた。

# -*- coding : UTF-8 -*-

import math
import binascii

def getint(filename):
    f = open(filename, 'r')
    hex_str = f.read().strip()
    return int(hex_str, 16)

for i in range(1, 100):
    for j in range(i+1, 101):
        n1 = getint('modulus/'+str(i)+'.pem.mod.txt')
        n2 = getint('modulus/'+str(j)+'.pem.mod.txt')
        if math.gcd(n1, n2) != 1:
            print ('i=',i,'j=', j)
            common_prime = math.gcd(n1, n2)
            q1 = n1 // common_prime
            q2 = n2 // common_prime
            print ('common_prime', common_prime)
            print ('q1: ', q1)
print ('q2: ', q2)

実行結果

$ python3 search_common_prime.py
i= 64 j= 87
common_prime 168736462866079204789584058199620418225526506348478399447895958829038354002285480486576728303147995561507709511105490546002439968559726489519296139857978907240880718150991015966920369123795034196767754935707681686046233424449917085120027639055362329862072939086970892956139024391556483288415208981014264336691
q1:  137852341825115687630372545540234125575043643297743715914372468140743017665122928684176567678186288631724569119078697598260381091322877334920545216266418987980787824645288016924652387350842372904949656504253960440751217710040954075691996893620788950284865727480192510130305432030965910622333944701850333681207
q2:  139208418683860744636489594107518498051692876942105482068436575406002091300025595750940476658875774324613311765708231971440632450100860632595797604226237831396754383891914573698131769762436941837224713009721577421233571830899874638297795728204831707647487557389464078420524002550428515370686466308350190419191

64.pem87.pemに共通の素数がある事がわかった。これらを元に秘密鍵を作って復号すればいい。 秘密鍵の作成にはrsatoolを使った。

組み合わせが2種類あるので秘密鍵を2つ作って復号する。それぞれprivate64.keyとprivate87.keyという名前で保存しておいた。 復号プログラムはhttps://docs.launchkey.com/developer/encryption/python/python-encryption.htmlのコードを利用した。

# -*- coding : utf-8 -*-

def decrypt_RSA(private_key_loc, package):
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import PKCS1_OAEP
    from base64 import b64decode
    key = open(private_key_loc, "r").read()
    rsakey = RSA.importKey(key)
    rsakey = PKCS1_OAEP.new(rsakey)
    decrypted = rsakey.decrypt(b64decode(package))
    return decrypted

package = open('flag.enc', "r").read()
message = decrypt_RSA('private87.key', package)

print (message)

実行結果

$ python3 depython3 decrypt_RSA.py
b'the_flag_is_b767b9d1fe02eb1825de32c6dacf4c2ef78c738ab0c498013347f4ea1e95e8fa'

よってflagはb767b9d1fe02eb1825de32c6dacf4c2ef78c738ab0c498013347f4ea1e95e8fa(秘密鍵はprivate87.key)

感想

RSAを勉強した知識が生きた。

ASIS Quals CTF 2015: Simple Algorithm Write-up

問題

ASIS Quals CTF 2015: Simple Algorithm

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題ファイルを解凍すると暗号文enc.txtと暗号化アルゴリズムが書かれたsimple_algorithm.pyが入っている。simple_algorithm.pyを読み解くと次のような変換を行っていることがわかった。

flag(ASCII文字列)を16進数に変換
↓
最初の1byteを除いて10進数に変換
↓
10進数表現で頭から2文字ずつ取り出しFAN関数に通す
↓
変換結果を文字列化して結合

FAN関数は入力した10進数を3進数ぽいものに変換して10進数表現を返している。FANへの入力は0〜99なので試しに全部変換してみると1〜4桁の10進数が返ってきた。これだと暗号文の区切りがわからないので、予め変換テーブルを用意して全ての区切りパターンを再帰を使って探索してみた。

#!/usr/bin/python
# -*- coding: utf-8 -*-

def FAN(n, m):
    i = 0
    z = []
    s = 0
    st = ''
    while n > 0:
        if n % 2 != 0:
            z.append(2 - (n % 4))
        else:
            z.append(0)
        n = (n - z[i])/2
        i = i + 1
    z = z[::-1]
    l = len(z)
    for i in range(0, l):
        p = z[i] * m ** (l - 1 - i)
        s += p
    return s

def encrypt():
    i = 0
    r = ''
    while i < len(str(iflag)):
        d = str(iflag)[i:i+2]
        nf = FAN(int(d), 3)
        print (d+':'+str(nf))
        r += str(nf)
        i += 2
    print r

def search(str, result):
    if len(str) == 0:
        return True

    for i in reversed(range(1,min(4, len(str))+1)):
        if table.has_key(int(str[:i])):
            result.append(table.get(int(str[:i])))
            if search(str[i:], result):
                return True

            result.pop()

    return False

encrypted_text = '2712733801194381163880124319146586498182192151917719248224681364019142438188097307292437016388011943193619457377217328473027324319178428'

table = {}
for i in range(100):
    table[FAN(i, 3)] = str(i).zfill(2)

result = []
search(encrypted_text, result)
result[-1] = str(int(result[-1]))
print 'A'+('%x' % int(''.join(result))).decode('hex')

このプログラムの実行結果は次の通り。

$ ./answer.py
ASIS{a9ab115c488a311896dac4e8bc20a6d7}

よってflagはASIS{a9ab115c488a311896dac4e8bc20a6d7}

補足

  • 38行目でforを逆順で回しているが、0から探しても別の結果が出るものの、復号してもflagにはならなかった。
  • FANへの入力は基本2桁だが、最後尾は1桁になる可能性がある。今回はそれに当たったので56行目で0埋めした数字から0を外して1桁に戻している。
  • ASISの問題なのでflagの頭はAだということで57行目で頭にAを追加している。

感想

はじめ、FANの逆関数を作ろうとして時間を無駄に割いてしまった。暗号文のパターンがわかっているときは変換テーブルを作って全探索するのがいいのかな。

再帰プログラムは久しぶりに書いたけどこういう時は便利だなぁ。

ASIS Cyber Security Contest 2015: simple Write-up

問題

ASIS Cyber Security Contest 2015: simple

チャレンジ中のリストはこちCrypto Challenges List(2015)

解法

問題ファイルはencryted_06bb0f5887231f735be0e2a21d68e79f。fileコマンドで調べるとxzファイルだったので解凍する。 中身は次のようなテキストファイルだった。

110d00_000a0701_1a00_00120812_171b1a171500111a150011_001b_071006001901_0900_787100_00091b00_00130805120f0908_0900_5143594353445602000105_140b0a000b_00021500151e141514_1b00_0a15000b0b0c0b02_1000131117_000f05_0a030000031b0908_001b_101f1c001a1d14_435340424400

16進数で表されたASCII文字列みたいだけど00とかが含まれている。英文が暗号化されているみたいだ。 _は暗号化されてないので単語間の区切りだと思われる。

「simple Cryptography」で調べると平文と鍵をXORする暗号化方式がヒットした。さらに調べると次のサイトにたどり着いた。

Pwn2Win CTF 2016 Simple Cryptography (Crypto 60) Writeup

別のCryptoの問題(しかも解いた問題より新しい)のWrite-upだが、暗号文が類似している。このサイトによると、_区切りの暗号文の各単語ごとに鍵(8bit)があり、その鍵を対応する単語に1文字ずつXORして暗号化する暗号方式のようだ。 この暗号方式だと踏んで鍵を探すプログラムを書いた。

# search_key.py
# -*- coding: utf-8 -*-
m = "110d00_000a0701_1a00_00120812_171b1a171500111a150011_001b_071006001901_0900_787100_00091b00_00130805120f0908_0900_5143594353445602000105_140b0a000b_00021500151e141514_1b00_0a15000b0b0c0b02_1000131117_000f05_0a030000031b0908_001b_101f1c001a1d14_435340424400"
m = m.split('_')
index = 0

for i in range(255):
    r = ''
    for j in range(0, len(m[index]), 2):
        d = int(m[index][j:j+2], 16)
        r += chr((d ^ i) % 256)

    print (str(i), ':', r)

このプログラムを実行すると意味のある英単語が出現した。方針は正しいみたい。 1単語ずつ復号し、実行結果を見ながら意味のある単語に復号される数字を記録していく。得られた鍵は

[101, 102, 115, 65, 116, 98, 117, 102, 53, 104, 102, 102, 48, 131, 112, 111, 101, 114, 97, 108, 98, 115, 33]

鍵がわかったので復号するプログラムを書いた。

# decrypt.py
# -*- coding: utf-8 -*-
m = "110d00_000a0701_1a00_00120812_171b1a171500111a150011_001b_071006001901_0900_787100_00091b00_00130805120f0908_0900_5143594353445602000105_140b0a000b_00021500151e141514_1b00_0a15000b0b0c0b02_1000131117_000f05_0a030000031b0908_001b_101f1c001a1d14_435340424400"
m = m.split('_')
key = [101, 102, 115, 97, 116, 98, 117, 102, 53, 104, 102, 102, 48, 131, 112, 111, 101, 114, 97, 108, 98, 115, 33]

r = ''
for i in range(len(m)):
    for j in range(0, len(m[i]), 2):
        d = int(m[i][j:j+2], 16)
        r += chr((d ^ key[i]) % 256)
    r += ' '

print ('decrypt message :', r)

実行結果

$ python3 decrypt.py
decrypt message : the flag is ASIS concatenate by result of MD5 hash function of asisctf2015 prepended to open
ning brace and followed by closing brace!

メッセージの通りasisctf2015MD5ハッシュ値を計算し、

$ md5 -s 'asisctf2015'
MD5 ("asisctf2015") = 7fc5bed10f3d903f1e69190a16562fcb

よってflagはASIS{7fc5bed10f3d903f1e69190a16562fcb}

まとめ

あのサイトにたどり着けたことが解答につながった。 ググってわかったがメッセージになんらかの鍵をXORする方法はよく用いられているみたいだ。

CTFよりも来週の暗号理論の期末テストの勉強しないと…

0CTF 2015 Quals CTF: oldcrypto Write-up

はじめに

研究室の先輩に勧められてCTFを始めることに。 そこで、練習のためにCrypto Challenges List(2015)をeasyから順に解いていき、Write-upをブログに残すことにした。

問題

0CTF 2015 Quals CTF: oldcrypto

チャレンジ中のリストはこちCrypto Challenges List(2015)

解法

問題のzipファイルを解凍すると次の2つのファイルが入っている。

  • ciphertext - 暗号文が書かれたファイル
  • oldcrypto.py - 暗号化関数、復号関数が定義されたpythonスクリプト

特徴的なのはoldcrypto.py内に変換テーブルがあること。いろいろ調べた結果ヴィジュネル暗号であることがわかった。

ヴィジュネル暗号 -Wikipedia-

Wikipediaによると多表式の換字式暗号でカシスキーテストなる方法で解読できるみたい。 簡単に説明するとメッセージが長いとき、ヴィジュネル暗号は鍵を繰り返し適用するので、似た文字列が繰り返し出現する。そこで繰り返しのスパンから鍵長を推測する。すると鍵のi番目で暗号化された文字の集合はただのシーザー暗号になる。あとは頻度分析をして暗号鍵を1文字ずつ推測する。

以上に基いて作ったコードがこれ。コードはpython3で書いた。 本問では暗号化関数内で次のようにテーブルの添字にi ** 7を加えて暗号文をシフトしていたので、このシフトを除いてから頻度分析を行う。

def encrypt(plaintext, key):
    ciphertext = ""
    for i in xrange(len(plaintext)):
        p = ord(plaintext[i]) - ord('a')
        k = ord(key[i % len(key)]) - ord('a')
        c = (tr[k][p] + i**7) % 26
        ciphertext += chr(c + ord('a'))
    return ciphertext

今回はカシスキーテストを実装できなかったので鍵長を1から30までに設定して全探索してる。

#! /usr/bin/env python3
# -*- encoding: utf-8 -*-

tr = [
        [12, 9, 16, 3, 13, 15, 22, 17, 20, 1, 10, 24, 0, 4, 19, 5, 2, 7, 23, 14, 8, 21, 6, 18, 11, 25],
        [19, 16, 7, 5, 22, 3, 15, 2, 8, 14, 18, 17, 25, 13, 9, 6, 1, 11, 10, 0, 21, 20, 4, 23, 24, 12],
        [0, 7, 9, 14, 19, 8, 12, 1, 5, 2, 24, 11, 6, 21, 3, 15, 18, 25, 16, 4, 20, 13, 23, 22, 10, 17],
        [4, 15, 22, 13, 0, 10, 21, 14, 11, 19, 5, 8, 17, 3, 7, 1, 20, 12, 24, 9, 16, 6, 2, 25, 18, 23],
        [10, 23, 15, 25, 8, 16, 20, 21, 4, 11, 0, 9, 13, 12, 17, 2, 5, 14, 22, 24, 6, 7, 18, 1, 19, 3],
        [8, 10, 23, 7, 12, 6, 5, 3, 0, 18, 1, 14, 4, 22, 11, 21, 19, 20, 9, 16, 17, 15, 13, 2, 25, 24],
        [13, 19, 11, 15, 16, 22, 18, 23, 12, 24, 20, 2, 8, 0, 25, 3, 4, 21, 6, 1, 10, 17, 5, 7, 9, 14],
        [14, 2, 1, 24, 11, 23, 16, 20, 13, 10, 9, 4, 22, 8, 0, 25, 6, 19, 21, 17, 7, 18, 12, 5, 3, 15],
        [7, 4, 10, 21, 1, 20, 13, 0, 15, 12, 2, 18, 9, 6, 23, 8, 22, 24, 11, 25, 5, 3, 16, 14, 17, 19],
        [20, 1, 5, 16, 10, 2, 9, 19, 21, 6, 4, 25, 18, 24, 22, 23, 3, 17, 12, 7, 0, 8, 14, 15, 13, 11],
        [6, 13, 3, 2, 5, 4, 0, 9, 23, 7, 25, 21, 20, 1, 24, 18, 17, 16, 15, 19, 12, 11, 22, 8, 14, 10],
        [17, 6, 13, 23, 18, 19, 1, 16, 24, 25, 12, 15, 10, 2, 20, 11, 7, 0, 4, 5, 14, 22, 21, 3, 8, 9],
        [3, 22, 8, 0, 7, 21, 11, 4, 2, 16, 19, 6, 15, 25, 14, 12, 9, 23, 18, 10, 24, 5, 1, 17, 20, 13],
        [18, 3, 2, 1, 17, 12, 10, 24, 16, 9, 6, 19, 5, 23, 21, 22, 8, 4, 0, 11, 25, 14, 15, 13, 7, 20],
        [16, 24, 21, 12, 15, 14, 23, 18, 25, 20, 11, 10, 3, 17, 5, 4, 0, 13, 7, 22, 9, 2, 19, 6, 1, 8],
        [5, 17, 4, 19, 2, 0, 25, 22, 18, 23, 13, 16, 14, 10, 12, 20, 11, 1, 8, 3, 15, 24, 7, 9, 21, 6],
        [11, 8, 20, 22, 14, 7, 6, 5, 1, 21, 16, 0, 12, 19, 4, 17, 10, 15, 25, 13, 2, 9, 3, 24, 23, 18],
        [9, 21, 14, 17, 24, 5, 7, 6, 10, 0, 8, 23, 19, 15, 2, 13, 16, 3, 20, 12, 18, 1, 25, 11, 4, 22],
        [22, 5, 6, 20, 23, 1, 2, 25, 9, 8, 17, 13, 16, 11, 18, 24, 12, 10, 14, 21, 3, 19, 0, 4, 15, 7],
        [25, 18, 19, 8, 20, 17, 14, 12, 3, 13, 15, 22, 7, 9, 6, 10, 24, 5, 1, 2, 4, 23, 11, 21, 16, 0],
        [24, 20, 17, 9, 25, 13, 8, 11, 6, 3, 22, 7, 23, 5, 15, 14, 21, 2, 19, 18, 1, 16, 10, 12, 0, 4],
        [15, 25, 18, 10, 6, 9, 4, 13, 17, 5, 3, 20, 21, 7, 16, 0, 14, 8, 2, 23, 11, 12, 24, 19, 22, 1],
        [23, 14, 24, 18, 4, 25, 17, 7, 19, 22, 21, 12, 11, 20, 1, 16, 15, 6, 3, 8, 13, 10, 9, 0, 2, 5],
        [21, 11, 25, 6, 9, 18, 3, 10, 14, 4, 7, 1, 24, 16, 8, 19, 13, 22, 5, 15, 23, 0, 17, 20, 12, 2],
        [2, 12, 0, 4, 3, 11, 24, 15, 22, 17, 14, 5, 1, 18, 10, 7, 23, 9, 13, 20, 19, 25, 8, 16, 6, 21],
        [1, 0, 12, 11, 21, 24, 19, 8, 7, 15, 23, 3, 2, 14, 13, 9, 25, 18, 17, 6, 22, 4, 20, 10, 5, 16]
    ]

def erase_shift(ciphertext):
    returntext = ""
    for i in range(len(ciphertext)):
        c = ord(ciphertext[i]) - ord('a')
        p = (c - i**7) % 26
        returntext += chr(p + ord('a'))
    return returntext

def grouping(cipertext, keylength):
    group = [None] * keylength
    for i in range(len(cipertext)):
        if group[i % keylength] == None:
            group[i % keylength] = []
        group[i % keylength].append(cipertext[i])
    return group

def frequency_analysis(text, padding=0):
    count_list = [0] * 26
    for i in range(len(text)):
        count_list[ord(text[i]) - ord('a')] += 1
    s = float(sum(count_list))
    occurences = [float(n)/s for n in count_list]
    return occurences

def frequency(group, i):
    alphabet_freq = [0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074]
    plain = [chr(tr[i][ord(n) - ord('a')] + ord('a')) for n in group]
    occurences = frequency_analysis(plain)
    f = 0.0
    for j in range(26):
         f += pow(alphabet_freq[j] - occurences[j],2) / alphabet_freq[j] #Chi-squared value
    return f

def get_key_letter(group):
    freq = [frequency(group, i)for i in range(26)]
    return freq.index(min(freq))

def decrypt(ciphertext, key):
    plaintext = ""
    for i in range(len(ciphertext)):
        c = ord(ciphertext[i]) - ord('a')
        k = ord(key[i % len(key)]) - ord('a')
        p = tr[k][c]
        plaintext += chr(p + ord('a'))
    return plaintext


with open('ciphertext') as f:
    ciphertext = f.read()

nciphertext = erase_shift(ciphertext)

for keylength in range(1,31):
    group = grouping(nciphertext, keylength)
    key = ''
    for i in range(keylength):
        key += chr(get_key_letter(group[i]) + ord('a'))
    print('length : '+str(keylength)+' key : ' + key)
    plaintext = decrypt(nciphertext, key)
    print('plaintext : ' + plaintext)

プログラムの実行結果を目視で確認してflagが含まれているものが正しい平文。今回は鍵長が20だった。

length : 20 key : classicalcipherisfun
plaintext : incryptanalysiskasiskiexaminationisamethodofattackingpolyalphabeticsubstitutioncipherssuchasthevigenerecipherinpolyalphabeticsubstitutioncipherswherethesubstitutionalphabetsarechosenbytheuseofakeywordthekasiskiexaminationallowsacryptanalysttodeducethelengthofthekeywordusedinthepolyalphabeticsubstitutioncipheroncethelengthofthekeywordisdiscoveredthecryptanalystlinesuptheciphertextinncolumnswherenisthelengthofthekeywordtheneachcolumncanbetreatedastheciphertextofamonoalphabeticsubstitutioncipherassucheachcolumncanbeattackedwithfrequencyanalysisthekasiskiexaminationinvolveslookingforstringsofcharactersthatarerepeatedintheciphertextthestringsshouldbethreecharacterslongormorefortheexaminationtobesuccessfulthenthedistancesbetweenconsecutiveoccurrencesofthestringsarelikelytobemultiplesofthelengthofthekeywordthusfindingmorerepeatedstringsnarrowsdownthepossiblelengthsofthekeywordsincewecantakethegreatestcommondivisorofallthedistancesthereasonthistestworksisthatifarepeatedstringoccursintheplaintextandthedistancebetweencorrespondingcharactersisamultipleofthekeywordlengththekeywordletterswilllineupinthesamewaywithbothoccurrencesofthestringthedifficultyofusingthekasiskiexaminationliesinfindingrepeatedstringsthisisaveryhardtasktoperformmanuallybutcomputerscanmakeitmucheasierhowevercareisstillrequiredsincesomerepeatedstringsmayjustbecoincidencesothatsomeoftherepeatdistancesaremisleadingthecryptanalysthastoruleoutthecoincidencestofindthecorrectlengththenofcoursethemonoalphabeticciphertextsthatresultmustbecryptanalyzedoooooooooooooooooooopsflagisthekeywithoopsprefixandbraces

よってflagは0ctf{classicalcipherisfun}

まとめ

初めて解いたけどなんとか解けた。今回は鍵長の範囲を適当に決めて解いたけど本当はカシスキーテストにあるように鍵長を推測してから解くべき。今後の課題。 CTFの練習と併せてpythonアルゴリズムの学習も進めないと… (記事が適当すぎる気がするので今後はブラッシュアップしていきたい)