SHA2017 CTF Writeup

この大会は2017/8/5 19:00(JST)~2017/8/7 7:00(JST)に開催されました。
今回もチームで参戦。結果は1800点で462チーム中26位でした。
自分で解けた問題をWriteupとして書いておきます。

Stack Overflow (Crypto 100)

添付のPythonコードを見ると、カウンタの値が固定。CTRモードの場合、ナンス+カウンタを暗号鍵で暗号化し、平文とXORを取るが、この問題ではナンス+カウンタが固定。つまり、暗号化したタイミングでは16バイトのブロックごとに同じ値になる。
16バイトの不明なXOR鍵で暗号化されているので、PDFのファイルフォーマットと照らし合わせながら、鍵を突き止め、復号する。

with open('flag.pdf.enc', 'rb') as f:
    data = f.read()

PDF_0_6 = '%PDF-1.'
PDF_12_15 = '\x0a%%E'
PDF_11 = ' '
PDF_07_10 = 'obj\x0a'

key_0_6 = []
for i in range(len(PDF_0_6)):
    code = ord(PDF_0_6[i]) ^ ord(data[i])
    key_0_6.append(code)

key_12_15 = []
for i in range(len(PDF_12_15)):
    code = ord(PDF_12_15[i]) ^ ord(data[i-7])
    key_12_15.append(code)

key_11 = []
for i in range(len(PDF_11)):
    code = ord(PDF_11[i]) ^ ord(data[i+11])
    key_11.append(code)

key_07_10 = []
for i in range(len(PDF_07_10)):
    code = ord(PDF_07_10[i]) ^ ord(data[i+55])
    key_07_10.append(code)

key = []
for i in range(len(key_0_6)):
    key.append(key_0_6[i])
for i in range(len(key_07_10)):
    key.append(key_07_10[i])
for i in range(len(key_11)):
    key.append(key_11[i])
for i in range(len(key_12_15)):
    key.append(key_12_15[i])

flag = ''
for i in range(len(data)):
    code = ord(data[i]) ^ key[i%len(key)]
    flag += chr(code)

with open('flag.pdf', 'wb') as f:
    f.write(flag)

f:id:satou-y:20170816215137p:plain

FLAG{15AD69452103C5DF1CF61E9D98893492}

bugs_bunny ctf 2k17 Writeup

この大会は2017/7/30 4:00(JST)~2017/7/31 4:00(JST)に開催されました。
今回もチームで参戦。結果は2921点で420チーム中12位でした。
自分で解けた問題をWriteupとして書いておきます。

Not found (Misc 1)

IRCのページからログインしてみる。

[04:19] -ChanServ- [#bugsbunnyctf] Bugs_Bunny{Th1s_1s_0ur_fl4g_f0rm4t}
Bugs_Bunny{Th1s_1s_0ur_fl4g_f0rm4t}

Locked PDF (Misc 40)

pdfcrackでパスワードを解析する。
辞書ファイルは https://wiki.skullsecurity.org/index.php?title=Passwords にあるものを使う。

$ pdfcrack -f Patricia.pdf -w dict/rockyou.txt 

PDF version 1.7
Security Handler: Standard
V: 4
R: 4
P: -516
Length: 128
Encrypted Metadata: False
FileID: 104c940ca5734c71b2e5fa3b26414f5e
U: 857e6a5a82ab5bc8fc9f9d4dfe5ba381684523c72e38fdcf6ec068ae127dc499
O: 7337f340e3f15670a5a5bc1f8a217a0714538ebf23a1a4a15206a4c0c0adff51
Average Speed: 34524.2 w/s. Current Word: 'belky'
Average Speed: 34157.8 w/s. Current Word: 'puba23'
found user-password: 'g00skie'

見つかったパスワード g00skie でPDFを開くと、薄い字だがフラグが見つかった。

Bugs_Bunny{Pdf_Cr4Ck1nG_1s_Ea5y}

Crypto-15 (Crypto 15)

シーザー暗号と推定し、http://www.geocachingtoolbox.com/index.php?lang=en&page=caesarCipherでフラグ部分を復号する。ROT1で復号できた。

Bugs_Bunny{C35aR_3NC0D3_4R3_N0T_S3CuR3_AT_4LL}

Crypto-20 (Crypto 20)

Brainf*ck言語。オンラインツール https://sange.fi/esoteric/brainfuck/impl/interp/i.html で実行すると、フラグが表示された。

Bugs_Bunny{Br41N_Fu**}

Scy way (Crypto 45)

タイトルからスキュタレー暗号を推測。http://www.dcode.fr/scytale-cipherブルートフォース
ターン数が2のときに、ISHOULDLEARNMORECIPHERとなり、英文として読める。

Bugs_Bunny{ISHOULDLEARNMORECIPHER}

Crypto-50 (Crypto 50)

かなり長いBase64文字列データ。Base64デコードを繰り返せば良さそう。

with open('enc.txt', 'r') as f:
    data = f.read()

for i in range(50):
    print 'Round %d' % (i+1)
    data = data.decode('base64')
    print data

36回デコードすると、フラグを得ることができた。

Bugs_Bunny{N0T_H4Rd_4T_4ll}

Baby RSA (Crypto 55)

nをfactordbで素因数分解する。

n = 2165121523231 * 9456131321351327

enc.txtの中身は複数行の数値。それぞれ復号した後、ASCIIコードとして文字に置き換える。

n = 20473673450356553867543177537
e = 17
p = 2165121523231
q = 9456131321351327

a = (p - 1) * (q - 1)

with open('enc.txt', 'r') as f:
    c_list = f.readlines()

flag = ''
for c_str in c_list:
    c = int(c_str.strip())

    x = 0
    while True:
        if (a * x + 1) % e == 0:
            d = (a * x + 1) / e
            break
        x = x + 1

    m = pow(c, d, n)
    flag += chr(m)

print flag
Bugs_Bunny{Baby_RSA_Its_Cool_Lik3_school_haHAha}

RSA2 (Crypto 80)

eが非常に大きいため、Wiener's attackで復号する。

from fractions import Fraction

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    gcd, a, b = egcd(e, phi)
    d = a
    pt = pow(c, d, n)
    return hex(pt)[2:-1].decode('hex')

def continued_fractions(n,e):
    cf = [0]
    while e != 0:
        cf.append(int(n/e))
        N = n
        n = e
        e = N%e
    return cf

def calcKD(cf):
    kd = list()
    for i in range(1,len(cf)+1):
        tmp = Fraction(0)
        for j in cf[1:i][::-1]:
            tmp = 1/(tmp+j)
        kd.append((tmp.numerator,tmp.denominator))
    return kd

def int_sqrt(n):
    def f(prev):
        while True:
            m = (prev + n/prev)/2
            if m >= prev:
                return prev
            prev = m
    return f(n)

def calcPQ(a,b):
    if a*a < 4*b or a < 0:
        return None
    c = int_sqrt(a*a-4*b)
    p = (a + c) /2
    q = (a - c) /2
    if p + q == a and p * q == b:
        return (p,q)
    else:
        return None

def wiener(n,e):
    kd = calcKD(continued_fractions(n,e))
    for (k,d) in kd:
        if k == 0:
            continue
        if (e*d-1) % k != 0:
            continue
        phin = (e*d-1) / k
        if phin >= n:
            continue
        ans = calcPQ(n-phin+1,n)
        if ans is None:
            continue
        return (ans[0],ans[1])

c = 0x217c8bf9b45601267624c3b1ba89ae93d04c8fae32dc15496262f36f48d06c0dc9e178a77b77a33708dcbe1fcd55ea9eb636fe5684c2f0f08df3389f47b36a128636671eba300491c829ed1e252b1bb4dbb3b93bc46d98a10bb5d55347752052ab45e143fd46799be1d06ac3ff7e8b1eb181dfbba8dfac3910202fd0b9a25befe
e = 266524484526673326121255015126836087453426858655909092116029065652649301962338744664679734617977550306567819672969837450223062478394149960243362563995235387971047857994699247277712682103161537347874310994510059329875060868679654080020041070975648626636209785889112656335054840517934593236597457100751820027783
n = 412460203584740978970185080155274765823237615982150661072746604041385717906706098256415230390148737678989448404730885157667896599397615737297545930957425615121654272472589331747646564634264520011009284080299605233265170506809736069720838542498970453928922703911186788239628906189362646418960560442406497717567

p, q = wiener(n, e)

flag = decrypt(p, q, e, c)
print flag
Bugs_Bunny{Baby_Its_Cool_Lik3_school_haHAha}

Nothing here (Web 5)

ソースのコメントにこう書いてある。

QnVnc19CdW5ueXs1MjljNDI5YWJkZTIxNzFkMGEyNTU4NDQ3MmFmODIxN30K

Base64デコードする。

$ echo QnVnc19CdW5ueXs1MjljNDI5YWJkZTIxNzFkMGEyNTU4NDQ3MmFmODIxN30K | base64 -d
Bugs_Bunny{529c429abde2171d0a25584472af8217}
Bugs_Bunny{529c429abde2171d0a25584472af8217}

Web100 (Web 100)

HTMLソースはスクリプトのみで、以下の通り。

<script type="text/javascript">
var generate = function(string) {

    function RT(lValue, iShiftBits) {
        return (lValue << iShiftBits) | (lValue >>> (32 - iShiftBits));
    }

    function AU(lX, lY) {
        var lX4, lY4, lX8, lY8, lResult;
        lX8 = (lX & 0x80000000);
        lY8 = (lY & 0x80000000);
        lX4 = (lX & 0x40000000);
        lY4 = (lY & 0x40000000);
        lResult = (lX & 0x3FFFFFFF) + (lY & 0x3FFFFFFF);
        if (lX4 & lY4) {
            return (lResult ^ 0x80000000 ^ lX8 ^ lY8);
        }
        if (lX4 | lY4) {
            if (lResult & 0x40000000) {
                return (lResult ^ 0xC0000000 ^ lX8 ^ lY8);
            } else {
                return (lResult ^ 0x40000000 ^ lX8 ^ lY8);
            }
        } else {
            return (lResult ^ lX8 ^ lY8);
        }
    }
    function F(x, y, z) { return (x & y) | ((~x) & z); }
    function G(x, y, z) { return (x & z) | (y & (~z)); }
    function H(x, y, z) { return (x ^ y ^ z); }
    function I(x, y, z) { return (y ^ (x | (~z))); }

    function FF(a, b, c, d, x, s, ac) {
        a = AU(a, AU(AU(F(b, c, d), x), ac));
        return AU(RT(a, s), b);
    };

    function GG(a, b, c, d, x, s, ac) {
        a = AU(a, AU(AU(G(b, c, d), x), ac));
        return AU(RT(a, s), b);
    };

    function HH(a, b, c, d, x, s, ac) {
        a = AU(a, AU(AU(H(b, c, d), x), ac));
        return AU(RT(a, s), b);
    };

    function II(a, b, c, d, x, s, ac) {
        a = AU(a, AU(AU(I(b, c, d), x), ac));
        return AU(RT(a, s), b);
    };

    function CTWA(bytes) {
        var lWordCount;
        var lMessageLength = bytes.length;
        var lNumberOfWords_temp1 = lMessageLength + 8;
        var lNumberOfWords_temp2 = (lNumberOfWords_temp1 - (lNumberOfWords_temp1 % 64)) / 64;
        var lNumberOfWords = (lNumberOfWords_temp2 + 1) * 16;
        var lWordArray = Array(lNumberOfWords - 1);
        var lBytePosition = 0;
        var lByteCount = 0;
        while (lByteCount < lMessageLength) {
            lWordCount = (lByteCount - (lByteCount % 4)) / 4;
            lBytePosition = (lByteCount % 4) * 8;
            lWordArray[lWordCount] = (lWordArray[lWordCount] | (bytes[lByteCount] << lBytePosition));
            lByteCount++;
        }
        lWordCount = (lByteCount - (lByteCount % 4)) / 4;
        lBytePosition = (lByteCount % 4) * 8;
        lWordArray[lWordCount] = lWordArray[lWordCount] | (0x80 << lBytePosition);
        lWordArray[lNumberOfWords - 2] = lMessageLength << 3;
        lWordArray[lNumberOfWords - 1] = lMessageLength >>> 29;
        return lWordArray;
    };

    function WordToHex(lValue) {
        var WordToHexValue = "", WordToHexValue_temp = "", lByte, lCount;
        for (lCount = 0; lCount <= 3; lCount++) {
            lByte = (lValue >>> (lCount * 8)) & 255;
            WordToHexValue_temp = "0" + lByte.toString(16);
            WordToHexValue = WordToHexValue + WordToHexValue_temp.substr(WordToHexValue_temp.length - 2, 2);
        }
        return WordToHexValue;
    };

    function Utf8Encode(string) {
        string = string.replace(/\r\n/g, "\n");
        var result = Array();

        for (var n = 0; n < string.length; n++) {

            var c = string.charCodeAt(n);

            if (c < 128) {
                result.push(c);
            }
            else if ((c > 127) && (c < 2048)) {
                result.push((c >> 6) | 192);
                result.push((c & 63) | 128);
            }
            else {
                result.push((c >> 12) | 224);
                result.push(((c >> 6) & 63) | 128);
                result.push((c & 63) | 128);
            }
        }
        return result;
    };

    var x = Array();
    var k, AA, BB, CC, DD, a, b, c, d;
    var S11 = 7, S12 = 12, S13 = 17, S14 = 22;
    var S21 = 5, S22 = 9, S23 = 14, S24 = 20;
    var S31 = 4, S32 = 11, S33 = 16, S34 = 23;
    var S41 = 6, S42 = 10, S43 = 15, S44 = 21;

    var bytes = Utf8Encode(string);
    x = CTWA(bytes);

    a = 0x67452301; b = 0xEFCDAB89; c = 0x98BADCFE; d = 0x10325476;

    for (k = 0; k < x.length; k += 16) {
        AA = a; BB = b; CC = c; DD = d;
        a = FF(a, b, c, d, x[k + 0], S11, 0xD76AA478);
        d = FF(d, a, b, c, x[k + 1], S12, 0xE8C7B756);
        c = FF(c, d, a, b, x[k + 2], S13, 0x242070DB);
        b = FF(b, c, d, a, x[k + 3], S14, 0xC1BDCEEE);
        a = FF(a, b, c, d, x[k + 4], S11, 0xF57C0FAF);
        d = FF(d, a, b, c, x[k + 5], S12, 0x4787C62A);
        c = FF(c, d, a, b, x[k + 6], S13, 0xA8304613);
        b = FF(b, c, d, a, x[k + 7], S14, 0xFD469501);
        a = FF(a, b, c, d, x[k + 8], S11, 0x698098D8);
        d = FF(d, a, b, c, x[k + 9], S12, 0x8B44F7AF);
        c = FF(c, d, a, b, x[k + 10], S13, 0xFFFF5BB1);
        b = FF(b, c, d, a, x[k + 11], S14, 0x895CD7BE);
        a = FF(a, b, c, d, x[k + 12], S11, 0x6B901122);
        d = FF(d, a, b, c, x[k + 13], S12, 0xFD987193);
        c = FF(c, d, a, b, x[k + 14], S13, 0xA679438E);
        b = FF(b, c, d, a, x[k + 15], S14, 0x49B40821);
        a = GG(a, b, c, d, x[k + 1], S21, 0xF61E2562);
        d = GG(d, a, b, c, x[k + 6], S22, 0xC040B340);
        c = GG(c, d, a, b, x[k + 11], S23, 0x265E5A51);
        b = GG(b, c, d, a, x[k + 0], S24, 0xE9B6C7AA);
        a = GG(a, b, c, d, x[k + 5], S21, 0xD62F105D);
        d = GG(d, a, b, c, x[k + 10], S22, 0x2441453);
        c = GG(c, d, a, b, x[k + 15], S23, 0xD8A1E681);
        b = GG(b, c, d, a, x[k + 4], S24, 0xE7D3FBC8);
        a = GG(a, b, c, d, x[k + 9], S21, 0x21E1CDE6);
        d = GG(d, a, b, c, x[k + 14], S22, 0xC33707D6);
        c = GG(c, d, a, b, x[k + 3], S23, 0xF4D50D87);
        b = GG(b, c, d, a, x[k + 8], S24, 0x455A14ED);
        a = GG(a, b, c, d, x[k + 13], S21, 0xA9E3E905);
        d = GG(d, a, b, c, x[k + 2], S22, 0xFCEFA3F8);
        c = GG(c, d, a, b, x[k + 7], S23, 0x676F02D9);
        b = GG(b, c, d, a, x[k + 12], S24, 0x8D2A4C8A);
        a = HH(a, b, c, d, x[k + 5], S31, 0xFFFA3942);
        d = HH(d, a, b, c, x[k + 8], S32, 0x8771F681);
        c = HH(c, d, a, b, x[k + 11], S33, 0x6D9D6122);
        b = HH(b, c, d, a, x[k + 14], S34, 0xFDE5380C);
        a = HH(a, b, c, d, x[k + 1], S31, 0xA4BEEA44);
        d = HH(d, a, b, c, x[k + 4], S32, 0x4BDECFA9);
        c = HH(c, d, a, b, x[k + 7], S33, 0xF6BB4B60);
        b = HH(b, c, d, a, x[k + 10], S34, 0xBEBFBC70);
        a = HH(a, b, c, d, x[k + 13], S31, 0x289B7EC6);
        d = HH(d, a, b, c, x[k + 0], S32, 0xEAA127FA);
        c = HH(c, d, a, b, x[k + 3], S33, 0xD4EF3085);
        b = HH(b, c, d, a, x[k + 6], S34, 0x4881D05);
        a = HH(a, b, c, d, x[k + 9], S31, 0xD9D4D039);
        d = HH(d, a, b, c, x[k + 12], S32, 0xE6DB99E5);
        c = HH(c, d, a, b, x[k + 15], S33, 0x1FA27CF8);
        b = HH(b, c, d, a, x[k + 2], S34, 0xC4AC5665);
        a = II(a, b, c, d, x[k + 0], S41, 0xF4292244);
        d = II(d, a, b, c, x[k + 7], S42, 0x432AFF97);
        c = II(c, d, a, b, x[k + 14], S43, 0xAB9423A7);
        b = II(b, c, d, a, x[k + 5], S44, 0xFC93A039);
        a = II(a, b, c, d, x[k + 12], S41, 0x655B59C3);
        d = II(d, a, b, c, x[k + 3], S42, 0x8F0CCC92);
        c = II(c, d, a, b, x[k + 10], S43, 0xFFEFF47D);
        b = II(b, c, d, a, x[k + 1], S44, 0x85845DD1);
        a = II(a, b, c, d, x[k + 8], S41, 0x6FA87E4F);
        d = II(d, a, b, c, x[k + 15], S42, 0xFE2CE6E0);
        c = II(c, d, a, b, x[k + 6], S43, 0xA3014314);
        b = II(b, c, d, a, x[k + 13], S44, 0x4E0811A1);
        a = II(a, b, c, d, x[k + 4], S41, 0xF7537E82);
        d = II(d, a, b, c, x[k + 11], S42, 0xBD3AF235);
        c = II(c, d, a, b, x[k + 2], S43, 0x2AD7D2BB);
        b = II(b, c, d, a, x[k + 9], S44, 0xEB86D391);
        a = AU(a, AA);
        b = AU(b, BB);
        c = AU(c, CC);
        d = AU(d, DD);
    }

    var temp = WordToHex(a) + WordToHex(b) + WordToHex(c) + WordToHex(d);

    return temp.toLowerCase();
}
__seceret = '622b010e27e3f82d0f4e2e69a3785a395767c7a39599aea7114553448239eb41cab90bfecd4a8a0881d0a8128f27c483';
var _=__=___='';
for (var i = 0; i < __seceret.length; i+=3) {
   _+=__seceret[i+0]; 
   __+=__seceret[i+1];
   ___+=__seceret[i+2];
}
var h = prompt("Please enter your passowrd");
if(generate(h[11]+h[8]+h[1]+h[0]+h[9]+h[4]+h[13])==_&&generate(h[15]+h[10]+h[3]+h[5]+h[6])==__&&generate(h[16]+h[12]+h[14]+h[2]+h[7])==___){
    alert('your flag is Bugs_Bunny{'+h+'}');
}else{
    alert('I\'m sorry my son it\' not easy');
}
</script>

Chromeデベロッパーツールを使いながら、変数の値を確認する。

_ = "6b07fd4ea837c39e1542e1bbca01a224"
__ = "20ee80e63596799a1543bc9fd88d8878"
___ = "21232f297a57a5a743894a0e4a801fc3"

またgenerateの動作を確認する。

generate('a')
→"0cc175b9c0f1b6a831c399e269772661"
generate('b')
→"92eb5ffee6ae2fec3ad71c777531578f"
generate('c')
→"4a8a08f09d37b73795649038408b5f33"

この結果からgenerateはmd5を算出していると考えられる。フラグを表示させる条件を考えると、以下のようになっている必要がある。

h[11]+h[8]+h[1]+h[0]+h[9]+h[4]+h[13] = "6b07fd4ea837c39e1542e1bbca01a224" のMD5逆変換
h[15]+h[10]+h[3]+h[5]+h[6] = "20ee80e63596799a1543bc9fd88d8878" のMD5逆変換
h[16]+h[12]+h[14]+h[2]+h[7] = "21232f297a57a5a743894a0e4a801fc3" のMD5逆変換

つまり以下のようになる。

h[11]+h[8]+h[1]+h[0]+h[9]+h[4]+h[13] = 'tunisia'
h[15]+h[10]+h[3]+h[5]+h[6] = 'bunny'
h[16]+h[12]+h[14]+h[2]+h[7] = 'admin'

このことから h = 'inininynusutdamba' であることがわかる。

Bugs_Bunny{inininynusutdamba}

Stego10 (Steganography 10)

EXIFのCommentにフラグあり。

Bugs_Bunny{0258c4a75fc36076b41d02df8074372b}

For25 (Forensics 25)

xxdの情報が書いてあるので、次のコマンドでバイナリに戻す。

$ xxd -r hex > hex.zip

zip解凍するとhex.pngが展開され、フラグが書かれていた。
f:id:satou-y:20170801200957p:plain

Bugs_Bunny{Y0u_D1D_1T_W3ll}

UNKOWN file !! (Forensics 30)

pngファイルのバイナリが逆転しているので、逆にして画像にする。

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

with open('flag.png', 'wb') as f:
    f.write(data[::-1])

結果のPNGファイルを見ると、フラグが逆に書いてある。
f:id:satou-y:20170801201335p:plain

Bugs_Bunny{E4Sy_T4Sk_F0R_H4X0r_L1KeS_Y0u}

Lost data (Forensics 50)

バイナリエディタでファイルを見てみると、flag.arjの文字列が含まれていることがわかる。このファイルはARJ形式の圧縮ファイルが壊れているものであると推定する。ARJ形式の圧縮ファイルは先頭2バイトが60 EAであると決められているので、先頭2バイトを 60 EA に変更する。この変更後の圧縮ファイルを解凍すると、flag.pngが入っていて、フラグが書かれていた。
f:id:satou-y:20170801201826p:plain

Bugs_Bunny{r3m3mb3r_4ll_w4ys_t0_ch3ck_h34d3r_f1l3}

Give me the Flag ! (Forensics 85)

旗の画像の中にQRコードの破片の画像が紛れ込んでいる。
QRコードを組み立て、読み込む。

== 34Sy_P4SSW0Rd_H4X0r ==

読み込んだ文字列をパスワードとして、flag.zipを解凍する。展開したReadmeの中に2進数8桁の文字列がスペース区切りでたくさん書いてある。これをASCIIコードとして読む。

with open('Readme', 'r') as f:
    data = f.read()

codes = data.split(' ')
flag = ''
for code in codes:
    if code != '':
        flag += chr(int(code, 2))

print flag
Bugs_Bunny{2b97263beb70d0f659bdb93cc5291d0a}

ZERO-ONE ! (Programation 45)

ZEROを0、ONEを1に変換し、2進数をASCIIコードとして読む。BASE64エンコード文字列になるので、デコードする。

with open('progTask.txt', 'r') as f:
    data = f.read()

data = data.replace('ZERO ', '0')
data = data.replace('ONE ', '1')

b64_flag = ''
for i in range(0, len(data), 8):
    b64_flag += chr(int(data[i:i+8], 2))

flag = b64_flag.decode('base64')
print flag
Bugs_Bunny{05fe8238cfee1e5f04b65339bea4fed2}

Capital (Programation 80)

$ nc 34.253.165.46 11223
Hi, do YOU love math ?!?!
Level 1.: Alaska
Juneau
Great, keep it up
Level 2.: x + 4 = 1119
1115
Great, keep it up

州都を答える問題か方程式を解く問題かどちからかが出題される。州都は対応表を作って、州に対応する州都を取得し、方程式は四則演算の左側がxである前提で計算し、答えていく。

import socket
import re

capitals={"Washington":"Olympia","Oregon":"Salem",\
    "California":"Sacramento","Ohio":"Columbus",\
    "Nebraska":"Lincoln","Colorado":"Denver",\
    "Michigan":"Lansing","Massachusetts":"Boston",\
    "Florida":"Tallahassee","Texas":"Austin",\
    "Oklahoma":"Oklahoma City","Hawaii":"Honolulu",\
    "Alaska":"Juneau","Utah":"Salt Lake City",\
    "New Mexico":"Santa Fe","North Dakota":"Bismarck",\
    "South Dakota":"Pierre","West Virginia":"Charleston",\
    "Virginia":"Richmond","New Jersey":"Trenton",\
    "Minnesota":"Saint Paul","Illinois":"Springfield",\
    "Indiana":"Indianapolis","Kentucky":"Frankfort",\
    "Tennessee":"Nashville","Georgia":"Atlanta",\
    "Alabama":"Montgomery","Mississippi":"Jackson",\
    "North Carolina":"Raleigh","South Carolina":"Columbia",\
    "Maine":"Augusta","Vermont":"Montpelier",\
    "New Hampshire":"Concord","Connecticut":"Hartford",\
    "Rhode Island":"Providence","Wyoming":"Cheyenne",\
    "Montana":"Helena","Kansas":"Topeka",\
    "Iowa":"Des Moines","Pennsylvania":"Harrisburg",\
    "Maryland":"Annapolis","Missouri":"Jefferson City",\
    "Arizona":"Phoenix","Nevada":"Carson City",\
    "New York":"Albany","Wisconsin":"Madison",\
    "Delaware":"Dover","Idaho":"Boise",\
    "Arkansas":"Little Rock","Louisiana":"Baton Rouge"
}

pattern = 'Level (.+)\.: (.+)'

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('34.253.165.46', 11223))

data = s.recv(256)
print data

for i in range(1, 10000):
    data = s.recv(256)
    print data
    m = re.match(pattern, data)
    q = m.group(2)
    if capitals.has_key(q):
        ans = capitals[q]
    else:
        ope = q.split(' ')[1]
        val1 = int(q.split(' ')[2])
        val2 = int(q.split(' ')[4])
        if ope == '+':
            ans = str(val2 - val1)
        elif ope == '-':
            ans = str(val2 + val1)
        elif ope == '*':
            ans = str(val2 / val1)
        elif ope == '/':
            ans = str(val2 * val1)
        else:
            ans = ''
    print ans
    s.sendall(ans + '\n')
    data = s.recv(256)
    print data

500回正解すると、フラグが表示された。

Bugs_Bunny{M4TH_LO0k!_HarD_But_s0_EA5Y}

CTFZone 2017 Writeup

この大会は2017/7/15 18:00(JST)~2017/7/17 6:00(JST)に開催されました。
今回もチームで参戦。結果は1153点で55チーム中24位でした。
自分で解けた問題をWriteupとして書いておきます。

MPRSA (CRYPTO)

Multi-Prime RSAの問題。まず素因数分解したいが、factordbではできなかった。
暗号化のプログラムから、deltaの値(5~15)は総当たりで素数の構成を作り、nと同じ値になるものを探す。数時間かかったが、次のようなプログラムで素因数を割り出すことができた。ちなみに delta=14の場合に該当するnが見つかった。

from gmpy2 import next_prime

def compute_module(primes):
    n = 1
    for prime in primes:
        n *= prime
    return n

with open('public.txt', 'r') as f:
    data = f.read()

n = int(data.split('\n')[1].split(' = ')[1])

delta = 14
p = 177739015005173300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

adjust = pow(2, 1024)
p0 = p
while True:
    #print p
    P = [next_prime(p)]
    for i in range(1, 4):
        P.append(next_prime(P[i-1] * delta))
    mul = compute_module(P)
    print mul
    if mul == n:
        print 'P[0] =', P[0]
        print 'P[1] =', P[1]
        print 'P[2] =', P[2]
        print 'P[3] =', P[3]
        break
    else:
        diff = n - mul
        if diff < 0:
            if adjust == 1:
                print 'Not Found (delta = %d)' % delta
                break
            else:
                adjust /= 2
                p = p0
        else:
            p0 = p
            p = next_prime(p + adjust)

素因数分解の結果は以下の通り。

P[0] = 177739015005173306533752250332928388271426563815093455666936081629571193511808970499241559574326686383600364964248435983786753776661738101198468295487687752622214814554023747926012377837938347566934895426939099916675611018615527164379921811922640194594903892753383803569371101697376356302460080232868430713251
P[1] = 2488346210072426291472531504660997435799971893411308379337105142813996709165325586989381834040573609370405109499478103773014552873264333416778556136827628536711007403756332470964173289731136865937088535977147398833458554260617380301318905366916962724328654498547373249971195423763268988234441123260158029986729
P[2] = 34836846941013968080615441065253964101199606507758317310719471999395953928314558217851345676568030531185671532992693452822203740225700667834899785915586799513954103652588654593498426056235916123119239503680063583668419759648643324218464675136837478140601162979663225499596735932685765835282175725642212419814243
P[3] = 487715857174195553128616174913555497416794491108616442350072607991543354996403815049918839471952427436599401461897708339510852363159809349688597002818215193195357451136241164308977964787302825723669353051520890171357876635081006539058505451915724693968416281715285156994354303057600721693950460158990973877400281

この結果から、Muti-Prime RSAの復号プログラムを書く。

import gmpy

def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)

    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * gmpy.invert(p, n_i) * p
    return sum % prod

with open('data.enc', 'r') as f:
    c = int(f.read())

with open('public.txt', 'r') as f:
    pub = f.read()

e = int(pub.split('\n')[0].split(' = ')[1])
n = int(pub.split('\n')[1].split(' = ')[1])

primes = [
    177739015005173306533752250332928388271426563815093455666936081629571193511808970499241559574326686383600364964248435983786753776661738101198468295487687752622214814554023747926012377837938347566934895426939099916675611018615527164379921811922640194594903892753383803569371101697376356302460080232868430713251,
    2488346210072426291472531504660997435799971893411308379337105142813996709165325586989381834040573609370405109499478103773014552873264333416778556136827628536711007403756332470964173289731136865937088535977147398833458554260617380301318905366916962724328654498547373249971195423763268988234441123260158029986729,
    34836846941013968080615441065253964101199606507758317310719471999395953928314558217851345676568030531185671532992693452822203740225700667834899785915586799513954103652588654593498426056235916123119239503680063583668419759648643324218464675136837478140601162979663225499596735932685765835282175725642212419814243,
    487715857174195553128616174913555497416794491108616442350072607991543354996403815049918839471952427436599401461897708339510852363159809349688597002818215193195357451136241164308977964787302825723669353051520890171357876635081006539058505451915724693968416281715285156994354303057600721693950460158990973877400281]

n_ary = []
a_ary = []
for p in primes:
    phi = p - 1
    d = gmpy.invert(e, phi)
    mk = pow(c, d, p)
    n_ary.append(p)
    a_ary.append(mk)

m = chinese_remainder(n_ary, a_ary)
flag = ('%x' % m).decode('hex')
print flag

実行結果は次の通り。

Mr.D (12:10):
Okey, see you later ;)

Mr.D (19:30):
So can you help me?

Anonymous (19:31):
Yeah, we will have 10,000 falsified voters. Transfer 100000$ to my bank account: ctfzone{3177809746931830}
ctfzone{3177809746931830}

MeePwn CTF 1st 2017 Writeup

この大会は2017/7/14 9:00(JST)~2017/7/16 9:00(JST)に開催されました。
今回もチームで参戦。結果は900点で542チーム中32位でした。
自分で解けた問題をWriteupとして書いておきます。

nub_cryptosystem (CRYPTO)

暗号化のコードが与えられているので、読んでいくとMerkle-Hellmanナップサック暗号であることがわかる。この場合、解読できる条件は秘密鍵が超増加列になっていることだが、これも当然のごとくあてはまる。ということで、復号プログラムを書く。

def load_data():
    with open('pubkey.txt', 'r') as f:
        pub_keys = f.read().strip()[1:-1].split(', ')

    with open('enc.txt', 'r') as f:
        ciphertext = int(long(f.read().strip()))

    return pub_keys, ciphertext

def create_matrix_from_knapsack(ciphertext, pub_keys):
    last_col = []
    for p in pub_keys:
        last_col.append(int(long(p)))

    last_col.append(ciphertext)
    last_row = [1 for i in pub_keys]

    my_matrix = MatrixSpace(ZZ, len(pub_keys))(2)
    m_last_row = matrix(ZZ, 1, len(last_row), last_row)
    m_last_col = matrix(ZZ, len(last_col), 1, last_col)

    my_matrix = my_matrix.stack(m_last_row)
    my_matrix = my_matrix.augment(m_last_col)

    return my_matrix

def is_short_vector(vector):
    for v in vector:
        if v != 1 and v != -1 and v != 0:
            return False
    return True

def find_short_vector(matrix):
    for row in matrix:
        if is_short_vector(row):
            return row

def main():
    pub_keys, cipher = load_data()
    my_matrix = create_matrix_from_knapsack(cipher, pub_keys)

    new_matrix = my_matrix.LLL()

    short_vector = find_short_vector(new_matrix)

    bin_flag = ''
    for v in short_vector:
        if v == 1:
            bin_flag += '0'
        elif v == -1:
            bin_flag += '1'

    flag = ''
    for i in range(0, len(bin_flag), 8):
        flag += chr(int(bin_flag[i:i+8], 2))

    flag = 'MeePwnCTF{' + flag + '}'
    print flag

if __name__ == '__main__':
    main()

これで復号でき、フラグが得られた。

MeePwnCTF{Merkleee-Hellmannn!}

PoliCTF 2017 参戦

この大会は2017/7/7 18:00(JST)~2017/7/9 18:00(JST)に開催されました。
今回もチームで参戦。結果は1416点で252チーム中28位でした。
今回も自分が得点した問題は1問もありませんでした。
他の人のWriteup見ても、暗号の問題はもう一息だったんだけど、本当に残念!

MNCTF 2017 Writeup

このイベントは2016/7/6 10:00(JST)~2016/7/6 11:30(JST)に
カンファレンスの一つとして開催されました。
個人戦の大会で、最初の確認の問題以外は100点が基準で
解いた人が多くなると点数が下がっていくというルール。
結果は151点であまり良くない成績でした。
解けた問題をWriteupとして書いておきます。

練習問題 (MISC 1)

フラグは問題に書かれていた。

MNCTF

昇進試験 (MISC 60)

Linuxコマンドに関するクロスワードの問題。
クロスワードを解くと、フラグが表示された。
f:id:satou-y:20170711215835p:plain

f148052f5b4eea45dd395d6f45fb19ea

脅迫文書 (MISC 90)

脅迫文の中の写真にURL(onionドメイン)とランダムな文字列がある。
まずTor BrowserでURLにアクセスする。パスワードを聞かれたので、写真のランダムな文字列を入れてみると、フラグが書いてあるページが表示された。
f:id:satou-y:20170711221311p:plain

TORPASTEBIN

SECUINSIDE CTF Quals 2017 Writeup

この大会は2017/7/1 9:00(JST)~2017/7/2 16:33(JST)に開催されました。
今回もチームで参戦。結果は60点で543チーム中153位でした。
自分で解けた問題は答えが書てあるものだけですが、Writeupとして書いておきます。

SANITY CHECK (MISC)

問題に書いてある。参加表明問題。

SECU[THIS_IS_FLAG]

CAT CARRIER (MISC)

これも一見隠されているフラグを探す問題かと思ったが、記載されているフラグが正解。

SECU[____MEOW_____MEOW____]