Lucky Number
5 minutos de lectura
Se nos proporciona el código fuente del servidor en 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()
Análisis del código fuente
Aunque el código fuente puede ser un poco difícil de leer, es fácil de entender. Básicamente, se nos pide que ingresemos dos números s y t que satisfagan una cierta condición. Si sucede, se mostrará la flag.
Nótese que la flag está cifrada al principio, pero esto es inútil ya que el servidor la descifra una vez que encontremos tales números s y t. Además, hay un bucle for (for l in range(0,5)) que también es inútil, ya que solo necesitamos un par de valores s y t.
Encontrando números de la suerte
Hay algunas limitaciones en los valores de s y 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
Entonces, concluimos que $20000 \leqslant s < 150000000000$ y $0 \leqslant t \leqslant 42$.
Después de eso, tenemos $n = 2^t - 1$ y la siguiente comprobació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
Esta comprobación verifica que $n$ es un número primo (no hay divisores debajo de su raíz cuadrada, excepto $1$). Por lo tanto, necesitamos que $m$ sea un primo de Mersenne. Tenemos estos:
$ 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
Después de eso, el servidor calcula $u = t - 1$ y $\mathtt{number} = 2^u (2^t - 1)$. Y aquí hay otra comprobación:
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...😞")
Si pasamos esta comprobación, obtendremos la flag. Esta vez, la comprobación solo está tomando los divisores de $s$ y sumándolos. Si la suma de divisores (sin contar el propio número $s$) es igual a $s$ y a $\mathtt{number}$, pasamos la comprobación.
Solución
Obsérvese que el valor de $t$ es uno de ${2, 3, 5, 7, 13, 17, 19, 31}$, por lo tanto, también tenemos los valores posibles para $u$ y $\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
Entonces, uno de estos números de la derecha debe ser válido. Podemos verificar si la suma de divisores es igual a esos números:
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
Ahí los tenemos.
Flag
Tomemos un par de ellos y enviémoslo al servidor:
$ 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?}