No Way Back Home

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: crt_with_factor_p, recover_blinding_secret, shared_secret_via_product_of_transcripts

Summary

Task: a homemade commutative (Massey-Omura style) key exchange where v=(prandint)%n is multiplicatively blinded by Alice's k_A and Bob's k_B; the transcript leaks vka=vkA, vkakb=vkAkB, vkb=vkB mod n, and p,q. Solution: vkavkb = v^2kAkB = v*(vkAkB) = vvkakb mod n, so v = vkavkb*inverse(vkakb) — but everything is a multiple of p (not invertible mod n), so compute v mod q via inverse mod q and CRT with v≡0 mod p to recover v, then AES-ECB decrypt with sha256(long_to_bytes(v)).

No Way Back Home — cryptohack (Mathematics)

Description

"Quantum Computers are going to break RSA, ECC and others... so why don't we make our own Quantum-Safe Key Exchange Protocol?"

Files: nowayback.py, out.txt. A commutative (three-pass / Massey-Omura-flavoured) exchange:

 python read-only • copy allowed Copy
n = p * q
v   = (p * randint(1, n)) % n      # secret; note v ≡ 0 (mod p)
k_A = unit mod n;  vka   = (v   * k_A) % n
k_B = unit mod n;  vkakb = (vka * k_B) % n
vkb = (vkakb * inverse(k_A, n)) % n          # = v * k_B
v_s = (vkb   * inverse(k_B, n)) % n          # = v   (Bob recovers v)
key = sha256(long_to_bytes(v)).digest()      # AES-ECB key over the flag

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The output leaks p, q, vka, vkakb, vkb and the ciphertext c.

Analysis

Let kA = k_A, kB = k_B. The transcript is:

vka   = v · kA
vkakb = v · kA · kB
vkb   = v · kB

Multiply the two "single-blinded" values:

vka · vkb = (v·kA)(v·kB) = v² · kA · kB = v · (v·kA·kB) = v · vkakb   (mod n)

so formally v = vka · vkb · vkakb⁻¹ (mod n). The catch: v = (p·randint) % n is a multiple of p, hence so are vka, vkb, vkakb — none of them are invertible mod n (they share the factor p). Work modulo q only, then CRT back: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

v ≡ 0                                   (mod p)     # v is a multiple of p
v ≡ vka · vkb · vkakb⁻¹                 (mod q)     # all units mod q

CRT these two congruences to recover the exact integer v ∈ [0, n), then derive the AES key.

Solution

 python read-only • copy allowed Copy
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes, inverse
from hashlib import sha256
from sympy.ntheory.modular import crt

p, q  = (10699940648196411028170713430726559470427113689721202803392638457920771439452897032229838317321639599506283870585924807089941510579727013041135771337631951,
         11956676387836512151480744979869173960415735990945471431153245263360714040288733895951317727355037104240049869019766679351362643879028085294045007143623763)
n = p * q
vka   = 124641741967121300068241280971408306625050636261192655845274494695382484894973990899018981438824398885984003880665335336872849819983045790478166909381968949910717906136475842568208640203811766079825364974168541198988879036997489130022151352858776555178444457677074095521488219905950926757695656018450299948207
vkakb = 114778245184091677576134046724609868204771151111446457870524843414356897479473739627212552495413311985409829523700919603502616667323311977056345059189257932050632105761365449853358722065048852091755612586569454771946427631498462394616623706064561443106503673008210435922340001958432623802886222040403262923652
vkb   = 6568897840127713147382345832798645667110237168011335640630440006583923102503659273104899584827637961921428677335180620421654712000512310008036693022785945317428066257236409339677041133038317088022368203160674699948914222030034711433252914821805540365972835274052062305301998463475108156010447054013166491083
c = 'fef29e5ff72f28160027959474fc462e2a9e0b2d84b1508f7bd0e270bc98fac942e1402aa12db6e6a36fb380e7b53323'
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

vq   = (vka % q) * (vkb % q) % q * inverse(vkakb % q, q) % q
v, _ = crt([p, q], [0, vq])
key  = sha256(long_to_bytes(int(v))).digest()
print(unpad(AES.new(key, AES.MODE_ECB).decrypt(bytes.fromhex(c)), 16))

Output:

b'crypto{REDACTED}'

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍