Skip to content

Instantly share code, notes, and snippets.

@reteps
Created June 21, 2021 01:10
Show Gist options
  • Save reteps/a8b97511e2925e506e3e6d3200350e53 to your computer and use it in GitHub Desktop.
Save reteps/a8b97511e2925e506e3e6d3200350e53 to your computer and use it in GitHub Desktop.

Regulus Calendula

We are given:

e
1/2 bits randomly of P
1/2 bits randomly of Q
N
(P*Q=N)

We can get these bits by testing 8 hex characters and checking the output of the service. The relevant source is:

if guesses > 8:

    code = list(hex(p)[2:])
else:
    code = list(hex(q)[2:])
guess = input("Make a guess.\n: ")
while len(guess) != hex_factor_size:
    guess = input("Try again.\n: ")
guess = list(guess)
a = "".join(["1" if guess[i] == code[i]
                else "0" for i in range(hex_factor_size)])
print(a)
guesses -= 1

Originally, we rabbit-holed into this idea of solving for N given random bits of P and Q.

After reading some papers, we stumbled upon this python attack. However, we don't know quite enough bits for it to be effective.

If at least 57% of the bits are known, this attack should be polynomial time, however, smaller percentages might still work.

Finally, we had a breakthrough and realized that we didn't have to test every hex character, just the ones remaining. (E.g. check 89abcdef instead of 0123456789abcdef). With some modifications / rewrite of the _branch_and_prune_pq algorithm, it ran much faster and worked on the 4096 bit numbers.

Our solve script ended up looking like this:

HEX_FACTOR_SIZE = 1024


def recover(n, pbits, qbits, i):
    nbits = list(hex(n)[2:])[::-1]
    if i == len(pbits):
        yield pbits, qbits
    else:
        possible_p = []
        possible_q = []
        if pbits[i] is None:
            possible_p = ['8', '9', 'a', 'b', 'c', 'd', 'e', 'f']
        else:
            possible_p = [pbits[i]]
        if qbits[i] is None:
            possible_q = ['8', '9', 'a', 'b', 'c', 'd', 'e', 'f']
        else:
            possible_q = [qbits[i]]
        for possible_pbit, possible_qbit in product(possible_p, possible_q):
            p_ = int(''.join(pbits[:i] + [possible_pbit])[::-1], 16)
            q_ = int(''.join(qbits[:i] + [possible_qbit])[::-1], 16)
            if hex(p_ * q_)[-(i + 1):] == ''.join(nbits[:i+1])[::-1]:
                yield from recover(n, pbits[:i] + [possible_pbit] + pbits[i+1:], qbits[:i] + [possible_qbit] + qbits[i+1:], i+1)

vals = recover(n, partial_p[::-1], partial_q[::-1], 0)

Yielding us the flag!

flag{P0g_Po5_pOG_i_Sh0Ok_mY-pHoN3_t0_5O_kMs_leTs_goOOoO0oO}

The full script is below. note it requires a local version of googles pow python script in the same directory.

import pwn
import subprocess
import sympy
from itertools import product
import sys

sys.setrecursionlimit(10000)
HEX_FACTOR_SIZE = 1024


def recover(n, pbits, qbits, i):
    nbits = list(hex(n)[2:])[::-1]
    if i == len(pbits):
        yield pbits, qbits
    else:
        possible_p = []
        possible_q = []
        if pbits[i] is None:
            possible_p = ['8', '9', 'a', 'b', 'c', 'd', 'e', 'f']
        else:
            possible_p = [pbits[i]]
        if qbits[i] is None:
            possible_q = ['8', '9', 'a', 'b', 'c', 'd', 'e', 'f']
        else:
            possible_q = [qbits[i]]
        for possible_pbit, possible_qbit in product(possible_p, possible_q):
            p_ = int(''.join(pbits[:i] + [possible_pbit])[::-1], 16)
            q_ = int(''.join(qbits[:i] + [possible_qbit])[::-1], 16)
            if hex(p_ * q_)[-(i + 1):] == ''.join(nbits[:i+1])[::-1]:
                yield from recover(n, pbits[:i] + [possible_pbit] + pbits[i+1:], qbits[:i] + [possible_qbit] + qbits[i+1:], i+1)


def skip_menu_get_guess(rem):

    l = int(rem.recvuntil('left.').split(b'\n')[-1].split(b' ')[2])
    # print(l)
    rem.recvuntil(': ')
    return l


def get_values(rem):
    p_bits = [None] * HEX_FACTOR_SIZE
    q_bits = [None] * HEX_FACTOR_SIZE
    guess_chars = '01234567'
    assert len(guess_chars) == 8
    # Get P BITS
    for char in guess_chars:
        guesses = skip_menu_get_guess(rem)
        print(guesses)
        assert guesses > 8
        rem.sendline('4')
        rem.recvuntil(b': ')
        rem.sendline(char * HEX_FACTOR_SIZE)
        match = list(rem.recvline().strip().decode())
        assert len(match) == HEX_FACTOR_SIZE
        for i in range(len(match)):
            if match[i] == '1':
                p_bits[i] = char
    # Get Q BITS
    for char in guess_chars:
        guesses = skip_menu_get_guess(rem)
        print(guesses)
        assert guesses <= 8
        rem.sendline('4')
        rem.recvuntil(b': ')
        rem.sendline(char * HEX_FACTOR_SIZE)
        match = list(rem.recvline().strip().decode())
        assert len(match) == HEX_FACTOR_SIZE
        for i in range(len(match)):
            if match[i] == '1':
                q_bits[i] = char
    # Get N
    guesses = skip_menu_get_guess(rem)
    print(guesses)
    rem.sendline('2')
    n = int(rem.recvuntil('e').split(b'\n')[
            1].replace(b'n = ', b'').decode())
    return p_bits, q_bits, n


def main():
    if pwn.args.REMOTE:
        rem = pwn.remote('regulus-calendula.hsc.tf', 1337)
        problem = rem.recvuntil(b'===').split(
            b'\n')[-2].strip().decode().split()[-1]
        print(problem)
        solution = subprocess.check_output(
            ['./pow.py', 'solve', problem], timeout=99999).decode()
        # print(solution)
        rem.recvuntil(b'Solution?')
        rem.sendline(solution)
        status = rem.recvline()
        print(status)
    else:
        rem = pwn.process('./main.py')

    partial_p, partial_q, n = get_values(rem)
    print('p=', '0x' + ''.join(x if x is not None else '?' for x in partial_p))
    print('q=', '0x' + ''.join(x if x is not None else '?' for x in partial_q))
    print('n=', '0d' + str(n))

    found_p = -1
    found_q = -1
    vals = recover(n, partial_p[::-1], partial_q[::-1], 0)
    for (poss_p, poss_q) in vals:
        poss_p = ''.join(poss_p[::-1])
        poss_q = ''.join(poss_q[::-1])
        if int(poss_p, 16) * int(poss_q, 16) == n:
            found_p = int(poss_p, 16)
            found_q = int(poss_q, 16)
            break
    e = 0x10001
    # print(q_bits_mask)
    # print(p_bits_mask)
    print(found_p)
    print(found_q)
    assert found_p * found_q == n
    # print(e)
    # print(n)
    d = sympy.mod_inverse(e, (found_p-1)*(found_q-1))
    skip_menu_get_guess(rem)
    rem.sendline(b'3')
    rem.recvuntil(b': ')
    rem.sendline(str(d))
    rem.interactive()


main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment