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

file.enc key.enc pubkey.pem

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

ke = RSA.importKey(open("pubkey.pem","r").read().strip())
e = ke.e
n = ke.n
f = open("file.enc","r").read().strip().decode("base64")
f = ston(f)
k = int(open("key.enc","r").read().strip())

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