Inefficient Algorithmic Complexity Affecting jose package, versions >=1.7.7 <1.11.13

Affected versions of this package are vulnerable to Inefficient Algorithmic Complexity via the convert_sfm_to_crt/1 function in jose_jwk_kty_rsa.erl, which is triggered when parsing an RSA private key in SMF (Straightforward Method) form that omits the CRT parameters (p, q, dp, dq, qi). An attacker can supply a malicious JWK whose modulus n is a prime number, causing the prime-recovery loop in convert_sfm_to_crt_find_p/6 to run indefinitely until an internal watchdog terminates the worker after approximately one second. Submitting a small number of such payloads to any endpoint that calls JOSE.JWK.from_binary/1 on externally supplied key material can exhaust CPU resources and crash the service.

The attached script rsa_jwk_parse_triggers_attacker_controlled_prime_recovery_co_2320.exs demonstrates the amplification directly against the trust boundary, JOSE.JWK.from_binary/1, which is the same parser an application would call on any externally supplied key. No HTTP server is needed to measure the parser's CPU cost.

The script builds a malicious JWK whose fields cannot form a valid RSA private key:

• It deterministically obtains a large prime by generating a real 2048-bit RSA key and taking its p value — any RSA prime works, and an attacker can produce one offline.

• It uses that prime as the alleged modulus n, with e = 65537 and d = 3:

  malicious_map = %{"kty" => "RSA", "n" => prime_modulus,
                    "e" => b64.(65_537), "d" => b64.(3)}
  

Because n is prime, the recovery search in convert_sfm_to_crt_find_p/6 can never split it into p * q, so the loop runs until jose's internal 1000 ms watchdog kills the worker. The map omits p, q, dp, dq, and qi, which is exactly the condition that routes from_map_rsa_private_key/2 into convert_sfm_to_crt/1.

The script encodes the map with JOSE.encode/1, prints its size (a few hundred bytes), then times a single JOSE.JWK.from_binary/1 call with :timer.tc, catching any raise or exit. It asserts the call reached the watchdog — elapsed time between 900 ms and 2000 ms — and that the parser ultimately rejected the key:

watchdog_reached? = elapsed_ms >= 900 and elapsed_ms < 2_000

When both hold, it prints a VERIFIED: line reporting that one tiny attacker JWK forced roughly a second of prime-recovery work; otherwise it raises NOT VERIFIED. The full script is attached below under "Scripts and Logs" so the reader can run it themselves.

Note: The PoC script runs against JOSE.JWK.from_binary/1 directly with no HTTP server, using a malicious 2048-bit RSA JWK whose modulus is prime and whose CRT fields are omitted.

• cna.erlef.org
• GitHub Advisory
• GitHub Commit
• GitHub Commit
• osv.dev