John & Bill (crypto 250)

Category: crypto Points: 250 Solves: 2
Author : valentin
Description : You have intercepted a message your boss send to two of your managers. You would like to read it but it is encrypted. Can you read it anyway ?
Attachment : cry250.zip

Information sur les clefs :

<sam@sam-ecl:~/grehack/crypto/250>
zsh 7508 % openssl rsa -inform PEM -pubin -in John.pub -text -noout 
Public-Key: (2048 bit)
[...]
<sam@sam-ecl:~/grehack/crypto/250>
zsh 7507 % openssl rsa -inform PEM -pubin -in Bill.pub -text -noout
Public-Key: (2048 bit)
[...]

Extraction des données des clefs :

<sam@sam-ecl:~/grehack/crypto/250>
zsh 7505 % grep -v -- ----- John.pub | tr -d '\n' | base64 -d | openssl asn1parse -inform DER -i -strparse 19
    0:d=0  hl=4 l= 264 cons: SEQUENCE          
    4:d=1  hl=4 l= 257 prim:  INTEGER           :BDA0280816678FFA9BAF2B3AE04AD94848A0C4889AA527F365F605001B798CDE3ED91A29EBEA08BE24F766D68B0739A56BD56B4757F94ABD2652BC0AE3C65F412E71BB6619AB8C187B08990CE45D2AB067A88AF62B6CC6D7D33E486EEC762FF2A922D81889F99E6F1396FC65A5321441153C2F896D6467A8238CEF9D1B7E7EFA544BDA91C747CFB1FF3D71B6A01A77CADEAA229E6E637B32AD520462D239E71C3A526692040230CA27044B2039BFC019718D2B4EAF95A3AB9C5E98D5BFBA0BB9956049D148418EF18557A3F6B9FC4E17D92FC2A1800DB27A662815EC9BD005CEA3CCAEB83ED2502B5B86A16B501FCBDEFEE47C0571DE625B283398715E765FC7
  265:d=1  hl=2 l=   1 prim:  INTEGER           :03
<sam@sam-ecl:~/grehack/crypto/250>
zsh 7505 % grep -v -- ----- Bill.pub | tr -d '\n' | base64 -d | openssl asn1parse -inform DER -i -strparse 19
    0:d=0  hl=4 l= 266 cons: SEQUENCE          
    4:d=1  hl=4 l= 257 prim:  INTEGER           :BDA0280816678FFA9BAF2B3AE04AD94848A0C4889AA527F365F605001B798CDE3ED91A29EBEA08BE24F766D68B0739A56BD56B4757F94ABD2652BC0AE3C65F412E71BB6619AB8C187B08990CE45D2AB067A88AF62B6CC6D7D33E486EEC762FF2A922D81889F99E6F1396FC65A5321441153C2F896D6467A8238CEF9D1B7E7EFA544BDA91C747CFB1FF3D71B6A01A77CADEAA229E6E637B32AD520462D239E71C3A526692040230CA27044B2039BFC019718D2B4EAF95A3AB9C5E98D5BFBA0BB9956049D148418EF18557A3F6B9FC4E17D92FC2A1800DB27A662815EC9BD005CEA3CCAEB83ED2502B5B86A16B501FCBDEFEE47C0571DE625B283398715E765FC7
  265:d=1  hl=2 l=   3 prim:  INTEGER           :010001

Extraction des messages :

<sam@sam-ecl:~/grehack/crypto/250>
zsh 7509 % xxd -p message1 | tr -d '\n'
2133678c443a32de129e2e75523583758f7785c2ee96200e036d3d4a1f47d5a1f15e20ef89c6ba43b345a537072dce440d4d22c3572fafdb550b2784f09a44ef40bef021f07170a4a4ec274a98d01574ae43807507655722402277ebc6dcd5884e320b37795bed73e592389a765ca6b111e7249bb0384999ab9e8c975cdb6900bce95ca0ce5901f35595c72bc2b139066d57b504d2082e1d1a31f2e69c646d015b3f6d8051bb671c32bbf1301edc4f4a987aca0c1a02886b6a44dc32060aeb924f1c7dfd2cbbd5977cdf4ec72c94951878dc26ea91ec5195e3a460bb8202e131e32a4fe104dd6c1478d75bcc15ec86b0b0d8568a5869a8247384616102dca18d
<sam@sam-ecl:~/grehack/crypto/250>
zsh 7510 % xxd -p message2 | tr -d '\n'
6fc8b761875dcd54eb7ebfd1a3696a42a26cb47f8aa99da274919796ebd69a40a9b7d7a3965e0f5932888667dd65ab331276ee2d7f0d56b1f8083520730a3961af62ed9e54df54a86864d56075689bd394c70567309f0a69302c15dcab5cc5779dbd129ee4443a1a64347c3cd3ccb6662f4785bd8058d951f5b8c4c73d96d66dd328c2e4d2244f2797d8c7c7f5b11d51436ce9d44e967ce2f09c2c2bebe8a652520dd2b538f513b2d0cbde89aef54735383afbbc1751b7b35fa3f1fdeeeb71e83b7fa156f091b607536fb717a53077dbefb08d119a25790050ca62a21fae84272281dd23aef958aef0b461e65d1b59e42c5d96f9e99467c685d1442f5ed1c540

On a 2 clefs publiques avec le même modulo et 2 exposants différents. Le même message a été chiffré par ces 2 clefs.
Parfait on va pouvoir utiliser le « Common Modulus Attack » qui se prête justement à ce cas de figure.

L’équation pour résoudre cette attaque : c2^y * c1^x % N = m
Je vais utiliser sage pour résoudre cette équation.

x et y sont obtenus grâce au théorème de Bezout :
si e1 et e2 sont premiers entre eux (gcd(e1,e2)=1) alors e1*y + e2*x = 1
La fonction qui permet d’utiliser le théoreme de Bezout avec sage est xgcd (Extended Euclidean algorithm).

Voici ma solution :

Script : crypto250.sage

from sage.all import *

# modulus
N  = 0xBDA0280816678FFA9BAF2B3AE04AD94848A0C4889AA527F365F605001B798CDE3ED91A29EBEA08BE24F766D68B0739A56BD56B4757F94ABD2652BC0AE3C65F412E71BB6619AB8C187B08990CE45D2AB067A88AF62B6CC6D7D33E486EEC762FF2A922D81889F99E6F1396FC65A5321441153C2F896D6467A8238CEF9D1B7E7EFA544BDA91C747CFB1FF3D71B6A01A77CADEAA229E6E637B32AD520462D239E71C3A526692040230CA27044B2039BFC019718D2B4EAF95A3AB9C5E98D5BFBA0BB9956049D148418EF18557A3F6B9FC4E17D92FC2A1800DB27A662815EC9BD005CEA3CCAEB83ED2502B5B86A16B501FCBDEFEE47C0571DE625B283398715E765FC7
# cipher 1
c1 = 0x6fc8b761875dcd54eb7ebfd1a3696a42a26cb47f8aa99da274919796ebd69a40a9b7d7a3965e0f5932888667dd65ab331276ee2d7f0d56b1f8083520730a3961af62ed9e54df54a86864d56075689bd394c70567309f0a69302c15dcab5cc5779dbd129ee4443a1a64347c3cd3ccb6662f4785bd8058d951f5b8c4c73d96d66dd328c2e4d2244f2797d8c7c7f5b11d51436ce9d44e967ce2f09c2c2bebe8a652520dd2b538f513b2d0cbde89aef54735383afbbc1751b7b35fa3f1fdeeeb71e83b7fa156f091b607536fb717a53077dbefb08d119a25790050ca62a21fae84272281dd23aef958aef0b461e65d1b59e42c5d96f9e99467c685d1442f5ed1c540
# cipher 2
c2 = 0x2133678c443a32de129e2e75523583758f7785c2ee96200e036d3d4a1f47d5a1f15e20ef89c6ba43b345a537072dce440d4d22c3572fafdb550b2784f09a44ef40bef021f07170a4a4ec274a98d01574ae43807507655722402277ebc6dcd5884e320b37795bed73e592389a765ca6b111e7249bb0384999ab9e8c975cdb6900bce95ca0ce5901f35595c72bc2b139066d57b504d2082e1d1a31f2e69c646d015b3f6d8051bb671c32bbf1301edc4f4a987aca0c1a02886b6a44dc32060aeb924f1c7dfd2cbbd5977cdf4ec72c94951878dc26ea91ec5195e3a460bb8202e131e32a4fe104dd6c1478d75bcc15ec86b0b0d8568a5869a8247384616102dca18d
# exponent 1
e1 = 3
# exponent 2
e2 = 65537
# extend euclidean algorithm
gxy=xgcd(e1,e2)
x=gxy[1]
y=gxy[2]
# message
m=(c2**y) * (c1**x) % N
# cleartext
print hex(int(m))[2:-1].decode("hex")
<sam@sam-ecl:~/grehack/crypto/250>
zsh 7511 % sage crypto250.sage 
Congratulations, you have the plaintext. The flag is "suludoMnommoC". The end of this file is useless random padding. Do not pay attention to it.e401db19428896f6332a6256c427b513dedfad098dc5dfd1acc43bd0116ac11dad41248f41c0dd0f52226f8e3e6357db3ab99291d37e73

Flag : suludoMnommoC

Write-Up by sambecks

Leave a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *