チーム yharima で参加したので、write up を書いておく。暗号ばっかり解いていた。

CR2

問題文を読むと、one time pad を使ったけど one time と呼ばれる意味が分かっていない、的なことが書いてあったので、鍵が使いまわされているんだろうなあと予想。

one time pad といっても色々あるらしいのだが、XORで暗号文を作ると予想して、次のリンクにある通り解読を試みた。
http://crypto.stackexchange.com/questions/59/taking-advantage-of-one-time-pad-key-reuse/64

鍵をK、平文をTとしたときに、暗号文Cは鍵と平文の XOR をとったもの。

C = K ⊕ T

同じ鍵の暗号文が複数用意されている (C1, C2) とき、暗号文どうしの XOR をとると、鍵の影響を排除できる。

C1 = K ⊕ T1
C2 = K ⊕ T2
C1 ⊕ C2 = (K ⊕ T1) ⊕ (K ⊕ T2)
        = T1 ⊕ T2

C1 ⊕ C2に対し、平文に入っていそうな単語で適当な位置のXORをとってみて、結果が読める文になるところを探す。見つかった場合、その部分の平文が明らかになったことになる。ただし、元の単語と XOR の結果のどちらが C1 に含まれるのかはわからない。

問題のテキストは 11 行になっていたので、hex から byte に変換してから、適当な2行を選んで思いついた単語が入っているか確認していった。

結果、どうやら3行目に crypt という文字列が含まれているらしいことがわかった。これで、次のような感じの平文になっていることが判明したので、あとは左右にそれっぽい文字がくるよう適当に伸ばしていけば全部解読できた。

___________________ime I__
___________________e and__
___________________crypt__
___________________hat i__
___________________ion m__
___________________tical__
___________________racke__
___________________kept __
___________________f you__
___________________ this__
___________________ways.

解読結果はこちら。

Dear Friend, This time I u
nderstood my mistake and u
sed One time pad encryptio
n scheme, I heard that it 
is the only encryption met
hod that is mathematically
 proven to be not cracked 
ever if the key is kept se
cure, Let me know if you a
gree with me to use this e
ncryption scheme always.

結局、鍵がフラグだった。
ALEXCTF{HERE_GOES_THE_KEY}
（初めからALEXCTF{とXORとっていけばよかった）

CR4

RSAの問題。とりあえず modulus を見てみる。

$ openssl rsa -noout -text -in key.pub -pubin
Public-Key: (399 bit)
Modulus:
    52:a9:9e:24:9e:e7:cf:3c:0c:bf:96:3a:00:96:61:
    77:2b:c9:cd:f6:e1:e3:fb:fc:6e:44:a0:7a:5e:0f:
    89:44:57:a9:f8:1c:3a:e1:32:ac:56:83:d3:5b:28:
    ba:5c:32:42:43
Exponent: 65537 (0x10001)

399 bit の RSA コンテストはなかったが、factordb に聞いたら素因数分解してもらえた。あとは Wikipedia にある通り、例の式に従って復号。
フラグは ALEXCTF{SMALL_PRIMES_ARE_BAD}

CR5

nc でつなぐと、次の数字を教えてもらうか、予想の入力をすることができる。教えてもらうと乱数列が返ってくるので、これを予想すればいいっぽい

線形合同法では？、と思い次のリンクの通り乱数列の予測を試みた。
security.stackexchange.com

リンク先に書いてある通りだが、ここにもまとめておく。

x[n + 1] = a * x[n] + b (mod m)

より

x[n + 1] - x[n] = a * (x[n] - x[n - 1]) (mod m)

となるので、

y[n] = x[n + 1] - x[n] (mod m)

とおくと、

y[n + 1] = a * y[n] (mod m)

よって

y[n + 2] * y[n] - (y[n + 1])^2 = 0 (mod m)

これにより、y[n + 2] * y[n] - (y[n + 1])^2 を十分な数の n について集め、最大公約数をとれば、m が求められる。

あとは、y[1] = a * y[0] (mod m) を解いて a を出して、x[1] = a * x[0] + b (mod m) を解いて b を出すだけ。

最初の10回くらいは聞いて、それをもとに m, a, b を求め、乱数列を出す。 10回連続で正解すると、フラグを出してくれた。

flag is ALEXCTF{f0cfad89693ec6787a75fa4e53d8bdb5}

書いたスクリプトはこんな感じ。

#!/usr/bin/env python

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b:
        a, b = b, a%b
    return a

def egcd(a, b):
    x, lx = 0, 1
    y, ly = 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, lx = lx - q * x, x
        y, ly = ly - q * y, y
    return lx, ly

x = [
    4251151823,
    2502705517,
    4101273005,
    1396379746,
    4159332548,
    3671236567,
    433240385,
    465003001,
    2767252763,
    952274152
]

# x[i + 1] = a * x[i] + b (mod m)
# y[i + 1] = a * y[i] (mod m)
y = []
for i in range(len(x) - 1):
    y.append(x[i + 1] - x[i])

# z[i] = y[i + 2] * y[i] - (y[i + 1])^2 = 0 (mod m)
z = []
for i in range(len(y) - 2):
    zz = y[i + 2] * y[i] - y[i + 1] * y[i + 1]
    if zz < 0:
        zz = -zz
    z.append(zz)

m = z[0]
for i in range(len(z)):
    m = gcd(m, z[i])

for i in range(len(y)):
    while y[i] < 0:
        y[i] += m

# p * y[0] + q * m = r (mod m)
# p * y[0] = r (mod m)
p, q = egcd(y[0], m)
r = (p * y[0]) % m
# y[1] = a * y[0]
# p * y[1] = a * p * y[0] = a * r
a = ((y[1] / r) * p) % m

# a * x[0] + b = x[1] (mod m)
# b = x[1] - a * x[0] (mod m)
b = (x[1] - a * x[0]) % m

print "check y"
yy = []
yy.append(y[0])
for i in range(len(y) - 1):
    t = (a * yy[i]) % m
    yy.append(t)
    print y[i + 1], yy[i + 1], (y[i + 1] - yy[i + 1])

print

print "check x"
xx = []
xx.append(x[0])
for i in range(len(x) - 1):
    t = (a * xx[i] + b) % m
    xx.append(t)
    print x[i + 1], xx[i + 1], (x[i + 1] - xx[i + 1])

print

print "show x"
xx = []
xx.append(x[0])
for i in range(29):
    t = (a * xx[i] + b) % m
    xx.append(t)

for i in range(len(xx)):
    print '{0}\t{1}'.format(i, xx[i])

次CTFに参加するときは暗号以外も解きたい。

liniku's blog

AlexCTF 2017 write up

CR2

CR4

CR5