Poison | hotwater

Crypto, Medium, 200 pts

Flag: flag{p01s0n3d_3cc_f4u1t_4tt4ck_succ3ss!}

We get chall.py (and a Sage port, chall.sage) and out.txt. The challenge is ElGamal over P-192 (secp192r1) where the flag, read as a big integer, is the private key d, and Q = d*G. A plaintext point M is encrypted as C1 = k*G, C2 = M + k*Q. out.txt holds the plaintexts ms, the ciphertexts C1s, C2s, and decs, the outputs of a "faulty hardware" decryption.

The fault is a single bit flip of the private key per sample. In chall.py, sample number count flips string index total_bits - 1 - count of the MSB-first binary string, which is bit count counting from the LSB. So sample i decrypts with d_i = d +/- 2^i: plus if bit i of d is 0, minus if it is 1.

Since Q = d*G and C1 = k*G:

text

dec = C2 - d_i*C1 = M + (d - d_i)*C1
dec - M = +2^i * C1   if bit i is 1
dec - M = -2^i * C1   if bit i is 0

Because we know M, C1 and dec for every sample, each one reveals one key bit by comparing dec - M with 2^i * C1. There is no discrete log to solve.

python

import ast

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
a = 0xfffffffffffffffffffffffffffffffefffffffffffffffc
b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
G = (0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
     0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811)

def add(P, Q):
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None
    if P == Q:
        m = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:
        m = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (m * m - x1 - x2) % p
    return (x3, (m * (x1 - x3) - y1) % p)

def neg(P):
    return None if P is None else (P[0], (-P[1]) % p)

def sub(P, Q):
    return add(P, neg(Q))

def mul(k, P):
    R = None
    while k > 0:
        if k & 1:
            R = add(R, P)
        P = add(P, P)
        k >>= 1
    return R

data = {}
for line in open("out.txt"):
    name, value = line.strip().split(" = ", 1)
    data[name] = ast.literal_eval(value)

ms, C1s, decs = data["ms"], data["C1s"], data["decs"]
L = len(ms)

bits = [0] * L          # bits[i] is bit i, counting from the LSB
for i in range(L):
    D = sub(decs[i], ms[i])
    T = mul(1 << i, C1s[i])
    if D == T:
        bits[i] = 1
    elif D == neg(T):
        bits[i] = 0
    else:
        raise ValueError(f"bit {i} did not match")

s = "".join(str(bits[i]) for i in range(L - 1, -1, -1))
d = int(s, 2)
flag = d.to_bytes((d.bit_length() + 7) // 8, "big")
print(flag)

This prints b'flag{p01s0n3d_3cc_f4u1t_4tt4ck_succ3ss!}'. As a check, the recovered d decrypts every ciphertext to the matching ms[i]. The same script is solve.py.

Related writeups