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):
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するだけ。
import random
import numpy
from struct import *
def Str2matrix(s):
return [map(lambda x : ord(x), list(s[i:i+4])) for i in xrange(0, len(s), 4)]
def WStr2matrix(s):
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):
return ''.join(map(lambda x : ''.join(map(lambda y : pack('!H', y), x)), m))
def Generate(password):
random.seed(password)
return [[random.randint(0,64) for i in xrange(4)] for j in xrange(4)]
def Multiply(A,B):
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"
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))