InCTF 2020 | Bakflip & Sons - crypto-writeup-public

#!/usr/bin/env python3

import random, sys
from binascii import hexlify, unhexlify
from ecdsa import SigningKey, NIST192p
from flag import flag

secret_multiplier = random.getrandbits(101)

def menu():
    menu = [exit, signMessage, verifyMessage, getFlag, sys.exit]

    print("""
    bakflip&sons Signature Scheme

        1) Sign Message
        2) Verify Signature
        3) Get Flag
        4) Exit
    [ecdsa@cryptolab]# """, end = "")

    choice = int(input())
    menu[choice]()

def signMessage():
    print("""
    Sign Message Service - courtsy of bakflip&sons
    """)

    message = input("Enter a message to sign: ").encode()
    if message == b'please_give_me_the_flag':
        print("\n\t:Coughs: This ain't that easy as Verifier1")
        sys.exit()
    secret_mask = int(input("Now insert a really stupid value here: "))

    secret = secret_multiplier ^ secret_mask

    signingKey = SigningKey.from_secret_exponent(secret)
    signature = signingKey.sign(message)
    print("Signature: ", hexlify(signature).decode())


def verifyMessage():
    raise(
        NotImplementedError(
            "Geez! We are working round the clock to get this Beetle fixed."
        )
    )

def getFlag():
    print("""
    BeetleBountyProgram - by bakflip&sons

        Wanted! Patched or Alive- $200,000
        Submit a valid signature for 'please_give_me_the_flag' and claim the flag
    """)
    signingKey = SigningKey.from_secret_exponent(secret_multiplier)
    verifyingKey = signingKey.verifying_key
    try:
        signature = unhexlify(input("Forged Signature: "))
        if verifyingKey.verify(signature, b'please_give_me_the_flag'):
            print(flag)
    except:
        print("Phew! that was close")

       
if __name__=="__main__":
    for i in range(73): menu()

overview

73回まで、 sign または getFlag ができる
sign
- $mesg$ と $mask$ を入力にとって、 $d = secret \oplus mask$ とし、 NIST192p という EllipticCurve 上で ECDSA によって $mesg$ へ署名する
- ただし、平文に please_give_me_the_flag は渡せない
getFlag
$d = secret$ とし、署名を検証する。 please_give_me_the_flag という平文の検証に成功するとフラグ

考察

secret がわかれば解けそう
sign による署名でどうにかして secret を求めることができないか
- 平文と mask を渡せることの意図は……？
NIST192p を使っているので、単純な楕円曲線に対するアプローチではなさそう……？
何度も署名できるので、一部分ずつ secret を特定する OR 何回かのリクエストの結果を組み合わせて復元する……？
mesg は固定して良さそう
$d$ と $d\oplus 1$ による署名がそれぞれあった時なにかできることがあるか？
$d\oplus 1 = d \pm 1$ なので $d+1$ と $d-1$ について試してなんかする、みたいな感じか

$k_i$ がわかってないのでそれは難しそう……？

$s_1 k_1 = h + r_1d \mod n$

$s_2k_2 = h + r_2(d + 1) = h + r_2d + r_2 \mod n$

$s_1k_1 - s_2 k_2 = d(r_1 - r_2) - r_2 \mod n$

だめそう……

作戦1

$h, r_i, s_i$ は偶奇が分かっているので $d$ の偶奇がわからないか？
$s_1, s_2$ がそれぞれ偶数なら左辺は偶数になるので、右辺で $r_1-r2$ が奇数なら、 $d$ の偶奇がわかりそう
73回の制限が厳しい

解法

署名時の $r$ の算出における $dG$ について $(d\oplus mask) G$ を考える
- r, sからP=dGを求めるを使った
mask = 1 のとき $d$ が奇数であれば $dG - G$ 、 $d$ が偶数であれば $dG + G$ であるから
- mask = 0 のときの署名用の鍵 $dG$ と比較して $d$ の偶奇を得られる
同様にして mask = 1 << i として送ると、署名用の鍵が $dG \pm 2^iG$ になるので $d$ の $i$ bit目の偶奇を得られる
- ので、これを101回やることで $d$ 全体を復元できる
- が、今、73回までしかループを回せない
そこで、 mask = 0b11 << 2*i として送ることで、一度のクエリで2bitの情報を得ることにする
$d$ の該当するbitが 00 なら $dG + 2^{2i}G + 2^{2i+1}G$ となる
$d$ の該当するbitが 01 なら $dG - 2^{2i}G + 2^{2i+1}G$ となる
$d$ の該当するbitが 10 なら $dG + 2^{2i}G - 2^{2i+1}G$ となる
$d$ の該当するbitが 11 なら $dG - 2^{2i}G - 2^{2i+1}G$ となる

from ecdsa import SigningKey, NIST192p
from ecdsa.ecdsa import Signature
from hashlib import sha1
from itertools import product
from ptrlib import Socket

mesg = b"hello"
h = int.from_bytes(sha1(mesg).digest(), "big")
G = NIST192p.generator

sock = Socket("localhost", 19999)
def oracle(mask):
    sock.sendlineafter("# ", "1")  # sign

    sock.sendlineafter(": ", mesg)
    sock.sendlineafter(": ", str(mask))

    rs = bytes.fromhex(sock.recvlineafter(": ").decode())
    return int.from_bytes(rs[:len(rs)//2], "big"), int.from_bytes(rs[len(rs)//2:], "big")

def recover_public_keys(r, s):
    return [key.point for key in Signature(r, s).recover_public_keys(h, NIST192p.generator)]

r, s = oracle(0)
dGs = recover_public_keys(r, s)

r, s = oracle(1)
d_Gs = recover_public_keys(r, s)
for P, P_ in product(dGs, d_Gs):
    if P_ == P + G or P_ == P + -G:
        break
else:
    raise Exception("a")

print("[+] P = ({}, {})".format(P.x(), P.y()))

d = 0
for k in range(0, 101, 2):
    r, s = oracle(0b11 << k)
    d_Gs = recover_public_keys(r, s)

    found = False
    for d_G in d_Gs:
        cands = [
            P + (+2**k + 2**(k+1))*G,
            P + (-2**k + 2**(k+1))*G,
            P + (+2**k - 2**(k+1))*G,
            P + (-2**k - 2**(k+1))*G,
        ]
        try:
            i = cands.index(d_G)
            d = d | (i<<k)
            break
        except ValueError:
            pass
    else:
        raise Exception("b at {}".format(k))

print("[+] d = {}".format(d))

# make sign
msg = b'please_give_me_the_flag'
key = SigningKey.from_secret_exponent(d)
signature = key.sign(msg)

sock.sendlineafter("# ", "3")  # getFlag
sock.sendlineafter(": ", signature.hex())
print(sock.recvline())