Buffer Overflow in Integer.cpp

[Tony Stead]

Hello,

I have been using the Integer class for some big number operations and seem to have found a buffer overflow in at least the Integer::And routine, I have not yet inspected any more..

Extract from integer.cpp 

// This is a bit operation. We set sign to POSITIVE, so there's no need to
// worry about negative zero. Also see http://stackoverflow.com/q/11644362.
Integer Integer::And(const Integer& t) const
{
if (this == &t)
{
return AbsoluteValue();
}
else if (reg.size() >= t.reg.size())
{
Integer result(t);
AndWords(result.reg, reg, t.reg.size());

result.sign = POSITIVE;
return result;
}
else // reg.size() < t.reg.size()
{
Integer result(*this);
AndWords(result.reg, t.reg, reg.size());

result.sign = POSITIVE;
return result;
}
}

The issue is casued in the temporary result variable.  When result copies t or this in its constructor, it calculates the minimum size required to fit the current number in t or this.  If the top order bits of t or this have gone zero it will allocate less bytes than the size of t or this.  However the following AndWords routine performs a copy using the size of the original number, either t or this.  

Changing the value to result.reg.size() appears to fix the issue at least for my use case. 

Best Regards,

Tony. 

[Tony Stead]

Taking even a tiny amount of time to look beneath it looks like it may be a potential problem with a lot of the routines in integer.cpp.

[Jeffrey Walton]

Thanks Tony.

Do you have a reproducer? I'd like to look at it.

We have test cases setup and they are run under the sanitizers. I
don't recall seeing a finding. We might be missing a test case for it,
however.

Jeff

[Jeffrey Walton]

On Fri, Oct 8, 2021 at 12:02 AM Jeffrey Walton <nolo...@gmail.com> wrote:
>
> On Thu, Oct 7, 2021 at 5:11 AM Tony Stead <ths...@gmail.com> wrote:
> >
> > I have been using the Integer class for some big number operations and seem to have found a buffer overflow in at least the Integer::And routine, I have not yet inspected any more..
> >

> > ...

> > The issue is casued in the temporary result variable. When result copies t or this in its constructor, it calculates the minimum size required to fit the current number in t or this. If the top order bits of t or this have gone zero it will allocate less bytes than the size of t or this. However the following AndWords routine performs a copy using the size of the original number, either t or this.
> >
> > Changing the value to result.reg.size() appears to fix the issue at least for my use case.
>
> Thanks Tony.
>
> Do you have a reproducer? I'd like to look at it.
>
> We have test cases setup and they are run under the sanitizers. I
> don't recall seeing a finding. We might be missing a test case for it,
> however.

I can't seem to reproduce the issue with our test data. Integer is
testing OK with UBsan, Asan and Valgrind.

Would you be able to provide a reproducer?

Thanks again.

----------
Here's the Valgrind build I am testing.

$ CXXFLAGS="-DDEBUG -g3 -O0" make -j 12
Using testing flags: -DDEBUG -g3 -O0
g++ -fPIC -pthread -pipe -DDEBUG -g3 -O0 -c cryptlib.cpp
g++ -fPIC -pthread -pipe -DDEBUG -g3 -O0 -c cpu.cpp
g++ -fPIC -pthread -pipe -DDEBUG -g3 -O0 -c integer.cpp
...

$ valgrind -- ./cryptest.exe v 9997
==13696== Memcheck, a memory error detector
==13696== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==13696== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==13696== Command: ./cryptest.exe v 9997
==13696==
Using seed: 1633666228

Testing Integer bit operations...

passed: Bitwise AND over 32-bits to 1024-bits
passed: Bitwise OR over 32-bits to 1024-bits
passed: Bitwise XOR over 32-bits to 1024-bits

Seed used was 1633666228
Test started at Fri Oct 8 00:10:28 2021
Test ended at Fri Oct 8 00:10:31 2021
==13696==
==13696== HEAP SUMMARY:
==13696== in use at exit: 0 bytes in 0 blocks
==13696== total heap usage: 451,126 allocs, 451,126 frees,
22,872,284 bytes allocated
==13696==
==13696== All heap blocks were freed -- no leaks are possible
==13696==
==13696== For lists of detected and suppressed errors, rerun with: -s
==13696== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

[Jeffrey Walton]

On Fri, Oct 8, 2021 at 12:02 AM Jeffrey Walton <nolo...@gmail.com> wrote:
>

> On Thu, Oct 7, 2021 at 5:11 AM Tony Stead <ths...@gmail.com> wrote:
> >
> > I have been using the Integer class for some big number operations and seem to have found a buffer overflow in at least the Integer::And routine, I have not yet inspected any more..
> >

> > ...

> > The issue is casued in the temporary result variable. When result copies t or this in its constructor, it calculates the minimum size required to fit the current number in t or this. If the top order bits of t or this have gone zero it will allocate less bytes than the size of t or this. However the following AndWords routine performs a copy using the size of the original number, either t or this.
> >
> > Changing the value to result.reg.size() appears to fix the issue at least for my use case.
>
> Thanks Tony.
>
> Do you have a reproducer? I'd like to look at it.
>
> We have test cases setup and they are run under the sanitizers. I
> don't recall seeing a finding. We might be missing a test case for it,
> however.

By the way, here's the test data we use for testing the integer
operations. It was generated using Java, so you should get the same
result between Crypto++ and Java. You can find the Java program at
http://github.com/weidai11/cryptopp/issues/336.

https://github.com/weidai11/cryptopp/blob/master/validat2.cpp#L34

Jeff

[Tony Stead]

Hi,

Sorry I hadn't noticed your response.  

I have created a fairly simple demonstration.  In doing so I realise you may need to manipulate two integers to create the problem..  But this triggers the issue.

// To cause the overrun we need to manipulate two integers that then cross a 64 bit boundary.
// In addition they need to be positioned such that they cross a boundary in the lookup table within
// RoundupSizeTable table in integer.cpp..

//------------------------------
// static const unsigned int RoundupSizeTable[] = {2, 2, 2, 4, 4, 8, 8, 8, 8};
//
//static inline size_t RoundupSize(size_t n)
//{
// if (n<=8)
// return RoundupSizeTable[n];
// else if (n<=16)
// return 16;
// else if (n<=32)
// return 32;
// else if (n<=64)
// return 64;
// else
// return size_t(1) << BitPrecision(n-1);
//}
//-------------------------------

// With the following number we will downsize from 5 lots of 64 bits to 4, making the lookup
// in roundup table cross from 8 to 4.
std::uint8_t bitstream[] =
{ 0x01,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
CryptoPP::Integer bigint1(bitstream, sizeof(bitstream));
CryptoPP::Integer bigint2(bitstream, sizeof(bitstream));

// Bit shift to top bits are zeroised, this means that the CountWords algorithm will later ignore leading zero bytes.
// I figure you could probably also use substract here, anything that does not reallocate the reg buffer.
bigint1 >>= 1;
bigint2 >>= 1;

// Now perform one of the vulnerable manipulations.
// It is within this operator that a new integer is allocated with the reduced buffer size, but
// the full length of one of the original integers is copied into the buffer.
auto result = bigint2 & bigint1;

Hope this helps, let me know if I can help any further. 

Cheers,

Tony.

[Jeffrey Walton]

Thanks.

Do you have a *.cpp file I can compile and run?

Jeff

[Tony Stead]

I may not be using my eyes properly, but I cannot see how to attach files to this...

Shall I email you it?  Is just the cpp OK or do you want a makefile etc.?  Makefile will take a little longer as I will need to set that up....  And my wife is demanding attention so may not be able to do it immediately..

[Jeffrey Walton]

On Fri, Oct 8, 2021 at 1:23 PM Tony Stead <ths...@gmail.com> wrote:
>
> I may not be using my eyes properly, but I cannot see how to attach files to this...

Yeah, you have to click the paperclip in Gmail.

> Shall I email you it? Is just the cpp OK or do you want a makefile etc.? Makefile will take a little longer as I will need to set that up.... And my wife is demanding attention so may not be able to do it immediately..

We are tracking this issue at https://github.com/weidai11/cryptopp/issues/1072.

Jeff

[Jeffrey Walton]

On Fri, Oct 8, 2021 at 1:41 PM Jeffrey Walton <nolo...@gmail.com> wrote:
> ...

> > Shall I email you it? Is just the cpp OK or do you want a makefile etc.? Makefile will take a little longer as I will need to set that up.... And my wife is demanding attention so may not be able to do it immediately..
>
> We are tracking this issue at https://github.com/weidai11/cryptopp/issues/1072.

This issue was cleared at
https://github.com/weidai11/cryptopp/commit/4adfcd2c6c13.

Thanks again.