Hey there! I usually write in spanish here but as the attendance at Campus Party Europe was pretty international I’ll do this one in english so anyone can understand it.
All the information to try the challenge is at Eloi’s blog since he released it as challenge a couple of days ago. Before continuing I guess you either have played in the hacking contest at Campus Party Europe or already have read that post, if not… you are being late!
So, we receive 3 files: an AES encrypted file, a public key file and a readme with some instruction and data.
From the readme, this are some hints to understand what’s going on here:
- It uses a cryptographic device that contains a 1024 bit modular exponentiation accelerator
- A pair of RSA signatures over the same data, one of these signatures contains a fault injection
From those hints we get that it is actually using the RSA-CRT algorithm, which is a RSA variation to reduce computational costs using the Chinese Remainder Theorem. The point is that instead of using the 2048 bit modular exponentation it splits them into two modular operations, aproximately half the size, make the calculations and then recombine the results as needed to obtain the regular RSA result. But here’s the trick, if we inject a fault in one of these two exponentiations, via power glitching for example, there’s a way to recover the private RSA key. The use of RSA-CRT is common in embedded devices such as smart cards, mainly because of the hardware limitations. You can read a post about it at Eloi’s blog, it’s in spanish though: RSA-CRT Fault Injection.
RSA signs a message doing:
- s = m^d (mod n)
RSA-CRT does:
- s1 = m^dq (mod q)
- s2 = m^dp (mod p)
- s = a*s1 + b*s2 (mod n) = m^d (mod n)
- a being congruent to one modulo p and zero modulo q
- b being congruent to zero modulo p and one modulo q
Using the faulty signatures:
- s – s’ = a*s1 – a*s1′ will be congruent to zero modulo q
- s – s’ = b*s2 – b*s2′ will not be congruent to zero modulo p
Then if we calculate the greatest common divisor (using the Euclidean algorithm for example) between c-c’ and n ¡we will obtain the factor q! because c-c’ is multiple of q but not p. Then with p = n / q we will have both prime factors used in RSA 
Now we have to implement the attack, we need to deal with really big integers so I first though of using Java and its BigInteger, Matlab or Sage. I do hate Java, Matlab would have been nice, usually it treats big integers as arrays and uses proper algorithms adapted to array calculations but Sage was going to be the easiest and quickest for me.
We have s1, s2 and the encrypted message. First we need to obtain the exponent and the modulus from the public.key file, let’s use openssl:
$ openssl rsa -pubin -text -in public.key Modulus (2048 bit): 00:e8:52:42:77:0a:66:69:8c:64:49:61:5a:d4:8f: 70:e5:ff:7f:49:ca:45:33:43:7d:85:36:7e:1a:f3: 8f:31:aa:35:94:8e:b3:3f:97:88:f7:16:4a:1d:d5: c3:87:5b:f8:6b:69:3b:d8:cc:82:e2:cb:cb:d0:1c: f7:d1:b4:51:ef:67:cb:72:90:fa:79:0e:e1:02:24: e3:72:5b:37:b6:bc:3d:53:56:da:9d:0f:ba:c1:e0: 6b:b2:6f:f2:43:03:d9:06:d3:c9:66:c8:1b:19:9a: 78:b9:ef:02:2b:0f:b9:28:e5:82:fc:0c:e0:29:57: f6:b1:64:21:01:f9:2e:83:4a:ab:47:24:9e:e4:08: c2:91:d3:fc:e8:72:c1:44:69:12:31:37:f4:da:49: 28:00:75:03:36:47:20:69:f4:e2:4b:4a:0e:3e:e5: 15:85:ae:78:68:43:a3:c0:39:61:c2:12:a1:e3:94: d2:71:e8:26:14:c4:e7:aa:1d:5d:a4:16:01:1f:9b: 40:81:a8:e4:70:65:75:1a:de:de:51:d0:90:97:fb: 8a:41:ac:be:2e:54:5c:b6:d4:04:40:1d:59:16:c3: f6:86:16:e9:66:79:b3:5f:77:74:a9:e4:42:b1:98: 74:14:b0:22:ee:06:f0:0f:ac:3d:dd:b6:14:19:43: e5:53 Exponent: 65537 (0x10001) writing RSA key -----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA6FJCdwpmaYxkSWFa1I9w 5f9/ScpFM0N9hTZ+GvOPMao1lI6zP5eI9xZKHdXDh1v4a2k72MyC4svL0Bz30bRR 72fLcpD6eQ7hAiTjcls3trw9U1banQ+6weBrsm/yQwPZBtPJZsgbGZp4ue8CKw+5 KOWC/AzgKVf2sWQhAfkug0qrRySe5AjCkdP86HLBRGkSMTf02kkoAHUDNkcgafTi S0oOPuUVha54aEOjwDlhwhKh45TScegmFMTnqh1dpBYBH5tAgajkcGV1Gt7eUdCQ l/uKQay+LlRcttQEQB1ZFsP2hhbpZnmzX3d0qeRCsZh0FLAi7gbwD6w93bYUGUPl UwIDAQAB -----END PUBLIC KEY-----
To copy the modulus it’s easier from here:
$ openssl rsa -pubin -modulus -in public.key Modulus=E85242770A66698C6449615AD48F70E5FF7F49CA4533437D85367E1AF38F31AA35948EB33F9788F7164A1DD5C3875BF86B693BD8CC82E2CBCBD01CF7D1B451EF67CB7290FA790EE10224E3725B37B6BC3D5356DA9D0FBAC1E06BB26FF24303D906D3C966C81B199A78B9EF022B0FB928E582FC0CE02957F6B1642101F92E834AAB47249EE408C291D3FCE872C14469123137F4DA492800750336472069F4E24B4A0E3EE51585AE786843A3C03961C212A1E394D271E82614C4E7AA1D5DA416011F9B4081A8E47065751ADEDE51D09097FB8A41ACBE2E545CB6D404401D5916C3F68616E96679B35F7774A9E442B1987414B022EE06F00FAC3DDDB6141943E553 writing RSA key -----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA6FJCdwpmaYxkSWFa1I9w 5f9/ScpFM0N9hTZ+GvOPMao1lI6zP5eI9xZKHdXDh1v4a2k72MyC4svL0Bz30bRR 72fLcpD6eQ7hAiTjcls3trw9U1banQ+6weBrsm/yQwPZBtPJZsgbGZp4ue8CKw+5 KOWC/AzgKVf2sWQhAfkug0qrRySe5AjCkdP86HLBRGkSMTf02kkoAHUDNkcgafTi S0oOPuUVha54aEOjwDlhwhKh45TScegmFMTnqh1dpBYBH5tAgajkcGV1Gt7eUdCQ l/uKQay+LlRcttQEQB1ZFsP2hhbpZnmzX3d0qeRCsZh0FLAi7gbwD6w93bYUGUPl UwIDAQAB -----END PUBLIC KEY-----
Now we have the modulus and exponent. So let’s start Sage and apply what we’ve seen before 
Load the values:
sage: s1 = 0x3ae81964c8ecf1524b47c42cb0ecd2a3b6768dccd55960d7ff0a998f839b8c312a2cd821c270ae961777dd4dd50aa631fe823a8afd914911adf69c1c6cfda3b3aed01dad372cfdd6e9f63a4cc39e1a455cbfd04dea72bf07c4790d5fec469198ce28113d6d38a7baced9d3c3695ab27cbc5ab434aa8d2b5f53f66a383e079ddaed485d4a2b446e410eafcadbba9f159494c28c4a19fd416dff90f8c141e96d8260f8e6e0901832e31899c48ce0cbdae6a24595a19a01e490c87e7b48860e09006920d8ef7384217358c6db90638d6e8cbc795a091240f24105d8f3b27fe4b98fe9a507e00590b4cded41777b1b8967b0f752231e0e856b8f0132bde30a6e082e sage: s2 = 0x391e0340e5931a202012572ddacad877e5af3a1d846b70c1e64e3041f9ac0a3c7e8f82621df908eadca44fe777a6b1c799610be829e13ca233982fd268034addb5a79fa19f984631fdf3a61d32fc75ed77176c7a0b719504e804076dca66f10111aa124a7efe743ada75dda2ec53f3c28882a7724928685918261739f960a3648aa3eadc426181aa146a8ba0ff20f1c53de2113e0196af09595dc2ad1a0fe12096ff681f61363044615a7f72edf1f8c6531055e66c1e5f4498434c731d2308fecae46c779379ea3d7d7a5f1c2a0efeb5bc1b8a4af4fb21fce1dae943c27043e86642b3b1e6b889a31e7c4bc01bc2ebae4dc8432344532567d1d3df8b9bcafcbf sage: encrypted = 0x19303a82cbc50a56dc22f9aafc554da2ea632e33bee1d33c35edb13269ba0fd2fa791744e86eda7fc1cb15433f1232f86a42afcd5470215ccf0d05096ce1b8f075e6dc45df74896345297fcc145a4765aeaea78babaa6441ead3a2e73b37931dc7c07d4e04b7115284c7c04c85a61c7e555194d0f4ee762d47a8aeec2efcd75ee45e3e6a65f876f9a67aa01016f3ce9552d8f0b50cc150c70333aa6ac3a4ac8860d2879cad8439566f0ffda32612cb75dd9c1b456a4e1828582f05932f495452f19d71f300f2f48b8c1f8cde1b1b8d8ada3f6ff506e10d5d18d91d61402bc36756a88196381ff795980eee932a179525264e3a968f0abe9edbe672560c41833a sage: exponent = 0x10001 sage: modulus = 0xe85242770a66698c6449615ad48f70e5ff7f49ca4533437d85367e1af38f31aa35948eb33f9788f7164a1dd5c3875bf86b693bd8cc82e2cbcbd01cf7d1b451ef67cb7290fa790ee10224e3725b37b6bc3d5356da9d0fbac1e06bb26ff24303d906d3c966c81b199a78b9ef022b0fb928e582fc0ce02957f6b1642101f92e834aab47249ee408c291d3fce872c14469123137f4da492800750336472069f4e24b4a0e3ee51585ae786843a3c03961c212a1e394d271e82614c4e7aa1d5da416011f9b4081a8e47065751adede51d09097fb8a41acbe2e545cb6d404401d5916c3f68616e96679b35f7774a9e442b1987414b022ee06f00fac3dddb6141943e553
Calculate q and p:
sage: q = gcd(s1-s2,modulus) sage: p = modulus / q
In Sage to work with modular arithmetics you need to declare a group and then use the variables in that group. First let’s calculate the private RSA key
sage: G1 = IntegerModRing(lcm(q-1,p-1)) sage: private_key = G1(exponent)^-1
And finally working in modulo ‘modulus’ make the decryption to get the message:
sage: G2 = IntegerModRing(modulus) sage: message = G2(encrypted)^G2(private_key) sage: message 333277202522695828352578908493424296965 sage: hex(333277202522695828352578908493424296965) 'fabadababecafedeadbeef0102030405'
It’s a fabada password! xD We now have the plaintext which is the AES key. Let’s use again openssl to decipher the file. The readme file says it’s AES in ECB mode with a 128 bit key. The key length it’s obvious but if we didn’t know the operation mode we could just try them all.
$ openssl enc -d -aes-128-ecb -in encrypted.aes -out unencrypted.file -K fabadababecafedeadbeef0102030405 $ file unencrypted.file unencrypted.file: PNG image, 124 x 124, 8-bit/color RGB, non-interlaced
We can see that it worked like a charm: the file it’s a PNG image. The first thing you think when you see a PNG it’s uhmm… a bit of stego? thumbnails? LSB? Well, this one is just a QR Code.
Using any QR decoder (I used http://zxing.org/w/decode.jspx ) we get:
Key: DoubleCheckYourCryptoResults
Which is a funny final password since one of the common protections against fault injection attacks is to double-check all sensitive computations
Congratulations to Eloi for this challenge! I found it one of best I’ve ever done because it has to do with real world attacks and crypto related maths, so it’s not just another cryptic puzzle where mostly you only have to use tools or need a smart guess.
I hope you liked it!
Many thanks also to SecurityByDefault for an excelent wargame and congratulations to the winners:
- knx
- FluxReiners
- aw3a
–
Fuente original en http://vierito.es/wordpress
4 responses so far ↓
1 papanoel
// Apr 19, 2010 at 11:53 pm
Nice write-up!! I’m relieved to see that there is life beyond Matlab… it looks like Sage doesn’t spam ‘matrix dimensions must agree’ messages as Matlab, this made my day!
I’ll include Sage in my to-do list.
PS (in spanish): ponle un módulo de Tex a tu blog, lo pide a gritos
Fabada con café power!!
2 vierito5
// Apr 20, 2010 at 9:44 am
Thanks papanoel! I’m totally new to Sage but it seems pretty nice
.
And yeah, I do need a LaTeX plugin, I promise I won’t write this way again xDD
3 Fidel
// Apr 21, 2010 at 2:33 pm
Buenísimo el post Javi!!
4 Curiosa manera de recuperar una clave privada RSA [eng]
// Apr 26, 2010 at 1:42 pm
[...] Curiosa manera de recuperar una clave privada RSA [eng] vierito.es/wordpress/2010/04/19/crypto04-challenge-write-up-… por niktofun hace 5 segundos [...]
Leave a Comment