Lucky Number
5 minutes to read
We are given the server source code in Python:
#!/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()
Source code analysis
Although the source code might be a bit difficult to read, it is easy to understand. Basically, we are asked to enter two numbers s and t that satisfy a certain condition. If so happens, the flag will be printed out.
Note that the flag is encrypted at the beginning, but this is useless since it is decrypted by the server once we find such numbers s and t. Moreover, there is a for loop (for l in range(0,5)) that is also useless, since we only need one pair of values s and t.
Finding lucky numbers
There are some limitations on the values of s and t:
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
So, we conclude that $20000 \leqslant s < 150000000000$ and $0 \leqslant t \leqslant 42$.
After that, we have $n = 2^t - 1$ and the following check:
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
This check is verifying that $n$ is a prime number (there are no divisors below its square root, except for $1$). Therefore, we need that $n$ is a Mersenne prime number. We have these:
$ sage -q
sage: for t in range(43):
....: n = 2 ** t - 1
....: if is_prime(n):
....: print(t, n)
....:
2 3
3 7
5 31
7 127
13 8191
17 131071
19 524287
31 2147483647
After that, the server computes $u = t - 1$ and $\mathtt{number} = 2^u (2^t - 1)$. And there is another check:
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...😞")
If we pass this check, we will get the flag. This time, the check is just taking the divisors of $s$ and adding them up. If the sum of divisors (not counting the number $s$) equals both $s$ and $\mathtt{number}$, we pass the check.
Solution
Notice that the value of $t$ is one of ${2, 3, 5, 7, 13, 17, 19, 31}$, so we also have the possible values for $u$ and $\mathtt{number}$:
sage: for t in range(43):
....: n = 2 ** t - 1
....: if is_prime(n):
....: u = t - 1
....: number = 2 ** u * (2 ** t - 1)
....: print(t, n, u, number)
....:
2 3 1 6
3 7 2 28
5 31 4 496
7 127 6 8128
13 8191 12 33550336
17 131071 16 8589869056
19 524287 18 137438691328
31 2147483647 30 2305843008139952128
Therefore, one of these rightmost numbers must be valid. We can check if the sum of divisors is equal to those numbers:
sage: for t in range(43):
....: n = 2 ** t - 1
....: if is_prime(n):
....: u = t - 1
....: number = 2 ** u * (2 ** t - 1)
....: print(t, number, sum(divisors(number)) - number == number)
....:
2 6 True
3 28 True
5 496 True
7 8128 True
13 33550336 True
17 8589869056 True
19 137438691328 True
31 2305843008139952128 True
There we have it.
Flag
Let’s take one pair of them and send it to the server:
$ nc flu.xxx 10010
Starting Challenge
8J/XYznM/Qt94PG0Naw0HUun2JNhf/yezXuDmlXniZsN9jbO5+iisYXtvAmj/C+B
You know the moment when you have this special number that gives you luck? Great cause I forgot mine
33550336
I also had a second lucky number, but for some reason I don't remember it either :(
13
You found them, well done! Here have something for your efforts:
flag{luck_0n_fr1d4y_th3_13th?}