Maojui

Seccon 2017 - Very Smooth (Crypto, 300)

2017-12-11

Very Smooth

In Pcap :
Find Client and Server’s Conversation
Cipher Suite TLS_RSA_WITH_AES_128_CBC_SHA (0x002f)

Find Certificate in Pcap

Get Certificate Raw

1
tshark -V -r s.pcap -T jsonraw 'ssl.handshake.certificates' | grep 'ssl.handshake.certificate_raw' | uniq

Write in the file

1
2
3
4
from libnum import *
certificate = n2s(0x308201d33082013c020900a18b630c7b3099df300d06092a864886f70d01010b0500302e310b3009060355040613024a503111300f06035504080c084b61776173616b69310c300a060355040a0c0353524c301e170d3137313030383032343731375a170d3138313030383032343731375a302e310b3009060355040613024a503111300f06035504080c084b61776173616b69310c300a060355040a0c0353524c30819f300d06092a864886f70d010101050003818d0030818902818100d546aa825cf61de97765f464fbfe4889ad8bf2f25a2175d02c8b6f2ac0c5c27b67035aec192b3741dd1f4d127531b07ab012eb86241c09c081499e69ef5aeac78dc6230d475da7ee17f02f63b6f09a2d381df9b6928e8d9e0747feba248bffdff89cdfaf4771658919b6981c9e1428e9a53425ca2a310aa6d760833118ee0d710203010001300d06092a864886f70d01010b050003818100789211fb6ce17af72a33b88b08a7f75bdecf620ba0edbed069883893949d054173bd7eb332ec8e10bc3a62b056c7c13f6066a7beb946f746226af35a25d56694570efcb51633051c6ff5857457a4a0c6ce4ffd645394a983b896bf5ba7ee8b1e48a7d243060e4f5a86626905e2c0bd4e89c9af044a77a234866ab8d23b32b739)
with open('cert.der','wb') as der:
    der.write(certificate)

Transform DER into PEM

1
2
openssl x509 -inform der -pubkey -noout -in cert.der > public_key.pem
openssl x509 -inform der -in cert.der -text

Get Public Key

1
2
3
4
5
6
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDVRqqCXPYd6Xdl9GT7/kiJrYvy
8lohddAsi28qwMXCe2cDWuwZKzdB3R9NEnUxsHqwEuuGJBwJwIFJnmnvWurHjcYj
DUddp+4X8C9jtvCaLTgd+baSjo2eB0f+uiSL/9/4nN+vR3FliRm2mByeFCjppTQl
yioxCqbXYIMxGO4NcQIDAQAB
-----END PUBLIC KEY-----

Decrypt RSA

Load the pem

1
2
3
4
5
6
7
from Crypto.PublicKey import RSA
pem = b''
with open('public_key.pem','rb') as f :
    for line in f.readlines():
        pem += line
pub = RSA.importKey(pem)
n, e = pub.n, pub.e

Use Williams P+1 Algorithm solve the smooth prime.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def williams_pp1(n):
    
    def mlucas(v, a, n):
        """ Helper function for williams_pp1().  Multiplies along a Lucas sequence modulo n. """
        v1, v2 = v, (v**2 - 2) % n
        for bit in bin(a)[3:]: v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n) if bit == "0" else ((v1*v2 - v) % n, (v2**2 - 2) % n)
        return v1

    if isprime(n): return n
    m = ispower(n)
    if m: return m
    for v in count(1):
        for p in primegen():
            e = ilog(isqrt(n), p)
            if e == 0: break
            for _ in range(e): v = mlucas(v, p, n)
            g = gcd(v - 2, n)
            if 1 < g < n: return g
            if g == n: break

Find p & q

1
2
3
4
5
p = williams_pp1(n)
q = n//p
priv = RSA.construct((pub.n, pub.e, invmod(pub.e, (p - 1) * (q - 1))))
with open('private_key','wb') as f:
    f.write(priv.exportKey('PEM'))

Solution

Find the Conversation which ‘tcp stream eq 5’
Right Click and choose ‘add RSA key list’.
Add the private_key.

index.html

1
2
3
4
5
6
7
8
<html>
<head><title>Very smooth</title></head>
<body>
<h1>
Answer: One of these primes is very smooth.
</h1>
</body>
</html>

SECCON{One of these primes is very smooth.}

Tags: RSA certificate
← RSA - CTF 常見題型 Seccon 2017 - Simon ... (Crypto, 100) →