[Medium] Arranged

Arranged

​ 17^th Dec 2023 / Document No. D24.102.29

​ Challenge Author(s): ir0nstone

Synopsis

Arranged is a Medium crypto challenge that involves ECC with unknown variables. The player must use basic rearrangement and GCD operations to identify the prime $p$ and the constant $b$, then notice the order of the point $G$ is incredibly low.

Description:

Noiselessly turning the corner, you see before you two men. In a former life, the two were best friends; pressure and pain has reduced them to mere animals, single-minded automatons devoid of emotion or feeling. The sickening, grim reality of the competition is that it is what it is designed to do, and none escape the inevitable doom. You raise your bow and bury two arrows into their chests; given their past, it was the least you could do. Death would be kinder to them than life.

Skills Required

• An understanding of Elliptic-Curve Cryptography
• A basic understanding of Group Theory

Skills Learned

• An understanding of the order of group elements

Enumeration

We are given the following script:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

from secret import FLAG, p, b, priv_a, priv_b

F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)

A = G * priv_a
B = G * priv_b

print(A)
print(B)

C = priv_a * B

assert C == priv_b * A

# now use it as shared secret
secret = C[0]

hash = sha256()
hash.update(long_to_bytes(secret))

key = hash.digest()[16:32]
iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print(encrypted)

This looks like standard ECC:

• An elliptic curve $E$ is defined with a generator point $G$
  • The prime $p$ and constant $b$ are secret
• $A=aG$ and $B=bG$ are calculated
  • $a$ and $b$ are kept secret, as standard
• The values are exchanged (printed out) and then both sides calculate $abG$ independently
• This value is used as a shared secret for encryption

The values are found in output.txt:

(6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997 : 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696 : 1)
(4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734 : 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865 : 1)
b'V\x1b\xc6&\x04Z\xb0c\xec\x1a\tn\xd9\xa6(\xc1\xe1\xc5I\xf5\x1c\xd3\xa7\xdd\xa0\x84j\x9bob\x9d"\xd8\xf7\x98?^\x9dA{\xde\x08\x8f\x84i\xbf\x1f\xab'

Solution

We have three points $G$, $A$ and $B$ that fit the equation $y^2 \equiv x^3 + 726x + b \mod p$:

$$\begin{align}y_A^2 &\equiv x_A^3 + 726x_A + b \mod p \\ y_B^2 &\equiv x_B^3 + 726x_B + b \mod p \\ y_G^2 &\equiv x_G^3 + 726x_G + b \mod p\end{align}$$

If we take away the second and third congruences from the first, we can eliminate $b$:

$$\begin{align}y_A^2 - y_B^2 &\equiv x_A^3 + 726x_A - x_B^3 - 726x_B \mod p \\ y_A^2 - y_G^2 &\equiv x_A^3 + 726x_A - x_G^3 - 726x_G \mod p\end{align}$$

Now we can move all the terms to one side and get an expression congruent to $0$:

$$\begin{align}y_A^2 - y_B^2 - x_A^3 - 726x_A + x_B^3 + 726x_B &\equiv 0 \mod p \\ y_A^2 - y_G^2 - x_A^3 - 726x_A + x_G^3 + 726x_G &\equiv 0 \mod p\end{align}$$

We now have two values that we know are multiples of $p$. How can we extract $p$ itself? Using the GCD, of course!

A = (6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997, 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696)
B = (4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734, 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865)
G = (926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)

# get the congruences mentioned above
x1 = A[1]^2 - B[1]^2 - A[0]^3 - 726*A[0] + B[0]^3 + 726*B[0]
x2 = A[1]^2 - G[1]^2 - A[0]^3 - 726*A[0] + G[0]^3 + 726*G[0]

p = gcd(x1, x2)
F = GF(p)

And we successfully retrieve $p$. Let's now rearrange the equation for $b$:

$$b \equiv y^2 - x^3 - 726x \mod p$$

b = (A[1]^2 - A[0]^3 - 726*A[0]) % p

Now we can set up the elliptic curve and analyse the points.

E = EllipticCurve(F, [726, b])
G = E(G[0], G[1])

We immediately think about printing out the order of $G$. It takes a while, but eventually we get it:

sage: G.order()
11

So $G$ only has order $11$! This means $abG$ has only $11$ possibilities, which are easy to brute force. For every multiple of $G$, we can attempt a decryption and see if we get the flag.

enc_flag = b'V\x1b\xc6&\x04Z\xb0c\xec\x1a\tn\xd9\xa6(\xc1\xe1\xc5I\xf5\x1c\xd3\xa7\xdd\xa0\x84j\x9bob\x9d"\xd8\xf7\x98?^\x9dA{\xde\x08\x8f\x84i\xbf\x1f\xab'

def decrypt(Q):
    secret = Q[0]

    hash = sha256()
    hash.update(long_to_bytes(secret))

    key = hash.digest()[16:32]
    iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
    cipher = AES.new(key, AES.MODE_CBC, iv)

    decrypted = cipher.decrypt(enc_flag)
    return decrypted

E = EllipticCurve(F, [726, b])
G = E(G[0], G[1])

# brute force the result
for i in range(1, 12):
    P = i*G
    msg = decrypt(P)

    if b'HTB{' in msg:
        print(msg)
        break

And we do!