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 <(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
