<- CRYPTO

TurboCipher

7 minutes to read

This challenge was made by me for Hack The Box. We are given the Python source code of a server:

#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, getPrime, getRandomRange
from secret import FLAG, fast_turbonacci, fast_turbocrypt
from typing import Callable


def turbonacci(n: int, p: int, b: int, c: int) -> int:
    if n < 2:
        return n

    return (b * turbonacci(n - 1, p, b, c) + c * turbonacci(n - 2, p, b, c)) % p  


def lcg(x: int, m: int, n: int, p: int) -> int:
    return (m * x + n) % p


def turbocrypt(pt: int, k: int, f: Callable[[int], int]) -> int:
    return sum((f(i + 1) - f(i)) for i in range(k, pt))


def menu() -> int:
    print('Choose one option')
    print('1. Encrypt flag')
    print('2. Encrypt ciphertext')
    print('3. Exit')

    return int(input('> '))


def main():
    while True:
        b, c, p = getPrime(512), getPrime(512), getPrime(512)

        try:
            for i in range(10):
                assert turbonacci(i, p, b, c) == fast_turbonacci(i, p, b, c)
                assert turbocrypt(i, -1, int) == fast_turbocrypt(i, -1, int)

            break
        except Exception:
            pass

    print('Welcome to TurboCipher. Please login first')
    print(f'MathFA enabled. Parameters:\n{p = }\n{b = }\n{c = }\n')

    nonce = getRandomRange(1, p)
    print(f'Please, use {nonce = } to generate for your TurbOTP')

    otp = int(input('OTP: '))

    if otp != fast_turbonacci(nonce, p, b, c):
        print('Login incorrect')
        exit(1)

    print('Login successful')

    m, n, k = getPrime(512), getPrime(512), getPrime(512)

    def f(x: int) -> int: return lcg(x, m, n, p)

    while (option := menu()) != 3:
        if option == 1:
            assert len(FLAG) * 8 <= p.bit_length()
            print(f'ct = {fast_turbocrypt(bytes_to_long(FLAG), k, f) % p}')

        if option == 2:
            pt = input('pt = ').strip().encode()
            assert len(pt) * 8 <= p.bit_length()
            print(f'ct = {fast_turbocrypt(bytes_to_long(pt), k, f) % p}')

    print('Thank you for using TurboCipher. See you soon!')


if __name__ == '__main__':
    main()

It uses a secret module to import FLAG, and two functions fast_turbonacci and fast_turbocipher, which are unknown.

First, the server asks for an OTP:

$ nc 161.35.164.52 32367
Welcome to TurboCipher. Please login first
MathFA enabled. Parameters:
p = 10661659656379701807207261625348824751044033238211111392569849487054221229293575280702103750314537453326306932228658369569073454707040110605919691900717053
b = 12467593298053953965932052065048352989295927860843731540896042086471795704069496789019816662750919938406850889847371974931468184690216537470130947978922201
c = 11194882392775831341327777305934471543299757495348856577436606655177652476332452517826350158956329959274674376711531677439838317968689922977478169623064503

Please, use nonce = 2791192687229595789736103907396883444691405059827201603678061147070993788594701998445970292672198658759814772391655851185818845695170123065778918881488885 to generate for your TurbOTP  
OTP: 1234
Login incorrect

Recurrence relation

This OTP is computed using fast_turbonacci, but we are only given turbonacci:

def turbonacci(n: int, p: int, b: int, c: int) -> int:
    if n < 2:
        return n

    return (b * turbonacci(n - 1, p, b, c) + c * turbonacci(n - 2, p, b, c)) % p

It looks like a Fibonacci sequence, but adding coefficients b and c and using modulo p. Let’s define $T_n$ as the $n$-th term of the Turbonacci sequence:

$$ T_0 = 0 $$

$$ T_1 = 1 $$

$$ T_n = b \cdot T_{n - 1} + c \cdot T_{n - 2} \mod{p} \quad, n > 1 $$

For the OTP, we are given a nonce value. And the OTP is $T_\text{nonce}$.

Obviously, we can’t use the provided turbonacci function because it is recursive and won’t work for a big value. Hence, we must find a closed form for the Turbonacci sequence.

Finding a closed form

We can begin by taking the characteristic polynomial (we can forget about the modulo for the moment):

$$ t^n = b \cdot t^{n - 1} + c \cdot t^{n - 2} $$

Which is equivalent to

$$ t^2 = b \cdot t + c $$

Now we solve the quadratic equation:

$$ t = \frac{b \pm \sqrt{b^2 + 4c}}{2} $$

And with this, we can express $T_n$ as

$$ T_n = \alpha \cdot \left(\frac{b + \sqrt{b^2 + 4c}}{2}\right)^n + \beta \cdot \left(\frac{b - \sqrt{b^2 + 4c}}{2}\right)^n $$

Let $r_1 = \frac{b + \sqrt{b^2 + 4c}}{2}$ and $r_2 = \frac{b - \sqrt{b^2 + 4c}}{2}$.

In order to find $\alpha$ and $\beta$, we can use two known values (for instance, $T_0$ and $T_1$).

$$ \begin{cases} T_0 = \alpha + \beta = 0 \newline T_1 = \alpha \cdot r_1 + \beta \cdot r_2 = 1 \end{cases} $$

And we have to solve a system of two linear equations:

$$ \alpha = \frac{1}{r_1 - r_2} = -\beta $$

And now we have a closed form for $T_n$:

$$ T_n = \frac{r_1^n - r_2^n}{r_1 - r_2} $$

Ok, it is time to apply modulo $p$.

In order to compute $\sqrt{\Delta} = \sqrt{b^2 + 4c} \pmod{p}$, we will need Tonelli-Shanks or Cipolla methods (find $x$ such that $x^2 \equiv n \pmod{p}$).

We need to change every division into a multiplicative inverse modulo $p$.

In the end, we can implement fast_turbonacci as follows:

def fast_turbonacci(n: int, p: int, b: int, c: int) -> int:
    sqrt_delta = tonelli((pow(b, 2, p) + 4 * c), p)
    r1 = (b + sqrt_delta) * pow(2, -1, p) % p
    r2 = (b - sqrt_delta) * pow(2, -1, p) % p
    return (pow(r1, n, p) - pow(r2, n, p)) * pow(r1 - r2, -1, p) % p

We can start creating a Python script to enter the OTP:

def main():
    io = get_process()
    io.recvuntil(b'p = ')
    p = int(io.recvline().decode())

    io.recvuntil(b'b = ')
    b = int(io.recvline().decode())

    io.recvuntil(b'c = ')
    c = int(io.recvline().decode())

    io.recvuntil(b'nonce = ')
    nonce = int(io.recvuntil(b' ').strip().decode())  

    otp = fast_turbonacci(nonce, p, b, c)

    io.sendlineafter(b'OTP: ', str(otp).encode())
    io.interactive()

$ python3 solve.py 161.35.164.52:32367
[+] Opening connection to 161.35.164.52 on port 32367: Done  
[*] Switching to interactive mode
Login successful
Choose one option
1. Encrypt flag
2. Encrypt ciphertext
3. Exit
> $

Alternative

Another way of finding the OTP is by computing the nonce power of the following matrix under $\mathbb{F}_p$:

$$ \begin{pmatrix} b & 1 \\ c & 0 \end{pmatrix} $$

The OTP will be the up-left entry of the resulting matrix.

Telescoping series

Alright, now we can get the encrypted flag and also encrypt arbitrary plaintexts:

    while (option := menu()) != 3:
        if option == 1:
            assert len(FLAG) * 8 <= p.bit_length()
            print(f'ct = {fast_turbocrypt(bytes_to_long(FLAG), k, f) % p}')  

        if option == 2:
            pt = input('pt = ').strip().encode()
            assert len(pt) * 8 <= p.bit_length()
            print(f'ct = {fast_turbocrypt(bytes_to_long(pt), k, f) % p}')

The encryption is handled using fast_turbocrypt, but we only have turbocrypt:

def turbocrypt(pt: int, k: int, f: Callable[[int], int]) -> int:  
    return sum((f(i + 1) - f(i)) for i in range(k, pt))

We can express this function in mathematical terms as (let’s call it $E$):

$$ E(\text{pt}) = \sum_{i = k}^{\text{pt} - 1} f(i + 1) - f(i) $$

This is a telescoping series, and its closed form is:

$$ E(\text{pt}) = f(\text{pt}) - f(k) $$

Hence, fast_turbocrypt is:

def fast_turbocrypt(pt: int, k: int, f: Callable[[int], int]) -> int:  
    return f(pt) - f(k)

Linear Congruential Generator

The function f is a Linear Congruential Generator (LCG):

def lcg(x: int, m: int, n: int, p: int) -> int:
    return (m * x + n) % p


# ...


def main():
    # ...

    m, n, k = getPrime(512), getPrime(512), getPrime(512)

    def f(x: int) -> int: return lcg(x, m, n, p)

    while (option := menu()) != 3:
        if option == 1:
            assert len(FLAG) * 8 <= p.bit_length()
            print(f'ct = {fast_turbocrypt(bytes_to_long(FLAG), k, f) % p}')  

        # ...

So,

$$ f(x) = m \cdot x + n \pmod{p} $$

We know modulo $p$ from the beginning, but we don’t have $m$ and $n$.

Understanding encryption

The encryption function maps $\text{pt} \mapsto E(\text{pt}) = f(\text{pt}) - f(k)$. Since $f$ is an LCG, we can express $E(\text{pt}) = m \cdot (\text{pt} - k) \pmod{p}$ and forget about $n$.

In order to find $m$, we can encrypt two plaintexts:

$$ \begin{cases} \text{ct}_1 = E(\text{pt}_1) = m \cdot (\text{pt}_1 - k) \mod{p} \newline \text{ct}_2 = E(\text{pt}_2) = m \cdot (\text{pt}_2 - k) \mod{p} \end{cases} $$

Then

$$ \text{ct}_2 - \text{ct}_1 = m \cdot (\text{pt}_2 - \text{pt}_1) \mod{p} $$

So

$$ m = (\text{ct}_2 - \text{ct}_1) \cdot (\text{pt}_2 - \text{pt}_1)^{-1} \mod{p} $$

Actually, to simplify we can force that $\text{pt}_2 - \text{pt}_1 = 1$, so that

$$ m = \text{ct}_2 - \text{ct}_1 \mod{p} $$

Once we have $m$, we can get $k$ as follows

$$ k = \text{pt}_1 - \text{ct}_1 \cdot m^{-1} \mod{p} $$

And finally, find the flag:

$$ \text{flag} = k + E(\text{flag}) \cdot m^{-1} \mod{p} $$

Here’s the implementation for the second part of the challenge:

    io.sendlineafter(b'> ', b'1')
    io.recvuntil(b'ct = ')
    flag_enc = int(io.recvline().strip())

    pt1 = b'a'
    io.sendlineafter(b'> ', b'2')
    io.sendlineafter(b'pt = ', pt1)
    io.recvuntil(b'ct = ')
    ct1 = int(io.recvline().strip())

    pt2 = b'b'
    io.sendlineafter(b'> ', b'2')
    io.sendlineafter(b'pt = ', pt2)
    io.recvuntil(b'ct = ')
    ct2 = int(io.recvline().strip())

    io.sendlineafter(b'> ', b'3')
    io.close()

    m = ct2 - ct1
    k = (ord(pt1) - ct1 * pow(m, -1, p)) % p

    flag = (k + flag_enc * pow(m, -1, p)) % p
    log.success(bytes.fromhex(hex(flag)[2:]).decode())

Flag

$ python3 solve.py 161.35.164.52:32367
[+] Opening connection to 161.35.164.52 on port 32367: Done  
[*] Closed connection to 161.35.164.52 port 32367
[+] HTB{C4lcU1u5_m33t5_Cryp70_c4n_y0u_8e1i3ve_17???}

The full script can be found in here: solve.py.