Cyber Jawara 2023 Qual - Crypto

This year’s Cyber Jawara qual round had 4 crypto challs. 2 of them were particularly interesting because the bugs were hard to spot and exploit, unlike typical crypto challs where bugs are easy to spot but hard to exploit. Here are my solutions for these 2 challs:

Matryoshka
Aeonia

Matryoshka (940 points, 3 solves)

The web service encrypts multiple secrets into a JWT. The JWT payload has this format:

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

Conditions:

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

The service uses the python-jose library, and the encryption is done in the following code:

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

The service uses several optional params. We traced the library code to understand what these params do. Our first idea was to change the encryption type and algorithm, but it failed because other encryption types and algorithms didn’t support the key length used by the service, and the format was different.

After reading the python-jose library code, we found that the service uses the "DEF" argument for the zip parameter, which affects the plaintext before encryption. Here’s the relevant code from 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

A string with low entropy (many repeated chars/words) compresses to a shorter length than a string with high entropy. We can use this to guess the flag char by char. When we enter the secret “CJ2023CJ2023CJ2023” (which will be concatenated with the flag), the compression result will be shorter than “ASDFGHASDFGHASDFGH”. Knowing that the flag starts with “CJ2023{“ and is 31 chars long helps us recover the 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, several chars have low entropy. Our solver gives “CJ2023{yet_a” and “CJ2023{yet_p” which both have lower entropy than other chars. In these cases, we manually choose which char to use by ensuring the flag forms valid English words.

Flag

CJ2023{yet_another_jwt_pitfall}

Aeonia (940 points, 3 solves)

The program implements the Elliptic Curve Integrated Encryption Scheme (ECIES) in Golang. The source code shows it uses the ecies/go package which uses the secp256k1 curve.

After analysis:

The serverKey ecies object encrypts the flag. Its private key is only 128 bits on secp256k1 (should be 256 bits), which is suspicious
serverKey.ECDH and userPriv.ECDH don’t affect encryption/decryption, but the service shows them during encrypt/decrypt operations
We can modify the first 65 bytes of ciphertext with another public key during decryption, but without private keys (neither serverKey nor ephemeral), this seems unexploitable

After understanding the flow and reading the ecies/go package source code, we found no issues. The author then gave a hint that the bug occurs when compiling with CGO_ENABLED=0.

Solution

We tried to find differences between binaries compiled with CGO_ENABLED=0 and CGO_ENABLED=1. We found two main differences:

With CGO_ENABLED=0, NewPrivateKeyFromBytes doesn’t limit user input length, while with CGO_ENABLED=1 it errors when the private key exceeds 256 bits
With CGO_ENABLED=0, NewPublicKeyFromHex doesn’t verify if the public key is on the secp256k1 curve, so serverKey.ECDH still performs scalar multiplication with serverKey’s private key on the public key. With CGO_ENABLED=1, the scalar multiplication is performed incorrectly (or in a simple word, it fails)

The first difference wasn’t really exploitable, so we focused on the second one. The lack of curve validation lets us use a public key or point with a small order on a curve similar to secp256k1 (different only in constant b). This is known as Invalid Curve Attack.

First, we collected some points on the invalid curve with small orders. We collect points with prime orders up to 26 bits using this code:

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 attack works because we can calculate the discrete log (in a reasonable amount of time) of each point since they have small orders. All points are multiplied by the same scalar (the serverKey’s private key). The discrete log results are small for each point, but we can combine them using the Chinese Remainder Theorem (CRT) to recover the serverKey’s private key. When collecting points, we ensure they have different orders, as points with the same order won’t help in CRT. After using CRT, we get several 128-bit serverKey private key candidates. We test each candidate in the decrypt message option to find one that successfully decrypts the flag.

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()

Sometimes the discrete log fails at certain points. However, when all discrete logs succeed, we get the serverKey private key and can decrypt the flag.

Flag

CJ2023{real_world_crypto_3b8786f9}

PREVIOUSGemastik 2023 Final - Crypto