HITB Facebook CTF 2016 | capture Mexico-tls (Crypto200)

out.key

-----BEGIN RSA PRIVATE KEY-----
MIIEoQIBAAKCAQEAyOP3yjHxOk0I3NPJ4Q1HDvJmqAoxEdLMaNCiLxkVNSZwLTPMXnuoZikVznds
OZ9t2bAe4P/9L1Pfg+35jfmxe96Jzk6dAXiuFmFlaOsKl4yBxRat6Far/UjBM9A2ZJgmYxWJJr3T
MahpzZMWFbSD64QQYSBgPlX671xc4Q75omY0dfcANyPGYuTgTR9zmNyfk5s3e7yfYS9gZ+aU4Hmo
x4NgKypw7OHVAN5hTZ0V2B3pGR9c6VoReHiOXXOEKD8QZbD6LMyuVO6K+cEklW562sh0CJo9qn8+
FT1tG6kC7d1tU3tptY/MA5uUhLGDW34WfXtgE42eIR01Ovi+hzC82wIDAQABAoIBAEiIv1xbQf1J
+Uw6kCbZM3H7JgPAgk0sLrAdvKGCzfx9330CueTXg0s3xG7jAcmgffpetBeLdnBTOV4aW8Pehy3x
gRJjoh744uqjygji7NUhX225LZu5R6pRTakWob0ajqmyCe5aFdpVM7aNSCkYH5W2/m8DUJzRUKSC
VerRDGONHRCnNxV3w9u3EkdI5fvrOpY1TSqCmEZwCCPO+WfqIn8Ut/xNvHkNSXA2+h1KgmwyQQZ/
ZgsNeRa2+vZh2kgm3f1xccjQvyAel3t+5s0cPo0NI7qqHkiHNb6/yWR9AH+bGVXQc+VtR7GwisRZ
a1QrHWDSBNdRisv8dcBwQ3eAOmECgYEA+iOrtbYQUtSWOMFwnwzRumzqvJqr+7jAFKewNAOZa8ix
hHf7X+lQCXlN8DNJSvG5Pv3c3rtop7UPMNEB5Yvvq0RzlL/nz7fQ4kQfH3s3657iEdumgO9KNjJ0
DiF0wlfSA1+M0pdy5OF0RLyq1WvZxrdtUchWweeKpvIJTN13dpECgYEAzZjnZ+xgUx3ZUPXw6wTq
jYxinVlkTTpc/BAbO3QPSKfNuYuiV0Ac5R7xr7qLL9GgA0agd9AxyDqnN/5PtPu9PAmbe59Nh3Xx
4WtnCKldMkGEo9iy29ltzcITh+PnGuuJjyMiv/LACO5UfC6VjZUK0pIqKomXDsvIZFIb/C/E6qsC
gYEAvWNMmuQiL9SteINdlc7K7G+SuwIQvSIArKLaEke3XZgyb624McIgy0uA6yCpmYizTTJAjJMw
henceoWE/huZdv740+MIzIjMKsSRG/DbQhal7Ad2ZaDHe4lvvVMvaAW+CLfLk5b/crQQqAqA/d4O
oRo4NveMWHvKyuPujrgPv0ECgYBA9qOH7uSw3qmgL1YkrLUAbO9sEKbk0CA5dU1lh9Kcfok+q6Rs
NVHsA88SW7tHLNGGt3ZU5XAVeJMF2lGNOk4c/lwmv7tbpiT7uVghIILWMmWa8Anz9cwAS+an9Zc8
plgc5llAlY+gQs5nPsD6r7Fvv8ebEUat4i47pMY69U0faQJ/VmOKcWmCbnGnjUJIS8Mtvuofj/xW
dMyFgcYczD7cL9mY82TIeghR3cC6VnjPkLSQ3iNQYoAnWLrOBu09TgBKU765e6LD4yUpXTaxuo1p
TPNJIwQR/6WWiuVGt9COkJGsy5EbLGjU6paaTyqmPhvetJOamhnJIzqSAwudXYdpgQ==
-----END RSA PRIVATE KEY-----

solver.py

# filename: solver.sage
# reference: https://cryptologie.net/article/371/fault-attacks-on-rsas-signatures/

import hashlib
import fractions
import json

# openssl x509 -inform der -text -noout -in Facebook.cer
modulus = 0xC8E3F7CA31F13A4D08DCD3C9E10D470EF266A80A3111D2CC68D0A22F19153526702D33CC5E7BA8662915CE776C399F6DD9B01EE0FFFD2F53DF83EDF98DF9B17BDE89CE4E9D0178AE16616568EB0A978C81C516ADE856ABFD48C133D03664982663158926BDD331A869CD931615B483EB84106120603E55FAEF5C5CE10EF9A2663475F7003723C662E4E04D1F7398DC9F939B377BBC9F612F6067E694E079A8C783602B2A70ECE1D500DE614D9D15D81DE9191F5CE95A1178788E5D7384283F1065B0FA2CCCAE54EE8AF9C124956E7ADAC874089A3DAA7F3E153D6D1BA902EDDD6D537B69B58FCC039B9484B1835B7E167D7B60138D9E211D353AF8BE8730BCDB
public_exponent = 65537

client_nonce = "57b3c6a014f3bf75e49d99a7502a9cc94af24b26a05d06bc2eeefebe44ac7431"
server_nonce = "e98405e4b8801a69c54f067e094f6f3dc1c4e2f3937af72d9ae4a4ddd116392c"
server_params = "03001741046bdb6948d2ee1ad618f5718bd6f749a7f9e56109a235f3274be0a4a809d8764bc1ecd561a28b6d2cd45b2beb1570d64c2f0a4109dd1c39cbf193f855650a2d75"
signature = 0x85467d0a99623e161a3127a1a0803d9eb3ca3ac924fa289e26262dc0f67ddfdeb3f24ff7593e479c41ff7372e53eebdf729010e71b496a8d3136d5a315ab8627fb02afb06ce0e44539a493fe2654ef742986bf0883c42af22b1f180b3ddbe008559924be18716658a99f649799e989dbcfab5a2c520f41904cdcb6a8ead161af07090ad9e14797b6d9ba458acef7807f6124caa03bb3a65a6794be6214e72f04bf574f7605cf04dd80165e268751096de62781ebd0edf7d05609c9002149db7a63683060706c6c348bc3fe0e77e4b16db12d8312aa1ab6e4fc43e643ac03f6a16d29412b59d247ec1e90534dad1f05949f281f9b5c13330e6e9208edac02eb1f


# hash the signed_params
h = hashlib.sha384()
h.update(client_nonce.decode('hex'))
h.update(server_nonce.decode('hex'))
h.update(server_params.decode('hex'))
hashed_m = h.hexdigest()

# PKCS#1 v1.5 padding
prefix_sha384 = "3041300d060960864801650304020205000430"

# modulus_len = (len(bin(modulus)) - 2 + 7) // 8
pad_len = len(hex(modulus))//2 - 3 - len(hashed_m)//2 - len(prefix_sha384)//2

padded_m = "0001" + "ff" * pad_len + "00" + prefix_sha384 + hashed_m

# Attack to recover p
p = gcd(signature^public_exponent - int(padded_m, 16), modulus)

# recover private key
q = modulus // p

print "[+] p:", p
print "[+] q:", q

# [+] p: 175653817257988201872252461398014869917210874225448853815003947930455935718534599483648554364757192366777027353365686842637995245093817814681006694875563701749129380610245872302970760270178135267229182769865703809227042886311647300800244451485605724712789402082075692990708504289797644360642232301210951972497
# [+] q: 144375320529052563170771758136112981391320084191761405050100262698945023053917998934210557907437462850513877566391181801636784425109438166703467644073942904234072642337257376564706436275310549261709409447376094316557269103645124842590803426379133094214931175879865854394612579684959706322609923567196668488363

# python rsatool.py -p 175653817257988201872252461398014869917210874225448853815003947930455935718534599483648554364757192366777027353365686842637995245093817814681006694875563701749129380610245872302970760270178135267229182769865703809227042886311647300800244451485605724712789402082075692990708504289797644360642232301210951972497 -q 144375320529052563170771758136112981391320084191761405050100262698945023053917998934210557907437462850513877566391181801636784425109438166703467644073942904234072642337257376564706436275310549261709409447376094316557269103645124842590803426379133094214931175879865854394612579684959706322609923567196668488363 -o out.key

# flag{nevergonnagiveyouup}

TLSで暗号化された通信ログを復号する問題。複数回あるTLSハンドシェイクの中で一度だけエラーが起こっている（CRT exponentが壊れている）ので、RSA-CRT fault Attackを実行して秘密鍵を作成し、HTTPパケットを復号する。