Vote for Pedro

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: cube_root_mod_2k, hensel_lifting, small_cube_no_modular_reduction, suffix_forgery

Summary

Walkthrough of the CUSTOM Crypto Vote for Pedro. 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 dec

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. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering cube_root_mod_2k, hensel_lifting, small_cube_no_modular_reduction, suffix_forgery was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-06-22 • CUSTOM • Vote for Pedro • Difficulty: Medium