Aperi’CTF 2019 - Real Spy Agent

Challenge details

Event	Challenge	Category	Points	Solves
Aperi’CTF 2019	Real Spy Agent	Cryptography	175	6

Vous êtes un agent infiltré dont la mission est d’espionner les faits et gestes du grand patron d’ENO.corp. Vous savez de source sûre que cette société utilise un système cryptographique biaisé, basé sur le chiffrement RSA, pour échanger des messages secrets entre ses membres. Vous avez réussi à intercepter un de ces messages en provenance du patron, votre tâche est le déchiffrer au plus vite !

Fichiers :
- CEO_pb_key - md5sum: dc3bc6c21a493d7533a18e67f50ff01f
- your_pvt_key - md5sum: 7d26deb3ffbd4edd09832e231bbb827b
- message - md5sum: 5a2e6d32d6cdef50af8d61b63707bc48

TL;DR

RSA attack with same modulus but differents messages.

Methodology

We are clearly confronted to a case where the same modulus are used between 2 persons. But unlike classical common modulus attacks on RSA, we don’t have 2 identical messages in their encrypted form. This attack relies on the fact that we have a public key with the same modulus and we know our private exponent.

This attack is well explained and detailed in my blog post about it : https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/ Common modulus -> As an internal attacker

Full script available here

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/
import gmpy2
from Crypto.PublicKey import RSA
import base64

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


pvKey = RSA.importKey(open("../files/your_pvt_key.txt").read())

n = pvKey.n
e = pvKey.e
d = pvKey.d

pbKey = RSA.importKey(open("../files/CEO_pb_key.txt").read())

e_ceo = pbKey.e
c =  int(open("../files/message.enc").read().encode("hex"), 16)

k = ((e*d)-1)/n
phi = ((e*d)-1)/k
while phi*k != ((e*d)-1):
    k += 1
    phi = ((e*d)-1)/k
d2 = gmpy2.invert(e_ceo, phi)
m = pow(c,d2,n)
print ntos(m)

Output:

APRK{Y0ur_4_R34l_Spy_4r3n't_y4?}

Flag

APRK{Y0ur_4_R34l_Spy_4r3n't_y4?}

ENOENT