September 30th, 2012, 05:10 PM

RSA / encryption method strength
Hello, all.
I'm no cryptography expert, but today I put together a system that will be used to store highly sensitive information "out in the cloud"  so I've tried to make it as secure as possible using RSA.
I understand that the generally accepted practice is to use RSA to share a symmetric (e.g. AES) key, but in this particular case, I've chosen to instead use a combination of CBC with RSA to encrypt the data in chunks (using the same key, for practicality reasons).
i.e. To circumvent the length restrictions of RSA, the data to be encrypted is broken into chunks and each chunk is encrypted. Additionally, prior to the RSA encryption, each chunk is XOR'd against the previous chunk (in its postXOR state).
My question is, is there a direct security weakness caused by this implementation compared to the usual symmetric system? Speed is not an issue as this information will be accessed very rarely.
Thanks in advance.
October 3rd, 2012, 12:19 AM

Originally Posted by JNR
Hello, all.
I'm no cryptography expert, but today I put together a system that will be used to store highly sensitive information "out in the cloud"  so I've tried to make it as secure as possible using RSA.
I understand that the generally accepted practice is to use RSA to share a symmetric (e.g. AES) key, but in this particular case, I've chosen to instead use a combination of CBC with RSA to encrypt the data in chunks (using the same key, for practicality reasons).
i.e. To circumvent the length restrictions of RSA, the data to be encrypted is broken into chunks and each chunk is encrypted. Additionally, prior to the RSA encryption, each chunk is XOR'd against the previous chunk (in its postXOR state).
My question is, is there a direct security weakness caused by this implementation compared to the usual symmetric system? Speed is not an issue as this information will be accessed very rarely.
Thanks in advance.
Hi JNR,
Sorry, but I'm having trouble following your logic here  it would help if you could give a mathematical representation of exactly what you're doing with your plaintext bits (each block of them in this case).
From what it sounds like you're encrypting your plain text bits using the CBC encryption mode with RSA as the standard CBC pseudorandom function. Though most likely computationally secure, your scheme sounds very inefficient and unnecessary given the tools available to you. CBC is, of course, a very secure blockcipher mode (indistinguishable against chosen plaintext attacks, in fact) and RSA is computationally secure as well given a sufficient key size and implementation time but it sounds like there is absolutely no reason to use RSA instead of a symmetric key encryption scheme like AES or 3DES in your case. The main advantage of asymmetric key encryption is that it allows parties to send secure ciphertexts without having a mutually known (private) key. In your case, the data will just be sitting there, waiting to be accessed, so you are basically using public key encryption in a private key setting, if that makes sense. Furthermore, you'll still have to store your private key for RSA which will most likely be at least 1028 bits long.
In summation, there is no discernible weakness in your implementation other than the fact that RSA is exponentially less efficient and secure than a scheme such as AES or 3DES. May I ask why you elected to encrypt your data with RSA rather than with a symmetric key system?
October 3rd, 2012, 05:58 AM

Hello, Decave.
Your response sounds promising so far; I'll attempt to now clear up some of the confusion.
This is a remotelyhosted system which will be used to store and retrieve ad hoc information of a sensitive nature. For that, the information must be encrypted by the server as it is entered into a form, then decrypted on request.
Decryption will be done when the user (e.g. myself) requests a specific "file" and enters the private key (base 64 encoded) and the initialization vector (for the first XOR block).
The idea here is that, anyone who gains any access whatsoever to the server has a restricted ability to immediately decrypt the data  even with access to the code, keys stored on the server, etc.
Ultimately, this is intended to be hostproof.
Computational efficiency isn't an issue as this system will be used perhaps once or twice per month at the maximum.
Regarding the XOR CBC: Encryption takes the form of:
plaintext > XOR against initialization vector > XOR'd data becomes the vector for the next block > XOR'd data is encrypted using RSA
By my understanding, this means that even if one RSAencrypted block is broken, the adjacent block must also be broken.
Hopefully this gives you a better understanding of my motives. I welcome further input/criticism.
October 3rd, 2012, 01:05 PM

Hey JNR,
Thanks for clarifying. I might not still be 100% on the same page as you (in general, descriptions of systems like these are usually done more formally i.e. we have a ciphertext c defined as c_i := F(c_(i  1)) XOR mi ) but it's not completely necessary and I'll do my best to help you without it.
I'll start by saying that it's a security flaw to have your user input the IV as well as a private key when obtaining the decryption of a file from your server. IVs are used (in generally, sometimes they can be used to maintain state) to make an encryption scheme probabilistic, meaning that an adversary A cannot obtain a plaintext/ciphertext combination and then XOR that plaintext with the ciphertext to find the pseudorandom string that was created in the block cipher (CBC). Doing so, the adversary can then XOR that pseudorandom string with any future ciphertexts to obtain the underlying plaintexts. If a new IV is used for every encryption then the pseudorandom string will change for every encryption (while still being deterministic); preventing a very dangerous and easily implemented attack.
What would be a better approach is to have your encryption system generate a uniformly random IV for each different ciphertext that is encrypted and have it be stored as the first block of ciphertext. This would cause your scheme (assuming that you're implementing the rest of the scheme correctly) to be "chosen plaintext attack" secure  a MUCH stronger definition of security than plain indistinguishability against an eavesdropper. Note that the practice of generating a random IV for each implementation of IV should be done regardless of what pseudorandom function you're using for CBC.
Continuing, I still believe that AES would be a better tool for you to implement than RSA. From what I can tell, there is no advantage to using RSA in this scenario as you have the ability to store your private key safely, and AES is more secure, more efficient, can take in a key of size only 256 bits, and is based on a much stronger assumption of security than the difficulty of factoring. Note that "efficiency" is more than just the speed at which your computer implements a system  it is also the level of security achieved from an encryption scheme and the degree of "negligibility" that an efficient adversary is afforded in attempting to break the scheme. Both RSA and AES are computationally secure, but AES will be both easier for you to maintain and for your clients to interact with, as well as more secure. You should be able to easily set up a protocol that immediately decrypts the requested files even if they are encrypted with AES.
I hope that helps  remember that even if you elect to go with RSA that you absolutely must have your system encrypt choose a NEW uniformly random seed for every implementation of CBC. Not doing so leaves your system vulnerable to any competent and efficient adversary.
Comments on this post
October 3rd, 2012, 05:15 PM

Hello again.
Apologies for the lack of formal terminology; I don't know any of it. I'm more of a programmer than a cryptographer.
After what you've said about the CBC/XOR and after having thought about it some more, I think I've identified several weaknesses in my current XOR method.
My reasoning for keeping the "IV" separate was because I figured it'd eliminate the risk of an attacker just targetting the first block and getting the IV first. However, I guess it's more concerning that they'd potentially be able to decrypt all other encrypted files and blocks using the same vector.
I also notice that, using the postXOR block as a vector is flawed, as it's readily usable asis without having to be broken; the original block data would surely be a more secure method? Again, my reasoning here was that if an attacker were able to reverse the XOR (frequency analysis, etc), they'd be able to get two blocks worth of data from just one block.
Thanks again for your comments.
October 3rd, 2012, 05:26 PM

No problem  happy to help. You don't have to worry about the adversary getting your first block of plaintext because you run it through a pseudorandom function after XORing it with the IV so it still appears unintelligible to the adversary.
This is how I recommend implementing your CBC method:
1) XOR uniform, random IV with your first plaintext block, m1
2) Put m1 XOR IV through pseudorandom function (RSA, AES, etc)
3) Output ciphertext c1
4) Do F_k(c1 XOR m2) and output that as ciphertext c2
5) Repeat for all c_i = F_k(c_{i1} XOR mi)
6) Concatenate c1c2...ci and you have your ciphertext
A visualization of the scheme can be seen here: http://upload.wikimedia.org/wikipedia/commons/d/d3/Cbc_encryption.png
Also, note that F_k(m) is just notation for a psueodorandom function with key k and message m as input. Good luck!
P.S. I still highly, highly, highly, highly recommend using AES
Also, note that your scheme does not ensure authenticity which is an entirely different game altogether.
October 3rd, 2012, 05:46 PM

Hello again.
There's a few parts to your reply there that have confused me.
Mainly, where you say about using the ciphertext/s as the XOR vector/s. Does this not just make it even easier to break the XOR encryption? As I understand it, the purpose of CBC is to necessitate cracking two adjacent blocks to be able to revert the XORencrypted text back to plaintext.
But if the XOR vector is c1 and is sitting out in the open right next to c2, isn't it just ready to be used asis?
Also, would you be willing to elaborate on the authenticity point  or point me to the relevant reading material?
October 3rd, 2012, 07:21 PM

The purpose of CBC is to prevent various kinds of attacks, not just one. It's main purpose, however, is to give your encryption scheme what is called chosen plaintext security; meaning that if you have an adversary (running in polynomial time) who can submit plaintexts to an encryption oracle (basically just a blackbox that encrypts plaintext messages and sends their ciphertexts back to the adversary) then with a properly implemented CBC scheme using a pseudorandom function, the adversary will not be able to crack your scheme with greater than negligible probability. Even this level of security, however, is rather low on the totempole standards as it's completely insecure against an adversary who has the power to query ciphertexts and receive their plaintext decryptions.
Authenticity refers to when you append a tag to your message that verifies its authenticity as being sent from the source you intended and in the correct order, length, etc. For instance, in your case, you would want to make sure that when you requested a file from the server, that a third party attacker was not intercepting the request and sending you a false file instead with malware or other malaties. More can be seen here: http://en.wikipedia.org/wiki/Message_authentication_code
I don't mean to give offense, because this is a very common problem that a lot of great programmers and IT experts run into, but based on what you've told me I very highly recommend outsourcing this task to a reliable professional service that will take care of it competently and obsequiously. The unfortunate thing about cryptography is that the entire process is very, very fragile. In analogous fashion to a rubix cube  though it's relatively simple to solve the top layer, it's essentially meaningless until you know how to solve the much more difficult middle and bottom layers as well. Furthermore, the whole process has to work in harmony or the whole thing won't work at all. With cryptography, many different mechanisms are at play, with some of them drawing on math as complex as Galois field theory.
If the information you are trying to protect is highly sensitive, and the compromising of such data would put you or your company at risk, then I absolutely urge you to hire a professional to protect your data. What we've discussed so far is only the very bare surface of computational security and if you implement the scheme yourself then you are simply opening yourself up to an inevitable attack.
If you have any questions, I'd be happy to help, but I may not be able to respond until this weekend because I have a few projects that I'm trying to finish before Friday evening. Also, if you could give me reputation points for my responses then I would greatly appreciate it (I think that all you have to do is click the scales of justice in the top corner of any of my posts). I just started at this forum but I intend to be a regular contributor for people such as yourself. Again, best of luck.
Comments on this post
October 4th, 2012, 07:21 AM

While I readily accept I'm not the ideal candidate for this task, for better or for worse I am the company's best hope in this instance (for many reasons).
I am using OAEP in this RSA implementation. Does this not go some way towards addressing the concerns of your first paragraph?
Furthermore, what security does the CBC offer against a chosen plaintext attack if the attacker is able to XOR their plaintext prior to encryption, given that the XOR "key" is the previous ciphertext sitting in plain sight?
All other security concerns have been addressed; I've omitted everything from this thread not directly related to the cryptographic strength of the implementation.
Thanks again for your contributions. "Reputation" will be given as soon as I figure out how to do so.
October 4th, 2012, 11:10 AM

I see, well, let's do our best to make sure you nail it. Yes, OAEP has been proven CCA (chosen ciphertext attack) secure so that's a great idea and it does address the concerns in my first paragraph when correctly implemented. I will now address your second question:
Your concern about CBC is valid. In fact, what you just said is the way that decryption is performed in the CBC model! Remember, however, that if you use a random, uniformly chosen IV for each encryption then you're going to have a different ciphertext every time you encrypt the same plaintext (with probability 2^{n}). This means that even if the adversary queried an encryption oracle with the exact same plaintext after it was encrypted once, he/she would only be able to recover the pseudorandom string/previous ciphertext outputs for that one instance (because the IV will change) and would therefore not be able to use it to decrypt any future instances of encryption. So, if the adversary XORd the plaintext as you said and recovered the underlying pseudorandom string then it would only be of use to him if he had access to subsequent encryptions with the same key and IV (this, of course, goes back to my suggestion about using a random, uniformly chosen IV for each encryption).
Furthermore, notice that the adversary has to KNOW the plaintext before he can gain any information from the scheme. In the (generally far more stringent yet still applicable) security parameters of research and theoretical applications, an adversary can query a polynomial number of plaintexts and received an instant decryption of them. In the real world, the adversary can still obtain this power, but with a properly implemented system it's very unlikely that he have access to any of your data to know what to XOR with in the first place!
Hope that helps.