Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Zinflate and AddressSanitizer finding #414

Closed
noloader opened this issue May 10, 2017 · 11 comments

Comments

Projects
None yet
4 participants
@noloader
Copy link
Collaborator

commented May 10, 2017

We started fuzzing library classes. Its dumb fuzzing, and all we do is generate a random string and send it into a filter like Inflator or Gunzip. (There's some smartness for some of the classes, like ensuring data is formatted and magics are present).

It looks like Inflator is having some trouble. The assert below was added when we noticed some odd behavior.

Testing Compressors and Decompressors...

Assertion failed: zinflate.cpp(554): DecodeBody
zinflate.cpp:561:69: runtime error: index 31 out of bounds for type 'unsigned int [30]'
passed:  128 zips and unzips
Assertion failed: zinflate.cpp(554): DecodeBody
Assertion failed: zinflate.cpp(554): DecodeBody
passed:  128 deflates and inflates
passed:  128 zlib decompress and compress

Running the test suite under Address Sanitizer with garbage/random data results in the following. It looks like we have an out-of-bounds read. Its not clear if there's an accompanying write, or if it can be controlled by an attacker.

Assertion failed: zinflate.cpp(554): DecodeBody
=================================================================
==16749==ERROR: AddressSanitizer: global-buffer-overflow on address 0x000000b5a7dc at pc 0x000000961356 bp 0x7ffd88929970 sp 0x7ffd88929960
READ of size 4 at 0x000000b5a7dc thread T0
    #0 0x961355 in Inflator::DecodeBody() /home/cryptopp/zinflate.cpp:561
    #1 0x95f539 in Inflator::ProcessInput(bool) /home/cryptopp/zinflate.cpp:354
    #2 0x95ef69 in Inflator::Put2(unsigned char const*, unsigned long, int, bool) /home/cryptopp/zinflate.cpp:306
    #3 0x69fa21 in BufferedTransformation::ChannelPut2(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, unsigned char const*, unsigned long, int, bool) /home/cryptopp/cryptlib.cpp:438
    #4 0x872c70 in StringStore::CopyRangeTo2(BufferedTransformation&, unsigned long&, unsigned long, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool) const /home/cryptopp/filters.cpp:1132
    #5 0x8729d4 in StringStore::TransferTo2(BufferedTransformation&, unsigned long&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool) /home/cryptopp/filters.cpp:1122
    #6 0x6a19c1 in BufferedTransformation::TransferMessagesTo2(BufferedTransformation&, unsigned int&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool) /home/cryptopp/cryptlib.cpp:590
    #7 0x6a237b in BufferedTransformation::TransferAllTo2(BufferedTransformation&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool) /home/cryptopp/cryptlib.cpp:636
    #8 0x4767d3 in SourceTemplate<StringStore>::PumpAll2(bool) /home/cryptopp/filters.h:1361
    #9 0x4483dc in Source::PumpAll() /home/cryptopp/filters.h:1302
    #10 0x448465 in Source::SourceInitialize(bool, NameValuePairs const&) /home/cryptopp/filters.h:1335
    #11 0x52105d in StringSource::StringSource(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool, BufferedTransformation*) /home/cryptopp/filters.h:1404
    #12 0x50e5cb in Test::TestCompressors() /home/cryptopp/validat0.cpp:90
    #13 0x53bb05 in Test::ValidateAll(bool) /home/cryptopp/validat1.cpp:102
    #14 0x43c09e in Validate(int, bool, char const*) /home/cryptopp/test.cpp:911
    #15 0x433093 in main /home/cryptopp/test.cpp:401
    #16 0x7f9468830400 in __libc_start_main (/lib64/libc.so.6+0x20400)
    #17 0x4308a9 in _start (/home/cryptopp/cryptest.exe+0x4308a9)

0x000000b5a7dc is located 4 bytes to the right of global variable 'distanceStarts' defined in 'zinflate.cpp:504:29' (0xb5a760) of size 120
0x000000b5a7dc is located 36 bytes to the left of global variable 'distanceExtraBits' defined in 'zinflate.cpp:508:29' (0xb5a800) of size 120
SUMMARY: AddressSanitizer: global-buffer-overflow /home/cryptopp/zinflate.cpp:561 in Inflator::DecodeBody()
Shadow bytes around the buggy address:
  0x0000801634a0: f9 f9 f9 f9 00 00 00 00 00 00 00 00 00 00 00 00
  0x0000801634b0: 00 04 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x0000801634c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0000801634d0: 00 00 04 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x0000801634e0: 00 00 00 00 00 00 04 f9 f9 f9 f9 f9 00 00 00 00
=>0x0000801634f0: 00 00 00 00 00 00 00 00 00 00 00[f9]f9 f9 f9 f9
  0x000080163500: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 f9
  0x000080163510: f9 f9 f9 f9 00 00 00 00 00 00 00 00 00 00 00 00
  0x000080163520: 00 00 00 00 00 00 00 00 00 00 00 00 07 f9 f9 f9
  0x000080163530: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 07 f9 f9 f9
  0x000080163540: f9 f9 f9 f9 00 00 00 00 00 03 f9 f9 f9 f9 f9 f9
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==16749==ABORTING

This issue has been assigned CVE-2017-9434 (thanks @carnil). The issue was announced on OSS-Security at Crypto++ and invalid read in decompressor class.

@noloader

This comment has been minimized.

Copy link
Collaborator Author

commented May 10, 2017

Cleared at Commit 07dbcc3d9644.

Also see RFC 1950/Inflator feedback needed on the mailing list.

@noloader

This comment has been minimized.

Copy link
Collaborator Author

commented May 11, 2017

Here are the Crypto++ 5.6.x patches. It looks like the issue predates Crypto++ 5.0 released in 2002.


Crypto++ 5.6.5 (released 2016-10-11)

$ cat zinflate-565.diff
diff --git a/zinflate.cpp b/zinflate.cpp
index da473f3..3e3faf9 100644
--- a/zinflate.cpp
+++ b/zinflate.cpp
@@ -550,12 +550,16 @@ bool Inflator::DecodeBody()
                                                break;
                                        }
                case DISTANCE_BITS:
+                                       if (m_distance >= COUNTOF(distanceExtraBits))
+                                               throw BadDistanceErr();
                                        bits = distanceExtraBits[m_distance];
                                        if (!m_reader.FillBuffer(bits))
                                        {
                                                m_nextDecode = DISTANCE_BITS;
                                                break;
                                        }
+                                       if (m_distance >= COUNTOF(distanceStarts))
+                                               throw BadDistanceErr();
                                        m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
                                        OutputPast(m_literal, m_distance);
                                }
diff --git a/zinflate.h b/zinflate.h
index 8c08ed0..6442969 100644
--- a/zinflate.h
+++ b/zinflate.h
@@ -96,6 +96,7 @@ public:
        };
        class UnexpectedEndErr : public Err {public: UnexpectedEndErr() : Err(INVALID_DATA_FORMAT, "Inflator: unexpected end of compressed block") {}};
        class BadBlockErr : public Err {public: BadBlockErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in compressed block") {}};
+       class BadDistanceErr : public Err {public: BadDistanceErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in bit distance") {}};

        //! \brief RFC 1951 Decompressor
        //! \param attachment the filter's attached transformation


Crypto++ 5.6.4 (released 2016-09-11)

$ cat zinflate-564.diff
diff --git a/zinflate.cpp b/zinflate.cpp
index adffca0..1a12460 100644
--- a/zinflate.cpp
+++ b/zinflate.cpp
@@ -550,12 +550,16 @@ bool Inflator::DecodeBody()
                                                break;
                                        }
                case DISTANCE_BITS:
+                                       if (m_distance >= sizeof(distanceExtraBits)/sizeof(distanceExtraBits[0]))
+                                               throw BadDistanceErr();
                                        bits = distanceExtraBits[m_distance];
                                        if (!m_reader.FillBuffer(bits))
                                        {
                                                m_nextDecode = DISTANCE_BITS;
                                                break;
                                        }
+                                       if (m_distance >= sizeof(distanceStarts)/sizeof(distanceStarts[0]))
+                                               throw BadDistanceErr();
                                        m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
                                        OutputPast(m_literal, m_distance);
                                }
diff --git a/zinflate.h b/zinflate.h
index 8c08ed0..6442969 100644
--- a/zinflate.h
+++ b/zinflate.h
@@ -96,6 +96,7 @@ public:
        };
        class UnexpectedEndErr : public Err {public: UnexpectedEndErr() : Err(INVALID_DATA_FORMAT, "Inflator: unexpected end of compressed block") {}};
        class BadBlockErr : public Err {public: BadBlockErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in compressed block") {}};
+       class BadDistanceErr : public Err {public: BadDistanceErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in bit distance") {}};

        //! \brief RFC 1951 Decompressor
        //! \param attachment the filter's attached transformation


Crypto++ 5.6.3 (released 2015-11-20)

$ cat zinflate-563.diff
diff --git a/zinflate.cpp b/zinflate.cpp
index b0117ce..fc15e62 100644
--- a/zinflate.cpp
+++ b/zinflate.cpp
@@ -550,12 +550,16 @@ bool Inflator::DecodeBody()
                                                break;
                                        }
                case DISTANCE_BITS:
+                                       if (m_distance >= COUNTOF(distanceExtraBits))
+                                               throw BadDistanceErr();
                                        bits = distanceExtraBits[m_distance];
                                        if (!m_reader.FillBuffer(bits))
                                        {
                                                m_nextDecode = DISTANCE_BITS;
                                                break;
                                        }
+                                       if (m_distance >= COUNTOF(distanceStarts))
+                                               throw BadDistanceErr();
                                        m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
                                        OutputPast(m_literal, m_distance);
                                }
diff --git a/zinflate.h b/zinflate.h
index 8c08ed0..6442969 100644
--- a/zinflate.h
+++ b/zinflate.h
@@ -96,6 +96,7 @@ public:
        };
        class UnexpectedEndErr : public Err {public: UnexpectedEndErr() : Err(INVALID_DATA_FORMAT, "Inflator: unexpected end of compressed block") {}};
        class BadBlockErr : public Err {public: BadBlockErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in compressed block") {}};
+       class BadDistanceErr : public Err {public: BadDistanceErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in bit distance") {}};

        //! \brief RFC 1951 Decompressor
        //! \param attachment the filter's attached transformation


Crypto++ 5.6.2 (released 2013-02-20)

$ cat zinflate-562.diff
diff --git a/zinflate.cpp b/zinflate.cpp
index 4018e11..1ef8cdc 100644
--- a/zinflate.cpp
+++ b/zinflate.cpp
@@ -537,12 +537,16 @@ bool Inflator::DecodeBody()
                                                break;
                                        }
                case DISTANCE_BITS:
+                                       if (m_distance >= sizeof(distanceExtraBits)/sizeof(distanceExtraBits[0]))
+                                               throw BadDistanceErr();
                                        bits = distanceExtraBits[m_distance];
                                        if (!m_reader.FillBuffer(bits))
                                        {
                                                m_nextDecode = DISTANCE_BITS;
                                                break;
                                        }
+                                       if (m_distance >= sizeof(distanceStarts)/sizeof(distanceStarts[0]))
+                                               throw BadDistanceErr();
                                        m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
                                        OutputPast(m_literal, m_distance);
                                }
diff --git a/zinflate.h b/zinflate.h
index 7e1225b..2bf4d4d 100644
--- a/zinflate.h
+++ b/zinflate.h
@@ -93,6 +93,7 @@ public:
        };
        class UnexpectedEndErr : public Err {public: UnexpectedEndErr() : Err(INVALID_DATA_FORMAT, "Inflator: unexpected end of compressed block") {}};
        class BadBlockErr : public Err {public: BadBlockErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in compressed block") {}};
+       class BadDistanceErr : public Err {public: BadDistanceErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in bit distance") {}};

        /*! \param repeat decompress multiple compressed streams in series
                \param autoSignalPropagation 0 to turn off MessageEnd signal


Crypto++ 5.0 (released 2002-10-04)

$ cat zinflate-50.diff
diff --git a/zinflate.cpp b/zinflate.cpp
index fccbf83..6703cdb 100644
--- a/zinflate.cpp
+++ b/zinflate.cpp
@@ -534,12 +534,16 @@ bool Inflator::DecodeBody()
                                                break;
                                        }
                case DISTANCE_BITS:
+                                       if (m_distance >= sizeof(distanceExtraBits)/sizeof(distanceExtraBits[0]))
+                                               throw BadDistanceErr();
                                        bits = distanceExtraBits[m_distance];
                                        if (!m_reader.FillBuffer(bits))
                                        {
                                                m_nextDecode = DISTANCE_BITS;
                                                break;
                                        }
+                                       if (m_distance >= sizeof(distanceStarts)/sizeof(distanceStarts[0]))
+                                               throw BadDistanceErr();
                                        m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
                                        OutputPast(m_literal, m_distance);
                                }
diff --git a/zinflate.h b/zinflate.h
index b3172c8..e3d98b6 100644
--- a/zinflate.h
+++ b/zinflate.h
@@ -93,6 +93,7 @@ public:
        };
        class UnexpectedEndErr : public Err {public: UnexpectedEndErr() : Err(INVALID_DATA_FORMAT, "Inflator: unexpected end of compressed block") {}};
        class BadBlockErr : public Err {public: BadBlockErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in compressed block") {}};
+       class BadDistanceErr : public Err {public: BadDistanceErr() : Err(INVALID_DATA_FORMAT, "Inflator: error in bit distance") {}};

        /*! \param repeat decompress multiple compressed streams in series
                \param autoSignalPropagation 0 to turn off MessageEnd signal


anonimal added a commit to anonimal/kovri that referenced this issue May 11, 2017

Build: bump cryptopp to 35451f3
Includes hotfix for zinflate out-of-bounds read.

Referencing weidai11/cryptopp#414

anonimal added a commit to anonimal/kovri that referenced this issue May 17, 2017

Build: bump cryptopp to 1b1c32d
Relevant (to Kovri) updates:

- RDRAND build fix
- Features/tests/improvements related to compressor/decompressor/Gzip
- Hotfix for zinflate out-of-bounds read (weidai11/cryptopp#414)
@carnil

This comment has been minimized.

Copy link

commented Jun 5, 2017

This issue has been assigned CVE-2017-9434

@denisbider

This comment has been minimized.

Copy link
Collaborator

commented Jun 5, 2017

I should note I have not been able to reproduce this using any of the inputs provided by Jeffrey (@noloader) that were supposed to result in an out-of-bounds read under gcc + AddressSanitizer.

I tested using Visual Studio 2015, replacing the static int array with an object that would throw if an out-of-bounds index was provided. I could not get this issue to trigger.

I cannot say that the issue does not exist, but according to my current knowledge, it has not been proven to exist outside of the combination of gcc + AddressSanitizer.

@noloader

This comment has been minimized.

Copy link
Collaborator Author

commented Jun 5, 2017

@carnil,

This issue has been assigned CVE-2017-9434

Thanks Carnil.

Sorry about the delay in requesting the CVE. I'm going to copy it up to the initial report so others don't need to hunt for it.

One of the reasons for the delay is we wanted to test other interfaces, and then batch the request for CVE's. We were able to test a number of interfaces (including public keys, private keys and associated parameters), but we were not able to uncover additional problems. I think that's because of Issue 346, Security issue (DoS) in Crypto++ ASN1 decoder. The 346 issue was already known to us and it was previously hardened.


@denisbider,

I cannot say that the issue does not exist, but according to my current knowledge, it has not been proven to exist outside of the combination of gcc + AddressSanitizer.

Thanks Denis.

It may be worth noting we also added an assert, and it fires under debug builds with Clang, GCC, ICC and MSC. Others have experienced the assert on Windows machines; cf., Question about verification tests failing. And we see the assert logged during AppVeyor testing; cf., AppVeyor Build #70.

@denisbider

This comment has been minimized.

Copy link
Collaborator

commented Jun 5, 2017

It may be worth noting we also added an assert, and it fires under debug builds with Clang, GCC, ICC and MSC.

@noloader, in this case, I have not seen inputs that result in the assert. Do you have any I can test with?

@olalundqvist

This comment has been minimized.

Copy link

commented Jun 6, 2017

I'm looking through this problem for Debian wheezy but I have to ask a question about the patch.

m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];

This means that m_distance can be n + some value from distanceStarts. The highest value in distanceStarts is 24577.

Next time this part of the code is triggered then m_distance is used as index for both distanceExtraBits and distanceStarts. Both these arrays are 30 long. This is very far from 24577.

I do not say that the patch is wrong. It is just that I wonder if something more fundamentally is wrong.
Or have I missed something else that prevent this problem from occurring?

@noloader

This comment has been minimized.

Copy link
Collaborator Author

commented Jun 7, 2017

@olalundqvist,

I believe the code your are talking about is around zinflate.cpp : 570:

// TODO: this surfaced during fuzzing. What do we do???
CRYPTOPP_ASSERT(m_distance < COUNTOF(distanceStarts));
if (m_distance >= COUNTOF(distanceStarts))
    throw BadDistanceErr();
m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
OutputPast(m_literal, m_distance);

I was not able to get into that code path during testing with bad data. The problem area that we detected was the code before it, around zinflate.cpp : 560.

I believe what happened was the code around line 560 failed to fill the buffer, it dropped into the conditional, and it subsequently executed the break. The break ensured we did not perform a wild read around line 570.

bits = distanceExtraBits[m_distance];
if (!m_reader.FillBuffer(bits))
{
    m_nextDecode = DISTANCE_BITS;
    break;
}

I was having trouble tracing some of the code paths. Its the reason the code was loaded with asserts. Often times its easier to instrument code with asserts and then let the code debug itself. The instrumentation lead us to line 560 as the point of first failure on some of the negative test cases.

I have a small concern about the patch. It addresses the immediate problem of the out-of-bounds read in the identified area. My open question is, are we rejecting "good" input? In this respect, we could be failing safe at the possible expense of rejecting valid input. The "fail safe and reject good input" was the reason for this question on the mailing list: RFC 1950/Inflator feedback needed.

@olalundqvist

This comment has been minimized.

Copy link

commented Jun 7, 2017

@noloader

Thank you. Yes I was referring to these places in the code. Now I can also see a number of asserts in the more recent code that do not exist in version 5.6.1 (that we have in Debian wheezy). I think that explains why we can not get into the problem I was referring to. However I have a similar concern as you regarding the possibility of rejecting good input. However I have that already with the asserts that probably have been there for quite a while.

In any case now I understand how the package should be patched (I think at least).

@noloader

This comment has been minimized.

Copy link
Collaborator Author

commented Aug 19, 2017

@carnil, @denisbider, @olalundqvist, @gcsideal

I think I have some good news here. I think I tracked down the root cause. It explains why I would see the issue under GCC but Denis would not witness it under MSVC, It looks like the test code was violating GCC's strict aliasing rules, and it created problems with the random strings were were compressing, decompressing and tampering.

What was happening is, we would generate a random string:

unsigned int len = GlobalRNG().GenerateBlock(8 /*min*/, 0xfff /*max*/);
std::string src;
src.resize(len);

Then, we would get a hold of the non-const pointer with &src[0] and add some random data:

GlobalRNG().GenerateBlock(&src[0], src.size());

Now, here's where the problem started. The test program would do things like take part of the src array (and not the whole array) and do something with it. For example, the code below effectively lops-off the first two bytes in src.

const char* runt = &src[0]+2;  // length of len-2

And the place we would get into trouble was, we would use the runts and underruns until the end of the closing block. However, GCC was scheduling src's destructor before the end of the closing block. So we effectively had dangling pointers. MSVC was more forgiving, and it did not aggressively schedule the destructor.

We did not generate findings for undefined behavior, but that does not mean it was absent. I'm not sure about this area of the C++ standard. Usually you get in trouble when the arrays are different objects; and not when they are the same object. Maybe Denis knows more about it.

We also cannot rule out a bug in Address Sanitizer. If we did not have undefined behavior and we did not violate strict aliasing rules, the the issue could have been rooted in Asan. Asan's internal mechanics may have been doing something that we interacted poorly with.

After doing away with the pointers into the src and dest object arrays I have not witnessed the issue. Doing away with the subobject pointers just meant we created copies of existing objects or fresh objects.

So it looks like the CVE was a false alarm. Current and past versions of the library were not at risk. And no versions of Crypto++ were released with the defective driver program. I believe the worst case now is, we have some extra checks in the library that probably won't be exercised.

My apologies for the false alarm.

noloader added a commit that referenced this issue Aug 19, 2017

Update comments (Issue 414)
After more investigation it appears the issue was either Undefined Behavior or a Strict Aliasing violation in GCC; and it was in the test program and not the library. We're not sure which at the moment, but we were able to identify the problematic code. See the comments with Issue 414 (#414)
@denisbider

This comment has been minimized.

Copy link
Collaborator

commented Aug 21, 2017

@noloader - Excellent news! I was wondering about this issue, and if I should invest more time to try to reproduce it.

This unfortunately confirms my previous suspicions that GCC engages in over-aggressive and unsafe exploitation of technically undefined behavior that doesn't look undefined at first glance, or even second glance, and even to advanced users.

I think this is a considerable security risk for GCC users, and is one reason I avoid the compiler. I strongly disagree with the preference to optimize performance, instead of optimizing security, in situations such as this.

Do you know, is there even a warning that you can enable that would let you know there's undefined behavior in this case? Does GCC contain diagnostics for this, or is it necessary to use external tools to avoid this type of issue?

@noloader noloader removed the Security Bug label Aug 25, 2017

@noloader noloader closed this Aug 25, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.