Cyber Jawara 2023 Qual - Crypto

There are 4 crypto challenges in the qualification round of Cyber Jawara this year, and 2 of them are very interesting since I personally think the bug is quite difficult to find and also not easy to exploit, unlike other crypto challenges where the bug is easy to find but difficult to exploit. So in this post, I will write my solutions to the following 2 crypto challenges:

Matryoshka
Aeonia

Matryoshka (940 points, 3 solves)

There is a web service that can encrypt multiple secrets into a JWT. The plaintext of the JWT payload has the following format:

[{"username":"user1","secret":"secret1"},{"username":"user2","secret":"secret2"},{"username":"user3","secret":"secret3"},{"username":"user4","secret":"secret4"}]

The condition:

user1, user2, user3 are known
secret1, secret2, secret3 unknown
secret1 and secret2 are 16 random hex chars
secret3 is a flag
user4 and secret4 are controlled by user input

The web service uses the python-jose library and the encryption process is performed in the following way:

import json
import os
from jose import jwe

KEY = os.urandom(16)

def encrypt(plaintext):
    return jwe.encrypt(plaintext, KEY, 'A128CBC-HS256', 'A128KW', 'DEF', 'application/json', '13337')

def decrypt(token):
    try:
        decrypted = jwe.decrypt(token, KEY)
        data = json.loads(decrypted)
        return data
    except Exception:
        return False

Solution

A few optional parameters are used. We tried to trace the code from the library to know what are actually the parameters doing. The initial idea that came to our mind was to change the encryption type and algorithm. However, some of our experiments failed, the reason was that other types of encryption and algorithms didn’t support the key length used by the service, and also the format was quite different when using other types of encryption and algorithms. After reading the python-jose library code line-by-line for quite some time, we realized that the service uses the "DEF" argument for the zip parameter, which has implications for the plaintext before encryption is performed. Here is the following python-jose code that supports the compression: mpdavis/python-jose/jose/jwe.py.

def encrypt(plaintext, key, encryption=ALGORITHMS.A256GCM, algorithm=ALGORITHMS.DIR, zip=None, cty=None, kid=None):
    """Encrypts plaintext and returns a JWE cmpact serialization string.

    Args:
        plaintext (bytes): A bytes object to encrypt
        key (str or dict): The key(s) to use for encrypting the content. Can be
            individual JWK or JWK set.
        encryption (str, optional): The content encryption algorithm used to
            perform authenticated encryption on the plaintext to produce the
            ciphertext and the Authentication Tag.  Defaults to A256GCM.
        algorithm (str, optional): The cryptographic algorithm used
            to encrypt or determine the value of the CEK.  Defaults to dir.
        zip (str, optional): The compression algorithm) applied to the
            plaintext before encryption. Defaults to None.
        cty (str, optional): The media type for the secured content.
            See http://www.iana.org/assignments/media-types/media-types.xhtml
        kid (str, optional): Key ID for the provided key

def _compress(zip, plaintext):
    """
    Compress the plaintext based on the algorithm supplied

    Args:
        zip (str): Compression Algorithm
        plaintext (bytes): plaintext to compress

    Returns:
        (bytes): Compressed plaintext
    """
    if zip not in ZIPS.SUPPORTED:
        raise NotImplementedError("ZIP {} is not supported!")
    if zip is None:
        compressed = plaintext
    elif zip == ZIPS.DEF:
        compressed = zlib.compress(plaintext)
    else:
        raise NotImplementedError("ZIP {} is not implemented!")
    return compressed

In simple terms, a string with a low entropy (having many repetitions/similarities between one char/word and another) has shorter compression results than a string with a high entropy. We can use this to guess the secret flag char-by-char. The idea is, when we enter the secret “CJ2023CJ2023CJ2023” (which will later be concated with a secret flag), the compression result will have a shorter length than the compression result from “ASDFGHASDFGHASDFGH”. The information that the flag format begins with “CJ2023{“ and is 31 chars long can also help us in recovering the secret flag.

Implementation

import requests
import string
import sys

if len(sys.argv) == 2:
    burp0_url = "http://127.0.0.1:50003/store" # local
else:
    burp0_url = "http://137.184.6.25:50003/store" # remote

burp0_headers = {"Content-Type": "application/json"}

k = 401 # manual tuning
flag = 'CJ2023{'

while len(flag) != 31 - 1:
    res = {}

    for ch in string.digits + '_' + string.ascii_letters:
        secret = flag + ch
        secret = secret * k
        secret = secret[:k]
        username = 'Carian' * 7

        burp0_json={"secret": secret, "username": username}
        r = requests.post(burp0_url, headers=burp0_headers, json=burp0_json)
        print(len(r.text), repr(ch))

        if len(r.text) not in res:
            res[len(r.text)] = [ch]
        else:
            res[len(r.text)].append(ch)

    minn = min(res.keys())
    print(res)
    print(res.keys(), res[minn])
    print()

    if len(res[minn]) == 1:
        flag += res[minn][0]

    else:
        tmp = {x+1: y for x, y in enumerate(res[minn])}
        print('Current flag: ' + flag)
        print('Choose one?', tmp)
        idx = int(input('> '))
        flag += tmp[idx]

    print('Current flag: ' + flag)
    print()

flag += '}'
print('Final flag: ' + flag)

When executed, there are several chars that have low entropy. Our solver gives the strings “CJ2023{yet_a” and “CJ2023{yet_p” which both have low entropy compared to the other chars. For the case above, we try to manually choose which letters to use by ensuring that the sentence written on the flag is an English word and makes sense.

Flag

CJ2023{yet_another_jwt_pitfall}

Aeonia (940 points, 3 solves)

The program implements the Elliptic Curve Integrated Encryption Scheme (ECIES) in Golang. From the source code provided, it can be seen that the program also depends on the ecies/go package which uses the secp256k1 curve.

Our observation:

The ecies object named serverKey encrypts the flag. The serverKey has a private key that is quite small on the secp256k1, which is only 128 bits (which should be 256 bits), so this is quite suspicious and needs further attention
serverKey.ECDH and userPriv.ECDH don’t have any influence on encryption and decryption, but the service displays them every time we select the option to encrypt and decrypt a message
We can modify the first 65 bytes of ciphertext with another public key when we select the decrypt message option. However, because we don’t have any private keys (neither serverKey nor ephemeral), we think that this can’t be exploited

After understanding the flow for quite some time and reading the source code of the ecies/go package, we still haven’t found anything wrong in the program. Not long after, the author gave a hint that the bug occurred when we compile the binary with CGO_ENABLED=0.

Solution

From here, we start doing experiments to find out the differences between binary compiled with CGO_ENABLED=0 and CGO_ENABLED=1. From our experiments, we found two differences as follows:

In NewPrivateKeyFromBytes, the program doesn’t limit the length of user input when CGO_ENABLED is set to 0, while when set to 1 an error will appear when the private key entered exceeds 256 bits
In NewPublicKeyFromHex, the program doesn’t check whether the public key is on the secp256k1 curve, then serverKey.ECDH still performs scalar multiplication with serverKey’s private key on the public key when CGO_ENABLED is set to 0, while when it is set to 1 the scalar multiplication is performed incorrectly

On the 1st difference, we didn’t find anything we could exploit so we started focusing on the 2nd difference. The 2nd difference is because there is no checking whether the public key entered is on the secp256k1 curve. We can take advantage of this by looking for a public key or point that has a relatively small order on a curve that is similar/parallel to secp256k1 (only different in constant b). This type of attack is also known as Invalid Curve Attack.

As a first step, we collect several points on the invalid curve that have relatively small orders. Later, this set of points will be sent as a public key to the encryption option in the service. We collect points with a prime order of no more than 26 bits using the following code below:

from random import randint, getrandbits
from Crypto.Util.number import *

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

pesanan = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
E.set_order(pesanan * 0x1)

total = 1
GOOD_PRIMES = [p for p in range(2, 2 ^ 26) if Integer(p).is_prime()]
box = []

while total < 2**131:
    tb = getrandbits(40)
    iE = EllipticCurve(K, [a, tb])
    iG = iE.gen(0)
    og = iG.order()

    for z in GOOD_PRIMES:
        if og % z == 0:
            GOOD_PRIMES.remove(z)
            break
    else:
        continue

    iP = Integer(og / z) * iG
    og2 = iP.order()
    print(og2, tb, iP.xy())

    box.append((og2, tb, iP.xy()))
    total *= og2
    print(total, total.nbits())
    print()

print(sorted(box, key=lambda x: x[0]))

The main idea of this attack is that later we can calculate the discrete log of each given point because all of these points have small order. All these points will be multiplied by the same scalar, the private key belonging to serverKey. When the discrete log results are obtained, the numbers are very small for each point, but we can combine the entire discrete log results with the Chinese Remainder Theorem (CRT) to get serverKey’s private key again. In the process of looking for points with small order, we also have to ensure that all points have different orders from one another. Of course, two or more points that have the same order will not help us in using the CRT later. After using the CRT, we have many serverKey private key candidates which are 128 bits in size. We can test all the private key candidates in the decrypt message option, then see if any decryption was successful.

Implementation

from pwn import *
import sys

if len(sys.argv) == 2:
    io = remote('127.0.0.1', 50002) # local
else:
    io = remote('178.128.102.145', 50002) # remote

io.recvuntil(b'Encrypted flag: ')
enc_flag = io.recvline(0)

################################################################

from fastecdsa.curve import secp256k1 as curve

p = curve.p
K = GF(p)
a = K(curve.a)

box = [(2, 671448992455, (32931453793970922784303869375172340539973111016334485021174461631841986406962, 0)), (3, 1023628206162, (0, 88158283773910880916191988724615618570086310652216095272981718384971813401664)), (7, 794028507499, (2773516186970309747927824996943085084239074484155274110108735398476851500034, 35833938007666030823085771170784976619463989786559359975173423297164124671694)), (13, 359665466448, (37711941020466802600416717283580073091873318393600218004839469927590865720275, 55970129250173601858095048106455515428384144877109523796573820214312360637562)), (199, 1080774707358, (21720613664549333218930067184992069816777952435490867493850844086847098171033, 4218526125556849135120985805976303799848830879522698323244706583872251856992)), (3319, 721493862848, (60304245164493827430144340553095664129472197834837916845888757164818025575751, 22006356160415549833217660547103063164103208541113846952219265949390791516287)), (10903, 922546651517, (2554965584886902550507698588413595782826431004139737096244218863653201334031, 29337294264533562573264130225996498679144080955896530192703165998330217749913)), (18979, 630656122708, (108475585654808958728712941539217734373151448095383832173427485467285501509523, 103328225619756686962770929684687725214397883384030606138667812373170858080232)), (22639, 705402235523, (90136403449190897583592243094052165618014904445672548660430263402102488151937, 107486471628088927461845883953424224999513724359028840723781374184804176528137)), (109903, 254619012682, (49388485976693189170297253878413534689663824452436580875041145484763183172531, 97818439439260137275820892077769651501150222026342167056922349085541183283566)), (5290657, 167674815822, (56739846790343882184809104159705654679509283352308104714347545216721926302708, 83410335775875057780649451103413246150691566263159816798669588167232352014835)), (12977017, 1031451246740, (60722093304862252283249396770074322180754773189675920067248653309829433262797, 44601023093299441004559286668758610709000886638118855159108972488665278019243))]

rems1 = []
rems2 = []
mods = []

for bo in box:
    order = bo[0]
    new_b = bo[1]
    x, y = bo[2]

    pload = f"04{x:064x}{y:064x}".encode()

    io.sendlineafter(b'> ', b'2')
    io.sendlineafter(b'Enter your public key: ', pload)
    io.sendlineafter(b'Enter the message you want to encrypt (hex): ', b'64656f6d')
    io.recvuntil(b'Shared ephemeral secret: ')
    ss = io.recvline(0)

    E = EllipticCurve(K, (a, K(new_b)))
    base = E(x, y)
    target = E.lift_x(Integer(ss[2:], 16))

    sol = discrete_log_lambda(target, base, (0, order), operation='+')
    print(sol, order)

    rems1.append(sol)
    rems2.append(order - sol)
    mods.append(order)

print()

################################################################

LEN = len(mods)

poss_privkey = []

for wad in range(2**LEN):
    bins = f"{wad:0{LEN}b}"
    arr1 = [rems1[i] if bins[i]=='1' else rems2[i] for i in range(LEN)]
    arr2 = [rems2[i] if bins[i]=='1' else rems1[i] for i in range(LEN)]

    for arr in [arr1, arr2]:
        crt_sol = crt(arr, mods)
        if crt_sol.nbits() <= 128:
            print('FOUND', hex(crt_sol))
            poss_privkey.append(f"{crt_sol:032x}")

print()

################################################################

for sk in poss_privkey:
    io.sendlineafter(b'> ', b'3')
    io.sendlineafter(b'Enter your private key: ', sk.encode())
    io.sendlineafter(b'Enter the ciphertext you want to decrypt (hex): ', enc_flag)
    io.recvuntil(b'Shared ephemeral secret: ')
    ss = io.recvline(0).decode().strip()
    dec = io.recvline(0).decode().strip()
    print(ss, dec)

    if 'Decrypted message: ' in dec:
        dec = dec.split()[-1]
        print(bytes.fromhex(dec))
        break

io.close()

Strangely, the discrete log failed at certain points at some cases. However, when all the discrete logs were successful, we managed to get the serverKey private key and succeeded in decrypting the encrypted flag.

Flag

CJ2023{real_world_crypto_3b8786f9}

PREVIOUSGemastik 2023 Final - Crypto