Pederson

Se nos proporciona el código fuente en Python del servidor contiene la flag:

import os, random
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes, isPrime

FLAG = os.getenv("FLAG", "HackOn{goofy_flag}")

message = """
┌────────────────────────────────────────────────────────────────────────────────────────────────────┐
│This challenge uses the Pedersen Commitment Scheme to prove the knowledge of a secret to the server.│
│                       Can you convince me that you know the flag???                                │
└────────────────────────────────────────────────────────────────────────────────────────────────────┘
"""


def gen_params():
    """
    p = getPrime(512)
    q = 2*p + 1
    while not isPrime(q):
        p = getPrime(512)
        q = 2*p + 1
    """
    q = 17032131111613663616220932453285657100875982798803654483825551961255401977190250879374328409931719910151624310573638554219448137843402731248609029551378719
    g = random.randint(2, q-1)
    h = random.randint(2, q-1)

    return  q, g, h


print(message)

q,g,h = gen_params()
x = bytes_to_long(FLAG[:len(FLAG)//2].encode())
y = bytes_to_long(FLAG[len(FLAG)//2:].encode())
A = pow(g, x, q)*pow(h, y, q) % q

print(f"q = {q}\ng = {g}\nh = {h}\nA = {A}")

history = {"T":[], "s1":[], "s2":[]}
for _ in range(5):
    print(f"Round {_} to convince me, send  g^t1 * h^t2 mod q")

    k = random.randint(2, q-1)
    print(f"{k = }")

    T = int(input(">>> "))
    if T in history["T"]:
        print("Don't try to fool me")
        exit()
    history["T"].append(T)

    print("Now give me, s1 = t1 + k*x mod q and s2 = t2 + k*y mod q")
    s1 = int(input(">>> "))
    s2 = int(input(">>> "))

    if s1 in history["s1"] or s2 in history["s2"]:
        print("Don't try to fool me")
        exit()

    history["s1"].append(s1)
    history["s2"].append(s2)
    
    if pow(g, s1, q)*pow(h, s2, q) % q != T*pow(A, k, q) % q:
        exit()

print(f"Okay, not bad: {FLAG}")

Análisis del código fuente

El servidor implementa un protocolo de prueba de conocimento cero (ZKP, Zero-knowledge proof) basado en el esquema de compromiso de Pedersen. Wikipedia establece lo siguiente:

An example of an information-theoretically hiding commitment scheme is the Pedersen commitment scheme, which is computationally binding under the discrete logarithm assumption. Additionally to the scheme above, it uses another generator of the prime group and a random number . The commitment is set .

Si buscamos una explicación específica del uso de compromisos de pedersen para los protocolos de ZKP, podemos encontrar este increíble recurso de Trails of Bits. Simplemente copiaré aquí lo que dice:

Given a commitment , Alice can demonstrate to Bob that she knows and without revealing either or . This is a useful protocol for protecting against the additive properties of Pedersen commitments being used maliciously. The protocol works as follows:

This works because:

This is secure because, in order to trick Bob, Alice needs to break the discrete log problem.

Entonces, la idea de este protocolo de ZKP es que Alice está demostrando que sabe e sin revelar ninguno de los valores. Para esto, Alice calcula un compromiso y se lo envía a Bob. Luego, Bob verificará si el compromiso es válido, sin la necesidad de conocer e . Bob solo envía un número entero aleatorio y verifica si el compromiso es correcto con el valor (elegido por Alice) y (que dependen de ).

En este reto, estamos en la posición de Alice, necesitamos convencer al servidor (Bob) de que conocemos la flag… ¡pero no la sabemos!

Como se dice, para romper este protocolo ZKP, necesitamos poder resolver el problema de logaritmo discreto (DLP), que no es factible esta vez porque , por lo que está correctamente elegido. Por lo tanto, debe haber algo extraño en la implementación del protocolo.

Encontrar el defecto

El problema es que se nos envían al principio, antes de enviar el valor :

    print(f"Round {_} to convince me, send  g^t1 * h^t2 mod q")

    k = random.randint(2, q-1)
    print(f"{k = }")

    T = int(input(">>> "))

Como resultado, podemos hacer trampa porque podemos elegir en función del valor de .

Solución

Lo más simple es decir que , de manera que . Entonces simplemente podemos seleccionar , de forma que y la verificación se mantiene del lado de Bob.

Pero necesitamos probarlo 5 veces, y este enfoque solo funcionará una vez porque Bob guarda un histórico de valores usados de , y . Sin embargo, no es un problema en absoluto, porque podemos encontrar una solución más general:

• Para simplificar, seleccionemos el valor para y
• Luego
• Necesitamos que
• Entonces podemos hacer que y elegir un valor cualquiera para

Implementación

Entonces, se puede mentir en el protocolo de ZKP con el siguiente código (seleccioné como el número de a la ronda, porque sí):

def get_var(name: str) -> int:
    io.recvuntil(f'{name} = '.encode())
    return int(io.recvline())


io = get_process()

q = get_var('q')
g = get_var('g')
h = get_var('h')
A = get_var('A')

for r in range(5):
    k = get_var('k')

    s1 = s2 = r
    T = pow(A, -k, q) * pow(g * h, r, q) % q
    assert pow(g, s1, q) * pow(h, s2, q) % q == T * pow(A, k, q) % q

    io.sendlineafter(b'>>> ', str(T).encode())
    io.sendlineafter(b'>>> ', str(s1).encode())
    io.sendlineafter(b'>>> ', str(s2).encode())

io.success(io.recvline().decode())

Flag

Con todo esto, podemos capturar la flag:

$ python3 solve.py 0.cloud.chals.io 34487
[+] Opening connection to 0.cloud.chals.io on port 34487: Done
[+] Okay, not bad: HackOn{b4by_1ntr0_t0_z3r0_kn0wl33dg3:)}
[*] Closed connection to 0.cloud.chals.io port 34487

El script completo se puede encontrar aquí: solve.py.