Why cripple the .NET RSA implementation?

Posted on by

I just found out that RSACryptoServiceProvider, the RSA implementation in .NET, does not allow you to use a private key to encrypt data. I’m no cryptographic expert, but I do know how asymmetric key algorithms like RSA work, and that you can use a private key for encryption. That’s how signing works. But why cripple the implementation and limit it to just signing?

The rationale is in the common application of public-key cryptography, where:

  • Encrypting with the public key ensures confidentiality, i.e. the process known as encryption in common tongue. Encrypting with a public key ensures that only the entity in possession of the private key can read the data.
  • Encrypting with the private key ensures authenticity, i.e. the process known as signing in common tongue. There is no need to encrypt the entire data stream to ensure authenticity, so the common approach is to calculate a hash of the data and sign the hash instead.

To facilitate these patterns, the .NET public-key cryptography API is designed so that:

  • Encrypt() encrypts with a public key, Decrypt() requires a private key.
  • SignData() encrypts with a private key, but since that implies a signature, one must provide a hashing algorithm and a private key. VerifyData() uses a public key.

But I want to encrypt with my private key! Yes, this is what SignData() does, but it does so to just the hash calculated by the provided hashing algorithm, since that is the de-facto approach for signing, and implementing my own HashAlgorithm that passes in all the data is just wrong.

OK, these are the common uses, but why limit the API to that? There is no limitation in the RSA algorithm to my knowledge that prevents other uses than the two offered by RSACryptoServiceProvider. In fact, if I wanted to perform the traditional signing approach, I could just hash the data myself and encrypt it with my private key myself. Or even better, SignData() could be available to help me for convenience.

So, how do you apply RSA in .NET in an uncommon manner? Don’t use .NET’s cryptography API, but embrace an open source alternatives like BouncyCastle, which saves your day.

  • http://www.ciphersign.com Jingsong zhang

    I think because RSA private key encryption for a longer string is very slow.

  • http://larswilhelmsen.com/ Lars Wilhelmsen

    Hi,

    I believe Jingsong’s argument is correct. Asymmetric chiphers is ideal for solving the key sharing problem – but is not suitable for encryption of large amounts of data since they are quite CPU-intensive in computation.

    The way it works is that a shared secret – a key for the symmetric chipher – is encrypted with the asymmetric chipher – in this case RSA – and sent to the recipient. The recipient decrypts the shared secrets and uses it to decrypt the actual data.

    To validate authenticity a keyed or unkeyed hashing algorithm is applied; SHA-* is the most commonly used unkeyed algorithms used nowadays – and this hash is signed. .SignData(…) does this for you in the .NET crypto API.

    –larsw

  • http://ox.no Håvard

    Hi Lars and Jingsong,

    Your arguments and points are indeed correct. My point is that only allowing hash signing with the private key is an artificial limitation, since the real limitation lies in the time required to encrypt a relatively large amount of data using the private key.

    It is my opinion that the API should not protect you, or limit you, if you will, from doing something that is valid to do, although the usual approach is different. I apologize if my post implied something else than this.

  • Antonio

    Hi Håvard,

    I very much agree, I’m a bit frustrated by this aspect of the .net implementation myself. I’m working on a project that deals with ensuring the authenticity of information on ATM smart cards, which have sensitive data on them encrypted with a CA private key to ensure authenticity, so i need to be able to decrypt with the public key. Sign/verify just isn’t what I need, since I’m not the one putting the data on the cards.

    I’ve had a look at bouncycastle, but i found the library to be a bit hard to work with, due to the abundance of classes and the lack of documenation.

    Could you pls provide a few lines of example code for decryption with a public key using bublycastle? TIA!

  • http://ox.no Håvard

    Hi Antonio. I wrote a quick post on using BouncyCastle for RSA. Take a look at RSA using BouncyCastle. Hope it helps!

  • Antonio

    Hi Håvard,

    I ended up implementing RSA myself the same day I posted my question to you, but thanx anyway:) The implementation was trivial, RSA is explained well on wikipedia and the algorithm amounts to a single few-letter formula. All that’s needed besides the formula is an implementation of BigInteger(to represent the encrypted text and the key), which I found on codeproject(a very good one i might add, by a chap called Chew Keong TAN – he’s Danish apparently:))

    Anyway, just wanted to say thanks for posting the “RSA using BouncyCastle” (now that I see the code it seems simple:)) even tho i didn’t end up using it.

  • innocent bystander

    thank you for your post – I had exactly the same problem

  • Abhinav

    I’m facing the same problem. Did not want to implement and maintain RSA in my code, and could not find an opensource alternative.

    Lets see how Bouncy Castle works out!

  • Stuart

    I know this thread is a bit old, but I came across it via Google and felt I had to post this disclaimer in case anyone came across this “information”. RSA is an extremely fragile cryptosystem you should never try to roll your own way of using it – why?

    The problem is that RSA (i.e. the C= P^e mod n) stuff is NOT SECURE!!!

    Naive RSA can be broken easily, and only things like OEAP padding actually make it work. Things that do not work… Encryption without correct random padding, Encryption with the private key, signing raw data without padding it first. There are trivial mathematical attacks for all these cases (and not just theoretical ones – most can be performed in seconds).

    Also you should always hash before signing and never encrypt your data directly with RSA but encrypt a random symmetric key instead. Many people incorrectly state these restrictions are for performance, while true, not observing them can also dramatically reduce your security with RSA and considering 1024bit RSA only offers (at best) 80bit security you really don’t want to weaken it further. In fact modern adaptive plaintext attacks can reduce it to just about 20bits! A.k.a nothing.

    The reason the crypto API doesn’t let you do this is because you should NEVER do these things. OK, not never (with the exception of private key encryption – there is a very good LIST of reasons why the public exponent is small) but in most cases the list of conditions are as long as your arm and most cryptographers wouldn’t touch it with a 40 foot pole.

    Disclaimer: I am not a cryptographer but a software developer & security specialist, but I have found enough out to know what doesn’t work…

  • http://ox.no Håvard

    Stuart,

    You’re mixing different security concerns regarding PKI in general, RSA in particular, RSA key strength vs symmetric key strength, and a bunch of other things here, and you’re not doing well.

    First of all, RSA is secure under the assumption that factoring large primes is hard and cannot be solved in polynomial time. Sufficiently large keys are of course needed, and as machines grow faster, larger keys are required to avoid possible brute force attacks.

    With all respect, you’re wrong, and you’re confusing and misleading people by posting such comments. Don’t claim to be an expert a specialist when you really are not.

    Certainly not a security expert, – Håvard

  • Stuart

    I never claimed to be an expert. But suggesting that RSA private key encryption is generally a good idea is extremely misleading…. While I can sympathise with those who are constrained by existing interoperability requirements and hardware restrictions to suggest that this is the preferred strategy (without cautions) and that the crypto API is somehow deficient for not providing it is simply reckless. I can only imagine naive programmers coming across this post and assuming this is a reasonable approach in all cases. You may have supreme confidence in your abilities, and I would in no way question that. However, many on the internet are not so blessed and adding a few cautions would not be amiss. I am sorry but I tone I got from both your blog and your reply was as if you take little regard for these issues. RSA is particularly susceptible to adaptive plaintext attacks. If you allow attackers to pass data to be signed straight to your RSA “signing” function they can amount these attacks with ease. You, might say that only I provide the data to be signed, and if that is the case then good luck to you, but (and there is always a but) what if users get sloppy or a summer student comes in to clean up your old code? These apparently arbitrary restrictions may be questioned (after all its RSA so secure right?). Attackers very rarely come in through the front door and if they can convince people to sign apparently harmless things or “corrections” the mathematical nature of RSA will be your undoing. This is precisely the reason that padding with Hashing or random symmetric keys are mandated by the various standards. They may not apply to YOUR problem but they do apply to many problems and this is the distinction that I feel your advice lacks. Additionally, I never questioned the prime factoring problem as being hard, but with all due respect that is not the same as the RSA problem that depends on it. RSA makes further assumptions which may/or may not hold. e.g. without random padding encrypting the same message (or related messages) more than e (the public exponent) times you can employ Chinese reminder theorem to break the encryption (as stated on the Wikipedia article itself). If d is not much larger than SQRT(N) then N can be easily factored. When M << N, M can be found by C^1/e Etc. Etc. Etc. There are in fact so many conditions that RSA is usually considered insecure without additional hardening. In regards to the comparison to symmetric strength what would you have me do? You need some kind to ruler to measure an algorithm’s strength by and equivalent symmetric strength is the yardstick that is generally accepted. Numerous sources have repeatedly stated that 1024bit RSA is no stronger than a perfect 80bit (some even suggest even this may turn out to be optimistic) symmetric cipher based on the factoring time by the GNS and TWIRL algorithms. I think this brings home an important point since I have repeatedly seen people demand 256bit AES yet happily protect it with 1024bit RSA. Adaptive attacks lower the security bound further e.g. without blinding RSA decryption oracles can leak the private key less than a million (2^20) queries I never meant to question your knowledge of this matter, ability or even to come off as some kind of “expert” (I personally regard implementing a secure RSA cryptosystem as beyond my knowledge) but this a complex issue with many hidden pitfalls that should be stressed in any public discussion. If RSA themselves can introduce weaknesses in their padding schemes what hope do non-expert programmers have?

  • http://ox.no Håvard

    Stuart,

    I corrected “expert” to “specialist” in my previous comment. I apologize for the misquote.

    First of all, again, RSA is a secure algorithm. Use RSA with a sufficiently large (> 1024 bit) key size. It is secure. Your bank uses it. The web uses it. Your digital life depends on it.

    Let me try to repeat and perhaps clarify a point made in the post for you: Signing (the operation supported by the .NET API) is no different from encrypting with your private key. In fact, you are simply encrypting the calculated hash with your private key. This means you’re still using RSA, which means you’re no more secure than you would be without the symmetric cipher. The symmetric cipher is introduced for speed. (And in fact, introducing a symmetric cipher into the plot raises new security concerns, but that’s far beyond the scope of this comment.)

    You’re mixing paddings and blinding into the equation as well. These are manners taken to avoid attacks such as chosen plaintext attacks or chosen ciphertext attacks. You should of course use an RSA implementation with padding, or use blinding RSA, if you require protection against such attacks (and you usually do). My post does not state otherwise. (In fact, such RSA implementation concerns do not affect the point of the post.)

    Claiming that I do not consider security issues, based on an article does not discuss RSA as an algorithm, its strength, or other security aspects, is beyond my understanding. Beyond that, I’ve tried to answer and shed light on your claims regarding RSA.

    I recommend my readers to turn to a good book such as Network Security Essentials by William Stallings if they want an understanding of public key infrastructure and public key cryptography in general, RSA in particular, and other network security topics.

  • Stuart

    I feel you are still missing my point. While RSA “can” be perfectly secure it is not IND-CCA2 secure and this is the problem since many theoretically secure systems are let down by poor implementation.

    If you give and attacker the ability to encrypt anything with RSA they can try to encrypt a series of adaptively selected smooth numbers and determine the exponent. Normally, this is not an issue since the exponent e is public but in reverse this kind of attack can leak enough information to obtain d very quickly. Obviously using a collision resistant pseudo random hash can act as a barrier here (since an attacker can not easily generate messages that hash to the needed smooth numbers in these adaptive attacks) and hence its use in signing operations (along with obvious practical concers). If you remove this barrier then you need to ensure the rest of your implementation (e.g. padding and source of signed material) is bullet proof.

    I am not in any way suggesting it cannot be done, but in blog you ask why .net does not let you do this. The answer is obvious: it is a black box API designed to provide easy crypto to inexperienced devs. Why would they give their own development community enough rope to hang themselves with? Bouncy castle is a low level API designed for those who know what they are doing and thus for a completely different audience (I guess this includes you). Why do think that private key encryption is always referred to as signing? To discourage inexperienced people from thing of it as encryption (even though that’s exactly what it is).

    Rereading my post today I feel I may have a first come off as overly critical, and for that I apologise. Really my only criticism is the title of the blog since I would be appalled if Microsoft provided the functionality you ask for to the average windows developer.

  • http://ox.no Håvard

    Again, please keep in mind that the post says nothing about the implementation of RSA. It focuses on the API offered by .NET. Whether or not the actual RSA implementation includes padding and other protective measures is irrelevant to the post; the API can provide private key encryption regardless of these “implementation details”, but currently does not.

    You make some valid points regarding RSA security considerations in your latter response, but you’re still creating a blend of different concerns which have partially different reasonings and purposes, and all of which are beyond the scope of the post. If you want to discuss these issues further, I suggest a newsgroup or a forum which actually considers these aspects of RSA.

    What remains is that you are saying is that you think Microsoft limited the API to shield developers from implementing potentially insecure cryptographical solutions, which is a perfectly valid opinion.