Rating:
We are given a following script.
```
#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
import sys
import os
from secret import flag
MAX_COUNT = 128
key = RSA.generate(2048, e = 1337)
token = os.urandom(len(flag))
def loop():
print('My public modulus is:\n%d' % key.n)
print('Let me count how long it takes you to find the secret token.')
for counter in range(MAX_COUNT):
message = b'So far we had %03d failed attempts to find the token %s' % (counter, token)
print(pow(bytes_to_long(message), key.e, key.n))
print('What is your guess?')
sys.stdout.flush()
guess = sys.stdin.buffer.readline().strip()
if guess == token:
print('Congratulations for finding the token after %03d rounds. Here is your flag: %s' % (counter, flag))
sys.stdout.flush()
return
print('Nope! No more attempts.')
if __name__ == '__main__':
try:
loop()
except Exception as err:
print('encountered some error')
```
The service encrypts the same message with only difference is in the middle where the round number changes. It is then possible to know the difference between each message, hence we can perform franklin-reiter related message attack, one problem is the token length is unknown so we cannot count the difference between the message (Think of it like this, the difference between AAAAA -> BAAAA is not the same as AAAAAAAAAAA -> BAAAAAAAAAA). But assuming the length of the flag is somewhat reasonable and because the token have the same length as the flag, we can simply bruteforce the length of the token.
```
from sage.all import *
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
def franklinreiter(C1, C2, e, N, a, b):
print(a,b)
# P.<X> = PolynomialRing(Zmod(N))
P = PolynomialRing(Zmod(N), names=('X',))
(X,) = P._first_ngens(1)
g1 = (a*X + b)**e - C1
g2 = X**e - C2
print("Result")
result = -gcd(g1, g2).coefficients()[0]
return long_to_bytes(int(result))
from pwn import *
context.log_level = "debug"
e = 1337
r = remote("52.59.124.14", 10008)
r.recvuntil("My public modulus is:\n")
N = int(r.recvline().strip())
r.recvline()
C1 = int(r.recvline().strip())
r.recvline()
r.sendline(b"0")
C2 = int(r.recvline().strip())
print(N, C1, C2)
a = 1
counter = 0
for i in range(5, 50):
message = b'So far we had %03d failed attempts to find the token %s' % (counter, b"A"*i)
message2 = b'So far we had %03d failed attempts to find the token %s' % (counter+1, b"A"*i)
print(bytes_to_long(message2) - bytes_to_long(message))
m = franklinreiter(C2, C1, e, N, a, bytes_to_long(message2) - bytes_to_long(message))
print(i, m)
if b"So far" in m:
print("FOUND", i)
break
r.sendline(m.split(b"token ")[1])
r.interactive()
```
