Shutlock - Frozen Love

J’ai entendu dire qu’on pouvait forger des preuves sur mon implémentation de schnorr, imposer le commitment devrait résoudre le problème non ? Pas besoin de complétude de toute façon…

Source : frozen_love.py

SHA-256 : 2e3aca6a674261d62846322c7326a610cfbee595a577152f9a71ebc20e87a2c2 Link to heading

Présentation Link to heading

Frozen Love est une implémentation de Schnorr qui est ratée. Nous avons le code suivant:

import os
import socket
import hashlib
from sage.all import *
from json import loads, dumps

# secp256k1
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
K = GF(p)
E = EllipticCurve(K, [0, 7])
G = E(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
q = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

FLAG = os.getenv("FLAG", "SHLK{test}")


def sendline(f, data):
    f.write(data + b"\n")
    f.flush()


def Fiat_Shamir(R, G):
    h = hashlib.sha256()
    h.update(hex(int(R.xy()[0])).encode())
    h.update(hex(int(G.xy()[0])).encode())
    return int(h.hexdigest(), 16) % q

def setup():
    secret_r = ZZ.random_element(q)
    R = secret_r * G
    return R


def verify(Y, s, R):
    c = Fiat_Shamir(R, G)
    left_side = s * G
    right_side = R + (c * Y)
    return left_side == right_side


def handle(c):
    f = c.makefile("rwb")

    R = setup()
    sendline(f, b"If you want to prove something,you will have to use MY commitment! \n")

    coords = R.xy()
    payload = dumps((hex(int(coords[0])), hex(int(coords[1]))))
    sendline(f, b"Here it is:\n")
    sendline(f, payload.encode())
    sendline(f, b"Now try to give me a valid proof with that...")

    line = f.readline()
    if not line:
        return

    try:
        resp = loads(line)
        Y = E(int(resp["Y"][0], 16), int(resp["Y"][1], 16))
        s = int(resp["s"])
        valid = verify(Y, s, R)
    except Exception:
        valid = False

    if valid:
        sendline(f,FLAG.encode())
    else:
        sendline(f,b"Nope!")


server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)

server.bind(("0.0.0.0", 8000))
server.listen()

while True:

    c, _ = server.accept()
    try:
        handle(c)
    except (OSError, EOFError):

        pass 

    finally:
        c.close()

Si bien implémenté, c’est un algorithme très sérieux et robuste, mais ici nous avons un faiblesse au niveau de l’implémentation. En effet, dans un fonctionnement normal, les vérifications sont faites dans un ordre précis et le client ne doit pas avoir le contrôle de Y et de s, or dans notre cas, le serveur nous envoie R et c, puis c’est à nous de choisir Y et s.

ce raccourci nous permet d’influer sur l’équation de vérification s.G == R + c.Y

Et comme Y n’a pas été fixé en amont, n’importe quelle valeur est donc valide.

Exploitation Link to heading

Maintenant que nous avons notre angle d’attaque, nous allons pouvoir écrire notre exploitation en fixant s arbitrairement et résoudre l’équation de vérification pour Y.

c.Y = s.G - R puis Y = c^-1.(s.G-R)

je m’excuse si mon niveau d’explication est mauvais, mais je suis une bille en mathématique.

Le script Link to heading

from sage.all import *
from pwn import *
import hashlib
from json import loads, dumps

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
K = GF(p)
E = EllipticCurve(K, [0, 7])
G = E(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
      0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
q = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

def Fiat_Shamir(R, G):
    h = hashlib.sha256()
    h.update(hex(int(R.xy()[0])).encode())
    h.update(hex(int(G.xy()[0])).encode())
    return int(h.hexdigest(), 16) % q

io = remote("57.128.112.118", 10958)

payload = None
for _ in range(10):
    line = io.recvline().decode().strip()
    print("GOT:", repr(line))
    if line.startswith('["0x') or line.startswith('[ "0x'):
        payload = line
        break

rx, ry = loads(payload)
R = E(int(rx, 16), int(ry, 16))

c = Fiat_Shamir(R, G)

s = 1
c_inv = inverse_mod(c, q)
Y = c_inv * (s * G - R)

resp = dumps({
    "Y": (hex(int(Y.xy()[0])), hex(int(Y.xy()[1]))),
    "s": str(s)
})

io.sendline(resp.encode())
print(io.recvall(timeout=3))

Dans ce script, sage est utilisé pour GF(), EllipticCurve(), E(), .xy() et inverse_mod(). Pour ceux qui ont déjà vu mes writeups, inverse_mod() je le remplace habituellement par pow(c,-1,q), mais comme la librairie était chargée, autant en profiter.

SHLK{F1aT_Sh4m1r_TR4nsF0rM_21aebc78_912884021471848092148}