Sunday, March 23, 2014

All about RSA key formats

I've spent the past few weeks building up the PCLCrypto library which targets .NET Framework, Windows Store (WinRT), Windows Phone (WP8), Silverlight (SL), Xamarin.Android (XA) and Xamarin.iOS (XI). What started out pretty easy turned into a pretty rough ride. The short version is: everything I've learned is now included in the PCLCrypto library so all you have to do is use its simple WinRT-like API from your app or library and you'll get native performance on each platform with no additional work on your part.

Getting to that point was, as I said: a rough ride, mostly in the RSA space. There is no RSA available at all for Silverlight (from the platform, anyway). WinRT has its own unique API but it's a good one and supports a variety of key formats. The rest of the platforms (.NET, WP8, XA, XI) all share an RSACryptoServiceProvider class, which at first made it look easy. I had all my tests passing in very little time because I just had to write code for WinRT and .NET.
The problem started when I realized how incredibly slow RSA operations (especially key generation) were on Xamarin mobile apps. I discovered that while Microsoft implements RSACryptoServiceProvider by simply P/Invoking into the Win32 CryptoAPI, Xamarin/mono implements it in all managed code. Managed implementations of RSA are slow. RSA requires a lot of BigInteger math so optimizations even at the assembler level really make a huge difference, so managed code can't touch that perf.

So the problem to tackle became how to implement crypto for each platform. Each platform of course has its documentation and samples for how to do crypto, but that's about where the similarity ended. Their preferred languages were different: iOS uses Objective-C and Android uses Java. I had to write everything in C# for the PCL library. Fortunately Xamarin made (most of) the APIs available to my C# library. Translating the samples from Java to C# was straightforward, but translating from Objective-C was a lesson in a very foreign language syntax for me. I can now say that I can read the language reasonably well, although I certainly couldn't write it by myself yet.

And it just got harder from there. I had to support exporting private keys generated from each platform. For .NET and WinRT this was a piece of cake. Each key object has an Export method, possibly with options of different key formats, and that's it.
Android makes discovering the private keys more difficult to export, involving downcasts and gotchas like having to do it immediately after key generation or you lose the opportunity to get at some of the RSA parameters.
iOS was the worst: they have no supported way to export the private key. There is an unsupported way to do it that has worked since around 2010 (from what I could figure out from the forums), but the Apple folks strongly discourage its use, threatening that any future version of iOS could break the 'backdoor' for obtaining private keys. Nevertheless it hasn't been closed off yet, and there is no other way to get it done, so I had to take that route. Personally, I think it's a perfectly reasonable approach and one I think Apple should maintain and support.

Then there were the differences in native formats of the keys themselves after I got them exported. RSACryptoServiceProvider's native key format is called CAPI (which took some work to discover because their method calls it a "CspBlob". Not only is CAPI the format you get an exported key in, but it's the format used internally during computations (which will become interesting later).
Android's native private key format is PKCS#8 PrivateKeyInfo. The native format in iOS is PKCS#1 rsaPrivateKey. For these systems to be able to interoperate, I had to be able to freely convert each format to every other format. For WinRT this was easy, since it can import/export all these formats in the platform. For all the other platforms this required that I study several new RSA key specs, learn ASN.1, DER, and BER encoding rules, and implement all these in a PCL-compatible way so I could leverage the code to help all the platforms interoperate. What made this particularly difficult was putting together the information I could find on the Internet (between RFCs, forum posts, docs, samples, etc.) since all of them seemed to be focused on only a very tiny bit of my overall problem, provide old or incorrect information, hard-code a bunch of formats without reasonable abstractions (making discovering how ASN.1 really works difficult), or assumed a certain level of familiarity with all the preceding RFCs which I didn't have at the time.

Then there was the iOS P and Q problem. It turns out that when iOS generates an RSA keypair, the P parameter is longer than the Q parameter. For Windows and Android platforms these parameters tend to be the same length. In fact this tendency in Windows is so strong that the CAPI key format actually depends on it, because none of the parameter lengths are actually included in the file format -- all the lengths are assumed. If you have a private key with P and Q of different lengths, it's fundamentally incompatible with any CAPI-based RSA operations. That took a very long time to finally figure out. And to date I still haven't found a way to get iOS to generate keypairs with equal length P and Q.
On most platforms this isn't a problem. Almost every platform offers a way to use non-CAPI crypto. In fact CAPI crypto was deprecated with Windows Vista -- but .NET Framework still offers the old CAPI stuff. Using the newer CNG API requires either P/Invoking from .NET, or using a Security.Cryptography.dll library Microsoft dropped on CodePlex back in 2010 and hasn't touched since, and it comes with its own limitations.
The requirement I was working toward of course was to get a private key generated on iOS to work in PCLCrypto on every other platform. Mono.Security.dll offered a way: it has a managed RSA implementation that doesn't depend on the CAPI file format. So when targeting the .NET Framework, PCLCrypto would first try using the platform (CAPI) and if the RSA key isn't compatible with it, it falls back to the mono managed implementation of RSA. Why not use CNG? Well, I tried, but it doesn't let you import keypairs. Go figure.
That just left Windows Phone. How was I going to get these iOS-generated private keys working on Windows Phone 8.0, where P/Invoke is not allowed and the only RSA implementation is CAPI-based? CNG isn't an option. Mono.Security.dll doesn't target WP8, and while it target Silverlight and its RSA implementation seems to work on WP8, it lacks OAEP padding support which is a requirement. That's actually where I'm at with WP8: it can't import private keys generated with iOS today.

To repeat the summary at the top: all this study and sweat over the past few weeks has gone into PCLCrypto so that you can use the very simple API for many kinds of crypto including exchanging private keys in a variety of formats and between most platforms. You can reference it from your PCL library or your desktop, store, or mobile apps. It's also free and open source, so please check it out, send feedback and pull requests.

Would you like to donate to express thanks for the project?
Donate Bitcoins

Why am I doing all this? Two reasons: I enjoy contributing whatever I can to the community, and it helps me deliver Dart, my mobile app that provides more privacy in your communication than any other app.

No comments:

Post a Comment