View source for SSL/TLS Vulnerabilities: LuckyThirteen & BEAST


Lucky 13 is a timing attack on TLS/DTLS protocol discovered in 2012 by Nadhem AlFardan and [http://web.archive.org/web/20220531081741/https://www.isg.rhul.ac.uk/~kp/ Kenny Paterson]. In 2013, they published their findings and released their [http://web.archive.org/web/20190414143311/http://www.isg.rhul.ac.uk/tls/TLStiming.pdf white paper]. The attack is shown to only work on LAN and is hindered by noise on the network (unwanted traffic). Timing the operations done for decryption, Lucky 13 is able to restore plaintext from an encrypted message. 

== Basics ==
Cipher Block Chaining (CBC) and MAC-then-encrypt are being used in the DTLS record protocol.

=== Cipher Block Chaining (CBC) ===

CBC is a method of encrypting plaintext. It takes a block of clear text and adds it (bit-by-bit) to the previous encryption.

IV = Initialization Vector is a (pseudo)random sequence of characters added to an encryption key. The IV should be different for any two messages encrypted with the same cryptography key.
First step is to divide the pain text into block size (size depends on underlying symmetric encryption algorithm). Plain text (<math>P_i</math>) and previous ciphertext (<math>\C_{i-1}</math>) are combined with an XOR operation. Then it gets encrypted with the key. ''Repeat''.
In the first step we do not have any ciphertext (<math>C_i</math>) so we use the IV (initialization vector) for this one.
<math>E</math> stands for the encryption process.

This leaves us with this formula:

<math>C_i = E(P_i \oplus C_{i-1})</math>

[[File:CBC_example.png]]

=== MAC-then-encrypt ===

MAC provides '''message authentication'''. Sender and receiver share a symmetric key.
* The sender uses some publicly known MAC algorithm, inputs the message and the secret key K and produces a MAC value.
* Send it.
* On receipt of the message and the MAC, the receiver feeds the received message and the shared secret key K into the MAC algorithm and re-computes the MAC value.
* The receiver now checks equality of freshly computed MAC with the MAC received from the sender. If they match, then the receiver accepts the message and assures himself that the message has been sent by the intended sender.

[[File:MAC-then-encrypt.png]]


== DTLS Record Protocol ==
[[File:DTLS Protocol.png]]
=== Encryption ===

<math></math>

<math>R</math> = individual record (payload)

MAC calculation:

<math>T = \mathtt{SQN}||\mathtt{HDR}||R</math>
SQN and HDR are prepended and are 13 bytes long:
* SQN = 8-byte
* HDR = 5-byte
** version field = 2-byte
** type = 1-byte
** length = 2-byte
<math>T</math> is the resulting MAC.

Next, the plaintext (<math>P</math>) is created to encrypt with the following formula:

<math>P = R||T||\mathtt{pad}</math>

''pad'' stands for "padding" which is appended to the plaintext. The size of the padding is to fit the block size of the selected block cipher (3DSE = 8 bytes/ AES = 16 bytes). Padding may span over several blocks. Padding added in TLS and DTLS must consist of <math>p+1</math> copies of the same byte value <math>p</math>. The Range for <math>p</math> is <math>0 \le p \le 255</math>. For example, 1 times “0x00” or 3 times “0x02”.

Now the plaintext is being encrypted with CBC-mode:

<math>C_j=E_{K_e}(P_j \oplus C_{j-1})</math>

<math>P_j</math> is the information we want to encrypt. <math>_j</math> identifies the different blocks we want to encrypt. <math>C_0</math> is our starting point (IV). <math>K_e</math> is for the block cipher <math>E</math>.

Put together the data encrypted and being transmitted is:

<math>\mathtt{HDR}||C</math>

<math>C</math> being the cipher text and HDR including version, type and length field. No sequence number (SQN) being transmitted.

=== Decryption ===

<math>P_j=D_{K_e}(C_j) \oplus C_{j-1}</math>

<math>D</math> = Decryption algorithm of the block cipher.
<math>P_j</math> is the Plaintext we receive.
The decryption is performed block by block. When finished, the padding is removed and the MAC is being checked. Finally, the sequence number can be checked.

== HMAC ==

TLS and DTLS exclusively use the HMAC algorithm. HMAC-MD5, HMAC-SHA-1, and
HMAC-SHA-256 are supported in TLS 1.2.

Fomula:

<math>T = H((K_a \oplus \mathtt{opad})||H((K_a \oplus \mathtt{ipad})||M))</math>

<math>T</math> = MAC tag
<math>M</math> = Message
<math>K_a</math> = Key
<math>H</math> = Algorithm

HMAC applies the specified hash algorithem twice in an iterated fashion.

''opad'' and ''ipad'' are specific 64-byte values (padding) that combined with the Key are exaclty 64 bytes. The hash function uses an encoding step called ''Merkle-Damg ̊ard strengthening''.

HMAC is computed of 64 byte blocks. This block takes 8 bytes for the header and at least 1 byte of padding.
55 bytes of data is the maximum a single block can take. A Message of the length up to 55 bytes need 4 comparison function evaluations to complete: 2 in the hash operation, 2 in the outer hash operation.
Messages from 55 up to (64+55=) 119 bytes give us two 64-byte block. This means that the we have 3 inner hash operations and 2 outer hash operations. For more blocks (3 and more) we can assume you add 1 operation per block. Remember that every operation takes some amount of time to be computed. Operations are in the sub-μ seconds spectrum.

== Distinguishing Attack ==

A distinguishing attack is any form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data. A distinguishing attack on the TLS-Protocol is to be  considered a significant weakness on its own.

=== Example ===

Two Messages are being used.

<math>(M_b) M_0, M_1</math>

Where <math>_b</math> is our message, in this case it is a bite → 0 or 1.

The attacker needs to identify the value of <math>b</math>.
In this case, we define our bock-size as AES.

We let <math>M_0</math> consist of 32 random bytes followed by 256 copies of "0xFF".
We let <math>M_1</math> consist of 287 random bytes followed by "0x00".
Both messages are 288 bytes long -> 18 plaintext blocks.

Attacker submits both messages for encryption and receives a ciphertext:

<math>\mathtt{HDR}||C</math>

The mechanism adds some padding to the MAC tag in the process of encryption. Additional bytes (MAC + padding) are added because it aligns with a block boundary. This also means the additional bytes are encrypted in separate blocks from the original message.

Now the Attacker forms a new ciphertext <math>\mathtt{HDR}||C'$. $C'</math> keeps the IV from the original encryption operation but removes all non IV parts of <math>C</math> down to 288 bytes. This removes the MAC and padding of <math>C</math>.

Attacker submits <math>\mathtt{HDR}||C'</math> for decryption.
Case <math>M_0</math>: We get plaintext with 256-byte padding pattern "0xFF...0xFF". Padding is removed, and the remaining plaintext is interpreted as short message and MAC tag. MAC verification fails.
Case <math>M_1</math>: Plaintext with valid 1-byte padding pattern remains "0x00". Padding (single byte) is removed, and a long message remains (287 bytes). The message is interpreted as the same as previously, MAC and message. MAC verification fails as well. Then we compare how log it takes to calculate the MAC verification. 

The longer message <math>M_1</math> takes more time to calculate because a header and 255 bytes are passed through the MAC algorithm (compared to <math>M_0</math>'s 16 bytes). This allows us to distinguish between the two Messages <math>M_1</math> and <math>M_0</math>.


== Plain Text Attack ==

The injected ciphertext causes bad padding and/or a bad MAC.
This leads to a TLS error message, which the attacker times.

There is a timing difference between “01 01” case and the other 2 cases.
A single SHA-‐1 compression function evaluation.
Roughly 1000 clock cycles, circa 1μs on a typical processor.
Measurable difference on same host, LAN, or a few hops away.
(Compare with original padding oracle attack: 2ms.)

Detecting the “01 01” case allows the last 2 plaintext bytes in the target block Ct to
be recovered.
Using some standard CBC algebra.
The attack then extends easily to all bytes, as in a standard padding oracle attack.

== Countermeasures ==

What's basically needed is some constant-time decryption for TLS-CBC.

Some solutions are:
* Add dummy hash compression function computations when padding is good to ensure total is the same as when padding is bad.

* Add dummy padding checks to ensure number of iterations done is independent of padding length and/or correctness of padding.

These measure are better but not perfect. Distinguishing attack was still possible.

Some other countermeasures are:
* Introduce random delays during decryption.
* Switch to TLS 1.2 with support for AES-GCM and AES-CCM.


== References ==
<references />
* http://web.archive.org/web/20190414143311/http://www.isg.rhul.ac.uk/tls/TLStiming.pdf

[[Category:Documentation]]