Seccon 2017 - Very Smooth (Crypto, 300)

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

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

Write in the file

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

Transform DER into PEM

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

Get Public Key

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

Decrypt RSA

Load the pem

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.

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

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

<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.}