Null or Never

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: coppersmith_univariate, howgrave_graham, known_prefix_suffix_reduction, lll_reduction, stereotyped_message

Summary

Task: RSA with e=3, the flag is right-zero-padded to 100 bytes so m = FLAG_int * 256^57; the full message is ~2^342, just above n^(1/3) ~ 2^341, so a naive cube root fails. Solution: exploit the known flag prefix 'crypto{' and suffix '}' to write m = A + By with only a 35-byte unknown y (~2^280 < n^(1/3)); the monic cubic (A+By)^3 - c ≡ 0 mod n has a small root y, recovered by Howgrave-Graham/Coppersmith univariate small-roots via fpylll LLL.

Null or Never — cryptohack (Padding)

Description

Non-standard padding considered harmful.

Files: pad_encrypt_17109ca1e3e5d0c90e47b9dd13fb6a60.py, null_output.txt (n, e, c), solver solve_null3.py + coppersmith2.py.

 python read-only • copy allowed Copy
def pad100(msg):
    return msg + b'\x00' * (100 - len(msg))   # RIGHT zero-padding

key = RSA.generate(1024, e=3)
n, e = key.n, key.e
m = bytes_to_long(pad100(FLAG))
c = pow(m, e, n)

The flag is 43 bytes (crypto{ + 35 unknown + }), right-padded with zeros to 100 bytes, then cubed mod a 1024-bit n. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

Right zero-padding multiplies by a power of 256:

m = FLAG_int · 256^(100 − 43) = FLAG_int · 256^57

• n ≈ 2^1024, so n^(1/3) ≈ 2^341.
• FLAG_int (43 bytes) is ≈ 2^342 and m ≈ 2^(342+456) — far above n, so the cube does wrap mod n. A plain integer cube root of c fails because m^3 > n and FLAG_int itself (2^342) just exceeds the Coppersmith bound n^(1/3) ≈ 2^341. We're a single bit short.

The fix: the flag format is a known prefix crypto{ and suffix }, leaving only the middle 35 bytes unknown. Let y = UNK (35 bytes, y < 2^280). With P = bytes_to_long(b"crypto{") and S = ord('}') = 0x7d: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

FLAG_int = P·256^36 + y·256 + S
m        = FLAG_int · 256^57
         = P·256^93 + y·256^58 + S·256^57
         = A + B·y,        A = P·256^93 + S·256^57,  B = 256^58

Now the unknown y < 2^280 < n^(1/3) ≈ 2^341, comfortably inside the Coppersmith bound. We must solve

(A + B·y)^3 − c ≡ 0   (mod n)

for the small root y. Normalize to a monic cubic in y by multiplying through by (B^3)^{-1} mod n:

y^3 + c2·y^2 + c1·y + c0 ≡ 0  (mod n),   small |y| ≤ X = 2^281

and recover y with Howgrave–Graham / Coppersmith univariate small-roots (LLL on the lattice of shift polynomials x^j · N^(m−i) · f^i and x^i · f^m). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python read-only • copy allowed Copy
from Crypto.Util.number import long_to_bytes, bytes_to_long
import gmpy2
from coppersmith2 import small_roots   # Howgrave-Graham, fpylll LLL

n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

P = bytes_to_long(b"crypto{"); S = ord('}')
A = P*256**93 + S*256**57          # known constant
B = 256**58                        # coefficient of y

# (A + B*y)^3 - c  -> monic in y by dividing by B^3 mod n
Binv3 = int(gmpy2.invert(pow(B,3,n), n))
c0 = ((A**3 - c) * Binv3) % n
c1 = (3*A**2*B * Binv3) % n
c2 = (3*A*B**2 * Binv3) % n
pol = [c0, c1, c2, 1]              # low->high, monic

X = 1 << 281                       # y < 2^280
for (mm, tt) in [(4,6),(6,10),(8,14),(10,18)]:
    roots = small_roots(pol, n, beta=1.0, mm=mm, tt=tt, X=X)
    for y in roots:
        if y > 0:
            flag = b"crypto{" + long_to_bytes(y).rjust(35, b'\x00') + b"}"
            m = bytes_to_long(flag + b'\x00'*(100-len(flag)))
            if pow(m,3,n) == c:
                print("FLAG=", flag); raise SystemExit

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

The small-roots routine builds the Coppersmith lattice and LLL-reduces it:

 python read-only • copy allowed Copy
# coppersmith2.small_roots (sketch)
#   g_{i,j} = x^j * N^(m-i) * f^i     (i=0..m-1, j=0..d-1)
#   h_i     = x^i * f^m               (i=0..t-1)
#   scale column j by X^j, LLL-reduce, read short vector back as a polynomial,
#   take its integer roots -> y.

Takeaways

• Right zero-padding of a low-exponent RSA message is just multiplication by 256^k; it does not randomize the message and is fully exploitable.
• When the cube root fails because the unknown is just above n^(1/3), exploit any known prefix/suffix (flag format!) to write m = A + B·y with a smaller unknown y, then solve (A + B·y)^e − c ≡ 0 mod n with Coppersmith univariate small-roots.
• Coppersmith works when the unknown is < n^(1/e); shaving even one byte off the unknown via the flag wrapper can move you under the bound. Tune lattice parameters (m, t) upward if the first LLL run yields no root. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍