Cryptopp: Rijndael Base::UncheckedSetKey and out-of-bounds read on rcLE

[Blacktempel]

I've recently encountered some kind of undefined behaviour and asked on stackoverflow and later on the mailing list after figuring out what was wrong. (Using Version 5.6.3 from the website)

Debugging simultaneously with two Visual Studios (2015 - SP3) through the same solution using the same keys & data with different programs it showed that the values show a first difference at this line:

while (true)
{
    rk[keylen/4] = rk[0] ^ _mm_extract_epi32(_mm_aeskeygenassist_si128(temp, 0), 3) ^ *(rc++); //<--- Here

Curious what is going on there, I checked all values in the line with the debugger, and saw that rc is apparently out of bounds.

static const word32 rcLE[] = {
    0x01, 0x02, 0x04, 0x08,
    0x10, 0x20, 0x40, 0x80,
    0x1B, 0x36, /* for 128-bit blocks, Rijndael never uses more than 10 rcon values */
};
const word32 *rc = rcLE;

Adding a counter to the while (true) loop shows that it is being accessed 15 times, while the in-place array only has 10 values.
Taking into consideration that BLOCKSIZE of Rijndael is 16-byte and KEYLENGTH_MULTIPLE is 8-byte, and my data is padded correctly, else it would throw an exception, it should work.

I've also re-checked it with other used algorithms (Blowfish, Twofish, Serpent) and they seemed to work as intended. - Compared hashes of decrypted data with original.

I can also only reproduce this behaviour in one program.
In the other programs or even in a new test project using directly CryptoPP, it still does access out-of-bounds. It still loops 15 times, but apparently some kind of... lets call them "magic constant values"... in the memory after it are being accessed and therefore it looks like it is working as intended.

[Blacktempel]

I was able to fix this issue by adding more of the Rcon values.

[noloader]

Thanks @Blacktempel.

I'd like to get this isolated with a test case before applying a fix. Can you duplicate the issue with either cryptest.exe v or cryptest.exe tv all? If not, is there a minimal test case available somewhere?

I'll also need to study this code some more due to this comment:

// Rijndael never uses more than 10 rcon values

That seems to imply 10-round AES, which is AES-128. 12-round AES is AES-192; while 14-round AES is AES-256. So we will need to understand why only AES-128 is represented in the source code. Possibly related: How to use RCON In Key Expansion of 128 Bit Advanced Encryption Standard on the Crypto.SE.

I'll also grind through history to see if I managed to delete some of the rcon values. We had a drag/drop go bad to/from a VM, and it corrupted a bunch of files a while back. The drag/drop caused us to re-release Crypto++ 5.6.3.

---

Visual Studio x86_64 also has an unusual work around at rijndael.cpp:100. After the Visual Studio 2010 project file conversions, it was like a symbol went missing. It was very unusual.

# if defined(CRYPTOPP_X64_MASM_AVAILABLE)
// Unused; avoids linker error on Microsoft X64 non-AESNI platforms
namespace rdtable {CRYPTOPP_ALIGN_DATA(16) word64 Te[256+2];}
# endif

My first thought was the name mangling algorithm got nudged in the MSC toolchain. But dumpbin did not work on the rijndael.obj object file, so I could never ascertain the exact issue. Here's the issue documented on Stack Overflow: How to locate and display symbols when using /GL?

---

Related, AES (and SHA) is some of the hairiest code in the library. Its not readily apparent, but there's at least 6 implementations intertwined, and they include straight C/C++, SSE2 optimized, AES-NI optimized, GCC Assembler, Microsoft Assembler (MASM) and compressed tables (from Bernstein's Cache-timing attacks).

I don't like to touch AES source code due to fear of breaking something. Its the reason I have not cut-in the implementation for x86 Padlock or ARMv8 Crypto extensions. Things have gotten better now that we have a test script that automates testing, but we may be missing the test case (i.e., the reason you stumbled upon it).

[noloader]

Also see discussion at Pull Request 253: Fix Rijndael Base::UncheckedSetKey and out-of-bounds read on the mailing list and Pull Request 253: Fix Rijndael Base::UncheckedSetKey and out-of-bounds read.

[Blacktempel]

I can reproduce it IF the key-length is 8, which is valid according to the call to AssertValidKeyLength(keylen); and KEYLENGTH_MULTIPLE being 8.

So running the tests won't show it, as the tests only use 16, 24 and 32 byte keys.
Manually "waiting" with a breakpoint and setting the keylen to 8 will show this behaviour without modification to tests.
void Rijndael::Base::UncheckedSetKey

[noloader]

I can reproduce it IF the key-length is 8, which is valid according to the call to AssertValidKeyLength(keylen); and KEYLENGTH_MULTIPLE being 8.

8 is not a valid key length for AES. As you noted, valid AES key lengths are 16, 24 and 32.

I'll look into why AssertValidKeyLength is not throwing like it should. UncheckedSetKey will _not_ throw by design. But it's callers, like SetKey and SetKeyWithIV, should trigger the throw.

[Blacktempel]

I just tested it and it does not return 24 as valid key length, this is why I've deleted my previous comment.
16 and 32 are then the only valid key lengths.

I am calling GetValidKeyLength, pad it with some data if necessary and then SetKey.

[noloader]

@Blacktempel,

I'm happy to add some diagnostics now. What do you think about the following?

$ git diff rijndael.cpp > rijndael.cpp.diff
$ cat rijndael.cpp.diff
diff --git a/rijndael.cpp b/rijndael.cpp
index 0ba1a19..b927e77 100644
--- a/rijndael.cpp
+++ b/rijndael.cpp
@@ -238,9 +238,11 @@ void Rijndael::Base::UncheckedSetKey(const byte *userKey, unsigned int keylen, c
        __m128i temp = _mm_loadu_si128((__m128i *)(void *)(userKey+keylen-16));
        memcpy(rk, userKey, keylen);

+       size_t idx = 0;
        while (true)
        {
-           rk[keylen/4] = rk[0] ^ _mm_extract_epi32(_mm_aeskeygenassist_si128(temp, 0), 3) ^ *(rc++);
+           assert(idx < COUNTOF(rcLE));
+           rk[keylen/4] = rk[0] ^ _mm_extract_epi32(_mm_aeskeygenassist_si128(temp, 0), 3) ^ *(rc+idx++);
            rk[keylen/4+1] = rk[1] ^ rk[keylen/4];
            rk[keylen/4+2] = rk[2] ^ rk[keylen/4+1];
            rk[keylen/4+3] = rk[3] ^ rk[keylen/4+2];

I have a lot more latitude in adding diagnostics to debug builds. The criteria for change is effectively anything that improves debugging and diagnostics.

Release build changes have to be more discriminating. Do no harm is the first rule for the production code, and I'm not sure this change meets it.

[Blacktempel]

Looks good, but not necessary anymore IMO.
The problem is somewhere else:

Simply removing the macro from StaticGetValidKeyLength fixes the issue.

Not sure why the preprocessor checks a constant value, a define would be valid - at least for VS. Not sure if another compiler allows the preprocessor to check a constant int.

[Blacktempel]

Checked it with other algorithms, I've not seen any issues, will re-run the tests in a minute...

[Blacktempel]

Tests complete. Total tests = 4111. Failed tests = 0.

[noloader]

Not sure why the preprocessor checks a constant value, a define would be valid - at least for VS. Not sure if another compiler allows the preprocessor to check a constant int.

I'm guessing that's a bug introduced by me when attempting to squash an analysis tool finding. Probably what is happening is MIN_KEYLENGTH is not defined in the preprocessor, so it gets a value of 0 by default. Later, it acquires its actual value through CRYPTOPP_CONSTANT.

It seems I violated the "do no harm" rule. Sorry about that.

[noloader]

@Blacktempel,

By the way... I spun up a dev-branch that's attempting to achieve better code generation. Ultimately, I want to reduce Clang and VC++ self test running times by 20% to 30%. I hope the reductions occur through use of more template parameters in certain areas (like the rotate amount in a rotate), and use of C++11 constexpr. Also see contexpr dev branch and CRYPTOPP_CONSTEXPR.

If you see an opportunity, like in secblock.h, then grab it. I'm game for anything that improves running time without doing any harm:

//! \brief Returns the maximum number of elements the allocator can provide
//! \returns the maximum number of elements the allocator can provide
//! \details Internally, preprocessor macros are used rather than std::numeric_limits
//!   because the latter is \a not a \a constexpr. Some compilers, like Clang, do not
//!   optimize it well under all circumstances. Compilers like GCC, ICC and MSVC appear
//!   to optimize it well in either form.
CRYPTOPP_CONSTEXPR size_type max_size() const {return (SIZE_MAX/sizeof(T));}

Its kind of sad we have to tell compilers like Clang and VC++ a value won't change under the laws of the physical universe as we understand them, so its OK to treat a value as a constexpr. But it is what it is...

[DevJPM]

OK, I've read through this thread and the fix looks simple:

1. Fix the static function used as a helper for keylength checks
2. Optionally add more (all?) of the RCon values to the implementation

Will the first one be fixed into master instantly (this would be preferable?) or will we wait until the constexpr branch gets merged or will a new branch be created just for this fix, so we can run the test script over things?

[mouse07410]

It was hoped some time ago that the library would also support Rijndael, in addition to AES - the difference being the ability to support variable block size, as some applications (like Whirlpool) require a 256-bit block cipher.

To support those, wouldn't PR #253 be beneficial?

[Blacktempel]

@mouse07410 Adding more Rcon values is optional, of course this will not affect running systems / code as it only adds values to it, it does not modify existing algorithms.
Having a variable block size would require modifying more than that and leave it a custom implementation IMO.
@noloader What's your opinion on #253 ?

@DevJPM See #254

[noloader]

@DevJPM ,

Will the first one be fixed into master instantly (this would be preferable?)

Yes, its already been merged. I wanted to give @Crayon2000 some time to ensure I did not do any more damage to him or Borland. Crayon came back with test results earlier tonight, and the patch was merged about 10 minutes later.

I also tested @Blacktempel changes yesterday and early this morning under a number of platforms (including Android, Linux, OS X, iOS, i686, x86_64, ARM-32, Aarch64 and MIPS) and compilers (Clang, GCC, ICC).

I have not done a thorough round of Windows testing yet. I'm guessing it will be OK since we effectively reverted to pre-break status, and Windows was OK back then.

The last thing I need to do is add some test cases to ensure we can smoke this sort of thing out in the future. I will probably test that on the constexpr branch and megre it in a few days.

[noloader]

@DevJPM, @mouse07410 ,

Optionally add more (all?) of the RCon values to the implementation

No action has been taken on Rcon values at the moment.

Maybe we should spin up another bug report as a feature request for Rijndael-192 block size and Rijndael-256 block size.

[noloader]

So I got to add some tests which I believe would have caught the issue. See Commit 5057991a31bae69d.

RijndaelEncryption and RijndaelDecryption are working as expected:

RijndaelEncryption enc;
pass1 = enc.StaticGetValidKeyLength(8) == 16 && pass1;
pass1 = enc.StaticGetValidKeyLength(16) == 16 && pass1;
pass1 = enc.StaticGetValidKeyLength(24) == 24 && pass1;
pass1 = enc.StaticGetValidKeyLength(32) == 32 && pass1;
pass1 = enc.StaticGetValidKeyLength(64) == 32 && pass1;
pass1 = enc.StaticGetValidKeyLength(128) == 32 && pass1;

TwofishEncryption and TwofishDecryption are _not_ returning expected values. The unexpected results are commented out:

TwofishEncryption enc;
// pass1 = enc.StaticGetValidKeyLength(8) == 16 && pass1;
pass1 = enc.StaticGetValidKeyLength(16) == 16 && pass1;
pass1 = enc.StaticGetValidKeyLength(24) == 24 && pass1;
pass1 = enc.StaticGetValidKeyLength(32) == 32 && pass1;
// pass1 = enc.StaticGetValidKeyLength(64) == 32 && pass1;
// pass1 = enc.StaticGetValidKeyLength(128) == 32 && pass1;

It looks like the issue is with VariableKeyLength:

$ cat twofish.h.diff 
diff --git a/twofish.h b/twofish.h
index 5ebc244..f6d75ca 100644
--- a/twofish.h
+++ b/twofish.h
@@ -13,7 +13,7 @@ NAMESPACE_BEGIN(CryptoPP)

 //! \class Twofish_Info
 //! \brief Twofish block cipher information
-struct Twofish_Info : public FixedBlockSize<16>, public VariableKeyLength<16, 0, 32>, FixedRounds<16>
+struct Twofish_Info : public FixedBlockSize<16>, public VariableKeyLength<16, 16, 32, 8>, FixedRounds<16>
 {
    static const char *StaticAlgorithmName() {return "Twofish";}
 };

The same issue applies to CAST-256, Serpent and SHARK as well.

I thought this was going to be a quick due-diligence cut-in, but it looks like there may be more to things here...

[noloader]

I believe we visited most of the block ciphers and added a test for them.

I cross-checked into Coverage, and it shows we are testing 98% of secblock.h, and 91% of seckey.h. You can check the coverage with make coverage and then navigate to TestCoverage/index.html. (TestCoverage is created next to TestData and TestVectors):

Closing this ticket.

[noloader]

We have called for testers. Also see VS2015 and MinGW testing of constexpr dev-branch on the mailing list.

[mouse07410]

Maybe we should spin up another bug report as a feature request for Rijndael-192 block size and Rijndael-256 block size.

Will do that.

As a first step, this would require separating AES and Rijndael (much like we separate SHA3 and Keccak).