Security Vulnerability in PKCS7

To whom it may concern,

I am writing on behalf of a research team at the Department of Computer Science, Stony Brook University, regarding a security vulnerability related to padding scheme in latest version of gnutls. (https://github.com/gnutls/gnutls/blob/master/lib/crypto-api.c#L532)

We believe this has the potential to be exploited by a remote attack. If a developer uses pkcs7 padding scheme in AES-CBC settings in padding removal, an adversary can exploit it to retrieve information for recovering the value of last byte in every block even if it does not explicitly return invalid padding. Below we attached the function for your reference:

int gnutls_cipher_decrypt3(gnutls_cipher_hd_t handle, const void *ctext,
                size_t ctext_len, void *ptext, size_t *ptext_len,
                unsigned flags)
{
     api_cipher_hd_st *h = handle;
     int ret;

     ret = gnutls_cipher_decrypt2(handle, ctext, ctext_len, ptext,
                      *ptext_len);
     if (ret < 0) {
         return ret;
     }

     if (_gnutls_cipher_type(h->ctx_enc.e) == CIPHER_BLOCK &&
         (flags & GNUTLS_CIPHER_PADDING_PKCS7)) {
         uint8_t *p = ptext;
         uint8_t padding = p[*ptext_len - 1];
         if (!padding ||
             padding > _gnutls_cipher_get_block_size(h->ctx_enc.e)) {
             return gnutls_assert_val(GNUTLS_E_DECRYPTION_FAILED);
         }
         /* Check that the prior bytes are all PADDING */
         for (size_t i = *ptext_len - padding; i < *ptext_len; i++) {
             if (padding != p[*ptext_len - 1]) {
                 return gnutls_assert_val(
                     GNUTLS_E_DECRYPTION_FAILED);
             }
         }
         *ptext_len -= padding;
     }

     return 0;
}

The leakage is in the third if-block. Assume a ciphertext with a valid padding is supplied to the function, an adversary can manipulate the last byte to recover the padding. At this stage, if the last byte of a block is out of range in the if-block, then it will create an early return in this function. Otherwise, it will return at a later time due to the for-loop check afterwards. We illustrate how an adversary can recover the padding below.

Assume the given ciphertext is 32 bytes long with C = (IV, c_1), with block size = 16. The adversary first generates two ciphertexts: (1) flipping the least significant 4th and 5th bit in IV[-1], then XOR with IV[-1], and (2) flipping the least significant 4th, 5th and 6th bit in IV[-1], then XOR with IV[-1]. Then the adversary can feed both ciphertexts into the function. If the function returns valid for both crafted ciphertexts, the only possible padding byte will be 16. Otherwise, the value of padding byte will be on 1 to 15. To find the exact padding, the adversary can brute force the correct padding by XOR IV[-1] with flipped 4th bit and range 1 to 15 in IV[-1]. The adversary only needs to query at most 17 times to retrieve the correct padding, under the assumption that the ciphertext has correct padding. Moreover, even the assumption does not hold, the adversary can still recover the last byte of a block using few more queries.

Moreover, the PKCS7 for-loop on checking whether the padding bytes are equal will suffer from a padding oracle attack. An attacker can potentially reveal the plaintext based on the timing difference.

We have attached a PoC for the first vulnerability for your reference. An adversary is able to compute back the padding byte given a ciphertext with valid padding. To mitigate the issue, we suggest to use a constant time boolean function to replace the if-block and constant time implementation on the for-loop, so that the adversary is unable to get a clear signal to deduce the last byte of every block.

Please feel free to let us know if you have any further questions or comments regarding this matter. Thank you for your time and attention. We look forward to your reply.

Yours faithfully, Doria Tang PhD student Department of Computer Science Stony Brook University

poc.py