SSL/TLS Vulnerabilities: LuckyThirteen & BEAST

From Embedded Lab Vienna for IoT & Security
Revision as of 14:42, 22 October 2024 by NKirnbauer (talk | contribs) (link that doesnt exist)
Jump to navigation Jump to search

Lucky 13 is a timing attack on TLS/DTLS protocol discovered in 2012 by Nadhem AlFardan and Kenny Paterson. In 2013, they published their findings and released their 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 (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_i} ) and previous ciphertext (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \C_{i-1}} ) are combined with an XOR operation. Then it gets encrypted with the key. Repeat. In the first step we do not have any ciphertext (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_i} ) so we use the IV (initialization vector) for this one. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} stands for the encryption process.

This leaves us with this formula:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_i = E(P_i \oplus C_{i-1})}

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.

MAC-then-encrypt.png


DTLS Record Protocol

DTLS Protocol.png

Encryption


Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} = individual record (payload)

MAC calculation:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = \mathtt{SQN}||\mathtt{HDR}||R} 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is the resulting MAC.

Next, the plaintext (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} ) is created to encrypt with the following formula:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = R||T||\mathtt{pad}}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p+1} copies of the same byte value Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} . The Range for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \le p \le 255} . For example, 1 times “0x00” or 3 times “0x02”.

Now the plaintext is being encrypted with CBC-mode:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_j=E_{K_e}(P_j \oplus C_{j-1})}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_j} is the information we want to encrypt. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _j} identifies the different blocks we want to encrypt. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_0} is our starting point (IV). Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_e} is for the block cipher Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} .

Put together the data encrypted and being transmitted is:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathtt{HDR}||C}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} being the cipher text and HDR including version, type and length field. No sequence number (SQN) being transmitted.

Decryption

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_j=D_{K_e}(C_j) \oplus C_{j-1}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} = Decryption algorithm of the block cipher. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_j} 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = H((K_a \oplus \mathtt{opad})||H((K_a \oplus \mathtt{ipad})||M))}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} = MAC tag Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} = Message Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_a} = Key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} = 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.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (M_b) M_0, M_1}

Where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _b} is our message, in this case it is a bite → 0 or 1.

The attacker needs to identify the value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} . In this case, we define our bock-size as AES.

We let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_0} consist of 32 random bytes followed by 256 copies of "0xFF". We let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_1} 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathtt{HDR}||C}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathtt{HDR}||C'$. $C'} keeps the IV from the original encryption operation but removes all non IV parts of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} down to 288 bytes. This removes the MAC and padding of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} .

Attacker submits Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathtt{HDR}||C'} for decryption. Case Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_0} : 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_1} : 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_1} takes more time to calculate because a header and 255 bytes are passed through the MAC algorithm (compared to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_0} 's 16 bytes). This allows us to distinguish between the two Messages Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_0} .


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