dqi/custom_protocol.md Secret

## custom_protocol.md

      
    Raw
  

              custom_protocol.md
            
          
    Challenge description

Custom Protocol

I like to implement crypto myself. Please, take a look at my new
implementation. It looks amazing, right?


Category: Cryptography
Points: 420
Solves: 5

Introduction

Another year, another GoogleCTF write-up, it's becoming somewhat of a personal
tradition! This year I went for a Cryptography challenge and spent like 12
rough hours on it during the weekend. Playing as "i dont even like computers"
I was happy to get the third solve for this interesting challenge by
@pedroysb
Quick Summary / TLDR

The challenge consists of a server implementing several cryptographic
operations. The signing operation has a small bug we can use to recover the
private key with a coppersmith style lattice attack on a trivariate polynomial.
Solution

Provided Options

The challenge comes with three files where the main logic is implemented in
server.py. In the main function first an RSA key is generated. Then the
script enters the operation_loop. Here we as users can select from six
options. Lets start off by analyzing the options we have:

"Get Public key", it prints $n$ and $e$

"Get Encrypted flag"


The server first generates a random hmac_key, then call parse (I'll
analyze parse and unparse a bit later) on the flag and finally applies
textbook RSA encryption to the parsed message.


"Decrypt flag"


We can send a message to the server, the server uses the CRT to decrypt the
message (textbook RSA) and then unparses it. If the HMAC verifies and the
plain text in the message is the flag the server tells us everything went
okay, else it prints an error.


"Get signed flag"


The server generates a random hmac_key and parses and signs the message
first mod p and then again mod q. Then both parts are combined using the
CRT and the result is returned to the user. The server then also checks with
an assert if the signature is valid.


"Verify signed flag"


Again we send a message to the server, the server undoes the signing
operation by raising the message to the public exponent. Next the server
unparsed the message and verifies the HMAC with the supplied key in the
message. The server then tells us if the verification succeeded.


"Exit", It just exits

Parsing and Unparsing


Parsing (serializing) a message really just means filling in the fields of
the protobuf specified message format. Interestingly the message includes a
nonce, which is generated by computing a HMAC over the current time.


Unparsing (deserializing) reverses the operation, creating a python class


Analysis


Option 1 gets us the public key.
Option 2 seemed kinda interesting because of the textbook RSA encryption, I
tried to play with this for a while. But since parts of the message are
random each time you encrypt could not come up with an attack here.
Option 3 and 5 basically always fail for each message not directly generated
by the server so again no luck here.

Option 4 is very suspicious though, the CRT is supposed to combine signatures
on $m\bmod p$ and $m\bmod q$ as $m^d \bmod n$. Most of the time this is
indeed what happens here, but note that parse is called twice. This means one
of the nonces may be different from the other (remember the nonce comes from
the current time). Thus it may happen that the CRT combines two different
signed messages!
def get_sig():
     r.recvuntil('>>>')
     r.sendline('4')
     return int(r.recvline().split(b'=')[1].strip(), 16)

def verify(d):
    r.recvuntil('>>>')
    r.sendline('5')
    r.sendline(l2b(d).hex())
    return b'success' in r.recvline()

while True:
    sig = get_sig()
    if not verify(sig):
        break
What is also interesting is that the assert doesn't matter, we already have
the output of the signature and the encrypted flag. Furthermore even if we
didn't have the latter the server doesn't even exit because we are in a try ... except: pass block.
Faulty Signatures

When different messages are signed and combined the server computes a faulty
signature on the flag. Lets say the server gives us $s$ such that
$s\bmod p\equiv m_1^{dp}$ and $s\bmod q\equiv m_2^{dq}$ Then we have:
$$ s^e \equiv m_1 \bmod p \Rightarrow s^e - m_1 \equiv 0 \bmod p $$
but also:
$$ s^e \equiv m_2 \bmod q \Rightarrow s^e - m_1 \not\equiv 0 \bmod q $$
So $p\mid (s^e - m_1)$ but $q\nmid (s^e - m_1)$ so $gcd(s^e - m_1, N) = p$,
meaning we can recover the secret key to decrypt any message.
But the server does not give us $m_1$, so we cannot immediately perform
this attack, that said, in the message there are only three unknowns which we
can bound since we know their length in bytes:

20 bytes of HMAC digest
20 bytes of Nonce
16 bytes of HMAC key

We can define $M_{base}$ as the number where all these unknown bytes are 0. The
problem then reduces to finding a root modulo a hidden divisor of the RSA
modulus to the polynomial
$$
f = s^e - (M_{base} + 2^{1184}x + 2^{2472}y + 2^{3736}z)
$$
Many crypto ctfers will recognize this as a problem to be solved by
Coppersmith,
Howgrave-Graham
and Hermann &
May with
$\beta = 0.5$
mbase = 0xa194d792063727970746f2070726f746f636f6c2076302e302e311210000000000000000000000000000000001a8501466f722074686973207369676e696e67206f6964204920616d206e6f7420737572652c20627574204920776f756c6420677565737320736f6d657468696e6720696e206265747765656e20312e322e3834302e3131333534392e322e3720616e6420312e322e3834302e3131333534392e312e312e3520706c7573206e6f6e6365203a292e221400000000000000000000000000000000000000002a8801466f722074686973207369676e696e6720616c676f726974686d204920616d206e6f7420737572652c20627574204920776f756c6420677565737320736f6d657468696e6720696e206265747765656e20686d6163576974685348413120616e6420736861312d776974682d7273612d7369676e617475726520706c7573206e6f6e6365203a292e3214000000000000000000000000000000000000000080000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

B = 2**(296*4)
C = 2**(618*4)
D = 2**(934*4)

A = mbase - pow(sig, e, n)
PR = PolynomialRing(Integers(n), 'x, y, z')
x, y, z = PR.gens()
f = A + B*x + C*y + D*z
f /= B
f = f.change_ring(Integers())
However I could not get any of the public implementations of multivariate
polynomial root finding to work. After some time I then found
this paper by
Takayasu and Kunihiro where they build on the results of Hermann and Mays by
only adding polynomials to the matrix based on a new criterion computed from
the bound we have of the root size.
X = [2**160, 2**160, 2**128]
G = [RealField(20)(log(x, 2**4096)) for x in X]
m = 5
t = 1
b = 0.5
PX = PolynomialRing(Integers(), 'x, y, z')
xn, yn, zn = PX.gens()
g2 = (G[1] + G[2]) / 2

monomials = []
polys = []
for i1, i2, i3 in itertools.product(range(m+1), repeat=3):
    monomials.append(xn**i1 * yn**i2 * zn**i3)
    if sum([i1, i2, i3]) > m:
        continue
    cond2 = G[0]*i1 + g2*(i2+i3)
    if 0 > cond2 or cond2 > b*t:
        continue
    g = yn**i2 * zn**i3 * f**i1 * n**max(t-i1, 0)
    if g != 0:
        # assert g(dig,non,key) % p == 0
        polys.append(g)
Now I'm note quite sure if this is required (no polynomials appear to be
discarded). However with this strategy of building and selecting monomials
standard implementations of LLL and
root finding methods based on groebner bases are able to find the roots to the
polynomial within a couple of minutes. Which can then be used to find $p$, then
we can decrypt the flag.
# Note: hacked a bit to remove all zero columns and also return the indices of
# those columns
L, to_delete = small_roots.fill_lattice(polys, monomials, X)
monomials = [mon for i, mon in enumerate(monomials) if i not in to_delete]
L = small_roots.reduce(L)
polynomials = small_roots.reconstruct_polynomials(L, f, monomials, X)

for roots in small_roots.find_roots(polynomials, f.parent(), method='groebner'):
    roots = [roots[r] for r in roots]
    print('roots:')
    for r in roots:
        print('\t%x' % r)
    p = gcd(f(roots), n)
Results

/path/to/ctfs/googlectf22/custom_protocol/crypto-attacks $ time python solv.py
[+] Opening connection to custom-protocol.2022.ctfcompetition.com on port 1337: Done
roots:
    c0c6d24eb4db4ea6e2ab1ff1049b2e000fa66e00
    150edcec5d3a264b2d625d3de11765f2c8ff9e28
    f2d1845353456f951071053e8e7f04df
version: "My crypto protocol v0.0.1"
hmac_key: "\331\262\352\351Xq\247\343\240\"\276\007A\357:\355"
oid: "For this encryption oid I am not sure, but I would guess something in between 1.2.840.113549.2.7 and 1.2.840.113549.1.1.5 plus nonce :)."
nonce: "\306l\317\276]\315\231\177I\330W[\327\021M@\213\327\301M"
algorithm_name: "For this encryption algorithm I am not sure, but I would guess something in between hmacWithSHA1 and sha1WithRSAEncryption plus nonce :)."
digest_message: "\226\317\310u[Pb\017V\315\323\340`{\031\250\\N\333\377"
plaintext: "CTF{They_say_never_implement_your_own_crypto...ok_ok_lesson_learned}"

[*] Closed connection to custom-protocol.2022.ctfcompetition.com port 1337
INFO:pwnlib.tubes.remote.remote.140567849598736:Closed connection to custom-protocol.2022.ctfcompetition.com port 1337
python solv.py  230.10s user 1.19s system 73% cpu 5:12.91 total
CTF{They_say_never_implement_your_own_crypto...ok_ok_lesson_learned}

See also the full code (run from within cypto-attacks)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from pwn import *
from sage.all import inverse_mod
import itertools
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Util.number import bytes_to_long as b2l
from sage.all import PolynomialRing, Integers, RealField
from sage.all import log, parent, gcd
from shared import small_roots

host = 'custom-protocol.2022.ctfcompetition.com'
port = 1337
r = remote(host, port)
data = r.recvuntil('>>>')
r.sendline('1')
e = int(r.recvline().split(b'=')[1].strip(), 16)
n = int(r.recvline().split(b'=')[1].strip(), 16)

def get_enc():
    r.recvuntil('>>>')
    r.sendline('2')
    return int(r.recvline().split(b'=')[1].strip(), 16)


def get_sig():
    r.recvuntil('>>>')
    r.sendline('4')
    return int(r.recvline().split(b'=')[1].strip(), 16)


def verify(d):
    r.recvuntil('>>>')
    r.sendline('5')
    r.sendline(l2b(d).hex())
    return b'success' in r.recvline()


enc = get_enc()
while True:
    sig = get_sig()
    if not verify(sig):
        break

mbase = 0xa194d792063727970746f2070726f746f636f6c2076302e302e311210000000000000000000000000000000001a8501466f722074686973207369676e696e67206f6964204920616d206e6f7420737572652c20627574204920776f756c6420677565737320736f6d657468696e6720696e206265747765656e20312e322e3834302e3131333534392e322e3720616e6420312e322e3834302e3131333534392e312e312e3520706c7573206e6f6e6365203a292e221400000000000000000000000000000000000000002a8801466f722074686973207369676e696e6720616c676f726974686d204920616d206e6f7420737572652c20627574204920776f756c6420677565737320736f6d657468696e6720696e206265747765656e20686d6163576974685348413120616e6420736861312d776974682d7273612d7369676e617475726520706c7573206e6f6e6365203a292e3214000000000000000000000000000000000000000080000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

B = 2**(296*4)
C = 2**(618*4)
D = 2**(934*4)

A = mbase - pow(sig, e, n)
PR = PolynomialRing(Integers(n), 'x, y, z')
x, y, z = PR.gens()
f = A + B*x + C*y + D*z
f /= B
f = f.change_ring(Integers())
X = [2**160, 2**160, 2**128]
G = [RealField(20)(log(x, 2**4096)) for x in X]
m = 5
t = 1
b = 0.5
PX = PolynomialRing(Integers(), 'x, y, z')
xn, yn, zn = PX.gens()
g2 = (G[1] + G[2]) / 2

monomials = []
polys = []
for i1, i2, i3 in itertools.product(range(m+1), repeat=3):
    monomials.append(xn**i1 * yn**i2 * zn**i3)
    if sum([i1, i2, i3]) > m:
        continue
    cond2 = G[0]*i1 + g2*(i2+i3)
    if 0 > cond2 or cond2 > b*t:
        print('discarded:', (i1,i2,i3))
        continue
    g = yn**i2 * zn**i3 * f**i1 * n**max(t-i1, 0)
    if g != 0:
        polys.append(g)

L, to_delete = small_roots.fill_lattice(polys, monomials, X)
monomials = [mon for i, mon in enumerate(monomials) if i not in to_delete]
L = small_roots.reduce(L)
polynomials = small_roots.reconstruct_polynomials(L, f, monomials, X)

for roots in small_roots.find_roots(polynomials, f.parent(), method='groebner'):
    roots = [roots[r] for r in roots]
    print('roots:')
    for r in roots:
        print('\t%x' % r)
    p = gcd(f(roots), n)
    q = n // p
    d = inverse_mod(e, (p-1)*(q-1))

    import msgs_pb2
    def unpad(padded_data: bytes, block_size: int) -> bytes:
        #Remove ISO/IEC 7816-4 padding.
        pdata_len = len(padded_data)
        padding_len = pdata_len - padded_data.rfind(b'\x80')
        return padded_data[:-padding_len]

    dec = pow(enc, d, n)
    data = msgs_pb2.RSAEncryptionData()
    data.ParseFromString(unpad(l2b(dec), 512))
    print(data)
The diff for crypto-attacks fill_lattice function:
diff --git a/shared/small_roots/__init__.py b/shared/small_roots/__init__.py
index 2e4771f..6b00e6d 100644
--- a/shared/small_roots/__init__.py
+++ b/shared/small_roots/__init__.py
@@ -25,7 +25,12 @@ def fill_lattice(shifts, monomials, bounds):
         for col, monomial in enumerate(monomials):
             B[row, col] = shift.monomial_coefficient(monomial) * monomial(*bounds)

-    return B
+    to_delete = []
+    for i, col in enumerate(B.columns()):
+        if all(c == 0 for c in col):
+            to_delete.append(i)
+    B = B.delete_columns(to_delete)
+    return B, to_delete