lowe

CSAW'18 CTF Qualification - Cryptography (200 pts).

CSAW’18 CTF Qualification: lowe

Event Challenge Category Points Solves
CSAW’18 CTF Qualification lowe Crypto 200 114

Description

I personally prefer Home Depot

XOR Passes are the easiest way to use numbers to encrypt!

By Kris Kwiatkowski, Cloudflare

TL;DR

The key is encrypted using RSA with a small exponent (3), The key is small and no padding is applied so the cube root can be calculated to retrieve the key. Finally, a xor with the file gives the flag.

Finding the key

Given the title of this challenge and the small amount of informations, I deduced that the key was encrypted without padding.

The RSA public exponent used is 3. If the key (pk) is small enough, k=pow(pk,e,n) < n so computing the cube root of k would retrieve the original key.

But it seemed like pk was a bit too big, therefore we can’t deduce pk by computing the cube root of k but we can try with k+i*n because k+(i*n) % n == k

script

# -*- coding: utf-8 -*-
from Crypto.PublicKey import RSA
import gmpy2

def ntos(x):
n = hex(x)[2:].rstrip("L")
if len(n)%2 != 0:
n = "0"+n
return n.decode("hex")

def ston(x):
n = x.encode("hex")
return int(n,16)

def strxor(a,k):
s = ""
for i in range(len(a)):
s += chr(ord(a[i])^ord(k[i%len(k)]))
return s

e = ke.e
n = ke.n
f = ston(f)

i = 0
r = gmpy2.iroot(k+(i*n), 3)[0]
while r<n:
if pow(r,3,n) == k:
print strxor(ntos(f),ntos(r))
break
i += 1
r = gmpy2.iroot(k+(i*n), 3)[0]


Flag

flag{saltstacksaltcomit5dd304276ba5745ec21fc1e6686a0b28da29e6fc}

ENOENT