ASIS CTF finals - RSA

Crypto RSA, crypto, python Comments

Average: 4.18
Rating Count: 22
You Rated: Not rated
Points
113
Solves
64
Category
Crypto
Description

Find the flag.
http://asis-ctf.ir/tasks/rsa.txz_93b525e771c284b7a3f0bb45b290ce56987c5834

After extracting analysing the server.py file

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#!/usr/bin/python

import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

flag = open('flag', 'r').read() * 30

def ext_rsa_encrypt(p, q, e, msg):
    m = bytes_to_long(msg)
    while True:
        n = p * q
        try:
            phi = (p - 1)*(q - 1)
            d = gmpy.invert(e, phi)
            pubkey = RSA.construct((long(n), long(e)))
            key = PKCS1_v1_5.new(pubkey)
            enc = key.encrypt(msg).encode('base64')
            return enc
        except:
            p = gmpy.next_prime(p**2 + q**2)
            q = gmpy.next_prime(2*p*q)
            e = gmpy.next_prime(e**2)

p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((long(n), long(e)))
f = open('pubkey.pem', 'w')
f.write(pubkey.exportKey())
g = open('flag.enc', 'w')
g.write(ext_rsa_encrypt(p, q, e, flag))

Looks like a simple RSA encryption there are some strange things hapening here like the While True look with a try catch and “open(‘flag’, ‘r’).read() * 30”, we will see why this happens later right now we need to get our modulus N and e from the pubkey.pem file:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

(.env)kinyabitch@Debian ~/h/c/a/c/r/RSA> openssl rsa -in pubkey.pem -pubin -text -modulus
Public-Key: (256 bit)
Modulus:
    00:d8:e2:4c:12:b7:b9:9e:fe:0a:9b:c0:4a:6a:3d:
    f5:8a:2a:94:42:69:b4:92:b7:37:6d:f1:29:02:3f:
    20:61:b9
Exponent: 12405943493775545863 (0xac2ac3e0ca0f5607)
Modulus=D8E24C12B7B99EFE0A9BC04A6A3DF58A2A944269B492B7376DF129023F2061B9
writing RSA key
-----BEGIN PUBLIC KEY-----
MEIwDQYJKoZIhvcNAQEBBQADMQAwLgIhANjiTBK3uZ7+CpvASmo99YoqlEJptJK3
N23xKQI/IGG5AgkArCrD4MoPVgc=
-----END PUBLIC KEY-----

Now that we have the modulus and the Exponent we will try to factor modulus N with yafu (https://github.com/DarkenCode/yafu):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

(.env)kinyabitch@Debian ~/h/c/a/c/r/RSA>; ../../../../../crl/RSA2/bin/yafu "factor(0xD8E24C12B7B99EFE0A9BC04A6A3DF58A2A944269B492B7376DF129023F2061B9)" -threads 10


fac: factoring 98099407767975360290660227117126057014537157468191654426411230468489043009977
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits

starting SIQS on c77: 98099407767975360290660227117126057014537157468191654426411230468489043009977

==== sieving in progress (10 threads):   36224 relations needed ====
====            Press ctrl-c to abort and save state            ====


SIQS elapsed time = 1.9290 seconds.
Total factoring time = 2.0017 seconds


***factors found***

P39 = 315274063651866931016337573625089033553
P39 = 311155972145869391293781528370734636009

ans = 1

Now that we have the p and q we can get the private key using rsatool(https://github.com/ius/rsatool)

1
2
3
4
5
6
7
8
(.env)kinyabitch@Debian ~/h/c/a/c/r/RSA> rsatool/rsatool.py -p 311155972145869391293781528370734636009 -q 315274063651866931016337573625089033553 -e 12405943493775545863 -o priv.key
(.env)kinyabitch@Debian ~/h/c/a/c/r/RSA> cat priv.key 
-----BEGIN RSA PRIVATE KEY-----
MIGwAgEAAiEA2OJMEre5nv4Km8BKaj31iiqUQmm0krc3bfEpAj8gYbkCCQCsKsPgyg9WBwIgHtnK
UU3mNRl9yzxb34oYadECnCy7c1afLXiBA6d8n7cCEQDqFnXdoXEPZrAQBssgWxvpAhEA7S+Tc+wB
hnqru7wF2RkFUQIQNRmCtiEP0S+6uyda8zCbJwIRAJ5Uoh8oF1sz+8MdyveAYncCEB/QjyrzneAo
X5X8HRjafQM=
-----END RSA PRIVATE KEY-----

And now writing a little script with python to decrypt our cipher text:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5, PKCS1_OAEP
from base64 import b64decode
from Crypto.Hash import SHA
from Crypto import Random
import subprocess
import sys

def decrypt_RSA(privkey,message):
    key = open(privkey, "r").read()
    dsize = SHA.digest_size  
    sentinel = Random.new().read(15+dsize)
    rsakey = RSA.importKey(key)
    rsakey = PKCS1_v1_5.new(rsakey)
    decrypted = rsakey.decrypt(b64decode(message), None)
    return decrypted


print decrypt_RSA('priv.key', sys.argv[1])
1
2
3
4
5
6
7
8
9
10

(.env)kinyabitch@Debian ~/h/c/a/c/r/RSA> python rsa2.py $(cat flag.enc | tr -d '\n')
Traceback (most recent call last):
  File "rsa2.py", line 20, in <module>;
    print decrypt_RSA('priv.key', sys.argv[1])
  File "rsa2.py", line 16, in decrypt_RSA
    decrypted = rsakey.decrypt(b64decode(message), None)
  File "/home/kinyabitch/ctf/asis-2016/ppc/SecuPrim/.env/local/lib/python2.7/site-packages/Crypto/Cipher/PKCS1_v1_5.py", line 204, in decrypt
    raise ValueError("Ciphertext with incorrect length.")
ValueError: Ciphertext with incorrect length.

But we failed, incorrect length? remember this part of the code from server.py ?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

flag = open('flag', 'r').read() * 30
while True:
        n = p * q
        try:
            phi = (p - 1)*(q - 1)
            d = gmpy.invert(e, phi)
            pubkey = RSA.construct((long(n), long(e)))
            key = PKCS1_v1_5.new(pubkey)
            enc = key.encrypt(msg).encode('base64')
            return enc
        except:
            p = gmpy.next_prime(p**2 + q**2)
            q = gmpy.next_prime(2*p*q)
            e = gmpy.next_prime(e**2)

Yes the flag is being multiplied by 30 times so is going to be very big, and if you notice the try catch is used , so when an error occurs (length error) it updates our p,q and e getting the next primes!, so we had the wrong pubkey which only works for small cipher texts what we need to do here is to modify this encrypt script so we can get the next p,q,e with a very big string to make sure we can decrypt the original cipher text by simply modify our decrypt file

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#!/usr/bin/python

import gmpy
import sys
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

def ext_rsa_encrypt(p, q, e, msg):
  m = bytes_to_long(msg)
  c = 0
  while True:
    #print 'loop started'
    n = p * q
    try:
      phi = (p - 1)*(q - 1)
      d = gmpy.invert(e, phi)
      pubkey = RSA.construct((long(n), long(e)))
      f = open('possiblekeys', 'a+')
      f.write('%d,%d,%d,%d\n' % (p,q,n,e))
      f.close()
      key = PKCS1_v1_5.new(pubkey)
      enc = key.encrypt(msg).encode('base64')
      return enc
    except:
      c += 1
      p = gmpy.next_prime(p**2 + q**2)
      q = gmpy.next_prime(2*p*q)
      e = gmpy.next_prime(e**2)
if __name__ == '__main__':
  sys.stdout.write( ext_rsa_encrypt(311155972145869391293781528370734636009, 315274063651866931016337573625089033553, 12405943493775545863, "ASIS{IM_A_LEET_AND_BIG_FUCKING_STRING_OMG_PLZ}" * 100))

And now generating the private keys and trying to decrypt the flag:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5, PKCS1_OAEP
from base64 import b64decode
from Crypto.Hash import SHA
from Crypto import Random
import subprocess
import sys

def decrypt_RSA(privkey,message):
    key = open(privkey, "r").read()
    dsize = SHA.digest_size  
    sentinel = Random.new().read(15+dsize)
    rsakey = RSA.importKey(key)
    rsakey = PKCS1_v1_5.new(rsakey)
    decrypted = rsakey.decrypt(b64decode(message), None)
    return decrypted


#print decrypt_RSA('priv.key', sys.argv[1])
if __name__ == '__main__':
    f = open('possiblekeys', 'r')
    pqde = []
    for i in f:
        d = {}
        # print i
        l = i.split(',')
        d['p'] = l[0]
        d['q'] = l[1]
        d['n'] = l[2]
        d['e'] = l[3]
        pqde.append(d)
    c = 0
    for d in pqde:
        subprocess.check_output(["rsatool/rsatool.py", '-p', '%s' % d['p'], '-q', '%s' % d['q'], '-e', '%s' % d['e'], '-o', 'privkeys/priv%d.key' % c])
        try:
            print decrypt_RSA('privkeys/priv%d.key' % c, sys.argv[1])
        except Exception as e:
            print e
        c += 1

Running it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

(.env)kinyabitch@Debian ~/h/c/a/c/r/RSA> python rsa2.py (cat flag.enc | tr -d '\n')
Ciphertext with incorrect length.
Ciphertext with incorrect length.
Ciphertext with incorrect length.
Ciphertext with incorrect length.
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}
ASIS{F4ct0R__N_by_it3rat!ng!}

TeamRocketISTCTF Team

Portuguese Computer Science Students