Segmentation fault for malicious secure OOS16 about libote

[ladnir]

First of all the code you provided does not compile for me. At the end you have

	std::vector<block> messages(TOTALOTS);
        recv.receiveChosen(SETSIZE, messages, choices, prng, recverChl);

	::std::cout << "Receiver: " << "Result: \n";
	for (int i = 0; i < TOTALOTS; ++i) {
		std::cout << i << ": " << messages[i][0] << ", " << messages[i][1] << std::endl;
	}

but messages is a vector<block> and you are indexing it at two levels.

If I change that line to

std::cout << i << ": " << messages[i] << std::endl;

then the code compiles just fine and runs as expected with no segfault.

Can you compile the library with debug symbols and run with GDB to see exactly where it is segfaulting?

[erik-buchholz]

Sorry for that. On my machine both versions of the cout due to whatever reason.

The segfault occurs on exit of the function oos. It tries to clean up OosNcoOtReceiver recv but during that, the segfault occurs.
The segfault is only caused if the OosNcoOtReceiver::check function is called. If I comment this function out, and the corresponding function on the server side, no segfault takes place.

[erik-buchholz]

As an addition:
I cannot reproduce the segfault on Mac OS. However, I tested several different machines running Ubuntu and each of them produces a segfault.

[ladnir]

What happens if you use this version of OOS fucntion computeProof() https://gist.github.com/ladnir/b58941dc917615dfb3dc22951588e629

[erik-buchholz]

Unfortunately this did not fix the issue.
It still produces a segfault on leaving the function oos.
If I debug, the following happens:

1. The program steps into osuCrypto::OosNcoOtReceiver::~OosNcoOtReceiver
2. Then it executes some assembler code until a call to <std::vector<long long __vector(2), std::allocator<long long __vector(2)> >::~vector()>
3. This executes until some free is called which then triggers the Segfault.

Is there any other information I could provide you to figure out where the problem is?

[erik-buchholz]

I just tried to switch the roles and put the receiver code into the thread instead of the sender. However, the debugging showed that it is again osuCrypto::OosNcoOtReceiver::~OosNcoOtReceiver where the Segfault is caused.

[ladnir]

So it seems pretty clear that it's somehow writing out of memory and overwriting something. Can you use valgrind to check this?

https://praba.wordpress.com/2011/01/02/how-to-detect-memory-leaks-and-memory-corruption/

[ladnir]

Also, if you do

cmake . -DCMAKE_BUILD_TYPE=Debug

Then you will get the source view when you debug in gdb.

Also, if you need to add compile flags that is done here

[erik-buchholz]

Also, if you do

cmake . -DCMAKE_BUILD_TYPE=Debug

Then you will get the source view when you debug in gdb.

Also, if you need to add compile flags that is done here

I did not change anything in the cmake file, except for the path to Wolfssl because I installed a more recent version into $HOME.

With -DCMAKE_BUILD_TYPE=Debug there is no Segfault anymore. When I compile again with -DCMAKE_BUILD_TYPE=Release, the Segfault is back...
Compiling with -DCMAKE_BUILD_TYPE=RelWithDebInfo also produces no Segfault.

This is the valgrind output:

==5536== Memcheck, a memory error detector
==5536== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5536== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5536== Command: ./bin/min
==5536==
vex amd64->IR: unhandled instruction bytes: 0x62 0xF1 0x75 0x28 0xEF 0xC9 0x48 0xC7 0xC0 0x0
vex amd64->IR:   REX=0 REX.W=0 REX.R=0 REX.X=0 REX.B=0
vex amd64->IR:   VEX=0 VEX.L=0 VEX.nVVVV=0x0 ESC=NONE
vex amd64->IR:   PFX.66=0 PFX.F2=0 PFX.F3=0
==5536== valgrind: Unrecognised instruction at address 0x40aa8a.
==5536==    at 0x40AA8A: _GLOBAL__sub_I_Defines.cpp (in /home/buchholz/clion/cython/bin/min)
==5536==    by 0x4993EC: __libc_csu_init (in /home/buchholz/clion/cython/bin/min)
==5536==    by 0x5CAEB27: (below main) (libc-start.c:266)
==5536== Your program just tried to execute an instruction that Valgrind
==5536== did not recognise.  There are two possible reasons for this.
==5536== 1. Your program has a bug and erroneously jumped to a non-code
==5536==    location.  If you are running Memcheck and you just saw a
==5536==    warning about a bad jump, it's probably your program's fault.
==5536== 2. The instruction is legitimate but Valgrind doesn't handle it,
==5536==    i.e. it's Valgrind's fault.  If you think this is the case or
==5536==    you are not sure, please let us know and we'll try to fix it.
==5536== Either way, Valgrind will now raise a SIGILL signal which will
==5536== probably kill your program.
==5536==
==5536== Process terminating with default action of signal 4 (SIGILL)
==5536==  Illegal opcode at address 0x40AA8A
==5536==    at 0x40AA8A: _GLOBAL__sub_I_Defines.cpp (in /home/buchholz/clion/cython/bin/min)
==5536==    by 0x4993EC: __libc_csu_init (in /home/buchholz/clion/cython/bin/min)
==5536==    by 0x5CAEB27: (below main) (libc-start.c:266)
==5536==
==5536== HEAP SUMMARY:
==5536==     in use at exit: 0 bytes in 0 blocks
==5536==   total heap usage: 1 allocs, 1 frees, 72,704 bytes allocated
==5536==
==5536== All heap blocks were freed -- no leaks are possible
==5536==
==5536== For counts of detected and suppressed errors, rerun with: -v
==5536== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Illegal instruction (core dumped)

From what I found about vex amd64->IR: unhandled instruction bytes on Stackoverflow this might be an issue with Intel instructions on an AMD CPU. However, the server I am using has an Intel CPU so that this does not make much sense to me. I also removed -msse4.1 from the CMakeLists, but this did not change anything either.

[ladnir]

Here's an idea. Can you return early from that check function and "binary search" for where the problematic code is?

[erik-buchholz]

Yes, of course.
The problem is the variable mChallengeSeed.
As soon as there is write access to this variable, I get a Segfault in the end. If I replace all occurrences of mChallengeSeed by AllOneBlock (or OneBlock or any other value I tried) on both sender and receiver side, no Sefault occurs.
As soon as I add a simple mChallengeSeed = AllOneBlock in the code, the Segfault is back.

This is a git diff for a modifaction that produces no Segfault:
no-segfault.txt
OosNcoOtReceiver.txt
OosNcoOtSender.txt

diff --git a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp
index e5f297e..6f52e4f 100644
--- a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp
+++ b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp
@@ -405,6 +405,7 @@ namespace osuCrypto
         {
             sendFinalization(chl, wordSeed);
             recvChallenge(chl);
             computeProof();
             sendProof(chl);
         }
@@ -471,17 +472,17 @@ namespace osuCrypto
     {

         // the sender will now tell us the random challenge seed.
-        chl.recv((u8*)&mChallengeSeed, sizeof(block));
+        // chl.recv((u8*)&mChallengeSeed, sizeof(block));


     }
     void OosNcoOtReceiver::computeProof()
     {
-        if (eq(mChallengeSeed, ZeroBlock))
+        if (eq(OneBlock, ZeroBlock))
             throw RTE_LOC;

         // This AES will work as a PRNG, using AES-NI in counter mode.
-        AES aes(mChallengeSeed);
+        AES aes(OneBlock);
         // the index of the AES counter.
         u64 aesIdx(0);

diff --git a/libOTe/NChooseOne/Oos/OosNcoOtSender.cpp b/libOTe/NChooseOne/Oos/OosNcoOtSender.cpp
index fdb995a..7753099 100644
--- a/libOTe/NChooseOne/Oos/OosNcoOtSender.cpp
+++ b/libOTe/NChooseOne/Oos/OosNcoOtSender.cpp
@@ -409,18 +409,18 @@ namespace osuCrypto

     void OosNcoOtSender::sendChallenge(Channel & chl, block seed)
     {
-        mChallengeSeed = seed;
-        chl.asyncSend(mChallengeSeed);
+        // mChallengeSeed = seed;
+        // chl.asyncSend(mChallengeSeed);
     }

     void OosNcoOtSender::computeProof()
     {

-        if (eq(mChallengeSeed, ZeroBlock))
+        if (eq(OneBlock, ZeroBlock))
             throw RTE_LOC;

         // This AES will work as a PRNG, using AES-NI in counter mode.
-        AES aes(mChallengeSeed);
+        AES aes(OneBlock);
         // the index of the AES counter.
         u64 aesIdx(0);

Just adding the line mChallengeSeed = AllOneBlock; (e.g. at 408) is enough to trigger the Segfault again:
segfault.txt
OosNcoOtReceiver.txt
OosNcoOtSender.txt

diff --git a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp
index e5f297e..6f52e4f 100644
--- a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp
+++ b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp
@@ -405,6 +405,7 @@ namespace osuCrypto
         {
             sendFinalization(chl, wordSeed);
             recvChallenge(chl);
+            //mChallengeSeed = AllOneBlock;
             computeProof();
             sendProof(chl);
         }
@@ -471,17 +472,17 @@ namespace osuCrypto
     {

         // the sender will now tell us the random challenge seed.
-        chl.recv((u8*)&mChallengeSeed, sizeof(block));
+        // chl.recv((u8*)&mChallengeSeed, sizeof(block));


     }
     void OosNcoOtReceiver::computeProof()
     {
-        if (eq(mChallengeSeed, ZeroBlock))
+        if (eq(OneBlock, ZeroBlock))
             throw RTE_LOC;

         // This AES will work as a PRNG, using AES-NI in counter mode.
-        AES aes(mChallengeSeed);
+        AES aes(OneBlock);
         // the index of the AES counter.
         u64 aesIdx(0);

diff --git a/libOTe/NChooseOne/Oos/OosNcoOtSender.cpp b/libOTe/NChooseOne/Oos/OosNcoOtSender.cpp
index fdb995a..7753099 100644
--- a/libOTe/NChooseOne/Oos/OosNcoOtSender.cpp
+++ b/libOTe/NChooseOne/Oos/OosNcoOtSender.cpp
@@ -409,18 +409,18 @@ namespace osuCrypto

     void OosNcoOtSender::sendChallenge(Channel & chl, block seed)
     {
-        mChallengeSeed = seed;
-        chl.asyncSend(mChallengeSeed);
+        // mChallengeSeed = seed;
+        // chl.asyncSend(mChallengeSeed);
     }

     void OosNcoOtSender::computeProof()
     {

-        if (eq(mChallengeSeed, ZeroBlock))
+        if (eq(OneBlock, ZeroBlock))
             throw RTE_LOC;

         // This AES will work as a PRNG, using AES-NI in counter mode.
-        AES aes(mChallengeSeed);
+        AES aes(OneBlock);
         // the index of the AES counter.
         u64 aesIdx(0);

[erik-buchholz]

There is a even simpler way to avoid the segmentation fault:
After simpy adding the line block a = ZeroBlock; before block mChallengeSeed = ZeroBlock;, no segfault occurs anymore. (Of course, you are not allowed to access this variable a then.)
So it seems like the variable mChallengeSeed flows over somehow, but I do not understand why, as it happens on any write access, even without any pointer logic.
This is the diff for this dirty "fix":

diff --git a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h
index 5341856..30daa10 100644
--- a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h
+++ b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h
@@ -169,7 +169,7 @@ namespace osuCrypto

         std::vector<block> mWBuff, mTBuff;
         void sendFinalization(Channel& chl, block seed);
-
+        block a = ZeroBlock;^M
         block mChallengeSeed = ZeroBlock;
         void recvChallenge(Channel& chl);
         void computeProof();

and here is the modified OosNcoOtReceiver.h:
OosNcoOtReceiver.txt

EDIT:
Maybe a cleaner fix that worked for me:
Instead of passing mChallengeSeed via the member, I can pass it as a return value of recvChallengeand pass it as argument to void computeProof(block challengeSeed);
This solution does not produce a segfault either.
OosNcoOtReceiver.h
OosNcoOtReceiver.cpp

I also pushed the second fix here:
erik-buchholz@692f8b0

Unfortunately, this has breaks some code in libPSI, in particular, Grr18MPsiSender.cpp and Grr18MPsiReceiver.cpp. Those would have to be modified in case of this fix, too.
I pushed the corresponding fix for libPSI here: erik-buchholz/libPSI@6089c14

[ladnir]

that is wild... Never seen such a thing before.

And yeah that's why it's a member. So that Grr18 can call these functions in some other order.

What about if you do this code:

    void OosNcoOtReceiver::recvChallenge(Channel & chl)
    {

        // the sender will now tell us the random challenge seed.
        std::array<u8, sizeof(block)> buff;
        chl.recv(buff);
        mChallengeSeed = toBlock(buff.data());

    }

or more generally turn the mChallengeSeed member into a std::array<u8,sizeof(block)> adn then call toBlock(mChallenge.data()) when you need it in block form.

[erik-buchholz]

The first idea with changing the function does not work, because any write access to mChallengeSeed leads to a segfault, even assigning a constant to it.

Changing the datatype to std::array<u8,sizeof(block)> does not work either.

What does work, is moving the declaration of block mChallengeSeed = ZeroBlock;anywhere else in the OosNcoOtReceiver class. For example, if I just move this to line 38 where the other variables are defined, no segfault occurs anymore.
It looks to me like the problem is the exact position of the mChallengeSeed within memory. However, moving that line does probably not fix the underlying problem, I'm afraid. I guess something else would be overwritten and this is not detected in this example...

EDIT: diff

  diff --git a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h
  index 5341856..bc5f67e 100644
  --- a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h
  +++ b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h
  @@ -35,6 +35,7 @@ namespace osuCrypto
           u64 mStatSecParam = 0;
           LinearCode mCode;
           u64 mCorrectionIdx, mInputByteCount = 0;
  +        block mChallengeSeed = ZeroBlock;^M

           std::vector<std::array<PRNG, 2>> mGens;
           Matrix<block> mT0;
  @@ -169,8 +170,6 @@ namespace osuCrypto

           std::vector<block> mWBuff, mTBuff;
           void sendFinalization(Channel& chl, block seed);
  -
  -        block mChallengeSeed = ZeroBlock;
           void recvChallenge(Channel& chl);
           void computeProof();
           void sendProof(Channel& chl);

[ladnir]

OK, lets go with your fix of writing the ZeroBlock to it at the start.

But this looks like a compiler bug. If you changed mChallengeSeed into a std::array<u8,sizeof(block)> and then did recv(mChallengeSeed); and it segfaults, then there is something wrong with the code generation.

[erik-buchholz]

But this looks like a compiler bug. If you changed mChallengeSeed into a std::array<u8,sizeof(block)> and then did recv(mChallengeSeed); and it segfaults, then there is something wrong with the code generation.

Yes, that it is exactly what I did, and it segfaults:

  diff --git a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp
  index e5f297e..e313762 100644
  --- a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp
  +++ b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.cpp
  @@ -471,17 +471,17 @@ namespace osuCrypto
       {

           // the sender will now tell us the random challenge seed.
  -        chl.recv((u8*)&mChallengeSeed, sizeof(block));
  +        chl.recv(mChallengeSeed);^M


       }
       void OosNcoOtReceiver::computeProof()
       {
  -        if (eq(mChallengeSeed, ZeroBlock))
  +        if (eq(toBlock(mChallengeSeed.data()), ZeroBlock))^M
               throw RTE_LOC;

           // This AES will work as a PRNG, using AES-NI in counter mode.
  -        AES aes(mChallengeSeed);
  +        AES aes(toBlock(mChallengeSeed.data()));^M
           // the index of the AES counter.
           u64 aesIdx(0);

  diff --git a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h
  index 5341856..880e981 100644
  --- a/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h
  +++ b/libOTe/NChooseOne/Oos/OosNcoOtReceiver.h
  @@ -170,7 +170,7 @@ namespace osuCrypto
           std::vector<block> mWBuff, mTBuff;
           void sendFinalization(Channel& chl, block seed);

  -        block mChallengeSeed = ZeroBlock;
  +        std::array<u8,sizeof(block)> mChallengeSeed;^M
           void recvChallenge(Channel& chl);
           void computeProof();
           void sendProof(Channel& chl);

Output:

  Testing OOS16.------------------------------------------------------
  Sender: Configure done.
  Receiver: Configure done.
  Receiver: genBaseOts done.
  Sender: genBaseOts done.
  Sender: Finished
  Receiver: Result:
  0: 00000000000000000000000000000000
  1: 00000000000000000000000000000001
  2: 00000000000000000000000000000002
  3: 00000000000000000000000000000003
  4: 00000000000000000000000000000004
  5: 00000000000000000000000000000005
  6: 00000000000000000000000000000006
  7: 00000000000000000000000000000007
  8: 00000000000000000000000000000008
  9: 00000000000000000000000000000009
  Segmentation fault (core dumped)

OK, lets go with your fix of writing the ZeroBlock to it at the start.

Should I create a pull request or are you just pushing the change directly?

[ladnir]

I can change it.

[erik-buchholz]

Great, thanks a lot for your help!

[ladnir]

pushed. Let me know if it works.

[erik-buchholz]

pushed. Let me know if it works.

No unfortunately this does not work, I think we had a misunderstanding.
I modified the OosNcoOtReceiver.h.
The location of the declaration within the header file matters.
I create a pull request with the workaround that works on our servers, to avoid further confusion.

Sorry for the confusion!

[ladnir]

merged and closing this. But for the record im not convinced this is an issue with the source.