This past weekend, my team participated in UIUCTF. I was able to solve 3 of the 4 cryptography challenges.
Overall, these weren’t too challenging, but I couldn’t figure out the fourth without brute forcing (challenge name: too many primes).
My biggest two lessons here were that AI is very useful at identifying named
math concepts and that sympy is another powerful math library alongside z3.
I’ve designed the shortest crypto challenge - can you find the flag?
author: epistemologist
We get a single Python file, chal.py:
from Crypto.Cipher import AES
from hashlib import md5
from secret import a,b,c,d, FLAG
assert a**4 + b**4 == c**4 + d**4 + 17 and max(a,b,c,d) < 2e4 and AES.new( f"{a*b*c*d}".zfill(16).encode() , AES.MODE_ECB).encrypt(FLAG).hex() == "41593455378fed8c3bd344827a193bde7ec2044a3f7a3ca6fb77448e9de55155"
We are given an ciphertext encrypted in AES ECB, where the key is derived from 4 integers. Those 4 integers are all less than 20,000 and satisfy a polynomial equation.
In researching this problem, I found out that these were called Diophantine equations.
Up to a certain maximum, we can calculate every integer to the fourth power and store it in a map. Then, we can calculate every possible sum. The second time we do that, we check to see if the sum minus 17 is already present. If it is, we’ve found the solution.
I wrote a simple Python script to run this up to 1,000. 20,000 would take too long.
from Crypto.Cipher import AES
from collections import defaultdict
ciphertext_hex = "41593455378fed8c3bd344827a193bde7ec2044a3f7a3ca6fb77448e9de55155"
ciphertext = bytes.fromhex(ciphertext_hex)
MAX = 1000
pow4 = [i**4 for i in range(MAX)]
sums = defaultdict(list)
for a in range(1, MAX):
print(f"{a=}")
for b in range(a, MAX):
s = pow4[a] + pow4[b]
sums[s].append((a, b))
for c in range(1, MAX):
print(f"{c=}")
for d in range(c, MAX):
s2 = pow4[c] + pow4[d]
s1 = s2 + 17
if s1 in sums:
for a, b in sums[s1]:
product = a * b * c * d
key_str = str(product).zfill(16)
if len(key_str) != 16: # too long
continue
key = key_str.encode()
cipher = AES.new(key, AES.MODE_ECB)
plaintext = cipher.decrypt(ciphertext)
print(f"Found solution: a={a}, b={b}, c={c}, d={d}")
print(f"Key (decimal): {key_str}")
print(f"Decrypted plaintext: {plaintext}")
exit()
Running this was pretty quick, and we get the flag:
Found solution: a=264, b=651, c=530, d=570
Key (decimal): 0000051920114400
Decrypted plaintext: b'uiuctf{D1oPh4nTine__Destr0yer__}'
I don’t think you can predict my secret number from just its square root - can you prove me wrong?
author: epistemologist
We’re given two files: chal.py and output.txt.
chal.py:
from random import randint
from decimal import Decimal, getcontext
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import FLAG
K = randint(10**10, 10**11)
print('K', K)
leak = int( str( Decimal(K).sqrt() ).split('.')[-1] )
print(f"leak = {leak}")
ct = AES.new(
md5(f"{K}".encode()).digest(),
AES.MODE_ECB
).encrypt(pad(FLAG, 16))
print(f"ct = {ct.hex()}")
output.txt:
leak = 4336282047950153046404
ct = 7863c63a4bb2c782eb67f32928a1deceaee0259d096b192976615fba644558b2ef62e48740f7f28da587846a81697745
From here, we can see that we need to solve for K to decrypt the AES ECB ciphertext.
We are given the decimal part of the square in leak. However, since K is
not a square (the decimal part is not 0), this is almost certainly rounded.
I created a Python script to iterate over all possible square roots. To ensure that precision was not an issue, I added a filter to check close decimals.
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from decimal import Decimal, getcontext
getcontext().prec = 50
leak = 4336282047950153046404
ct_hex = "7863c63a4bb2c782eb67f32928a1deceaee0259d096b192976615fba644558b2ef62e48740f7f28da587846a81697745"
ct = bytes.fromhex(ct_hex)
d = len(str(leak))
f = Decimal(leak) / (10 ** d)
start = int(Decimal(10**10).sqrt())
end = int(Decimal(10**11).sqrt()) + 1
for N in range(start, end):
candidate = int( (Decimal(N) + f) ** 2 )
root_str = str(Decimal(candidate).sqrt())
fractional_str = root_str.split('.')[-1][:d]
# filter the results
if fractional_str.startswith("433628204"):
print(fractional_str, leak, candidate)
print("Found K:", candidate)
key = md5(str(candidate).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
try:
flag = unpad(cipher.decrypt(ct), 16)
print("FLAG:", flag)
break
except:
pass
It solves pretty quickly:
4336282047950153046403 4336282047950153046404 41642293072
Found K: 41642293072
FLAG: b'uiuctf{SQu4Re_Ro0T5_AR3nT_R4nD0M}'
I’m using four primes to encrypt my flag, so I’m only giving you three hints - can you decrypt the flag?
author: epistemologist
We’re given two files: chal.py and output.txt.
chal.py:
from Crypto.Util.number import *
from secret import FLAG
p, q, r, s = [getPrime(512) for _ in "1234"]
print(f"h1 = {p + q + r + s}")
print(f"h2 = {p**2 + q**2 + r**2 + s**2}")
print(f"h3 = {p**3 + q**3 + r**3 + s**3}")
N = p*q*r*s
print(f"N = {N}")
pt = bytes_to_long(FLAG)
ct = pow(pt, 65537, N)
print(f"ct = {ct}")
output.txt:
h1 = 44626154099651354925697068610752642661842459492769931945027538340211738148995902544351457443643808803963130274930824732652561687395268828472477422919262224
h2 = 516671113554555861164166966331322883848052630063409185414998284127910160310316421085219788291486248715029393774584960034375836715001130337767354512063372620828300201147366138270597133744747341658011663632381219284289144790858167258162656417236910634201286428763727072739569460623482985066956478781223378673732
h3 = 6147718474663450187001867904227777991349731066494841442199681943204194617136760567222545181562592364728655444222576167723225771866335920325045525027985716792468801076590684892140052786942251780392395274059384743594570343510311801194684613435002073956759521242578078411431891501758484581445964234548107005826532945720412531638919892681259687552977883437895032963223761216846303917338652743754915155934118353066174102436448393348040719582422022713292561416343278608
N = 14184841414933523698606245433393907034474143715949896731683874356940146602876788990832087413915033843120975580859113356518777762025417525571528638829956003882418585702756644491932279294535883798799580861254646149745925137179207140600356428758736111639677698862407787386573263961111978517446397007747429416079059195916290615125084899002162504424765939524455434579218079962808920072946861658695379491917567048202142417165204141307476222251547098848515065051745905180788313450494477967398727631152936238366581978379130450660235139256967936160718128731512409111209840405772933034600016694225294481603355934917366484109057
ct = 720607330561370237459911161481490697044029472780348552630924063963226757984368356580217337982783395620115957442082471977614781910209933696251479615689667675958354681196823652299435457532944189300223816303315625302472302494905575910600277892375951366031061219173465155686586206246661009612156094695841741309002508535764511343569015518587247600796520847856011377777228749182958947015029731456117404560626347774985507275302882865400315045173501559082431672490227728580592379740508214726249635835834752208899970446910850569489282065524329936561486377823093465841715608716032843259935185417766702677708267102415636848129
I used AI to help me with this problem, discovering that the hints can be used in Newton’s identities.
Because of this, the hints can be used to create a polynomial expression,
which the sympy library can solve.
Here’s my Python script:
from sympy import symbols, Poly
from Crypto.Util.number import long_to_bytes
h1 = 44626154099651354925697068610752642661842459492769931945027538340211738148995902544351457443643808803963130274930824732652561687395268828472477422919262224
h2 = 516671113554555861164166966331322883848052630063409185414998284127910160310316421085219788291486248715029393774584960034375836715001130337767354512063372620828300201147366138270597133744747341658011663632381219284289144790858167258162656417236910634201286428763727072739569460623482985066956478781223378673732
h3 = 6147718474663450187001867904227777991349731066494841442199681943204194617136760567222545181562592364728655444222576167723225771866335920325045525027985716792468801076590684892140052786942251780392395274059384743594570343510311801194684613435002073956759521242578078411431891501758484581445964234548107005826532945720412531638919892681259687552977883437895032963223761216846303917338652743754915155934118353066174102436448393348040719582422022713292561416343278608
N = 14184841414933523698606245433393907034474143715949896731683874356940146602876788990832087413915033843120975580859113356518777762025417525571528638829956003882418585702756644491932279294535883798799580861254646149745925137179207140600356428758736111639677698862407787386573263961111978517446397007747429416079059195916290615125084899002162504424765939524455434579218079962808920072946861658695379491917567048202142417165204141307476222251547098848515065051745905180788313450494477967398727631152936238366581978379130450660235139256967936160718128731512409111209840405772933034600016694225294481603355934917366484109057
ct = 720607330561370237459911161481490697044029472780348552630924063963226757984368356580217337982783395620115957442082471977614781910209933696251479615689667675958354681196823652299435457532944189300223816303315625302472302494905575910600277892375951366031061219173465155686586206246661009612156094695841741309002508535764511343569015518587247600796520847856011377777228749182958947015029731456117404560626347774985507275302882865400315045173501559082431672490227728580592379740508214726249635835834752208899970446910850569489282065524329936561486377823093465841715608716032843259935185417766702677708267102415636848129
e = 65537
# newton identity stuff
e1 = h1
e2 = (h1**2 - h2) // 2
e3 = (h3 - h1*h2 + e2*h1) // 3
e4 = N
print(f"e1 = {e1}")
print(f"e2 = {e2}")
print(f"e3 = {e3}")
print(f"e4 = {e4}")
# sympy stuff
x = symbols('x')
poly = Poly(x**4 - e1*x**3 + e2*x**2 - e3*x + e4, x)
factors = poly.factor_list()
roots = poly.all_roots(multiple=True)
print("Roots found (primes):")
for r in roots:
print(r)
# rsa stuff
p, q, r_, s = map(int, roots)
phi = (p-1)*(q-1)*(r_-1)*(s-1)
d = pow(e, -1, phi)
pt = pow(ct, d, N)
flag = long_to_bytes(pt)
print(flag)
Running gets the flag:
Roots found (primes):
7548210482031609254628239036450585126524219969101102758036356349664202189278050471821942598957928240892636138652241695616938250284364193387975349110335791
11720509023745330070672352993621618878401984828217667437378771886004263652565157044932587605594433712470181772050839394068041899938309942718323837036598733
12036239395955851928437393753272811434205086687378868594232210979013306320271322657469384311636175924595668977932222047946559068828189128531559625931330991
13321195197918563671959082827407627222711168008072293155380199125529965986881372370127542927455270926004643386295521595021022468344405563834618610840996709
b'uiuctf{5yMmeTRiC_P0lyS_FoRM_A_B4S15}'