Crypto-Pwn2Win-2017-Differential-Privacy

Differential Privacy

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

Server: nc 200.136.213.143 9999

We accessed the service and we try to get the info.

Hello, chose an option:
[1] Info
[2] Query the flag (in ASCII)
[3] Quit
1
You can query the flag, but the characters are private (indistinguishable).
Differential privacy mechanism: Laplace
Sensitivity: ||125 - 45|| = 80
Epsilon: 6.5

From this information we know that maybe the service is using a differential privacy mechanism to hide the flag. We also know that the mechanism is “Laplace”.
After a little research, we found the explanation of the differential privacy mechanism using the Laplace distribution. In this mechanism, the original value is added to a random value that obeys the Laplace distribution. This random value from the Laplace distribution is called laplace noise.
The specific laplace distribution used in differential privacy is Laplace(0, sensitivity/epsilon). For more information on the Laplace distribution follow https://en.wikipedia.org/wiki/Laplace_distribution.

anonymized = original + random_from_laplace

We query the flag and obtain:

Hello, chose an option:
[1] Info
[2] Query the flag (in ASCII)
[3] Quit
2
[75, 86, 83, 36, 56, 87, 146, 54, 97, 118, 110, 132, 101, 118, 120, 118, 112, 91, 103, 88, 140, 112, 110, 112, 120, 64, 95, 73, 97, 96, 114, 98, 113, 112, 113, 110, 118]

So, maybe, the service is adding laplace noise to the ASCII values (integer) of the flag.

If we query again, the values are different:

Hello, chose an option:
[1] Info
[2] Query the flag (in ASCII)
[3] Quit
2
[64, 82, 67, 35, 71, 82, 118, 74, 95, 128, 98, 92, 108, 102, 123, 107, 94, 99, 103, 78, 102, 98, 111, 101, 114, 113, 111, 135, 97, 74, 92, 107, 93, 114, 111, 90, 128]

We know that Laplace(0, sensitivity/epsilon) has average 0. So, if we average sufficient anonymized records of the flag, the random noise added will be canceled (because the average of the Laplace is 0), and the original value of the flag is obtained.

So, the trick here is to query the flag plenty of times (we queried 10000 times) and average each entry.

Here is sample code:

from pwn import *

def get_list():
    r = remote('200.136.213.143', 9999)
    r.recvline()
    r.recvline()
    r.recvline()
    r.recvline()
    r.send("2\n")
    return eval(r.recvline())

d = []

for i in range(37):
    d.append(list())

for i in range(10000):
    if i % 10 == 0:
        print i

    l = get_list()
    for j in range(len(l)):
        d[j].append(l[j])

for i in range(37):
    av = sum(d[i]) / len(d[i])
    result.append(int(round(av)))

print result

print "".join([chr(c) for c in result])

At the end, we obtain the flag:

CTF-BR{I_am_just_filtering_the_noise}

EDIT: bug in the source code. Thank you LFChang.