Rating:

[writeup by @dantt]

**CTF:** Pwn2Win CTF 2017

**Team:** spritzers (from [SPRITZ Research Group](http://spritz.math.unipd.it/))

**Points:** 173


Is it possible to have privacy on these days? The Rebelious Fingers do not think so. Get the flag.


We're given a server to connect to, which prompts us with the following:


Hello, chose an option:
[1] Info
[2] Query the flag (in ASCII)
[3] Quit


If we select 1 we discover interesting information:

1
You can query the flag, but the characters are private (indistinguishable).
Differential privacy mechanism: Laplace
Sensitivity: ||125 - 45|| = 80
Epsilon: 6.5

The scheme employed is then differential privacy, with Laplace additive noise. This means that the computed function (or query) on the "database" is perturbed with random noise, drawn from a Laplace distribution. The challenge also tells us some information about this: the security parameter epsilon (capturing information about the variance of the specific Laplace distribution, and the sensitivity of the computer function.
In particular, this hints that the computed function is actually very simple: ord(char) + noise. Indeed, sensitivity here is the maximum absolute difference between the minimum and maximum values that the function can have. Interestingly, chr(125) = } and chr(45) = -, which we expect to be part of the flag.

If we query the flag, we have confirmation of this:


2
[80, 79, 95, 49, 48, 79, 149, 46, 87, 126, 123, 131, 91, 109, 105, 120, 97, 80, 89, 93, 142, 125, 114, 104, 111, 61, 85, 74, 89, 91, 126, 83, 103, 119, 99, 101, 111]


Interpreting this as ASCII characters, we find a nonsensical PO_10O\x95.W~{\x83[mixaPY]\x8e}rho=UJY[~Sgwceo, as every character is perturbated by some random amount.

If we query again the flag within the same connection, we obtain the same encrypted string. However, if we reconnect, we get a different perturbation of the flag. This means that the task is very easy: Laplace distribution has zero mean - it is symmetric and zero-centered. Therefore, if we query the flag enough times, and average character-by-character, we eventually cancel out the noise. We setup a simple script to do it:

python
from pwn import *
import ast
import numpy as np

guess = []

for __ in range(1000):
p = remote("200.136.213.143", 9999)

p.recvuntil("Quit")
p.sendline("2")
guess.append(ast.literal_eval(p.recvuntil("]").strip("\n")))
print "".join([chr(int(round(xx))) for xx in np.mean(guess, axis=0)])
p.close()

print guess


1000 iterations are not enough to obtain perfect cancellation, but good enough for a bit of manual tweaking, giving us the flag:
CTF-BR{I_am_just_filtering_the_noise}

Original writeup (https://github.com/SPRITZ-Research-Group/ctf-writeups/tree/master/pwn2win-2017/crypto/differential_privacy).