Tough decisions

Champagne for my real friends, real pain for my sham friends.

Challenge contributed by CryptoHack

Challenge files:

• output.txt
• tough_decisions.py

Source code analysis

We are fiven a Python script that takes the flag as bits and, for each bit, it prints 6 outputs of either the real function (bit 0) or the fake function (bit 1):

if __name__ == "__main__":
    s = sample_key()
    for b in get_flag():
        print([[real, fake][b](s) for _ in range(6)])

Therefore, the objective is to find a way to differentiate between real and fake outputs in order to learn the bits of the flag.

Learning With Errors

The fake function returns just random bytes:

def fake(s):
    a = secrets.token_bytes(len(s))
    return a, secrets.randbelow(256)

Whereas real uses LWE (Learning With Errors) using s as key:

def real(s):
    a = secrets.token_bytes(len(s))
    e = sample_noise(7) - 64
    return a, (dot(a, s) + e) % 256

In LWE, the encryption works as follows:

Where we only know vector , modulus and the ciphertext . The dimension of the vectors and is , and all their elements are 8-bit numbers:

def sample_key():
    # LWE estimator told me I'd have more bits of security than bits in my key...
    return secrets.token_bytes(16)

Error distribution

Moreover, we know the possible values for the error :

def drbg():
    # wuch wow, very deterministic
    return secrets.randbelow(2)


def sample_noise(n):
    e = 0
    for _ in range(n):
        e |= drbg()
        e <<= 1
    return e

Since e = sample_noise(7) - 64, we observe that all errors are even numbers:

$ python3 -q
>>> import secrets
>>>
>>> def drbg():
...     # wuch wow, very deterministic
...     return secrets.randbelow(2)
...
>>>
>>> def sample_noise(n):
...     e = 0
...     for _ in range(n):
...         e |= drbg()
...         e <<= 1
...     return e
...
>>> {sample_noise(7) - 64 for _ in range(10000)}
{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, -64, -62, -60, -58, -56, -54, -52, -50, -48, -46, -44, -42, -40, -38, -36, -34, -32, -30, -28, -26, -24, -22, -20, -18, -16, -14, -12, -10, -8, -6, -4, -2}

Solution

So, we know that , and this is the oracle we need.

Moreover, since the flag is formed by ASCII bytes, we know that the most significant bit of every byte is . So, we already know some real outputs.

Using this knowledge, we can form this equation using samples:

Which is equivalent to this matrix equation:

It would be nice to find the value of . There are challenges related to LWE where it is possible to find by solving the Closest Vector Problem (CVP) using lattice reduction algorithms. However, it is not possible in this challenge because the errors are very large.

Instead, we can use the fact that all errors are even, so we can apply and find :

Therefore, we can find with at least 16 pairs of vectors and ciphertexts .

Once we have a value for , we can go through all the outputs we have, take each vector , multiply by and check if the ciphertext matches. If any of the 6 outputs we have for each bit of the flag does not match, we are sure that it is a fake output. Otherwise, if every 6 outputs match, with high probability we have a real output.

Flag

If we implement the above procedure, we will find the flag:

$ python3 solve.py
ECSC{D3c1s10n4l_LWE_m0d_2_445fb8dc91}

The full script can be found in here: solve.py.