crypik-pisang

Solved by: grb

This is what the challenge looks like, and we're given a single python script and its output.

Next, lets check out the python script and its output

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import bytes_to_long
from hashlib import sha256
from sage.all import *

KEY = open('flag.txt','rb').read().strip()
IV = KEY
p = 730750818665451459112596905638433048232067471723  
A,B =425706413842211054102700238164133538302169176474,203362936548826936673264444982866339953265530166
G = [125270202464411072778547771568975423382990845665,440970603958123875213441435758390311809187352362]

def encrypt(pts,p,a,b,G):
    E = EllipticCurve(GF(p),[a,b])
    cipher = AES.new(KEY, AES.MODE_CBC, IV)
    pts = [pts[i:i+16] for i in range(0, len(pts), 16)]
    finalct = []
    for pt in pts:
        ct = cipher.decrypt(pt)
        finalct.append(((E(G)*bytes_to_long(ct)).xy()[0],'ctx integrity: '+sha256(ct).hexdigest()))
    return finalct
    
print(encrypt(bytes.fromhex('bbbaaaddddccbbbbcccceeeccccccccc00000000000000000000000000000000bbbaaaddddccbbbbcccceeeccccccccc'),p,A,B,G))

[(100654093910178233482450277206809830661175065544, 'ctx integrity: 89612ef59e59993819e24dae93de2a9f7b5074b08cf677845f47f62fb7a020a5'), (132397736471501983656177189507553060216798395572, 'ctx integrity: 268cf3e32e6acc33912e4a6e92acfd9c49be15e5e88d99695938f00899c5363a'), (155421885985212557386540695456623238477786438216, 'ctx integrity: 2def65db2c4a902b233e8da2e8cde2ab54f29dbd1e59dde356f958a2cadb193a')]

So, the python script reads a 16-byte secret KEY (also used as the AES IV), AES-CBC-decrypts supplied 16-byte ciphertext blocks, and for each decrypted 16-byte block d it outputs two things:

1. The x-coordinate of the elliptic-curve point d · G (i.e. scalar multiplication of generator G by the integer d).
2. A SHA-256 tag of the raw 16-byte block d (sha256(d)).

The challenge provides three such leaked tuples (x, "ctx integrity: <sha256>") for three ciphertext blocks. Our goal is to recover the KEY (the flag).

We can recover the plaintext scalars for two blocks by solving EC discrete logs (using the leaked x-coordinate and verifying with sha256(d)), then XOR the two recovered 16-byte scalars (blocks) to obtain the AES key that yields the flag. This is our attack algorithm :

1. Let the x-coordinate be x_i and the corresponding SHA-256 hex digest h_i.
2. For a chosen x_i:
   • Use E.lift_x(x_i, all=True) to get the 1 or 2 candidate curve points with that x-coordinate.
   • For each candidate point Q, compute the discrete log k = discrete_log(Q, G) (i.e. find k such that k·G = Q).
   • Convert k to 16 bytes k_bytes = k.to_bytes(16, 'big') and compute sha256(k_bytes).hexdigest(); if it equals h_i, accept this k as the correct block value.
3. Repeat for p1 and p3 (the leaked first and third outputs in the challenge). Let these recovered scalars be k1 and k3.
4. Compute KEY = k1 ^ k3 (bitwise XOR on the integers, or XOR on the 16-byte sequences) and convert to ASCII — that's the flag.

You can check out the attack algorithm code here and try it your own.

Flag : compit{bad_parameters!!}

PO- PO- PO- PWNED!!!