From ebd3a49b90553d78ad89c6a21d673a2a0e70b7c2 Mon Sep 17 00:00:00 2001 From: Juraj Somorovsky Date: Sun, 16 Oct 2016 18:09:56 +0200 Subject: Lucky 13 patch for SHA-1 and SHA-256 --- src/lib/tls/tls_cbc/tls_cbc.cpp | 76 +++++++++++++++++++++++++++++++++++++++++ src/lib/tls/tls_cbc/tls_cbc.h | 2 ++ 2 files changed, 78 insertions(+) (limited to 'src/lib') diff --git a/src/lib/tls/tls_cbc/tls_cbc.cpp b/src/lib/tls/tls_cbc/tls_cbc.cpp index c7203003b..e5c504908 100644 --- a/src/lib/tls/tls_cbc/tls_cbc.cpp +++ b/src/lib/tls/tls_cbc/tls_cbc.cpp @@ -285,6 +285,81 @@ size_t TLS_CBC_HMAC_AEAD_Decryption::output_length(size_t) const return 0; } +/* +* This function performs additional compression calls in order +* to protect from the Lucky 13 attack. It adds new compression +* function calls over dummy data, by computing additianl HMACs. +* +* Background: +* - One SHA-1/SHA-256 compression is performed with 64 bytes of data. +* - HMAC adds an additional padding so that we have: +* - 0 - 55 bytes: 1 compression +* - 56 - 55+64 bytes: 2 compressions +* - 56+64 - 55+2*64 bytes: 3 compressions +* +* The implemented countermeasure: +* 1) computes max_comp: number of maximum compressions performed on the +* decrypted data +* 2) computes current_comp: number of compressions performed on the decrypted +* data, without padding +* 3) if current_comp != max_comp: It computes HMAC over dummy data so that +* max_comp compressions are performed. Otherwise, (max_comp-1). +* +* Note that the padding validation in Botan is always performed over +* min(plen,256) bytes, see the function check_tls_padding. This differs +* from the countermeasure described in the paper. +* +* Note that the padding length padlen does also count the last byte +* of the decrypted plaintext. This is different from the typical +* padding computation and different from the Lucky 13 paper. +* +* Remark: The attacker can still break indistinguishability of ciphertexts, in +* specific scenarios. For example, a ciphertext that decrypts to 288 bytes 0xFF +* results in one SHA-1 compression over the unpadded plaintext. A ciphertext +* that decrypts to 288 bytes 0x00 decrypts to 287 plaintext bytes and results in +* at least 4 SHA-1 compression executions. This would break our approach. +* However, this is only relevant in scenarios where the attacker can create +* ciphertexts with >68 valid padding bytes, and place the guessed secret next to +* the padding bytes (e.g., BEAST). Even then, he would be able to decrypt +* at most 16 plaintext bytes (due to the nature of CBC). +* +* TODO: This fix does not present a valid countermeasure for SHA-384. This +* hash function contains different compression function and thus different +* computations have to be performed. +* +* plen represents the length of the decrypted plaintext message P +* padlen represents the padding length +* +*/ +void TLS_CBC_HMAC_AEAD_Decryption::perform_additional_compressions(size_t plen, size_t padlen) + { + // number of maximum maced bytes + const uint16_t L1 = 13 + plen - tag_size(); + // number of current maced bytes (L1 - padlen) + // Here the Lucky 13 paper is different because the padlen length in the paper + // does not count the last message byte. + const uint16_t L2 = 13 + plen - padlen - tag_size(); + // From the paper: |compress|=ceil((L1-55)/64)-ceil((L2-55)/64) + // ceil((L1-55)/64) = floor((L1+8)/64) + const uint16_t max_comp = ((L1+8)/64); + const uint16_t current_comp = ((L2+8)/64); + + // If max_comp == current_comp, compute HMAC over dummy data as if there were + // (current_comp-1) compressions. Otherwise, compute HMAC over dummy data + // of full record length + const uint8_t equal_comp = CT::is_equal(max_comp, current_comp) & 0x01; + // the minimum number of bytes we compute the HMAC + const uint16_t min_mac = (L1 < 55) ? L1 : 55; + const uint16_t comp = (max_comp > 0) ? (max_comp-1) : 0; + const uint16_t to_mac = equal_comp * (min_mac + 64 * comp) + (equal_comp^1) * L1; + + std::unique_ptr dmac(Botan::MessageAuthenticationCode::create(mac().name())); + byte data[L1]; + dmac->update(data, to_mac); + std::vector mac_buf(tag_size()); + dmac->final(mac_buf); + } + void TLS_CBC_HMAC_AEAD_Decryption::finish(secure_vector& buffer, size_t offset) { update(buffer, offset); @@ -393,6 +468,7 @@ void TLS_CBC_HMAC_AEAD_Decryption::finish(secure_vector& buffer, size_t of } else { + perform_additional_compressions(record_len, pad_size); throw TLS_Exception(Alert::BAD_RECORD_MAC, "Message authentication failure"); } } diff --git a/src/lib/tls/tls_cbc/tls_cbc.h b/src/lib/tls/tls_cbc/tls_cbc.h index 90b54bb5a..846774998 100644 --- a/src/lib/tls/tls_cbc/tls_cbc.h +++ b/src/lib/tls/tls_cbc/tls_cbc.h @@ -159,6 +159,8 @@ class BOTAN_DLL TLS_CBC_HMAC_AEAD_Decryption final : public TLS_CBC_HMAC_AEAD_Mo private: void cbc_decrypt_record(byte record_contents[], size_t record_len); + + void perform_additional_compressions(size_t plen, size_t padlen); }; } -- cgit v1.2.3 From cbe0da5b1ebc9f9aa4f5d8d18ac717f674ac5fc3 Mon Sep 17 00:00:00 2001 From: Juraj Somorovsky Date: Sat, 22 Oct 2016 16:41:23 +0200 Subject: SHA384 countermeasure (not perfect, but makes the attack harder) --- src/lib/tls/tls_cbc/tls_cbc.cpp | 46 ++++++++++++++++++++++++----------------- 1 file changed, 27 insertions(+), 19 deletions(-) (limited to 'src/lib') diff --git a/src/lib/tls/tls_cbc/tls_cbc.cpp b/src/lib/tls/tls_cbc/tls_cbc.cpp index e5c504908..a623f39ec 100644 --- a/src/lib/tls/tls_cbc/tls_cbc.cpp +++ b/src/lib/tls/tls_cbc/tls_cbc.cpp @@ -298,20 +298,19 @@ size_t TLS_CBC_HMAC_AEAD_Decryption::output_length(size_t) const * - 56+64 - 55+2*64 bytes: 3 compressions * * The implemented countermeasure: -* 1) computes max_comp: number of maximum compressions performed on the +* 1) computes max_compressions: number of maximum compressions performed on the * decrypted data -* 2) computes current_comp: number of compressions performed on the decrypted -* data, without padding -* 3) if current_comp != max_comp: It computes HMAC over dummy data so that -* max_comp compressions are performed. Otherwise, (max_comp-1). +* 2) computes current_compressions: number of compressions performed on the +* decrypted data, without padding +* 3) if current_compressions != max_compressions: It computes HMAC over dummy +* data so that max_comp compressions are performed. Otherwise, (max_comp-1). * * Note that the padding validation in Botan is always performed over * min(plen,256) bytes, see the function check_tls_padding. This differs * from the countermeasure described in the paper. * * Note that the padding length padlen does also count the last byte -* of the decrypted plaintext. This is different from the typical -* padding computation and different from the Lucky 13 paper. +* of the decrypted plaintext. This is different from the Lucky 13 paper. * * Remark: The attacker can still break indistinguishability of ciphertexts, in * specific scenarios. For example, a ciphertext that decrypts to 288 bytes 0xFF @@ -323,35 +322,44 @@ size_t TLS_CBC_HMAC_AEAD_Decryption::output_length(size_t) const * the padding bytes (e.g., BEAST). Even then, he would be able to decrypt * at most 16 plaintext bytes (due to the nature of CBC). * -* TODO: This fix does not present a valid countermeasure for SHA-384. This -* hash function contains different compression function and thus different -* computations have to be performed. -* * plen represents the length of the decrypted plaintext message P * padlen represents the padding length * */ void TLS_CBC_HMAC_AEAD_Decryption::perform_additional_compressions(size_t plen, size_t padlen) { + uint16_t block_size; + uint16_t max_bytes_in_first_block; + if(mac().name() == "HMAC(SHA-384)") + { + block_size = 128; + max_bytes_in_first_block = 111; + } + else + { + block_size = 64; + max_bytes_in_first_block = 55; + } // number of maximum maced bytes const uint16_t L1 = 13 + plen - tag_size(); // number of current maced bytes (L1 - padlen) // Here the Lucky 13 paper is different because the padlen length in the paper // does not count the last message byte. const uint16_t L2 = 13 + plen - padlen - tag_size(); - // From the paper: |compress|=ceil((L1-55)/64)-ceil((L2-55)/64) - // ceil((L1-55)/64) = floor((L1+8)/64) - const uint16_t max_comp = ((L1+8)/64); - const uint16_t current_comp = ((L2+8)/64); + // From the paper, for SHA-256/SHA-1 compute: ceil((L1-55)/64) and ceil((L2-55)/64) + // ceil((L1-55)/64) = floor((L1+64-1-55)/64) + // Here we compute number of compressions for SHA-* in general + const uint16_t max_compresssions = ( (L1 + block_size - 1 - max_bytes_in_first_block) / block_size); + const uint16_t current_compressions = ((L2 + block_size - 1 - max_bytes_in_first_block) / block_size); // If max_comp == current_comp, compute HMAC over dummy data as if there were // (current_comp-1) compressions. Otherwise, compute HMAC over dummy data // of full record length - const uint8_t equal_comp = CT::is_equal(max_comp, current_comp) & 0x01; + const uint8_t equal_comp = CT::is_equal(max_compresssions, current_compressions) & 0x01; // the minimum number of bytes we compute the HMAC - const uint16_t min_mac = (L1 < 55) ? L1 : 55; - const uint16_t comp = (max_comp > 0) ? (max_comp-1) : 0; - const uint16_t to_mac = equal_comp * (min_mac + 64 * comp) + (equal_comp^1) * L1; + const uint16_t min_mac = (L1 < max_bytes_in_first_block) ? L1 : max_bytes_in_first_block; + const uint16_t comp = (max_compresssions > 0) ? (max_compresssions-1) : 0; + const uint16_t to_mac = equal_comp * (min_mac + block_size * comp) + (equal_comp^1) * L1; std::unique_ptr dmac(Botan::MessageAuthenticationCode::create(mac().name())); byte data[L1]; -- cgit v1.2.3 From 6d04d15171af730093230bd88dbd7c7e8e7f9334 Mon Sep 17 00:00:00 2001 From: Juraj Somorovsky Date: Sun, 23 Oct 2016 15:13:07 +0200 Subject: Final changes, now using the countermeasure from the Lucky 13 paper again (or a countermeasure that is very similar to it). Timing differences in the test suite show at most 120 clock cycle difference (SHA-1/256/384). --- src/lib/tls/tls_cbc/tls_cbc.cpp | 68 +++++++++++++++++++---------------------- 1 file changed, 32 insertions(+), 36 deletions(-) (limited to 'src/lib') diff --git a/src/lib/tls/tls_cbc/tls_cbc.cpp b/src/lib/tls/tls_cbc/tls_cbc.cpp index a623f39ec..fd020ac73 100644 --- a/src/lib/tls/tls_cbc/tls_cbc.cpp +++ b/src/lib/tls/tls_cbc/tls_cbc.cpp @@ -288,22 +288,30 @@ size_t TLS_CBC_HMAC_AEAD_Decryption::output_length(size_t) const /* * This function performs additional compression calls in order * to protect from the Lucky 13 attack. It adds new compression -* function calls over dummy data, by computing additianl HMACs. +* function calls over dummy data, by computing additional HMAC updates. +* +* The countermeasure was described (in a similar way) in the Lucky 13 paper. * * Background: * - One SHA-1/SHA-256 compression is performed with 64 bytes of data. -* - HMAC adds an additional padding so that we have: +* - HMAC adds 8 byte length field and padding (at least 1 byte) so that we have: * - 0 - 55 bytes: 1 compression * - 56 - 55+64 bytes: 2 compressions -* - 56+64 - 55+2*64 bytes: 3 compressions +* - 56+64 - 55+2*64 bytes: 3 compressions ... +* - For SHA-384, this works similarly, but we have 128 byte blocks and 16 byte +* long length field. This results in: +* - 0 - 111 bytes: 1 compression +* - 112 - 111+128 bytes: 2 compressions ... * -* The implemented countermeasure: -* 1) computes max_compressions: number of maximum compressions performed on the -* decrypted data -* 2) computes current_compressions: number of compressions performed on the -* decrypted data, without padding -* 3) if current_compressions != max_compressions: It computes HMAC over dummy -* data so that max_comp compressions are performed. Otherwise, (max_comp-1). +* The implemented countermeasure works as follows: +* 1) It computes max_compressions: number of maximum compressions performed on +* the decrypted data +* 2) It computes current_compressions: number of compressions performed on the +* decrypted data, after padding has been removed +* 3) If current_compressions != max_compressions: It invokes an HMAC update +* over dummy data so that (max_compressions - current_compressions) +* compressions are performed. Otherwise, it invokes an HMAC update so that +* no compressions are performed. * * Note that the padding validation in Botan is always performed over * min(plen,256) bytes, see the function check_tls_padding. This differs @@ -312,15 +320,8 @@ size_t TLS_CBC_HMAC_AEAD_Decryption::output_length(size_t) const * Note that the padding length padlen does also count the last byte * of the decrypted plaintext. This is different from the Lucky 13 paper. * -* Remark: The attacker can still break indistinguishability of ciphertexts, in -* specific scenarios. For example, a ciphertext that decrypts to 288 bytes 0xFF -* results in one SHA-1 compression over the unpadded plaintext. A ciphertext -* that decrypts to 288 bytes 0x00 decrypts to 287 plaintext bytes and results in -* at least 4 SHA-1 compression executions. This would break our approach. -* However, this is only relevant in scenarios where the attacker can create -* ciphertexts with >68 valid padding bytes, and place the guessed secret next to -* the padding bytes (e.g., BEAST). Even then, he would be able to decrypt -* at most 16 plaintext bytes (due to the nature of CBC). +* This countermeasure leaves a difference of about 100 clock cycles (in +* comparison to >1000 clock cycles observed without it). * * plen represents the length of the decrypted plaintext message P * padlen represents the padding length @@ -340,9 +341,9 @@ void TLS_CBC_HMAC_AEAD_Decryption::perform_additional_compressions(size_t plen, block_size = 64; max_bytes_in_first_block = 55; } - // number of maximum maced bytes + // number of maximum MACed bytes const uint16_t L1 = 13 + plen - tag_size(); - // number of current maced bytes (L1 - padlen) + // number of current MACed bytes (L1 - padlen) // Here the Lucky 13 paper is different because the padlen length in the paper // does not count the last message byte. const uint16_t L2 = 13 + plen - padlen - tag_size(); @@ -351,21 +352,16 @@ void TLS_CBC_HMAC_AEAD_Decryption::perform_additional_compressions(size_t plen, // Here we compute number of compressions for SHA-* in general const uint16_t max_compresssions = ( (L1 + block_size - 1 - max_bytes_in_first_block) / block_size); const uint16_t current_compressions = ((L2 + block_size - 1 - max_bytes_in_first_block) / block_size); - - // If max_comp == current_comp, compute HMAC over dummy data as if there were - // (current_comp-1) compressions. Otherwise, compute HMAC over dummy data - // of full record length - const uint8_t equal_comp = CT::is_equal(max_compresssions, current_compressions) & 0x01; - // the minimum number of bytes we compute the HMAC - const uint16_t min_mac = (L1 < max_bytes_in_first_block) ? L1 : max_bytes_in_first_block; - const uint16_t comp = (max_compresssions > 0) ? (max_compresssions-1) : 0; - const uint16_t to_mac = equal_comp * (min_mac + block_size * comp) + (equal_comp^1) * L1; - - std::unique_ptr dmac(Botan::MessageAuthenticationCode::create(mac().name())); - byte data[L1]; - dmac->update(data, to_mac); - std::vector mac_buf(tag_size()); - dmac->final(mac_buf); + // number of additional compressions we have to perform + const uint16_t add_compressions = max_compresssions - current_compressions; + const uint8_t equal = CT::is_equal(max_compresssions, current_compressions) & 0x01; + // We compute the data length we need to achieve the number of compressions. + // If there are no compressions, we just add 55/111 dummy bytes so that no + // compression is performed. + const uint16_t data_len = block_size * add_compressions + equal * max_bytes_in_first_block; + secure_vector data(data_len); + mac().update(unlock(data)); + // we do not need to clear the MAC since the connection is broken anyway } void TLS_CBC_HMAC_AEAD_Decryption::finish(secure_vector& buffer, size_t offset) -- cgit v1.2.3