Fix GCM counter increment

GCM is defined as having a 32-bit counter, but CTR_BE incremented the
counter across the entire block. This caused incorrect results if
a very large message (2**39 bits) was processed, or if the GHASH
derived nonce ended up having a counter field near to 2**32

Thanks to Juraj Somorovsky for the bug report and repro.

5 files changed, 54 insertions, 4 deletions

diff --git a/doc/news.rst b/doc/news.rst
index 2a9fe53a6..0087782d3 100644
--- a/doc/news.rst
+++ b/doc/news.rst
@@ -9,6 +9,17 @@ Version 1.11.30, Not Yet Released
   a MAC failure. Records like this are used by OpenSSL in TLS 1.0
   connections in order to randomize the IV.
 
+* A bug in GCM caused incorrect results if the 32-bit counter field
+  overflowed. With a 96-bit nonce, this could only occur if 2**32
+  128-bit blocks were encrypted. This actually exceeds the maximum
+  allowable length of a GCM plaintext.
+
+  However if a GCM nonce of any other size is used, the bug triggers
+  randomly, with increasing probability on longer messages. For
+  instance when encrypting 256 MiB of data under a random 128 bit
+  nonce, an incorrect result would be produced about 1/256 of the
+  time. With 1 MiB texts, the probability of error reduced to 1/65536.
+
 * The Transform and Keyed_Transform interfaces has been removed. The
   two concrete implementations of these interfaces were Cipher_Mode
   and the Compressor_tkk. The Cipher_Mode interface remains unchanged
@@ -37,7 +48,7 @@ Version 1.11.30, Not Yet Released
 
 * X509_CRL previously had an option to cause it to ignore unknown
   critical extensions. This has been removed.
- 
+
 * Added support for ChaCha stream cipher with 12 rounds.
 
 * Add ECGDSA signature algorithm (GH #479)
diff --git a/src/lib/modes/aead/gcm/gcm.cpp b/src/lib/modes/aead/gcm/gcm.cpp
index 1dc5efe4f..e23551cb4 100644
--- a/src/lib/modes/aead/gcm/gcm.cpp
+++ b/src/lib/modes/aead/gcm/gcm.cpp
@@ -168,7 +168,7 @@ GCM_Mode::GCM_Mode(BlockCipher* cipher, size_t tag_size) :
 
    m_ghash.reset(new GHASH);
 
-   m_ctr.reset(new CTR_BE(cipher)); // CTR_BE takes ownership of cipher
+   m_ctr.reset(new CTR_BE(cipher, 4)); // CTR_BE takes ownership of cipher
 
    if(m_tag_size != 8 && m_tag_size != 16)
       throw Invalid_Argument(name() + ": Bad tag size " + std::to_string(m_tag_size));
diff --git a/src/lib/stream/ctr/ctr.cpp b/src/lib/stream/ctr/ctr.cpp
index 88c7a8d8e..f5301c099 100644
--- a/src/lib/stream/ctr/ctr.cpp
+++ b/src/lib/stream/ctr/ctr.cpp
@@ -23,10 +23,23 @@ CTR_BE::CTR_BE(BlockCipher* ciph) :
    m_cipher(ciph),
    m_counter(m_cipher->parallel_bytes()),
    m_pad(m_counter.size()),
+   m_ctr_size(m_cipher->block_size()),
    m_pad_pos(0)
    {
    }
 
+CTR_BE::CTR_BE(BlockCipher* cipher, size_t ctr_size) :
+   m_cipher(cipher),
+   m_counter(m_cipher->parallel_bytes()),
+   m_pad(m_counter.size()),
+   m_ctr_size(ctr_size),
+   m_pad_pos(0)
+   {
+   //BOTAN_CHECK_ARG(m_ctr_size > 0 && m_ctr_size <= cipher->block_size(), "Invalid CTR size");
+   if(m_ctr_size == 0 || m_ctr_size > m_cipher->block_size())
+      throw Invalid_Argument("Invalid CTR-BE counter size");
+   }
+
 void CTR_BE::clear()
    {
    m_cipher->clear();
@@ -79,7 +92,7 @@ void CTR_BE::set_iv(const byte iv[], size_t iv_len)
       {
       buffer_insert(m_counter, i*bs, &m_counter[(i-1)*bs], bs);
 
-      for(size_t j = 0; j != bs; ++j)
+      for(size_t j = 0; j != m_ctr_size; ++j)
          if(++m_counter[i*bs + (bs - 1 - j)])
             break;
       }
@@ -99,7 +112,7 @@ void CTR_BE::increment_counter()
    for(size_t i = 0; i != n_wide; ++i)
       {
       uint16_t carry = static_cast<uint16_t>(n_wide);
-      for(size_t j = 0; carry && j != bs; ++j)
+      for(size_t j = 0; carry && j != m_ctr_size; ++j)
          {
          const size_t off = i*bs + (bs-1-j);
          const uint16_t cnt = static_cast<uint16_t>(m_counter[off]) + carry;
diff --git a/src/lib/stream/ctr/ctr.h b/src/lib/stream/ctr/ctr.h
index 8e931605c..003297b92 100644
--- a/src/lib/stream/ctr/ctr.h
+++ b/src/lib/stream/ctr/ctr.h
@@ -44,12 +44,15 @@ class BOTAN_DLL CTR_BE final : public StreamCipher
       * @param cipher the underlying block cipher to use
       */
       explicit CTR_BE(BlockCipher* cipher);
+
+      CTR_BE(BlockCipher* cipher, size_t ctr_size);
    private:
       void key_schedule(const byte key[], size_t key_len) override;
       void increment_counter();
 
       std::unique_ptr<BlockCipher> m_cipher;
       secure_vector<byte> m_counter, m_pad;
+      size_t m_ctr_size;
       size_t m_pad_pos;
    };
 
diff --git a/src/tests/data/aead/gcm.vec b/src/tests/data/aead/gcm.vec
index 21bc3a53e..516e828ec 100644
--- a/src/tests/data/aead/gcm.vec
+++ b/src/tests/data/aead/gcm.vec
@@ -38,6 +38,29 @@ In     = D9313225F88406E5A55909C5AFF5269A86A7A9531534F7DA2E4C303D8A318A721C3C0C9
 AD     = FEEDFACEDEADBEEFFEEDFACEDEADBEEFABADDAD2
 Out    = 8CE24998625615B603A033ACA13FB894BE9112A5C3A211A8BA262A3CCA7E2CA701E4A9A4FBA43C90CCDCB281D48C7C6FD62875D2ACA417034C34AEE5619CC5AEFFFE0BFA462AF43C1699D050
 
+# GCM vectors generated by OpenSSL via Python cryptography
+#
+# These GCM nonces are not 96 bits and so are hashed with GHASH to
+# produce the counter value. For these inputs the CTR value is
+# very near 2^32, which exposed a bug in GCM when the counter overflowed
+
+Key    = 00000000000000000000000000000000
+Nonce  = 0AAC82F3E53C2756034F7BD5827C9EDD
+In     = 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+Out    = 38C21B6430D9A3E4BC6749405765653AE91051E96CE0D076141DD7B515EC150FDB8A65EE988D206C9F64874664CDBF61257FFAE521B9A5EB5B35E3745F4232025B269A6CD7DCFE19153ECF7341CE2C6A6A87F95F2109841350DA3D24EEED4E4E32D2BED880737670FFE8ED76DB890FD72A0076300E50914984A777C9F2BC843977396C602B24E7A045F04D15CD2EAC01AD8808064CFE5A2DC1AE9FFFA4BF0A6F0C07668097DEEB9C5CA5EC1F9A52F96A403B73FEA2DBBF44473D355553EE7FB1B4D6630777DAF67804BE213089B9F78652CE970C582FD813F87FF0ECBACCE1CA46247E20D09F3E0B4EF6BFCD13244C6877F25E6646252CAD6EB7DBBA3476AAAC83BC3285FF70B50D6CDEDC8E5921944A
+
+Key    = 00000000000000000000000000000000
+Nonce  = 63ADFF969337DB7AAA3D862A8A827558
+In     = 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+Out    = E7813D2279516D5EE54E03371B0192FE2B66EF4BF3C7F741D2B8E1809CA5C1805908ADEFE6C5884736DF98B7EBCB08110B58C384E4A2FF25644CDFEAA2104FA3B33F00B689319EF7F09B2F066AEC96DC
+
+Key    = 00000000000000000000000000000000
+Nonce  = E60108DFED8198FB286E0A77E699DA7B
+In     = 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+Out    = A833DCC2EC04BEF5ED9E7E7FB08D61244CD795C21FEE194E7AAF7D9BD66B324F39FFC46DB5A7B9E1D6703F95290027DE6AC274CAE11C632F16261B71CE97EEA6CBE8A82B4F55F5A8B5CE1B268A7B35D8
+
+
+
 [AES-192/GCM]
 # Nist | Test Case 7
 Key    = 000000000000000000000000000000000000000000000000