CYBER APOCALYPSE CTF 2021 | Forge of Empires

cyber_apocalypse_ctf_2021 elgamal署名

#cyber_apocalypse_ctf_2021

from random import randint
from math import gcd
from Crypto.Util.number import long_to_bytes, bytes_to_long

def gen_keys():
    x = randint(1, p-2)
    y = pow(g, x, p)
    return (x, y)

def sign(message: str, x: int):
    while True:
        m = int(message, 16) & MASK
        k = randint(2, p-2)
        if gcd(k, p - 1) != 1:
            continue 
        r = pow(g, k, p)
        s = (m - x*r) * pow(k,-1,p-1) % (p - 1)
        if s == 0:
            continue
        return (r,s)

def verify(message: str, r: int, s: int, y: int):
    m = int(message, 16) & MASK
    if any([x <= 0 or x >= p-1 for x in [m,r,s]]):
        return False
    return pow(g, m, p) == (pow(y, r, p) * pow(r, s, p)) % p

def get_flag(message: str, r: int, s: int, y: int):
    if b'get_flag' not in bytes.fromhex(message):
        return 'Error: message does not request the flag'
    elif verify(message, r, s, y):
        return FLAG
    else:
        return 'Error: message does not match given signature'

if __name__ == "__main__":
    import os
    os.chdir(os.path.abspath(os.path.dirname(__file__)))

    with open("flag.txt", 'rb') as f:
        FLAG = f.read()

    p = 2**1024 + 1657867
    g = 3
    MASK = (2**p.bit_length() - 1)

    x, y = gen_keys()
    print(f"Server's public key: {y}")
    
    print(f'Please send your request message and signature (r,s)')

    message = input('message: ')
    r = int(input('r: '))
    s = int(input('s: '))

    flag = get_flag(message, r, s, y)
    print(flag)

overview

  • #Elgamal署名

  • get_flag を含むメッセージとそれについての署名を送って、向こうで検証に成功すればフラグがもらえる

  • sign , verify では message のビット数を MASK で制限している

solution

  • 基本的に公開鍵から署名を作ることはできないので解けないように見えるが、 get_flag で文字列が b"get_flag" を含んでいるか確認したあと、 verify では m = message & MASK と値を切り落としているので、 message = b"get_flag\0\0...\0m" としておけば、 verify ではすきな m の署名を検証してもらえる

  • m, r, s 自由に決めていい時は署名を偽造するのはそんなに難しくなくて、 t を好きにえらんで次のように値を決めれば通る

    • r = g^ty \pmod{p}

    • s \equiv -r \pmod{q}

    • m \equiv ts \pmod{q}

  • たしかめておく

  • g^m \equiv g^{ts} \mod p

  • y^rr^s \equiv y^rg^{ts}y^s \equiv y^{r-r}g^{ts} \equiv g^{ts} \mod p

from random import randint
from math import gcd
from Crypto.Util.number import long_to_bytes, bytes_to_long

p = 2**1024 + 1657867
MASK = (2**p.bit_length() - 1)
g = 3

def forgery(y: int):
    e = randint(1, p-1)
    r = y*pow(g,e,p) % p
    s = -r % (p - 1)
    m = (e*s) % (p-1)
    m += (bytes_to_long(b'get_flag') << 1200)
    M = hex(m)[2:]
    return(M,r,s)

y = int(input('public key: '))
M, r, s = forgery(y)
print(f'M: {M}')
print(f'r: {r}')
print(f's: {s}')