Vote for Pedro

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: cube_root_mod_2k, hensel_lifting, small_cube_no_modular_reduction, suffix_forgery

Summary

Task: a voting server computes pow(vote, 3, N) and strips padding by splitting on NUL and taking the last chunk, accepting it if it equals b'VOTE FOR PEDRO'. Solution: only the low 120 bits of the decryption must equal b'\x00VOTE FOR PEDRO', so solve x^3 ≡ bytes_to_long(b'\x00VOTE FOR PEDRO') mod 2^120 by Hensel lifting; because x is small, x^3 < N means no modular reduction happens, so pow(x,3,N) decodes to bytes literally ending in the target string, passing the check.

Vote for Pedro — cryptohack (Signatures)

Description

"Place your vote. Pedro offers a reward to anyone who votes for him!"

File: 13375_7eaca879f3911da349a7248f302c6344.py, key alice_*.key (N, e=3), solver solve_ch4.py. Live service: socket.cryptohack.org:13375.

 python read-only • copy allowed Copy
ALICE_E = 3
def challenge(self, your_input):
    if your_input['option'] == 'vote':
        vote = int(your_input['vote'], 16)
        verified_vote = long_to_bytes(pow(vote, ALICE_E, ALICE_N))
        vote = verified_vote.split(b'\x00')[-1]      # take LAST chunk after NUL split
        if vote == b'VOTE FOR PEDRO':
            return {"flag": FLAG}

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

The server "verifies" a vote by computing pow(vote, 3, N), splitting the byte string on \x00, and accepting if the last chunk equals b'VOTE FOR PEDRO'.

Analysis

We need a number x (our vote) such that pow(x, 3, N) decodes to bytes that end with ...\x00VOTE FOR PEDRO (the \x00 guarantees VOTE FOR PEDRO is its own trailing chunk after the split). Two observations make this trivial:

1. Only the suffix matters. The split-on-NUL/last-chunk logic ignores everything above the trailing \x00VOTE FOR PEDRO. So we only need to control the low 8·15 = 120 bits of the plaintext, namely T = bytes_to_long(b'\x00VOTE FOR PEDRO'). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

2. Make the cube small so there's no modular reduction. If we find a small x with x^3 < N and x^3 ≡ T (mod 2^120), then pow(x, 3, N) = x^3 exactly (no wraparound), and its byte encoding literally ends in \x00VOTE FOR PEDRO. T is 120 bits, so a cube root mod 2^120 gives x ≈ 2^40, and x^3 ≈ 2^120 ≪ N (1024-bit).

Solving x^3 ≡ T (mod 2^120) is a Hensel lifting problem. T is odd (trailing byte 'O' = 0x4F), so a unique odd cube root exists mod each power of 2, lifted bit by bit: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

x_0 = 1 (mod 2);  at each step decide whether to add 2^i so that x^3 ≡ T (mod 2^(i+1))

Solution

 python read-only • copy allowed Copy
from Crypto.Util.number import bytes_to_long, long_to_bytes

ALICE_N = 22266616657574989868109324252160663470925207690694094953312891282341426880506924648525181014287214350136557941201445475540830225059514652125310445352175047408966028497316806142156338927162621004774769949534239479839334209147097793526879762417526445739552772039876568156469224491682030314994880247983332964121759307658270083947005466578077153185206199759569902810832114058818478518470715726064960617482910172035743003538122402440142861494899725720505181663738931151677884218457824676140190841393217857683627886497104915390385283364971133316672332846071665082777884028170668140862010444247560019193505999704028222347577
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def cube_root_mod_2k(T, k):
    assert T % 2 == 1
    x = 1
    for i in range(1, k):
        mod = 1 << (i + 1)
        if pow(x, 3, mod) != (T % mod):
            x += (1 << i)
        assert pow(x, 3, mod) == (T % mod)
    return x

suffix = b'\x00VOTE FOR PEDRO'
T = bytes_to_long(suffix)
m = cube_root_mod_2k(T, 8 * len(suffix))     # 120 bits
assert pow(m, 3) < ALICE_N                    # small cube -> no mod reduction
assert long_to_bytes(pow(m, 3, ALICE_N)).split(b'\x00')[-1] == b'VOTE FOR PEDRO'
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# send vote = hex(m); server returns the flag
print(format(m, 'x'))

Sending vote = hex(m) makes the server compute m^3 (un-reduced), strip the NUL, see VOTE FOR PEDRO, and return the flag.

Takeaways

• When an RSA "verify" only checks a suffix of the decrypted bytes (split-on-NUL, endswith, last-chunk), you only need to control the low bits of the plaintext.
• Solve x^e ≡ target (mod 2^k) by Hensel lifting (unique odd root for odd target), and keep x small enough that x^e < N so pow(x,e,N) performs no modular reduction — the cube then decodes to bytes literally ending in your target.
• This is the same "suffix forgery via small cube" trick that breaks lazy e=3 signature/format checks; the NUL-split padding logic is the real bug. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍