HIGHT cipher troubles with FileSource (CTR mode only)

[clementmartin971]

Using the code provided as HIGHT example in Wiki and replacing CBC_Mode by CTR_Mode is working... but next switching from StringSource to FileSource doesn't work anymore.

• the first ciphered block has 0 content (with 0 Key and Iv) instead of correct values
• ciphered content with StringSource : 7f 9f 0c 1c c1 9f c4 33 82 3f ee 8f dc
• ciphered content with FileSource : 00 00 00 00 00 00 00 00 82 3F EE 8F DC

The source code to reproduce:

int main(int argc, char* argv[])
{
   AutoSeededRandomPool prng;
   SecByteBlock key(HIGHT::DEFAULT_KEYLENGTH);
   SecByteBlock iv(HIGHT::BLOCKSIZE);

   prng.GenerateBlock(key, key.size());
   prng.GenerateBlock(iv, iv.size());
   // set key to 0 to better see error
   memset(key.BytePtr(),0,key.size());
   memset(iv.BytePtr(),0,iv.size());
   std::string plain = "CTR Mode Test";
   std::string cipher, encoded, recovered;

   /*********************************\
   \*********************************/

   try
   {
      std::cout << "plain text: " << plain << std::endl;

      CTR_Mode< HIGHT >::Encryption e;
      e.SetKeyWithIV(key, key.size(), iv);

      #if 0 
      // string source is working well
      StringSource s(plain, true, 
         new StreamTransformationFilter(e,
            new StringSink(cipher)
         ) // StreamTransformationFilter
      ); // StringSource
      #endif

      // file source doesn't work :(
      FileSource f("ansi_text_file_with_content_CTR Mode Test_.txt", true, 
         new CryptoPP::StreamTransformationFilter(e,
            new CryptoPP::StringSink(cipher)
         ) // StreamTransformationFilter
      ); // StringSource
      // at this point cipher differ from StringSource and FileSource
   }
   catch(const CryptoPP::Exception& e)
   {
      std::cerr << e.what() << std::endl;
      exit(1);
   }

   /*********************************\
   \*********************************/

   Print("key", std::string((const char*)key.begin(), key.size()));
   Print("iv", std::string((const char*)iv.begin(), iv.size()));
   Print("cipher text", cipher);

   /*********************************\
   \*********************************/

   try
   {
      CTR_Mode< HIGHT >::Decryption d;
      d.SetKeyWithIV(key, key.size(), iv);

      // The StreamTransformationFilter removes
      //  padding as required.
      StringSource s(cipher, true, 
         new StreamTransformationFilter(d,
            new StringSink(recovered)
         ) // StreamTransformationFilter
      ); // StringSource

      std::cout << "recovered text: " << recovered << std::endl;
   }
   catch(const CryptoPP::Exception& e)
   {
      std::cerr << e.what() << std::endl;
      exit(1);
   }
   return 0;
}

[noloader]

Thanks @clementmartin971.

Yeah, something is going sideways here. Whatever is wrong is not a new break. I'm seeing the same result back to Crypto++ 5.6.2.

We also lack a good set of test vectors for HIGHT in https://github.com/weidai11/cryptopp/blob/master/TestVectors/hight.txt. I don't think the missing test vectors affected this problem, however. Test vectors are run through a StringSource.

[noloader]

So I've got this tracked down to a function called AdditiveCipherTemplate::ProcessData around line 94. It calls a function called OperateKeystream(operation, outString, inString, iterations).

I think the problem is inString == outString. They are the same pointers, and it violates GCC aliasing rules. Sometimes GCC gives us a demerit and breaks us. Other times it does not.

This is a tricky problem because the compiler is removing code without a diagnostic. We can't debug what is not there...

I think we need to get on a code path that calls OperateKeystream(operation, inoutString, iterations). The problem is, the underlying cipher may not support in-place encryption.

This class has caused us a lot of trouble in the past. Scroll down to around 200 and read the comments for CFB mode.

Let me see what I can do to get this fixed.

[clementmartin971]

I can understand that it's not easy to fix.

I have tried a little to see what was wrong and didn't success (else I would have post the patch :) )

That surprised me was that it works for StringSource but not for FileSource; like FileStore::TransferTo2 / FileStore::CopyRangeTo2 where doing more processing.

Thank you for working on it

[clementmartin971]

You were right in analysis troubles occurred when inString == outString.

For string source inString != outString because StreamTransformationFilter::NextPutMultiple is called (and calls m_cipher.ProcessString(space, inString, len)) while for file source StreamTransformationFilter::NextPutModifiable is called providing m_cipher.ProcessString(inString, len).

A patch can be done in strciphr.cpp AdditiveCipherTemplate<S>::ProcessData by allocating a temporary output buffer if inString == outString.

I have done the following but I'm not sure to use correct allocation functions and if wiping is necessary (I didn't know enough cryptopp internals functions and way of protecting data)

template <S>
void AdditiveCipherTemplate<S>::ProcessData(byte *outString, const byte *inString, size_t length)
{
	byte *outStringBack = outString;
	byte *outStringAlloc = NULLPTR;
	size_t FullLength = length;
	if (outString == inString)
	{
		outStringAlloc = static_cast<byte*>(AlignedAllocate(FullLength));
		if (outStringAlloc == NULLPTR)
			throw std::bad_alloc();
        
		// fill outStringAlloc with inString, in case of error or early break (for copy back at the end of the function)
		memcpy(outStringAlloc,inString,FullLength);

		// make outString point to new allocated buffer
		outString = outStringAlloc;
	}

	if (m_leftOver > 0)
	{
		const size_t len = STDMIN(m_leftOver, length);
		xorbuf(outString, inString, PtrSub(KeystreamBufferEnd(), m_leftOver), len);

		length -= len; m_leftOver -= len;
		inString = PtrAdd(inString, len);
		outString = PtrAdd(outString, len);

		// if (!length) {return;}
		if (!length) {goto CleanUp;}
	}

	PolicyInterface &policy = this->AccessPolicy();
	unsigned int bytesPerIteration = policy.GetBytesPerIteration();

	if (policy.CanOperateKeystream() && length >= bytesPerIteration)
	{
		const size_t iterations = length / bytesPerIteration;
		unsigned int alignment = policy.GetAlignment();
		volatile int inAligned = IsAlignedOn(inString, alignment) << 1;
		volatile int outAligned = IsAlignedOn(outString, alignment) << 0;

		KeystreamOperation operation = KeystreamOperation(inAligned | outAligned);
		policy.OperateKeystream(operation, outString, inString, iterations);

		inString = PtrAdd(inString, iterations * bytesPerIteration);
		outString = PtrAdd(outString, iterations * bytesPerIteration);
		length -= iterations * bytesPerIteration;

		// if (!length) {return;}
		if (!length) {goto CleanUp;}
	}

	size_t bufferByteSize = m_buffer.size();
	size_t bufferIterations = bufferByteSize / bytesPerIteration;

	while (length >= bufferByteSize)
	{
		policy.WriteKeystream(m_buffer, bufferIterations);
		xorbuf(outString, inString, KeystreamBufferBegin(), bufferByteSize);

		length -= bufferByteSize;
		inString = PtrAdd(inString, bufferByteSize);
		outString = PtrAdd(outString, bufferByteSize);
	}

	if (length > 0)
	{
		bufferByteSize = RoundUpToMultipleOf(length, bytesPerIteration);
		bufferIterations = bufferByteSize / bytesPerIteration;

		policy.WriteKeystream(PtrSub(KeystreamBufferEnd(), bufferByteSize), bufferIterations);
		xorbuf(outString, inString, PtrSub(KeystreamBufferEnd(), bufferByteSize), length);
		m_leftOver = bufferByteSize - length;
	}
    
CleanUp:
	if (outStringAlloc)
	{
		memcpy(outStringBack,outStringAlloc,FullLength);
		SecureWipeBuffer(outStringAlloc,FullLength); // Is this required ???
		AlignedDeallocate(outStringAlloc);
	}
}

[noloader]

@clementmartin971,

No joy yet. PR #1019 cleaned up strciphr.cpp. Commit 4eac79fad8e4 cleaned up some shady casts in xorbuf.

I also tried your patch with no joy. It failed to decrypt HIGHT ciphertext properly. It also broke OFB mode. (It did produce ciphertext, but I am not sure if it was correct).

I'm scratching my head...

[noloader]

Thanks again @clementmartin971,

This issue was cleared at Commit 71a812ed9e7c and Commit bbc45ddfd7fc. (The first commit failed to check-in the updated header file).

Re: this workaround + the xorbuf cleanup... It looks like AES/CTR lost about 0.03-0.05 cpb on x86_64 with both changes. That is acceptable. In general, most ciphers gained 0.1-0.6 cpb. And RC6 gained 4.4 cpb.

I also tried your patch with no joy...

This was incorrect. My implementation was bad. I revisited it this morning and fixed my mistake.

Thanks again for your help.

[clementmartin971]

Thanks a lot for the resolution. I was about to test again my "workaround" according to your comment of yesterday.
Happy to see you finally solve it, and sorry for not supporting you so much, but internal code is quite complex for me.
I need to spend more time to see all the interactions between classes and internal structures and to be able to provide you real help
Many thanks for your support

[noloader]

@clementmartin971,

We now have some self tests that use FileSource in addition to StringSource. The new tests were mostly copy/paste of existing StringSource tests. We should be able to detect a problem like this in the future.

Also see Commit 07951c11e5d1 and Commit 0c88471e7aad.

[noloader]

@PassMark, @dgm3333, @clementmartin971

I checked in some code to avoid the extra buffer and memcpy's. It is sitting on the strciphr branch.

The code tested Ok for me on x86_64. That's where HIGHT bock cipher had problems. ARMv7 had problems on Linux, and I it also tested Ok. Can you guys test it on your platforms, please?

You can fetch the code with:

$ git fetch origin
$ git checkout strciphr -f && git pull

We announced the testing branch on the mailing list at strciphr.cpp updates. If I don't get any complaints over the next week or so, I will merge the changes.

Thanks in advance.

[clementmartin971]

Hello,
Sorry for being late... but I'm also on x86_64

[dgm3333]

Thanks for this. I've been a bit swamped with another coding push but I should have a chance to rewrite the encryption routines to test impact of multithreading on timing later in the week. However for what it's worth an initial "single thread" (ie any multithreaded processing would be automatic compiler/operating system initiated) encryption/decryption loop of ~150GB / 15k files of data completed without triggering any warnings. (Test PC is running Win 10 pro 64 running on an AMD Ryzen 9 = 12 cores).

[noloader]

@dgm3333,

I merged the changes into master last night. You should test master now.

Jeff