VolgaCTF 2017 Quals Writeup

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

VC (crypto 50)

2つのノイズのような画像が与えられている。2つの画像の差がある部分を黒にしてみる。

from PIL import Image

img_a = Image.open('A.png').convert('RGB')
img_b = Image.open('B.png').convert('RGB')
w, h = img_a.size

img_o = Image.new('RGB', (w, h), (255, 255, 255))

for y in range(0, h):
    for x in range(0, w):
        r1, g1, b1 = img_a.getpixel((x, y))
        r2, g2, b2 = img_b.getpixel((x, y))
        if r1 == r2 and g1 == g2 and b1 == b2:
            img_o.putpixel((x, y), (255, 255, 255))
        else:
            img_o.putpixel((x, y), (0, 0, 0))

img_o.save('flag.png')

f:id:satou-y:20170331221319p:plain
フラグが表示された。

VolgaCTF{Classic_secret_sharing_scheme}

Curved (crypto 200)

$ nc curved.quals.2017.volgactf.ru 8786
Solve a puzzle: find an x such that 26 last bits of SHA1(x) are set, len(x)==29 and x[:24]=='875378c8c528de3c569e29a6'

最初にこの問題を解く必要がある。その後、ECDSAの問題となる。
添付のスクリプトを見てみると、以下のことがわかる。

・サーバOS上でls、dir、cd、catコマンド、また抜けるためにexitやleaveというコマンドが使える。
・ただし、該当するシグネチャと合わせて、チェックを通らないと実行できない。
・exitとleaveのシグネチャは添付されており、rは同じ値になっている。

cat flagのシグネチャを作ることができれば、フラグを奪取できそうだ。
rが同じで、シグネチャが分かっているものが2組あれば、秘密鍵を導き出すことができる。

e1 = int(hashlib.sha512('exit').hexdigest(), 16)
e2 = int(hashlib.sha512('leave').hexdigest(), 16)
z1 = e1 >> 512 - nのビット長
z2 = e2 >> 512 - nのビット長
k = ((z1 - z2) % n) * invert(((s1 - s2) % n), n)
privatekey = (((((s1 * k) % n) - z1) % n) * invert(r1, n)) % n

秘密鍵がわかれば、どのコマンドでも添付のソースコード記載の通り、シグネチャを作成できる。プログラムは以下の通り。

#!/usr/bin/env python
import socket
import re
import string
import itertools
import hashlib
from gmpy2 import invert, bit_length

def import_public_key(file):
    with open(file, 'r') as f:
        data = f.read()
        d = data.split('\n')
        QAx = int(d[0])
        QAy = int(d[1])
        return QAx, QAy

def import_cmd_signature(cmd):
    file = '{0}.sig'.format(cmd)
    with open(file, 'r') as f:
        data = f.read()
        d = data.split('\n')
        (r, s) = (int(d[0]), int(d[1]))
        return r, s

class EllipticCurve(object):
    def __init__(self, a, b, p, n):
        self.a = a
        self.b = b
        self.p = p
        self.n = n

        self.discriminant = -16 * (4 * a * a * a + 27 * b * b)
        if not self.isSmooth():
            raise Exception("The curve %s is not smooth!" % self)

    def isSmooth(self):
        return self.discriminant != 0

    def testPoint(self, x, y, p):
        return (y ** 2) % p == (x ** 3 + self.a * x + self.b) % p

    def __str__(self):
        return 'y^2 = x^3 + %Gx + %G (mod %G)' % (self.a, self.b, self.p)

    def __eq__(self, other):
        return (self.a, self.b, self.p) == (other.a, other.b, other.p)


class Point(object):
    def __init__(self, curve, x, y):
        self.curve = curve
        self.x = x
        self.y = y
        if not curve.testPoint(x, y, curve.p):
            raise Exception("The point %s is not on the given curve %s" % (self, curve))

    def __neg__(self):
        return Point(self.curve, self.x, -self.y)

    def __add__(self, Q):
        if isinstance(Q, Ideal):
            return self
        x_1, y_1, x_2, y_2 = self.x, self.y, Q.x, Q.y
        if (x_1, y_1) == (x_2, y_2):
            if y_1 == 0:
                return Ideal(self.curve)
            s = (3 * x_1 * x_1 + self.curve.a) * int(invert(2 * y_1, self.curve.p))
        else:
            if x_1 == x_2:
                return Ideal(self.curve)
            s = (y_2 - y_1) * int(invert(x_2 - x_1, self.curve.p))
        x_3 = (s * s - x_2 - x_1) % self.curve.p
        y_3 = (s * (x_3 - x_1) + y_1) % self.curve.p
        return Point(self.curve, x_3, self.curve.p - y_3)

    def __sub__(self, Q):
        return self + -Q

    def __mul__(self, n):
        if not (isinstance(n, int) or isinstance(n, long)):
            raise Exception("Can't scale a point by something which isn't an int!")
        else:
            if n < 0:
                return -self * -n
            if n == 0:
                return Ideal(self.curve)
            else:
                Q = self
                R = self if n & 1 == 1 else Ideal(self.curve)
                i = 2
                while i <= n:
                    Q = Q + Q
                    if n & i == i:
                        R = Q + R
                    i = i << 1
        return R

    def __rmul__(self, n):
        return self * n

class Ideal(Point):

    def __init__(self, curve):
        self.curve = curve

    def __str__(self):
        return "Ideal"

    def __neg__(self):
        return self

    def __add__(self, Q):
        return Q

    def __mul__(self, n):
        if not isinstance(n, int):
            raise Exception("Can't scale a point by something which isn't an int!")
        else:
            return self

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('curved.quals.2017.volgactf.ru', 8786))

data = s.recv(1024)
print data

pattern = 'x\[:24\]==\'(.+)\''
m = re.search(pattern, data)
x_head = m.group(1)

for c in itertools.product(string.printable, repeat=5):
    x = x_head + ''.join(c)
    if int(hashlib.sha1(x).hexdigest(), 16) & 0x3ffffff == 0x3ffffff:
        break

print x
s.sendall(x + '\n')

data = s.recv(1024)
print data

p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
a = -3
b = int('b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef', 16)
NIST384 = EllipticCurve(a, b, p, n)

Gx = int('aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7', 16)
Gy = int('3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f', 16)
G = Point(NIST384, Gx, Gy)

QA = import_public_key('key.public')
QA = Point(NIST384, QA[0], QA[1])

r1, s1 = import_cmd_signature('exit')
r2, s2 = import_cmd_signature('leave')
e1 = int(hashlib.sha512('exit').hexdigest(), 16)
e2 = int(hashlib.sha512('leave').hexdigest(), 16)

Ln = bit_length(n)
z1 = e1 >> (512 - Ln)
z2 = e2 >> (512 - Ln)
k = int(((z1 - z2) % n) * invert(((s1 - s2) % n), n))
priv = int((((((s1 * k) % n) - z1) % n) * invert(r1, n)) % n)

cmd = 'cat flag'
e3 = int(hashlib.sha512(cmd).hexdigest(), 16)
z3 = e3 >> (512 - Ln)
xy = k * G
r3 = xy.x % n
s3 = int(invert(k, n) * (z3 + r3 * priv) % n)

ans = str(r3) + ' ' + str(s3) + ' ' + cmd
print ans
s.sendall(ans + '\n')

data = s.recv(1024)
print data

実行すると、フラグが表示された。

VolgaCTF{N0nce_1s_me@nt_to_be_used_0n1y_Once}