AIRBUS | Crypto150 [WRITEUP]

Those files were given :

$ file crypto.tgz
crypto.tgz: gzip compressed data, from Unix

$ ls
alice.crt  bob.crt  ca.crt  challenge1  charly.crt

$ file *
alice.crt:  PEM certificate
bob.crt:    PEM certificate
ca.crt:     PEM certificate
challenge1: MIME entity text
charly.crt: PEM certificate

 

– So, I had three PEM certificates and a S/MIME entity text file.
Well, that’s have a look at a certificate, using openssl :

    $ cat bob.crt
    -----BEGIN CERTIFICATE-----
    MIIEWTCCAkGgAwIBAwIRAJ+dUbxw7yHKXBTzB5gKKdgwDQYJKoZIhvcNAQELBQAw
    // ... snip long base64 encoded  ... //
    yS0OXmEBxulU7R28rg==
    -----END CERTIFICATE-----

    $ openssl x509 -in bob.crt -text -noout
    Certificate:
        Data:
            Version: 4 (0x3)
            Serial Number:
                9f:9d:51:bc:70:ef:21:ca:5c:14:f3:07:98:0a:29:d8
            Signature Algorithm: sha256WithRSAEncryption
            Issuer: C=FR, L=Paris, CN=ca@example.com
            Validity
                Not Before: Oct  7 07:22:29 2014 GMT
                Not After : Oct  6 07:22:29 2019 GMT
            Subject: C=FR, L=Paris, CN=bob@example.com
    // ... snip ... //

 

I noticed that the exponent is the smallest possible ( the RSA public exponent e is
an integer between 3 and n – 1 satisfying GCD(e, \lambda(n)) = 1,
where \lambda(n) = LCM(r_1 – 1, …, r_u – 1) [rfc3447]

 

– I displayed the exponent of the three .crt file :

    $ for CRT in !(ca).crt; do
        > openssl x509 -in $CRT -text -noout |egrep -i "exp"
        done
            Exponent: 3 (0x3)
            Exponent: 3 (0x3)
            Exponent: 3 (0x3)

Interesting ! The three .crt have a the smallest exponent and the same (0x03)

 

– After that, I focused on the file called challenge1 (remember that’s a S/MIME file) :

    $ cat challenge1 |head -3
    MIME-Version: 1.0
    Content-Disposition: attachment; filename="smime.p7m"
    Content-Type: application/x-pkcs7-mime; smime-type=enveloped-data;
                  name="smime.p7m"

	// ... snip long base64 encoded ... //

 

– If you want, you can try to decode the b64 and look for informations. But there
is an option in openssl which we can use to parse the pkcs7 object :

    $ openssl asn1parse -in <(tail -n+6 challenge1 |base64 -d) -inform der
    ...
    4:d=1  hl=2 l=   9 prim: OBJECT            :pkcs7-envelopedData
    ...

 

– That’s good, it’s a pkcs2 enveloped data. Now, let’s have a look at the octet
string :

    $ openssl asn1parse -in <(tail -n+6 challenge1 |base64 -d) -inform der \
        | grep "OCTET STRING.*"

        128:d=5  hl=4 l= <b>256</b> prim: OCTET STRING      [HEX DUMP]: ...
        487:d=5  hl=4 l= <b>256</b> prim: OCTET STRING      [HEX DUMP]: ...
        846:d=5  hl=4 l= <b>256</b> prim: OCTET STRING      [HEX DUMP]: ...
        1133:d=5 hl=2 l= <b>8</b>   prim: OCTET STRING      [HEX DUMP]: ...

 

– So, we have 4 octet strings. The first three have a length egal to 256, and the
last have a length egal to 8.
What does this mean?

 

The same message has been sent to three recipients. And what about the last octet
string ?
To understand what that is, look a little before :

    $ openssl asn1parse -in &lt;(tail -n+6 challenge1 |base64 -d) -inform der \
    | grep "01D4CE3AF4D17ABB" -B1
    1123:d=5  hl=2 l=   8 prim: OBJECT            :<b>des-ede3-cbc</b>
    1133:d=5  hl=2 l=   8 prim: OCTET STRING      [HEX DUMP]:01D4CE3AF4D17ABB

The object « des-ede3-cbc » means that the data is encrypted using the well-known
algorithm called 3DES (version 3).
FYI : 3DES is just the DES algorithm that’s used 3 times on the plaintext.

 

To sum up :
– Same message
– Three different recipients
– Same exponent (0x03)
So, we have (mathematically) :

c1 = m^3 % n1
c2 = m^3 % n2
c3 = m^3 % n3

 

We can replace m^3 by x :

c1 = x % n1
c2 = x % n2
c3 = x % n3

 

– So, we have a system with 3 equations, but only one unknown ! 🙂
Simplifying, we obtain :

m^3 = c1 * n2 * n3 * ((n2 * n3)^-1 [n1]) +
      c2 * n1 * n3 * ((n1 * n3)^-1 [n2]) +
      c3 * n1 * n2 * ((n1 * n2)^-1 [n3]) %
      (n1 * n2 * n3)

 

– m must be lower than the modulus :

    m < n1
    m < n2
    m < n3
______________
m^3 < n1*n2*n3

 

– That’s to say :

m^3 = ??? % (n1*n2*n3)

 

– Now, either we use python (or another language), either Sage (a powerfull
mathematic program).
I used Sage, that I didn’t know before, because it has interesting functions.

This is my final code :

aliceC =
0xC1E2357C6FC53F1CC5E0E76EB1224BE8F24E8839251CF954A98090C4549F1BAFB7BCB10
06DD2A982D56C1D2D3E6B422122D01F78DA0099776B789162E8CE94EE3D1E7B88AA8175DB
B86F2F4AC65361BC949B3B90460741CAEE6F1ABDC5BD6C5296FBC8F2DAFF77F7110EA32D3
30D38DD2CA2FE13E785C86FE2210B58074C2DA5F440794BA023FC98B3D1E7DC979DBAC667
2B5C19ABF4A91E21D5E474475BC09B78910D1F8E0290B38AE8D756E04D7F5EFBA64BFB5A0
E96CD3DE1D82F609544A423F666D08B63262229687E1982BC8E424C7B5266B11A59036625
F8E92C06740A3C9D8F3CE87FEB1F4444BC2039C8C6FF0AB9457D8AA63851ECF3C4AF1A232
8FD
aliceN =
0xEFBA9C442084759DC9770021B03C2E2913053E770779316F92C5DBFCAE4D3682E64006E
38FA6A3AC24CC13AD2E747A50E5735064549F590294E36F2A1B23DB29567B49C007F8F8C2
24D3CD19B81D3F198C540291C135965E549881B775EEE29684F0E6CD4C2A017BE38F2E78E
070D503BE9EE3EA2C491E53DE9C705FEB973918A168F275D90D055778289598BD2377D79A
CC1BA493F570C5C8301913CEF12CD513321F8F320D8EC8172182D03F33721F02DFCE24463
AE7A6CAB7C3A0CBB7D2AB149D347A2C9ABDB81BE4B60CAECBF31CF79C4BA0081FC00BB093
9A950CBACA5B7B79FF92AF273B0D01A7E183FF30C90F27705D18F70EBB32281C5A873ED0A
90D

bobC =
0x27EB5A62A311DFAECF09318BEF7D60B98EA151AF09BDBF2A89A884617B8A8A14FF6F8045
A8FD5D8956F5768C32A7E47AB17FA08D5F7D2EB590C4FC8296A1F70069C338CFA3C131A58F
E05A75E36D7457ECC7B1BB403C1FF31FA66FB478B1F4548325B57961191AE1BFDDD7F5AF6F
EC6FD94F66B1BC482337B579AD790466D1F33EDB09AA388085053D3C383F91A8EC40DB1503
65735B7E2D01F172E23717D31ABE0350FAC6730673C3C70EE593E8008A222DE40CF8A62615
D119CD119FE8C30DA49E7A1D3596279B659E72C584D6D8262B1126B8C8BCDC09A31761EE74
6A14ADA7EC387AF2C52CBABDD8F443DF1F4C5E70C83B82A12F3BBCB21494689D13791F
bobN =
0xC0028301D5645483592E2117463A804454BD1AE33B1CBEF33D9CDFF86EFD46CB24BA1984
874DAE3A4A3D3609D9607276F91DFAD38E9ED6B6BCE15F29C49E1C7E0B532AE2A1343AF3F8
064B4A093F23F981624D4E08F901787B761847B4F0963512EAC13B5D47DA4295FF614501A3
D7D7EDA6B4E6197B974A70BF11FDC5D619D50974415E209DE76C68F190DBCA5BB6F1963C1E
0E987BE105FF9082EAE003C2051A4C95E3299D3C1BC64D5F8E95D40C7B27EEEA5EBCD9B54C
D6B5655B0AB9AEAA15E976AE37EA228A151D2AFD5417D4BCBC3BFB396E6B10AF561CBE0FD0
374081B7034585C54096849FF82B79A117E44AE8FDB5B304BC0D9CA297C2F4A57FF91F

charlyC =
0x04991C5BA4882F329B03B18E2B317F4A54905ED4EB832B084A42AD700A0D3136A14BB57D
61D4A1982E2CAB0FF773356759EE4AD77C1982E642CF574332AB32D109952FDE6221D77C35
E4D0B69E559392DBE602E5336BD09239E85F21A70F4A824907AF75C9C372D4BE4C15E45431
C35FE678E2646017D74186B3B084A41F217655A2ED262AA5C300BA737AB0DF270BD0B38A2F
F215A3B5DB3CBB79350DDFEF1A08E40CB253B506D92002BBF4AD112AC1DDDB96CD4539A010
35E76B1CC5C43427F46C83DBAA318387FE2C8C7FAA75FC0099050CF98671015A568CFFC56D
FF6F8CB80A6A55B4CCB0D825AA9D99098DDA5D2EEC7D40D0BCCDA42D9E618A09AEC50A
charlyN =
0xCFA7854352FF9DF5E84AB10AB8F034F8106811D973BAB528BFCBD3DCBCFDF9FB5C398E23
B58BA883F7C78F47C6694B4F042CDB8E54E856040F8A8A9ADBCA4C6D0813894C43352EB3EE
19C1F76DF46DFD1B6BB38349BCE811036B0ED7ACFE2E5045FE4232F11DA3F113189A176964
C206155342FD9E2E8AD11CBBCB85DFDF30E62AEA068F2DD7CEC6CF818D1E312BBA5FA63854
61CA5ADCA0F95B6299FA366EEF8856416D72A42A93FD979E269D8FEA143870985FD353C858
50FB4A11B6E4BA483CDC97F7E1717C34DF7D9E34DF83F67A9DA97ACA69926167D44C2CB3BB
858EC041A244A6197D7F3B9AFD02A0562F13EACE6494F289184DAD16D2D995ED1ADC13

hex(int((CRT_list([aliceC, bobC, charlyC],[aliceN, bobN, charlyN]))^(1/3)))
[OUT] :
'0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
004f8957408f0ea202c785b95e206b3ba8da3dba7aea08dca1L'

 

– W00t, no error, and we have an output \o/
According to the rfc3447 :

<b>“EM = 0x00 || 0x01 || PS || 0x00 || T.”</b>

 

– So, we have 0x00 (not displayed ‘coz egal to 0), 0x01, 0xff (many times), 0x00
and 4f8957408f0ea202c785b95e206b3ba8da3dba7aea08dca1.
That is the 3DES key ! Cool 🙂

 

– The last thing to do ? Decrypt the message using the 3DES key :

    $ openssl des-ede3-cbc -d \
                             -iv 01D4CE3AF4D17ABB \
                             -K 4f8957408f0ea202c785b95e206b3ba8da3dba7aea08dca1 \
                             -in message.enc

Enjoy !
Notfound (Boris P.)

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s