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 -= 1Originally, 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()