INTRODUCTION

Cipher-block chaining mode: CBC mode processes the data based on some initialization vector IV which is a l-bit string. The input to the encryption algorithm is the XOR of the current plaintext block and the preceding cipher text block.

Secure Socket Layer (SSL) and Transport Layer Security (TLS): SSL was originated by Netscape. TLS working group was formed within IETF. First version of TLS can be viewed as an SSLv3.1. Figure 1 shows the record format of SSL.

Figure 2 shows the operation of the SSL Record Protocol.

TLS has the same record format as the SSL. It is defined in RFC 2246 and is similar to SSLv3. the differences between SSL and TLS are:

CBC-PAD in secured channels: Peer-to-peer secure and safe channels can be established by the Transport Layer Security Protocol. It requires:

Fig. 1:	SSl protocol stack

Fig. 2:	SSL record protocol

Let b be the block length in characters let b = 8 for DES as it requires 64-bit M. Let M be the message to be sent. First we append the MAC of M to M. We obtain MjMAC. Then we pad MjMAC with a padding PAD such that MjMACjPADjLEN is of length a multiple of b where LEN is a single byte whose value ` is the length of PAD in bytes. PAD is required by the TLS specifications to consist of l bytes equal to l. Then MjMACjPADjLEN is cut into a block sequence x 1, x 2…, x n (each x i has a length of b), then encrypted in CBC mode, i.e. changed into y 1, y 2,…, y n with

where, ENC denotes the block cipher. The initial vector IV y₀ can be either a part of the secret key, or a random value sent with the cipher text, or a xored value. When y 1, y 2,…, y n is received, it is first decrypted back into x 1, x 2,…, xn. Then we look at the last byte LEN, call l its value and separate the padding PAD of length l and LEN from the plaintext. It is required that PAD should be checked to consist of bytes all equal to l. If this is not the case, a padding error is generated. Otherwise the MAC is extracted then checked. If the MAC is not valid, a MAC error is generated. Otherwise the clear text M is extracted and processed. In TLS, fatal errors such as incorrect padding or bad MAC errors simply abort the session. The error messages are sent through the same channel, i.e. they are MACed, padded, then encrypted before being sent. A typical application of TLS is when an email application connects to a remote IMAP server. For this, the client simply sends the user name and password through the secured channel, i.e. the message M includes the password in clear.

Side channel attack against CBC-PAD: It assumes that we can send a cipher text to the server and get the answer which is either an error or an acknowledgment. We model it as an prediction P. When the answer is a padding error message (decryption failed), we say that P answers 0. Otherwise the prediction P returns 1. Let y be the cipher text block to decrypt. The purpose of the attack is to find the block x such that y = ENC(x). We first transform the prediction P into an prediction Check1(y; u) which checks whether the ENC 1 (y) block ends with the byte sequence u or not. We then use this prediction in DecryptByte1(y; s) in order to decrypt a new character in ENC 1 (y) from the known tail s of x.

Fig. 3:	Side channel attack against CBC-PAD

We then use this process in DecryptBlock1(y) in order to decrypt a full block y. The attack of Vaudenay^[1] works against WTLS^[2]. It does not work against TLS for two reasons. First of all, as soon as a padding or MAC error occurs the session is broken and needs to restart with a freshly exchanged key. The attack could have still worked in order to decrypt only the rightmost byte with a probability of success of 2^-8. It can also be adapted in order to test if x ends with a given pattern^[1]. This does not work either against TLS for another reason i.e. error messages are not available to the antagonist (they are indeed encrypted and indistinguishable). In order to make them even less distinguishable, standard implementations of the TLS protocol now use the same error message for both types or errors (as specified for SSL) in order to protect against this type of attack^[3].

Timing attack
Attack principles: In order to get access to the error type which is not directly available, we try to deduce it from a side channel by performing a timing attack^[4]. Instead of getting 0 or 1 depending on the error type, we now have prediction which outputs the timing answer T of the server. The principle of the attack is as follows: in order to check if the padding is correct, the server only needs to perform simple operations on the very end of the cipher text. When the padding is correct, the server further needs to perform cryptographic operations throughout the whole cipher text in order to check the MAC and this may take more time. We use the variation between the time it takes to perform the two types of operations in order to get the answer from the prediction P.

We increase the discrepancy of the two types of errors by enlarging the cipher text: the longer the cipher text, the longer the MAC verification.

Fig. 4:	Regular timing attack

(The MAC verification time increases linearly with the length of MES.) Hence we replace the r | y fake cipher text in DecryptByte1 by f |r| y where f is a random block sequence of the longest acceptable length (i.e. 214+2048 bytes in TLS).

On Fig. 4 is the updated algorithm. It uses a DecryptBlock2 algorithm which is similar to Fig. 3. Note that Check2 may miss the right byte, so DecryptByte2 needs to repeat the loop until the byte is found.

Experiment: We made a statistical analysis of the answer time for the two types of errors. The expected values μ_R and μ_w and the standard deviations μ_R and μ_w for the two distributions are as follows:

Note that these values were obtained on a LAN where, a fire wall was present between the attacker and the server, so the attacker was not directly connected to the server.

Analysis of the best ACCEPT predicate: The ACCEPT predicate is used in order to decide whether the distribution of the answers is DR (the predicate should be true) or DW (the predicate should be false). The predicate introduces two types of wrong information. We let ε+ (resp. ε-) be the probability of bad decision when the distribution is D_W (resp. D_R). The ε + and ε- probabilities can be interpreted as the probabilities of false positives and false negatives of a character correctness test. The optimal tradeoff between ε + and ε- is achieved by the ACCEPT predicate which is given by the Neyman-Pearson lemma:

with f_R and f_W the density functions of DR and DW, respectively and a given threshold ã. Depending on ã we trade ε + against ε. With the approximation by a normal distribution the ACCEPT test can be written

so we equivalently can change the definition of τ and consider

as the ACCEPT test choice. With this we obtain

where:

Using sequential decision rules: The following algorithm shows a more general skeleton. Basically, we collect timing samples T j until some STOP predicate decides that there are enough of these for the ACCEPT predicate to decide. We use DecryptByte3 and DecryptBlock3 algorithms which are similar to DecryptByte2 and ecryptBlock2 (Fig. 5).

Multi-session attack
Attack strategy: Since sessions are broken as soon as there is an error, the attacks from previous sections do not work. We now assume that each TLS session includes a critical plaintext block x which is always the same (e.g. a password) and that we intercept the corresponding cipher text block y = ENC(x y ‘). (Here y 0 is the previous cipher text block following the CBC mode.) The target x is constant in every session, but y and y 0 depend on the session. The full attack is depicted in the algorithm discussed in analysis. Here the Check4 prediction no longer relies on some y since this block is changed in every session. The Check4(u) is called in order to check whether \the x plaintext block ends with the byte sequence u" or not. The plaintext block x is equal to ENC^-1 (y) y ’ for some current key and some current cipher text blocks y and y’.

Fig. 5:	Timing attack with a sequential distinguisher

Fig. 6:	Password interception inside SSL/TLS

We assume that the prediction can get y and y ’.

Analysis: Let C be the average complexity of DecryptBlock4. Let Z denote the set of all possible byte values. Let p be the probability of success of DecryptBlock4.

Let p i be the success probability of DecryptByte4(s) assuming that s is the right tail of length I-1. We have p = p 1…p b.

In order to simplify our analysis, we assume that the target block is uniformly distributed in Z b so that step 1 of DecryptByte4 can be ignored (Fig. 6). We further consider a weaker algorithm in which the outer repeat/until loop of DecryptByte4 is removed (i.e. we consider that the attack fails as soon as a STOP predicate is satisfied but the ACCEPT predicate takes a bad decision).

Table 1:	Calculated complexity C and threshold values log τ- and log τ+ for algorithm DecryptBlock4 given success probability p with μR = 23.63, μW = 21.57, σ = 1.86 and heuristic value B = 32.93 for dictionary and distributions in Zb

Password interception with dictionary attack
Attack description: We now use the a priori distribution of x in the previous attack in order to decrease the complexity. For instance, if x is a password corresponding to an IMAP authentication, we perform a kind of dictionary attack on x. We assume that we have pre computed a dictionary of all possible x blocks with the corresponding probability of occurrence. We use it in the first step of DecryptByte4 in order to sort the c candidates.

Analysis: We consider a list of possible blocks c _b…c ₁. We let Pr[c _b…c ₁] be the occurrence probability of a plaintext block. We also let Pr[c _i…c ₁] be the sum Pr[c _b…c₁] for all possible c _b…c _i+1. We arrange the dictionary of all blocks into a search tree. The root is connected to many sub trees, each corresponding to a c₁ character. Each sub tree corresponding to a c₁ character is connected to many sub-sub trees, each corresponding to a c₂ character... We label each node of the tree by a c i…c 1 string. We assume that the list of sub trees of any node c i…c 1 is sorted in decreasing order of values of Pr[c I+1 c_i…c ₁]. We let N(c _i+1…c ₁) be the rank of the c _i+1…c ₁ sub tree of the node c i…c ₁ in the list.

Numerical example: We have used dictionary^[5] from which we have selected only words of size b = 8 characters (i.e. 8 bytes), giving a total word count of 712-786 words and ordered it as described the previous section. For this dictionary, we have calculated that C₀ = 31 and then implemented algorithm DecryptBlock4 and confirmed this result. Note that C₀ = 31 is a quite remarkable result since the best search rule for finding a password out of a dictionary of D = 712 0 786 words consists of |log ₂ D| = 20 binary questions, so the overhead is only of 11 questions.

Implementation of the attack : Here we describe how the DecryptBlock4 was implemented in practice against an IMAP email server.

Setup: The multi-session attack has been implemented using the Outlook Express 6.x client from Microsoft under Windows XP and an IMAP Rev 4 server 8. Outlook sends the login and password to the IMAP server using the following format:

Here XXXX are four random digits which are incremented each time Outlook connects to the server. An interesting feature of Outlook is that (by default) it checks for messages automatically every 5 min and also that it requires an authentication for each folder created on the IMAP user account, i.e. we have a bunch of free sessions every 5 min. For instance, with five folders (in, out, trash, read and draft), we obtain 60 sessions every hour. If Outlook is now configured to check emails every min, the fastest attack of Table 1 with 166 sessions requires half an hour. Outlook notices that some protocol errors occur but this does not seem to bother it at all. The TLS tunneling between the IMAP server and Outlook Express was implemented using stunnel v3.22 9.

This is a man-in-the-middle type attack where connection requests to the IMAP server from the Outlook client are redirected to the attacker's machine using DNS spoofing where the attacker intercepts the authentication messages and attempts to decrypt it using DecryptBlock4. Note that the attack is performed on a Local Area Network.

Conditions for the attack: Obviously, the attack works if the following conditions are met.