Learning About Cryptography through Pain
Tags: c, interop, cryptography, rsa
Published: 2020-07-12 13:43:27

---
title: Learning About Cryptography through Pain
published: true
description: A post-mortem on my attempt to create an interoperable 
tags: c#, interop, cryptography, rsa
//cover_image: https://direct_url_to_image.jpg
---

Due to a history that could be an entire series on its own, I recently found myself with the following task:  A C++ implementation that would be able to perform crypto and X509 operations using keys provided by something that wrapped the implementation (in this case C# and Java).  I have been taking on the C# challenge and I realized that when things go wrong in crypto, you are usually only left with a bunch of garbage bytes and no clue as to how you got there.  Here is what I've realized about the shortcomings of .NET Standard 2.0 and its comparable platforms.  There seems to have been improvements made for 2.1 and .NET 5, etc, but for now I will point out some things I've learned after banging the wall for a while.

So the operation I have been focused on is creating a valid X509 certificate for use with a server that uses TLS.  Currently the library is focused on the RSA algorithm, which for those unfamiliar is an algorithm which is asymmetric, meaning that two unique keys are used.  One is kept secret, and the other is distributed freely.  If a piece of data is encoded with one of the keys, it can be decoded with the other.  The logic for performing all the actual encoding, and construction of the certificate was done in C++, but the key operations were delegated out to the platform wrapping the implementation (C# here).  The operations that need to be performed are as follows:

1. Extract the public key data in DER format
2. Sign using the private key (This is so that the private key material does not need to be provided to the C++ implementation, and if possible can be generated in a way that never exposes it to the user)
3. Decrypt using the private key (Same reasoning as 2)

Aside from those operations, the rest can be performed in C++.  So let's begin on the journey.  The first operation, extracting the public key, immediately gave me problems.

The current class to use for these operations seems to be `RSACryptoServiceProvider` and it has no method to export to DER format.  There also doesn't appear to be any class that can encode it to DER, so this had to be written by hand.  ASN1 is quite confusing to work with, but I was able to write it entirely thanks to an answer from [Stack Overflow](https://stackoverflow.com/a/28407693/1155387).  There are export methods on the class, but they are only proprietary encodings for use with the Win32 crypto APIs.  

The bulk of the pain came from the sign operation.  The C++ library actually does something kind of funky first as a sanity check.  It will send a sentinel value to be signed, and then attempt to verify it to make sure that the public key associated is actually capable of working with the signed data.  That sounds simple enough, but to explain the reason it is not it is necessary to step back and give a brief primer about how signatures work in RSA.

Firstly, RSA cannot encode anything that is longer than its key.  It also cannot encode anything that is shorter than its key.  This is because it's actually not looking at the data as a set of bytes but rather a gigantic number that is represented by those bytes.  It then performs some clever math on that number, and the encoded bytes are the result of representing *THAT* number.  To reverse this, you take the resulting number, and do the same clever math but with the parameters of the other key and you will arrive back at the same gigantic number, and thus the original bytes.  

The primitive operation of RSA signing is the same as RSA decryption (that does _not_ mean that they are the same thing, but they use the same encoding process at some point).  But that means that you can only encode a relatively small amount of data (256 bytes, for example, using a 2048 bit key.  Actually less because of padding, which is coming up in a minute).  So what do you do when you want to sign something bigger?  The answer lies in the steps that come BEFORE the encoding of the data using RSA.  Instead of encoding the data itself, a hash of the data is encoded.  A number of algorithms are supported for hashing via RSA, but SHA256 is a commonly used one.  SHA256 is a 256 bit hashing algorithm, which means that it will reduce any arbitrarily large set of data into 32 bytes in a way that is unique, but non-reversible (it's actually not strictly unique, but that's part of the game.  It is unique enough that finding a non-unique hash is exceptionally hard.  Usually once it is found, it starts to become time to move on to the next algorithm that is newer).  

But wait, now the data is 32 bytes and it is too small!  This is no good either.  The answer is to fill up the other 224 bytes with padding data.  The padding data has to be defined and agreed upon otherwise it will be impossible to tell what is padding and what is not.  But now that things are the correct length things can be encoded and decoded properly.

This is where the first puzzling problem comes in.  For the reasons described above, when using RSA you need to say "I am using RSA with X hashing algorithm."  However, the first thing that came back from the C++ library was a request to encode something with RSA and using _no hash algorithm_.  I dislike reading long RFCs and I'm sure this is in there somewhere but apparently this means to skip the hashing part, and just encode the received data directly, because it is already less than or equal to the maximum length able to be encoded.  

Very well, that just means skip straight to the encoding portion, which as I mentioned before is the same as the decrypt function.  So I tried calling `Decrypt` on the `RSACryptoServiceProvider` class on the data I received.  Nope, it threw an exception.  Probably because it was expecting to get readable data on the other side (It can tell if the data is valid or not because of the padding scheme used).  It is _decrypting_ something after all.  That's disappointing.  Apple's signature API has a mode to sign without a hash function, and Java has the `NONEWithRSA` mode in its `Signature.getInstance` method, but C# has apparently left this out so there is no way to do this with `SignData` or `SignHash` either.  

Furthermore, the `Decrypt` method forces you to use a padding mode, meaning that it can only accept _unpadded_ data.  If I try to pass in data that I manually padded I get an exception again because the data is too long to encode (since it is trying to re-add the padding).  However, I began to wonder how complex the RSA encoding operation actually is.  It's actually surprisingly simple.  The bulk of the work comes from calculating the parameters to work with, but using the parameters is another story.  Excellent!

So there are three main numbers involved with encoding and decoding:  The modulus (n), the private exponent (d) and the public exponent (e).  There is a lot of complex math to get these numbers, but the result is that any number `m` can be transformed into `c` using `m ^ d mod n` and then transformed back to the original `m` using `c ^ e mod n`.  So I just have to repeat the first part of this operation in my "raw signature" method.  

Since these numbers have to be very very *VERY* large in order to provide security, normal integer primitives won't cut it.  `long` is, after all, a 64 bit number and it is recommended to have a number that is at least 2048 bits in order to be secure.  The way to work with such numbers in C# is to use the `BigInteger` class.  It even has a constructor that accepts `byte[]` directly, great!

So I manually padded the bytes I received, and then passed them into a `BigInteger` which even, conveniently, has a `ModPow` method for doing exactly what I described above.  So I did that using the parameters from the key and was meant with instant success.

Just kidding, it didn't work at all!  Often I would get exceptions saying that the exponent needed to be a positive number.  Well duh, why isn't it?  Well it turns out the answer lies in our old friend endianness.  As a review, endianness determines what order to read bytes when a numeric value is represented by more than one byte.  Little endian will read from the end of the block to the beginning, and big endian will read from the start to the end.  The bytes stored in the parameters of the key are in big endian, but `BigInteger` wants little endian.  This means that the bytes have to be reversed first before being used (.NET Core 3, and perhaps .NET Standard 2.1 have fixed this by adding an endianness option to `BigInteger`).  Furthermore, once the math is done, the resulting bytes have to be reversed a second time to get them back into big endian. 

Ready to work now right?  YES, well...sometimes.  `BigInteger` not only works with little endian, it works with _signed_ little endian meaning that it will interpret the bytes using the two complement (a method for representing negative numbers in binary).  In order to stop this, a 0 needs to be appended to the end of the last byte is higher than `0x80` to avoid it being falsely interpreted as a negative number.  Furthermore, on the way back out this 0 might still be there and so before sending it to C++ the zero needs to be trimmed before reversing the bytes and sending them.  

Finally after all that, the weird "no hash algorithm" method of signing was working.  However, the resulting certificates were all invalid.  I was still using another path for signing when an actual algorithm was specified, because that is what is supported in C#.  So what was going wrong?  Come to find out that there are two methods on `RSACryptoServiceProvider`:  `SignData` and `SignHash`.  The former will hash the data first before signing it, and the latter will just sign it directly (which makes me wonder why the latter takes a hashing algorithm as an argument.  It doesn't need to hash anything, after all.  I suppose it uses it to try to check that it actually received something of the valid size?).  The C++ library was sending me hashes to sign, not arbitrary data, and I was using the wrong one!  Switching to the correct one (`SignHash`) fixed that but it took me a while to figure out what the difference was.

Step 3 had no problems at all, as a call to `Decrypt` was all that was needed but hours and hours got spent on steps 1 and 2.  I'm hoping that this information can help someone who might be in a similar position at some point.  Happy cryptoing!