Rating:

[writeup by @dantt]

**CTF:** Pwn2Win CTF 2017

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

**Task:** crypto / differential privacy

**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).