Hack.lu-Qualifier-2023/Crypto/Lucky Numbers Writeup

1. challenge

• Author: zer0
• beginner-friendly!

Help me to find my lucky numbers. Bad luck is around...

nc flu.xxx 10010

Download challenge files

lucky_number.py

#!/usr/bin/env python
#hacklu23 Baby Crypyo Challenge
import math
import random
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
import base64
import os                                                   
    
def add(e): return e+(length-len(e)%length)*chr(length-len(e)%length)
def remove(e): return e[0:-ord(e[-1:])]
length=16 

def main():
flag= os.environ["FLAG"]
print("Starting Challenge")

key=get_random_bytes(32)
message=add(flag)
iv=get_random_bytes(length)
cipher=AES.new(key,AES.MODE_CBC,iv)
cipher_bytes=base64.b64encode(iv+cipher.encrypt(message.encode("utf8")))
print(cipher_bytes.decode())

for l in range(0,5):
A=[]
print("You know the moment when you have this special number that gives you luck? Great cause I forgot mine")
data2=input()
print("I also had a second lucky number, but for some reason I don't remember it either :(")
data3=input()
v=data2.strip()
w=data3.strip()
if not v.isnumeric() or not w.isnumeric():
print("You sure both of these are numbers?")
continue
s=int(data2)
t=int(data3)
if s<random.randrange(10000,20000):
print("I have the feeling the first number might be too small")
continue
if s>random.randrange(150000000000,200000000000):
print("I have the feeling the first number might be too big")
continue
if t>42:
print("I have the feeling the second number might be too big")
continue

n=2**t-1
sent=False
for i in range(2,int(n**0.5)+1):
if (n%i) == 0:
print("The second number didn't bring me any luck...")
sent = True
break
if sent:
continue
u=t-1
number=(2**u)*(2**(t)-1)
sqrt_num=math.isqrt(s)
for i in range(1,sqrt_num+1):
if s%i==0:
A.append(i)
if i!=s//i and s//i!=s:
A.append(s//i)
total=sum(A)
if total==s==number:
decoded=base64.b64decode(cipher_bytes)
cipher=AES.new(key,AES.MODE_CBC,iv)
decoded_bytes=remove(cipher.decrypt(decoded[length:]))
print("You found them, well done! Here have something for your efforts: ")
print(decoded_bytes.decode())
exit()
else:
print("Hm sadge, those don't seem to be my lucky numbers...😞")

print("Math is such a cool concept, let's see if you can use it a little more...")
exit()

if __name__ == "__main__":
main()

2. 分析

一个简单数学问题，也可以忽略数学关系，直接爆破。总之是一个新手友好题。

10000 <= s <= 200000000000, 0 <= t <= 42

if not v.isnumeric() or not w.isnumeric():
    print("You sure both of these are numbers?")
    continue
s=int(data2)
t=int(data3)
if s<random.randrange(10000,20000):
    print("I have the feeling the first number might be too small")
    continue
if s>random.randrange(150000000000,200000000000):
    print("I have the feeling the first number might be too big")
    continue
if t>42:
    print("I have the feeling the second number might be too big")
    continue

n 素数

n=2**t-1
sent=False
for i in range(2,int(n**0.5)+1):
     if (n%i) == 0:
        print("The second number didn't bring me any luck...")
        sent = True
        break
if sent:
    continue

u=t-1
number=(2**u)*(2**(t)-1)
sqrt_num=math.isqrt(s)
for i in range(1,sqrt_num+1):
    if s%i==0:
        A.append(i)
        if i!=s//i and s//i!=s:
            A.append(s//i)      
total=sum(A)
if total==s==number:
    # print flag

根据 直接生成 t 所对应的 s 即可，总计至多 42 个组合，不必处理 A 的生成。

实际上, s=sum(A) 是直接成立的。

3. solve

from Crypto.Util.number import isPrime

def solve():
answer = []
for t in range(42):
n = 2**t-1
if isPrime(n):
u = t-1
s = (2**u)*(2**(t)-1)
if 10000 <= s <= 200000000000:
answer.append((s, t))
return answer

answer = solve(); answer

[(33550336, 13), (8589869056, 17), (137438691328, 19)]

from pwn import *

r = remote(b"flu.xxx", 10010)

def io(s, t):
r.sendlineafter(b"Great cause I forgot mine", str(s).encode())
r.sendlineafter(b"I don't remember it either :(", str(t).encode())
r.recvuntil(b"for your efforts: n")
flag = r.recv()
print(flag)

io(*answer[0])
r.close()

[x] Opening connection to b'flu.xxx' on port 10010
[x] Opening connection to b'flu.xxx' on port 10010: Trying 31.22.123.45
[+] Opening connection to b'flu.xxx' on port 10010: Done
b'flag{luck_0n_fr1d4y_th3_13th?}n'
[*] Closed connection to b'flu.xxx' port 10010

4. Something interesting

官方服务器似乎少了一行代码：

if s<random.randrange(10000,20000):
    print("I have the feeling the first number might be too small")
    continue

导致有一些非预期解

❯ nc flu.xxx 10010

Starting Challenge
S8mQF5KqwDOu1PioMqy+ogh7o6V4YFEwy3ZNOLFFyBRPV4A8nsBoKbM1K8/1cnLu
You know the moment when you have this special number that gives you luck? Great cause I forgot mine
1
I also had a second lucky number, but for some reason I don't remember it either 
1
You found them, well done! Here have something for your efforts:
flag{luck_0n_fr1d4y_th3_13th?}

本文同步发表于

• blog: ssst0n3.github.io
• 公众号: 石头的安全料理屋
• 知乎专栏: 石头的安全料理屋