# ochazuke [InterKosenCTF 2020]
###### tags: `InterKosenCTF2020` `crypto`

## 概要

何がochazukeなのかわからないけどとにかくsageのスクリプトが与えられて、それがサーバで走ってるらしい。

from Crypto.Util.number import bytes_to_long
from binascii import unhexlify
from hashlib import sha1
import re

EC = EllipticCurve(
    GF(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff),
    [-3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b]
)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 # EC.order()
Zn = Zmod(n)
G = EC((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
        0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))

def sign(private_key, message):
    z = Zn(bytes_to_long(message))
    k = Zn(ZZ(sha1(message).hexdigest(), 16)) * private_key
    assert k != 0
    K = ZZ(k) * G
    r = Zn(K[0])
    assert r != 0
    s = (z + r * private_key) / k
    assert s != 0
    return (r, s)

def verify(public_key, message, signature):
    r, s = signature[0], signature[1]
    if r == 0 or s == 0:
        return False
    z = Zn(bytes_to_long(message))
    u1, u2 = z / s, r / s
    K = ZZ(u1) * G + ZZ(u2) * public_key
    if K == 0:
        return False
    return Zn(K[0]) == r

if __name__=="__main__":
    from secret import flag, d
    public_key = ZZ(d) * G
    print("public key:", public_key)
    
    your_msg = unhexlify(input("your message(hex): "))
    if len(your_msg) < 10 or b"ochazuke" in your_msg:
        print("byebye")
        exit()
    your_sig = sign(d, your_msg)
    print("your signature:", your_sig)

    sig = input("please give me ochazuke's signature: ")
    r, s = map(Zn, re.compile("\((\d+), (\d+)\)").findall(sig)[0])
    if verify(public_key, b"ochazuke", (r, s)):
        print("thx!", flag)
    else:
        print("it's not ochazuke :(")

内容はいわゆるECDSAで、楕円曲線のパラメータもいわゆる**prime256v1** というやつで安全そう。とくに捻ったところは見受けられない。

`ochazuke`の署名を作成するのが目的だが、`ochazuke`を含む文字列の署名は受け付けてくれない。

## 解法

ECDSAで異なる平文に対して同じ`k`を使ってはいけないというのは有名な話。だからこの場合も`k = Zn(ZZ(sha1(message).hexdigest(), 16)) * private_key`としてハッシュをとっている。

SHA1で。

まさかな、でもshatteredを使えばこれ解けるんだよな。

from sage.all import *
from binascii import hexlify, unhexlify
from hashlib import sha1
from ptrlib import Socket

EC = EllipticCurve(
    GF(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff),
    [-3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b]
)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 # EC.order()
Zn = Zmod(n)
G = EC((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
        0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))

def sign(private_key, message):
    z = Zn(int.from_bytes(message, "big"))
    k = Zn(ZZ(sha1(message).hexdigest(), 16)) * private_key
    assert k != 0
    K = ZZ(k) * G
    r = Zn(K[0])
    assert r != 0
    s = (z + r * private_key) / k
    assert s != 0
    return (r, s)

def verify(public_key, message, signature):
    r, s = signature[0], signature[1]
    if r == 0 or s == 0:
        return False
    z = Zn(int.from_bytes(message, "big"))
    u1, u2 = z / s, r / s
    K = ZZ(u1) * G + ZZ(u2) * public_key
    if K == 0:
        return False
    return Zn(K[0]) == r

with open("shattered-1.pdf", "rb") as f:
    data1 = f.read(320)

with open("shattered-2.pdf", "rb") as f:
    data2 = f.read(320)

assert data1 != data2
assert sha1(data1).hexdigest() == sha1(data2).hexdigest()

sock = Socket("localhost", 13005)
x, y = sock.recvregex("([0-9]+) : ([0-9]+)")
pubkey = EC((int(x), int(y)))

sock.sendlineafter("(hex): ", hexlify(data1))
r1, s1 = sock.recvregex("([0-9]+), ([0-9]+)")
sock.close()

sock = Socket("localhost", 13005)
sock.sendlineafter("(hex): ", hexlify(data2))
r2, s2 = sock.recvregex("([0-9]+), ([0-9]+)")

z1 = int.from_bytes(data1, "big")
z2 = int.from_bytes(data2, "big")

k = Zn(z1 - z2) / Zn(int(s1) - int(s2))
d = int((Zn(int(s1)) * k - z1) / Zn(int(r1)))

assert (d*G) == pubkey

ochazuke = b"ochazuke"
r,s = sign(d, ochazuke)
assert verify(pubkey, ochazuke, (r,s))

sock.sendlineafter("signature: ", "({}, {})".format(r, s))
print(sock.recvline())

`KosenCTF{ahhhh_ochazuke_oisi_geho!geho!!gehun!..oisii...}`

詰まらせてますやんか。

## 感想

あまりにも脆弱性がわからなさすぎて、まさかな……と思ったが、まさかだった。実際にはmediumくらいの難易度になってそう