Pederson

5 minutes to read

We are given the Python source code of the server contains the 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}")

Source code analysis

The server implements a Zero-knowledge proof (ZKP) protocol based on Pedersen commitment scheme. Wikipedia states the following:

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 .

If we search for a specific explanation of the use of Pedersen commitments for ZKP protocols, we can find this awesome resource by Trails of Bits. I’ll just copy here what it says:

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.

So, the idea of this ZKP protocol is that Alice is proving that she knows and without revealing any of them. For this, Alice computes a commitment and sends it to Bob. Then, Bob will check if the commitment is valid, without the need of knowing and . Bob only sends a random integer and checks if the commitment holds with the value (chosen by Alice) and (which depend on ).

In this challenge, we are in the position of Alice, we need to convince the server (Bob) that we know the flag… But we don’t!

As it is said, in order to break this ZKP protocol, we need to be able to solve the discrete logarithm problem (DLP), which is not feasible this time because , so it is correctly chosen. Therefore there must be something weird in the protocol implementation.

Finding the flaw

The problem is that is sent to us at the begining, before we send the value :

    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(">>> "))

As a result, we are able to cheat because we can choose considering the value of .

Solution

The simplest thing is to say that , so that . Then we can simply select , so that and the verification holds on Bob’s side.

But we need to prove it 5 times, and this approach will only work once because Bob keeps a set of used values for , and . However, it is not a problem at all, because we can come up with a general solution:

To simplify, let’s choose the value for both and
Then
We need that
So we can simply set and choose an arbitrary value for

Implementation

So, the ZKP protocol is cheated with the following code (I selected to be the round number, just because):

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

With all this, we can capture the 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

The full script can be found in here: solve.py.