Writeup For: Regulus Calendula HSCTF 8

In the challenge provided we are given a netcat and a python file with the source code for the challenge. The first option provided will just print out the source code (but the python file is given so :p). The second option will give our public key (our n and e values). The 3rd option is the portion that will give us our flag if we can provide a private key that can decrypt the file the ct properly. The 4th option is the most important one, it allows us to guess hex values of p and q and checks if we got bytes correct. This is found in: https://eprint.iacr.org/2020/1506.pdf (4.31). In that case the author does a dfs bruteforce that checks individual bits and creates a tree of all possible solutions (it is slightly optimized since it discards the options that are wrong every comparison. This is based on the fact that N=pq mod 2^i for every bit. *note: to guess p and q bytes just do go through the hex range (0-15). The rest of the chall is just coding up the solution:

from pwn import * Import sys from Crypto.Util.number import inverse sys.setrecursionlimit(1000000000000000000000) #init p = remote('regulus-calendula.hsc.tf', 1337) #funcs def guess(a, x): p.sendlineafter(':', '4') a = [x if i == -1 else i for i in a] p.sendlineafter(': ', ''.join(hex(i)[2:] for i in a)) s = p.recvlineS(keepends = False) return [i if j == '1' else -1 for i, j in zip(a, s)] def blist(a): ans=[] for i in a[::-1]: for j in range(k): if i != -1: ans.append((i >> j) & 1) elif j == k - 1: ans.append(1) else: ans.append(-1) return ans def lint(a): ret = 0 for i in range(len(a)): ret |= a[i] << i return ret def sol(x, a, b, n): if (lint(a[:x]) * lint(b[:x]) & ((1 << x) - 1)) != (n & ((1 << x) - 1)): return False if x == len(a): return lint(a) * lint(b) == n ta, tb = a[x] == -1, b[x] == -1 for i in range(2): for j in range(2): if (ta or a[x] == i) and (tb or b[x] == j): a[x], b[x] = i, j if sol(x + 1, a, b, n): return True if ta: a[x] = -1 if tb: b[x] = -1 return False #vars m, k, e = 1024, 4, 65537 a, b = [-1 for i in range(m)], [-1 for i in range(m)] #exploit #pass pow print(p.recvuntilS('?')) p.sendline(input('Gimme pow: ')) #get n p.sendlineafter(':', '2') p.recvuntil('= ') n = int(p.recvlineS(keepends = False)) log.info('n: \n' + hex(n)) #guess digits for i in range(1 << (k - 1)): a = guess(a, i) for i in range(1 << (k - 1)): b = guess(b, i) log.info('p guess: \n' + str(a)) log.info('q guess: \n' + str(b)) #turn to correct form a, b = blist(a), blist(b) #recurse fill in gaps if not sol(0, a, b, n): log.failure('Rip') print(a) print(b) exit(0) #get flag a, b = lint(a), lint(b) d = inverse(e, (a - 1) * (b - 1)) log.success('p: \n' + hex(a)) log.success('q: \n' + hex(b)) log.success('d: \n' + hex(d)) p.sendlineafter(':', '3') p.sendlineafter(':', str(d)) p.interactive()