Click to expand challenge code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#!/usr/bin/env python3
"""
Prove you know a satisfying assignment without revealing it—1 take per round, no pain.
Protocol (each round):
 1) Commit to each bit of your assignment.
 2) I'll challenge you >:)
 3) I'll pen either the full assignment or just the clause bits.
 4) Survive all 128 rounds, and I might just give yout the flag.
"""
import random
import hashlib
from Crypto.Util.number import isPrime, long_to_bytes, bytes_to_long
import os

P  = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
q  = 0xffffffffffffffffffffffff99def836146bc9b1b4d22831
h1 = 0x61a59ed8c6883f7ddfc05e18417627ce6501702d350d0dd5
h2 = 0x9a7b45924acce1f9131607e5c12438f6222a7d15196631e7
comm_params = (P, q, h1, h2)

FLAG = os.getenv("FLAG", b"FL1TZ{dummy_dum_dum}")
PURPLE = "\x1b[35m"
COLOR_RESET = "\x1b[0m"

def pedersen_commit(message: int, params=comm_params):
    r = random.randrange(q)
    C = (pow(h1, message, P) * pow(h2, r, P)) % P
    return C, r


def pedersen_open(C: int, m: int, r: int, params=comm_params) -> bool:
    return (C * pow(h1, -m, P) * pow(h2, -r, P)) % P == 1

def update_transcript(state: bytes,
                      commitments: list[int],
                      openings: list[tuple[int,int]],
                      masks: list[int]) -> bytes:
    h = hashlib.sha256()
    h.update(state)
    for C in commitments:
        h.update(C.to_bytes(32,'big'))
    for (bit,r), mask in zip(openings, masks):
        h.update(bytes([bit]))
        h.update(r.to_bytes(32,'big'))
        h.update(bytes([mask]))
    return h.digest()
"""
Here's a satisfiable formula for testing purposes

n = 4
clauses = [
    [(1, True),  (2, False), (3, True)],
    [(1, False), (2, True),  (4, True)]
]
alpha = [True,False,True,True]
"""

# But where's the fun in that?
# Here's the real challenge, even Novacain won't help you with this one!

n = 5
clauses = [
    [(1, False), (2, True),  (3, False)],
    [(3, False), (4, True),  (5, False)],
    [(2, True),  (4, True),  (1, False)],
    [(2, True),  (4, True),  (3, False)],
]
alpha = [True,False,True,False,True]


rounds = 128
def main():
    m = len(clauses)
    print(HEADER)
    print("Are you worth calling yourself a hero? We're about to find out...")

    FS_state = b""
    for rn in range(rounds):
        print(f"\n{PURPLE}[round {rn+1}/{rounds}]{COLOR_RESET}")

        print("Are you committed? PROVE IT:")
        A = []
        for i in range(n):
            c =   int(input(f"C {i+1}    > "))
            A.append(c)

        print("Lay down your openings:")
        openings = []
        for i in range(n):
            bit = int(input(f"bit  {i+1} > "))
            r   = int(input(f"r  {i+1}   > "))
            openings.append((bit, r))

        print("Take off your masks:")
        masks = []
        for i in range(n):
            mask= int(input(f"mask {i+1} > "))
            masks.append(mask)

        FS_state = update_transcript(FS_state, A, openings, masks)
        chal = bytes_to_long(FS_state) & m

        if chal == 0:
            for i in range(n):
                bit, r = openings[i]
                if not pedersen_open(A[i], bit, r):
                    print("Commitment break! No flag!")
                    exit(0)
                expected = (1 if alpha[i] else 0) ^ masks[i]
                if bit != expected:
                    print("Wrong note in the solo! You're off-key.")
                    exit(0)

        else:
            idx = chal - 1
            lits = clauses[idx]
            sat = False
            for (var, pol) in lits:
                bit, r = openings[var-1]
                if not pedersen_open(A[var-1], bit, r):
                    print("Commitment break! No flag!")
                    exit(0)
                val = bool(bit) ^ bool(masks[var-1])
                if (val and pol) or (not val and not pol):
                    sat = True
            if not sat:
                print(f"The idiot isn't always american after all...")
                exit(0)

        print(f"You're in tune! Round {rn+1} complete.")

    print("Well well well, guess you can find your way in blind alleys.")
    print(FLAG)

if __name__ == '__main__':
    try:
        main()
    except Exception as e:
        print(f"An error occurred: {e}")
        exit(1)

Now we’re getting into intermediate territory. This is the only ZKP challenge in the ctf, and considering that not many ctfs in tunisia incorporate zero knowledge proofs in crypt challenges, I thought that this one might be alien to them, (espceially since I hit them with pedersen commits from the get go xd)

Surprisingly, a good chunk of players managed to solve it! 15 teams exactly at the time of writing this. Even though some usually used LLMs to solve it, at least they learned something new, and prepare themselves for future ZKP tasks, they won’t be this easy x)

Analysis

NIZK

This task is a classic Non Interactive Zero Knowledge protocol NIZK where players are demanded to find a satisfying assignment for the 3-SAT problem, for clauses that are impossible to satisfy!

The Zero Knowledge property of this protocol is realize using pedersen commitments, which basically Bind the prover and Hide the underlying committed statement.
The security of this operation is fortified by the Discrete Log Problem, meaning that theoretically, it can only be broken if you break DLP (aka: weak curve, small subgroup… or attack relevant in the realm of DLP)

Unfortunately for players, h1 and h2 were securely generated (they’re derived from the hash of some value, I forgot exactly how), the point is, there is no known log for these two values in $GF(p)$, so this is out of the question.

There is another protocol in play here, the one assuring the Non Interactive part of the operation: it’s the Fiat Shamir Transformation which derives an appropriate challenge based from a random oracle which in this case is a hash value. This ensures the Soundness property of zero knowledge proofs, but is it implemented correctly here?

Implementation

1
2
FS_state = update_transcript(FS_state, A, openings, masks)
chal = bytes_to_long(FS_state) & m

Hmmmmmm, isn’t the FS transform supposed to derive a challenge from a random oracle? A hash could be considered as a random oracle under ideal circumstances, but only if it is resistant to Preimage attacks! The derived challenge here is only 2 bits, derived from the commitment of the prover. Those 2 bits are vulnerable to some sort of a preimage attack since it’s derived every single round!

Looking at the two cases (where chal==0 and otherwise):

Chal = 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
if chal == 0:
    for i in range(n):
        bit, r = openings[i]
        if not pedersen_open(A[i], bit, r):
            print("Commitment break! No flag!")
            exit(0)
        expected = (1 if alpha[i] else 0) ^ masks[i]
        if bit != expected:
            print("Wrong note in the solo! You're off-key.")
            exit(0)

In this case, the server only checks if the commitment is sound, which should’t be an issue if you correctly implement predersen commit

Chal != 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
idx = chal - 1
lits = clauses[idx]
sat = False
for (var, pol) in lits:
    bit, r = openings[var-1]
    if not pedersen_open(A[var-1], bit, r):
        print("Commitment break! No flag!")
        exit(0)
    val = bool(bit) ^ bool(masks[var-1])
    if (val and pol) or (not val and not pol):
        sat = True
if not sat:
    print(f"The idiot isn't always american after all...")
    exit(0)

In this case, the server actually checks if the masks we’re committing to actually verify a clause, which is literally impossible since they’re logically unverifiable: We should avoid this case at all cost!

Solution

Since we now know that we want the challenge to always equal 0, we can compute the FS_STATE locally before sending our commitment to the server, and only send it if the resulting challenge bit it zero!

We keep on doing that for 128 rounds and the server will spit out a flag

Solver

Click to expand solver code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import hashlib
import random
from Crypto.Util.number import bytes_to_long
from pwn import *
from tqdm import trange
P  = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
q  = 0xffffffffffffffffffffffff99def836146bc9b1b4d22831
h1 = 0x61a59ed8c6883f7ddfc05e18417627ce6501702d350d0dd5
h2 = 0x9a7b45924acce1f9131607e5c12438f6222a7d15196631e7
comm_params = (P, q, h1, h2)

def pedersen_commit(m):
    r = random.randrange(q)
    C = (pow(h1, m, P) * pow(h2, r, P)) % P
    return C, r


def pedersen_open(C: int, m: int, r: int, params=comm_params) -> bool:
    return (C * pow(h1, -m, P) * pow(h2, -r, P)) % P == 1

def update_transcript(FS_state: bytes,
                      commitments: list[int],
                      openings: list[tuple[int,int]],
                      masks: list[int]) -> bytes:
    h = hashlib.sha256()
    h.update(FS_state)
    for C in commitments:
        h.update(C.to_bytes(32,'big'))
    for (bit,r), mask in zip(openings, masks):
        h.update(bytes([bit]))
        h.update(r.to_bytes(32,'big'))
        h.update(bytes([mask]))
    return h.digest()

def commit_to_masks(masks):
    commits = []
    openings = []
    for i in range(len(masks)):
        C, r = pedersen_commit(masks[i])
        commits.append(C)
        openings.append((masks[i], r))
    return commits, openings

# --- Known LocalTest formula + assignment: ---
n = 5
clauses = [
    [(1, False), (2, True),  (3, False)],
    [(3, False), (4, True),  (5, False)],
    [(2, True),  (4, True),  (1, False)],
    [(2, True),  (4, True),  (3, False)],
]
alpha = [True,False,True,False,True]
m = len(clauses)

rounds = 128

FS_state = b""
io = remote("20.218.234.6", 1001)
for rn in trange(rounds):
    io.recvuntil(b"PROVE IT:\n")

    while True:
        Last_state = FS_state
        masks = [random.choice([0,1]) for i in range(n)]
        alpha_mask = [(1 if alpha[i] else 0) ^ masks[i] for i in range(n)]
        commits, openings = commit_to_masks(alpha_mask)


        Last_state = update_transcript(Last_state, commits, openings, masks)
        chal = bytes_to_long(Last_state) & m
        if chal == 0:
            FS_state = Last_state
            break
    pmasks = masks
    pops   = openings
    for i in range(n):
        bit, r = pops[i]
        assert pedersen_open(commits[i], bit, r)
        expected = (1 if alpha[i] else 0) ^ pmasks[i]
        assert bit == expected

    for i in range(n):
        io.sendlineafter(b" > ", str(commits[i]).encode())
    for i in range(n):
        bit, r = openings[i]
        io.sendlineafter(b" > ", str(bit).encode())
        io.sendlineafter(b" > ", str(r).encode())
    for i in range(n):
        io.sendlineafter(b" > ", str(masks[i]).encode())

io.interactive()

FL1TZ{B0ul3v4rD_0f_Br0k3n_C0mM1tm3nts}