RSA or HMAC

This covers the two parts of the challenge. The challenge is related to the CVE-2017-11424 key confusion vulnerability in pyJWT.

This is somewhat hinted by the challenge's description of a "patch" to enable the exploit. Looking at the commit, we see that one of the newly added invalid_strings is '-----BEGIN RSA PUBLIC KEY-----'. This implies that we can leverage the public key for some forging. Combined with this line from the source code:

xxxxxxxxxx
decoded = jwt.decode(token, PUBLIC_KEY, algorithms=['HS256', 'RS256'])

we can see that the PUBLIC_KEY can be used for verification of the HS256 generated token. Applied the patch, which involves removing the binary string '-----BEGIN RSA PUBLIC KEY-----' from _PEMS in file utils.py of pyjwt library, we can sign using the HS256 algorithm

For the second part, we are not given the public key, but this can be easily retrieved by calculating the GCD from the signature and signed message. I refer to this link about the technique used.

We can sign the dictionary where the admin value is True, using HS256 algorithm, with the key as the binary representation of the public key. The following is the code to do so

xxxxxxxxxx
encoded = jwt.encode({'username': username, 'admin': True}, PUBLIC_KEY, algorithm='HS256')

For the first challenge, as we know the public key, generating the JWT token is trivial - just supply the PUBLIC_KEY given from GET_PUBKEY() functionality on the CryptoHack website. For the second challenge, the public key is not given, hence we need a way to retrieve the public key.

We have full information of the signature, but the message, which is padded using EMSA-PKCS1-v1_5, needs a bit of reverse engineering to check out how everything works. I did try to do this, but information on the emLen (referring to RFC8017) is nowhere to be found in the source code. Apparently the value in use is 256, which can be derived from the length of the signature, but I was not exactly confident on this when I try to implement the script.

Hence, I use the script from JWT-Key-Recovery to retrieve the public key from two JWT token from two different username. The script is nice enough to supply the pem version after running.

This output from the above script is also the result of the export_key function of Pycryptodome. However, as observed from the command used to generate the public and private keys, and the output from the first challenge, the public key is not in PKCS#1 format, instead in PKCS#8. We can use the command from this link, we can use the command openssl rsa -pubin -in <filename> -RSAPublicKey_out to convert from PKCS#8 to PKCS#1 format.

That's not the end of the challenge. Doing the conversion on Windows will always run into the classic issue of DOS line endings \r\n versus UNIX line endings \n. Again, from checking the output returned in the first challenge, the public key file uses UNIX line endings. Hence, we have to do a conversion from DOS line endings to UNIX line endings before passing the public key to encode.

RSA public key in PKCS#1:

xxxxxxxxxx
-----BEGIN RSA PUBLIC KEY-----
MIIBCgKCAQEA7pgbuP6X8XHyFr47ybSr1yT+m++FNn/fUnnKP113bYbcp/Jn4nl5
kiRoK4cgXWv6yYaTxVMSyvLcdDkPsmZ0J4DfBXZSpUKY2QK+oR76nb5fZ+VNUEi0
Iu15GBJdIPj8yEA81OviDNcnXRyDpLBWtXZ1gNJyvoiOj/3DgRcIWz9yJNkze8ln
utMOzxobg/o2i9oewa2MJk+MHKUZOOCxoaVfmdczTqDIXdowxnWCTEgWb4SBN+MH
Gu+8pWgGqXCioGDPALHRR98CWopHC0z7Via/UXkLNGCjJfdNZiJFnLHG8tATDvDS
CDQSg46MARk5Ein4ekVPaNKnjc6INnO01QIDAQAB
-----END RSA PUBLIC KEY-----

Python Implementation:

xxxxxxxxxx
import jwt 

# PKCS#1 pem file is test.pem
with open('test.pem', 'r') as f:
    PUBLIC_KEY = f.read()

# Change \r\n on Windows to \n
PUBLIC_KEY = "\n".join(PUBLIC_KEY.splitlines())
PUBLIC_KEY = PUBLIC_KEY.encode() + b'\n'

print(PUBLIC_KEY)
def create_session(username):
    encoded = jwt.encode({'username': username, 'admin': True}, PUBLIC_KEY, algorithm='HS256')
    return encoded

print(create_session('qvinhprolol'))

The following is the way to solve the challenge without involving the use of external script. Kudos to maple3142 for this solution, I add some comments for places that the Python function is based on. We still need to do the PKCS#8 to PKCS#1 conversion though.

​x
from Crypto.Signature.pkcs1_15 import _EMSA_PKCS1_V1_5_ENCODE
from Crypto.PublicKey import RSA
from Crypto.Hash import SHA256
from Crypto.Util.number import long_to_bytes, bytes_to_long
import jwt  # PyJWT 1.5.0
import json
import base64
import gmpy2

# Private key generated using: openssl genrsa -out rsa-or-hmac-2-private.pem 2048
with open("challenge_files/rsa-or-hmac-2-private.pem", "rb") as f:
    PRIVATE_KEY = f.read()
# Public key generated using: openssl rsa -in rsa-or-hmac-2-private.pem -out rsa-or-hmac-2-public.pem -RSAPublicKey_out
with open("challenge_files/rsa-or-hmac-2-public.pem", "rb") as f:
    PUBLIC_KEY = f.read()

# From pyjwt utils.py
def base64url_encode(input):
    return base64.urlsafe_b64encode(input).replace(b"=", b"")

# From pyjwt utils.py
def base64url_decode(input):
    if isinstance(input, str):
        input = input.encode()
    rem = len(input) % 4

    if rem > 0:
        input += b"=" * (4 - rem)

    return base64.urlsafe_b64decode(input)

# From pyjwt algorithm.py flow
def rs256_sign(payload, key):
    msg = (
        base64url_encode(
            json.dumps({"typ": "JWT", "alg": "RS256"}, separators=(",", ":")).encode()
        )
        + b"."
        + base64url_encode(json.dumps(payload, separators=(",", ":")).encode())
    )
    h = SHA256.new(msg)
    padded = _EMSA_PKCS1_V1_5_ENCODE(h, 256)
    m = bytes_to_long(padded)
    return pow(m, key.d, key.n), m


# Sanity check
key = RSA.import_key(PRIVATE_KEY)
data = {"a": "a"}
jsig = jwt.encode(data, PRIVATE_KEY, algorithm="RS256").split(b".")[2]
sig, m = rs256_sign(data, key)
assert pow(sig, key.e, key.n) == m
assert base64url_encode(long_to_bytes(sig)) == jsig

import requests


def get_jwt(username):
    return requests.get(
        f"https://web.cryptohack.org/rsa-or-hmac-2/create_session/{username}/"
    ).json()["session"]


# Local testing
# def get_jwt(username):
#     return jwt.encode(
#         {"username": username, "admin": False}, PRIVATE_KEY, algorithm="RS256"
#     ).decode()


def get_sig_and_m(username):
    sig = bytes_to_long(base64url_decode(get_jwt(username).split(".")[-1]))
    _, m = rs256_sign({"username": username, "admin": False}, key)
    return sig, m


s1, m1 = get_sig_and_m("peko")
s2, m2 = get_sig_and_m("miko")

# mpz for faster exponentiation
a = gmpy2.mpz(s1) ** 65537 - gmpy2.mpz(m1)
b = gmpy2.mpz(s2) ** 65537 - gmpy2.mpz(m2)
print("running gcd")
n = int(gmpy2.gcdext(a, b)[0])
print(n)
pk = RSA.construct([n, 65537]).export_key().decode()
print(pk)
with open("pub.pem", "w") as f:
    f.write(pk)