<- 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 as the -th term of the Turbonacci sequence:

For the OTP, we are given a nonce value. And the OTP is .

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):

Which is equivalent to

Now we solve the quadratic equation:

And with this, we can express as

Let and .

In order to find and , we can use two known values (for instance, and ).

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

And now we have a closed form for :

Ok, it is time to apply modulo .

In order to compute , we will need Tonelli-Shanks or Cipolla methods (find such that ).

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

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 :

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 ):

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

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,

We know modulo from the beginning, but we don’t have and .

Understanding encryption

The encryption function maps . Since is an LCG, we can express and forget about .

In order to find , we can encrypt two plaintexts:

Then

So

Actually, to simplify we can force that , so that

Once we have , we can get as follows

And finally, find the flag:

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.