search
Homepwn

kleinvieh_2

This Challenge was covered in nullcon CTF 2025, this is a writeup.

Before I start I liked this challenge because it's a nice coppersmith exercise, ensuring proper understanding of the technique.

hashtag
Handouts

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
import math

# Utility functions
def chunks(l : list, n : int):
	"""Yield successive n-sized chunks from l."""
	for i in range(0, len(l), n):
		yield l[i:i + n]

# Encryption Methods

def encrypt1(message : bytes, key):
	return pow(bytes_to_long(message), key.e, key.n)

def encrypt2(message : bytes, key):
	r = 6882340053480090463606763880215995523230790077054797279541
	48955984833460337936950913921276804334830417982234720038650432
	72978049851415599561893741257560419681569060516183575560934138
	10921455481533129431196963983261449026392268314712005423371052
	82064399184931676924592908530791494346900227871404063095592748
	76429602825553057727865668046378265513942121930242289966766533
	92778247184219018318170431595521322520169452263706772780674245
	06514993298100924479619565269428391036310378044733517453768164
	25265593111120208943269707894718448626786594313865983615593934
	31347384089724269793291585060272806532093184794138952597743198
	48662706808171929571545923310500352950348748809789292920278241
	36201527896331548177702899734448017201096029400209857898946908
	92940225901348239139368695489071252944474774307390967674740264
	01347928008150737871869441842515706902681140123776591020038755
	23464218469985651732600457439392216291883939633654162021229687
	08326595761950104668967012490038085535608952398604541628467596
	35434691728716499056221797005696650174933343585361153344017021
	74782738919340566707333344356965956756224740628328245128415514
	97807379047609899109445504993166551283948992292847965847871986
	89342431338201610314893908441661953172106881929330452489260
	return pow(bytes_to_long(message) * r, key.e, key.n)

def encrypt3(message : bytes, key):
	bytelength = int(math.floor(math.log2(key.n))) // 8
	msg = message + b'\x00' * (bytelength - len(message))
	return pow(bytes_to_long(msg), key.e, key.n)

def encrypt4(message : bytes, key):
	bytelength = int(math.floor(math.log2(key.n))) // 8
	msg = message * (bytelength // len(message))
	return pow(bytes_to_long(msg), key.e, key.n)

def encrypt5(message : bytes, key):
	bytelength = int(math.floor(math.log2(key.n))) // 8
	msg = b'\x42' * (bytelength - len(message)) + message
	return pow(bytes_to_long(msg), key.e, key.n)

# Actual code
flag = open('flag.txt','r').read()
messages = [x for x in chunks(flag.encode(), len(flag) // 5 + 1)]

key = RSA.generate(4096, e = 3)
key_file = open('pubkey.pem','wb')
key_file.write(key.public_key().export_key())
key_file.close()

encryptors = [encrypt1,encrypt2,encrypt3,encrypt4,encrypt5]

for i in range(5):
	print(encryptors[i](messages[i], key))

hashtag
Analysis & Solver

So generally speaking, our plaintext is segmented into 5 different chunks, each chunk is encrypted using one of the encryptors sequentially, we're given the output of each chunk, and the public key used for encryption.

We know that e = 3 and N is 4096 bits long so 512 bytes.

hashtag
encrypt1

This function encrypts the first chunk of the flag with the public key.

Now since N is so big and e is so small and the fact the length of each chunk of plaintext is only a fraction of the length of the flag, this makes me think that pte<Npt^e < N, we can try finding the cubic root.

hashtag
encrypt2

This function multiplies a big number r with the plaintext chunk then encrypts it with the public key.

In this case, (pt×r)3>N(pt \times r)^3 > N, this calls for coppersmith's method.

hashtag
Coppersmith's Method

There is an advanced technique known as Coppersmith’s method which can sometimes recover small roots of univariate modular polynomial equations. The idea is that if the unknown mm (or in this case, m×rm \times r ) is small relative to N1eN^{\frac{1}{e}}.

So, (with e=3, roughly if

m×r<N1em \times r < N^{\frac{1}{e}}

even after reduction), then one might set up a polynomial equation:

f(x)=(r×m)3−c≡0(modN)f(x) = (r\times m)^3 -c \equiv 0\pmod N

where 𝑐 is your ciphertext, 𝑟 is the known constant, and the unknown 𝑥 corresponds to the message 𝑚 (since during encryption f(x)=x∗e2piiξxf(x) = x * e^{2 pi i \xi x}c=(m×r)3mod  Nc = (m \times r)^3 \mod N. The idea is that if the actual value 𝑚 is small enough relative to 𝑛 , then there exists an integer root x0x_0 of f(x)f(x) (with x0=mx_0 = m) that can be recovered by Coppersmith’s method.

hashtag
encrypt3

In this case the message is padded with null bytes for the 493 bytes (equalizing the padded plaintext bitlength with Ns bitlength)

what we did is M || "0x00" * 493 which is equivalent to a 493 bit shift to the left and can be represented like this: c=(pt∗2(511−18)×8)3mod  Nc = (pt * 2^{(511 - 18) \times 8})^3 \mod N, we can map this similarly to encrypt3 where r = 2 ** ((511 - 18) * 8) .

hashtag
encrypt4

This function pads the message with copies of itself until its bitlength is as long or longer than the bitlength of N.

hashtag
Representing the Repeated Message as an Integer

given that the length of our message (L) = 18

Concatenating bytes is equivalent to “shifting” and adding. In our case, the integer corresponding to the repeated message is

msg=M×Smsg = M \times S

where:

S=2560×L+2561×L+2562×L+...+256(k−1)×LS = 256^{0 \times L} + 256^{1 \times L} + 256^{2 \times L} + ... + 256^{(k-1) \times L}

Since 256L=28×L256^L = 2^{8\times L} the sum S is a geometric series:

S=1+256L+2562L+...+256(k−1)LS = 1 + 256^{L} + 256^{2 L} + ... + 256^{(k-1) L}

Its closed‐form is

S=256kL−1256L−1S = \frac {256^{kL} -1}{256^{L} -1}

We can represent c=S3∗M3mod  Nc = S^3 * M^3 \mod N, now if we wanna get rid of that S factor, we can find a=c×S−3=M3mod  Na = c \times S^{-3} = M^3 \mod N

That way we could write our polynomial in the form:

f(x)=x3−af(x) = x^3 - a

hashtag
encrypt5

This encryption pads "B" onto the most siginificant bits of the plaintext until its full bitlength has less than 144 bits difference from the bitlength of N

k=bytelength−L.k=bytelength−L.

so k = 511 - 18 = 493 bytes

Representing the Padded Message as an Integer:

Think of the padded message as a number in base 256. The left part is all the constant byte \x42, and the right part is the actual message. This number can be expressed as:

m=S×256L+Mm=S\times256^L+M

where:

  • M is the integer representation of the original 18-byte message.

  • S represents the contribution of the repeated \x42 bytes.

    Since each \x42 corresponds to the number 0x42, and there are k=493 of them, concatenated in base 256, we have:

S=0x42×(1+2560+2561+2562+...+256(k−1))S = \text{0x42} \times (1 + 256^{0} + 256^{1} +256^{2} + ... + 256^{(k-1)})

Its closed-form is:

S=0x42×256k−1256−1S = \text{0x42} \times \frac {256^{k} -1}{256 -1}

We can represent c≡(S×25618+M)3(modN)c \equiv (S \times 256^{18} + M)^3 \pmod N , let us set A=S×25618A = S \times 256^{18}, we can represent our polynomial

That way we could write our polynomial in the form:

f(x)=(x+A)3−cmod  Nf(x) = (x + A)^3 - c \mod N

and solve for 0.

PreviousBreaking RandomnessNextquickprime

Last updated