Writeup For: ZKP HSCTF 8
I thought this problem was just a troll. Realize that a solution is invalid if a clause has all false-valued literals. If we assume the literal values are completely random, they have a 7/8 chance of being valid. If you ask k random clauses for their values, you have a 1 - (7/8)^k chance of having at least one invalid clause, which is pretty high. This means if you test k clauses and they're all valid, it is likely a valid solution, otherwise it is definitely invalid. You can probably use bayes' theorem for better analysis on the probability of this being correct, but it is an easily guessable problem with little insight :(.
from pwn import * import random #init p = remote('zkp.hsc.tf', 1337) #vars k = 5 #exploit p.recvline() t = int(p.recvline(keepends = False)) print(t) for i in range(t): n = int(p.recvline(keepends = False)) m = int(p.recvline(keepends = False)) print(i, n, m) f = True for i in range(k): p.sendlineafter(': ', str(random.randint(1, n))) if not 'True' in p.recvlineS(): f = False p.sendline('next') p.sendlineafter(': ', '1') if not 'True' in p.recvlineS(): f = False print(f) p.sendline(str(f).lower()) #pray for flag p.interactive()