hack you 2014 - Crypto writeup

CTF

Scoreboard :: hack you 2014
個人戦で、47位。まだまだ精進が足りない :)
Cryptoはすべて解けたので、writeupを残しておく。

Crypto 100: Easy one

msg002.encをdecryptする問題。
与えられているmsg001とmsg001.encをXORするとkeyが出てくる。あとはそのkeyを使ってdecryptするだけ。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv) {
	if (argc != 3) {
		printf("USAGE: %s INPUT OUTPUT\n", argv[0]);
		return 0;
	}
	FILE* input  = fopen(argv[1], "rb");
	FILE* output = fopen(argv[2], "wb");
	if (!input || !output) {
		printf("Error\n");
		return 0;
	}
	char k[] = "VeryLongKeyYouWillNeverGuess";
	char c, p, t = 0;
	int i = 0, j;
	while ((p = fgetc(input)) != EOF) {
		for (j = 0; j <= 0xff; j++) {
			if (p == (char)(((char)j + (k[i % strlen(k)] ^ t) + i*i) & 0xff)) {
				printf("%c", j);
				fputc(j, output);
				t = j;
				break;
			}
		}
		i++;
	}
	return 0;
}

Crypto 200: Hashme

administratorになってログインする問題。ひとまず、SALTとKEYがわからないのでどうにかして推測できるかどうか試した。
サーバから生成されるcertはlogin=ユーザー名&role=anonymous + 独自のハッシュ関数(SALT + 'login=ユーザー名&role=anonymous')をBase64でencodeしたものである。KEYの長さはわからないが元の文字列はわかっているので、XORすればKEYを求めることができる。
したがって、KEYからcertをdecodeすることができる。ユーザー名aのときのcertはRK5yZMJaZX5PA31AmkxS6EpnEjvimts6QZetHTjtkk80yzLYnr1pJ2gToW/wB1UaxNAR8HM8だったため、decodeするとlogin=a&role=anonymousc69cc6019d99985cb099247b5f1591f1になる。ハッシュ値は逆算することはできないが、ハッシュ関数('login=a&role=anonymous')としているため、ハッシュ関数の性質から元の文字列に任意の文字列を付加したものを計算することができる。SALTがわからなくてもハッシュ値を計算することができる。よってhashme('login=a&role=anonymous&role=administrator')を計算できれば良い。
しかし、hashme()でいうlがわからないがlは32通り。すべて試したところ、うまくいくcertが見つかった。

KEY = "\x28\xc1\x15\x0d\xac\x67\x04\x58\x3d\x6c\x11\x25\xa7\x2d\x3c\x87\x24\x1e\x7f\x54\x97\xe9\xb8\x0c\x78\xf4\xce\x2b\x08\xdc\xab\x2b\x0d\xf2\x0b\xe0\xab\xde\x0b\x17\x51\x2a\x93\x5b\xc7\x65\x60\x7c\xf5\xe5"

def myhashme(j):
    #my secure hash function
    def F(X,Y,Z):
        return ((~X & Z) | (~X & Z)) & 0xFFFFFFFF
    def G(X,Y,Z):
        return ((X & Z) | (~Z & Y)) & 0xFFFFFFFF
    def H(X,Y,Z):
        return (X ^ Y ^ Y) & 0xFFFFFFFF
    def I(X,Y,Z):
        return (Y ^ (~Z | X)) & 0xFFFFFFFF
    def ROL(X,Y):
        return (X << Y | X >> (32 - Y)) & 0xFFFFFFFF

    B = 0xc69cc601
    A = 0x9d99985c
    D = 0xb099247b
    C = 0x5f1591f1

    X = [int(0xFFFFFFFF * sin(i)) & 0xFFFFFFFF for i in xrange(256)]

    for ch in '&role=administrator':
        k, l = ord(ch), j & 0x1f
        A = (B + ROL(A + F(B,C,D) + X[k], l)) & 0xFFFFFFFF
        B = (C + ROL(B + G(C,D,A) + X[k], l)) & 0xFFFFFFFF
        C = (D + ROL(C + H(D,A,B) + X[k], l)) & 0xFFFFFFFF
        D = (A + ROL(D + I(A,B,C) + X[k], l)) & 0xFFFFFFFF
        j += 1

    return ''.join(map(lambda x : hex(x)[2:].strip('L').rjust(8, '0'), [B, A, D, C]))

for i in range(32):
    s = 'login=a&role=anonymous&role=administrator'
    s += myhashme(i)
    s = b64encode(xor(s, KEY))
    print s

Crypto 300: Matrix

flag.wmv.outをdecryptする問題。
keyとなる4x4の行列を逆算すれば良い。WMVのsignatureは30 26 B2 75 8E 66 CF 11 A6 D9 00 AA 00 62 CE 6C (16 bytes) なので逆算するには十分な長さである。cipher = data * keyよりkey = data.I * cipherである。つまりWMVのsignatureを逆行列にしたものを掛けることでkeyが求められる。あとはdecryptするだけ。

#!/usr/bin/python
import random
import numpy
from struct import *

def Str2matrix(s):
    #convert string to 4x4 matrix
    return [map(lambda x : ord(x), list(s[i:i+4])) for i in xrange(0, len(s), 4)]

def WStr2matrix(s):
    # 16 bytes
    matrix = []
    for i in xrange(0, len(s), 8):
        r = []
        for j in xrange(0, 8, 2):
            r.append(unpack('!H', s[i+j:i+j+2])[0])
        matrix.append(r)
    return matrix

def Matrix2str(m):
    #convert matrix to string
    return ''.join(map(lambda x : ''.join(map(lambda y : pack('!H', y), x)), m))

def Generate(password):
    #generate key matrix
    random.seed(password)
    return [[random.randint(0,64) for i in xrange(4)] for j in xrange(4)]

def Multiply(A,B):
    #multiply two 4x4 matrix
    C = [[0 for i in xrange(4)] for j in xrange(4)]
    for i in xrange(4):
        for j in xrange(4):
            for k in xrange(4):
                C[i][j] += A[i][k] * B[k][j]
    return C

data = open('flag.wmv.out', 'rb').read()

dec = "\x30\x26\xB2\x75\x8E\x66\xCF\x11\xA6\xD9\x00\xAA\x00\x62\xCE\x6C" # wmv
key = numpy.round(numpy.matrix(Str2matrix(dec)).I * numpy.matrix(WStr2matrix(data[4:4+32])).tolist())

out = open('flag.wmv', 'wb')
for i in xrange(4, len(data), 32):
    c = WStr2matrix(data[i:i+32]) * numpy.matrix(key).I
    m = Matrix2str(numpy.round(c.tolist()))
    d = ''
    for j in xrange(0, len(m), 2):
        d += m[j+1]
    out.write(d)

Crypto 400: CRYPTONET

RSA暗号の問題。packets.pcapの中身を見ると19回通信していて、おそらくすべて同じ内容(同一平文)である。
eが17かつ暗号文が17個以上あるため、中国の剰余定理でcを求めることができる。平文mを求めるには、cの17乗根を計算すれば良い。

def crt(A, M):
     Mprod = prod(M)
     Mdiv = map(lambda x: Integer(Mprod / x), M)
     X = map(inverse_mod, Mdiv, M)
     x = sum([A[i]*X[i]*Mdiv[i] for i in xrange(len(A))])
     return mod(x, Mprod).lift()

def n2s(n):
    s = hex(n)[2:].rstrip("L")
    if len(s) % 2 != 0:
        s = "0" + s
    return s.decode("hex")

c = [...]
n = [...]

print n2s(crt(c, n).nth_root(17))