AES 256 Encryption - Is it really easy to decrypt if you have the key?

So this might sound like a crazy question but bear with me for a minute. I can't find any info on the internet and so am here, although this might have been a good place to start.

I've recently developed an encryption engine using the .net's AES managed classes. I use a 256 bit key generated by the Rfc2898DeriveBytes function. The key is generated from a pass phrase that is at least 40 characters long. The IV is also generated from this pass phrase. The encryption class uses a CypherMode of CBC and a padding mode of PKCS7. There is a static salt that is 8 bytes long.

The key is stored in a separate database to the data and is itself encrypted using a certificate based on the database master key.

So, my question is: is it really easy to decrypt the data if the attacker has the key? I'm not talking about the Chinese government (or even GHCQ given recent headlines), I'm talking about an attacker who steals both databases.

What would be the steps they have to follow and/or how can I stop them on their path? The reason I ask this is that I want to know how feasible it is. Is it something that can be done in minutes or does it fall into the bracket of being infeasible? Do they have to calculate all of the parameters used when encrypting?

-
If the encryption mode (CBC) isn't known to the attacker, then ciphertext(s) of round block size lengths (16, 32, 64, etc) should be a pretty good clue. –  hunter Jul 17 '13 at 11:38
Can someone (preferably the person who did it) explain to me why this was down marked ? –  bhs Jul 17 '13 at 13:47
What is the unknown part? The initialization vector? The mode of operation? Something else? –  Paŭlo Ebermann Jul 17 '13 at 17:09

3 Answers

I assume you follow Kerckhoff's principle so the attacker knows the padding scheme and derivation function so the answer is yes, it only takes a few seconds to decrypt and anyone can do it.

If he doesn't know these things, he can find them by trial and error (assuming he can get his hands on a valid ciphertext).

The IV can be sent in the clear so making it depend on the key reveals some information on the key. It should also be unique for each session so I'm a bit worried about it. It should be OK if the KDF you're using is non-deterministic, which implies it uses its own IV so the problem remains. See this question for more on IVs.

Edit based on comments: The cracking procedure is the following: $a$ is the number of all modern ciphers. Let's set this to 100. $m$ is the number of modes per cipher, set it to 6. $k=100$ is the number of key derivation functions, $p=100$ are the padding schemes. The values are arbitrary. So we have $(p*k*m*a*c)/n = 6*10^6$ which equals to approx. 69 days with $c=1$ second and $n=1$ processor.

Your adversary will solve the problem in $69/2=34.5$ days. Not as practical but definitely feasible, especially if you throw extra processors at it. This solution is completly brute-force, it makes no attempt at distinguishing and pre-eliminating ciphers.

Since non-indistinguishability is a business requirement (really?) you could just get away with using ECB instead of any other mode.

-
Can you give an example of a non-deterministic KDF? Your concern about IV-generation is valid - if the OP is using a static salt (ie, doesn't change with each encryption) and the KDF used to generate the key/iv is deterministic (I'm assuming it must be if it's being used to generate the key) then logically the IV would be static as well (big no-no). To avoid this, the salt should be refreshed with each encryption. ThomasPornin addresses this strategy in some detail here. –  hunter Jul 17 '13 at 11:54
I see your point. I spoke before thinking on this one. Cheers @hunter –  rath Jul 17 '13 at 11:58
I'm not following Kerckhoffs principle. The attacker has the encrypted data and the key and nothing else. –  bhs Jul 17 '13 at 13:43
@bhs Then get out a time machine and travel back a few centuries. It is a core principle of modern crypto that it must be secure if the attacker knows everything about the scheme, except the key. –  CodesInChaos Jul 17 '13 at 14:52
Ok, so that would be the case. However, my question still remains. If I had asked a different question and Kerckhoffs principle applied then I'd be happy to accept your suggestion. To elaborate, the crypto isn't the question here, I'm working on the assumption that an AES256 encrypted value without the key is safe. –  bhs Jul 17 '13 at 15:08

So to clarify then the question would be this: The attacker has the encrypted data and the plain text key and no other knowledge. How easy is it to decrypt the data and why.

As I understand it, modern ciphers can't be broken knowing just the ciphertext (and no other information). But, the cipher algorithym (eg. AES) is only one part of a wider system using RNGs, keys, salts, IVs, padding, signatures, certificates, and so on. People have developed amazing exploits against tiny deficiencies in how those parts all fit together. So even though the ciper itself is secure, that does not mean that the system as a whole is secure.

Here's a simple analogue. SCUBA tanks have a threaded hole where the valve screws in. Some of those holes use a "3/4 NPS" thread, others use an "M25" thread. An M25 valve will screw "perfectly" into a 3/4 NPS hole - but those two threads aren't quite the same. Result: the valve can explode from the tank when it is pressurized. Each component is fine on its own; they seem to fit together correctly; an amateur won't see any problem; but the resultant system can fail catastrophically.

Crypto's the same!

TC

-
As a fellow diver I certainly appreciate your answer. I simply don't have time to become an encryption expert so need to make sure I satisfy the business requirements. –  bhs Jul 18 '13 at 9:10
@bhs: I'm currently renovating my apartment. Like you, I simply don't have time to get personal expertise in the relevant fields (in this case painting, plumbing, electrical, flooring, and so on). I can't just pretend that I can ignore that fact - do the work myself - and still get a good result! Instead I have to hire other people who know what they're doing. Aren't you in that situation? –  user7576 Jul 19 '13 at 4:33
no I'm not. I'm in the position where I just apply the paint to the walls. I don't need to know exactly how the paint was created, i.e. exactly what percentage of each colour makes up my paint. I went to a shop where there were experts in paint and asked them. They were very helpful. To answer your point a bit more fully though and put you in the picture there are several business requirements to meet and they have been met to the satisfaction of the business and the parties that are auditing. Academic arguments about minutiae are interesting and nice to know but not relevant. –  bhs Jul 19 '13 at 8:20
@bhs: You say the relevant business requirements have been met to the satisfaction of the business and the auditors. But, with all due respect, your whole initial question shows that you really don't know much about the issues involved. So my bet is, your system contains significant holes - but neither you, the business, nor the auditors, are able to see those. This is not an "academic argument about minutiae". But clearly we will not agree. Good luck! –  user7576 Jul 19 '13 at 11:14
I'm really curious as to how you come to this conclusion. If you develop a WinForms app are you already an expert on every function within Windows - all of it ? Every function within the .Net framework ? I get the feeling you're a bit of a troll and so will happily take your good luck and wish you a good day. –  bhs Jul 19 '13 at 11:37

To answer your question: yes, your system is really easy to break.

The more detailed answer: While you started out using the proper set of cryptographic primitives (AES-256 in CBC mode, PBKDF2, etc), these primitives only work if used correctly, and it sounds like you've used them so poorly as to make them meaningless. You want the following to provide all of the security of your protocol:

1. The fact that an adversary is unaware that you're using AES-256-CBC.
2. A fixed but unknown IV.

Item #1 isn't going to help you at all. If I'm given a ciphertext and a key but don't know the underlying encryption scheme used, I guarantee you that AES-256-CBC will be on my top 5 list of choices: AES is the most common encryption scheme used, the 256 bit version is its 2nd most popular variant, and CBC mode is the most common mode of operation. Moreover, please don't use this logic to say "okay, now I'll switch to a less ubiquitous encryption scheme; as rath showed above, that's not really going to help much.

Item #2 is bad for a few reasons. First of all, you're making the encryption scheme deterministic. You argue that you "must do this for business purposes," so I recognize the futility of trying to convince you otherwise. I hope we can agree at least though that deterministic encryption is a Really Bad Thing. It is necessary sometimes though, so cryptographers have tried to find the "best" (even if not good) way of doing it. Your solution is not that way.

I'm going to sidestep the question of "can all the security of AES-256-CBC be provided by the IV," because it's irrelevant here. The major problem is that (if I understand your idea correctly) you're reusing the IV. This is another Really Bad Thing, and that will allow an attacker to break your system easily as well.

I'm not trying to be mean here, but I think you're trying to have things both ways here. On the one hand, you're disregarding all of the expertise of 50 years of cryptographic research, and dismissing it all away as saying "I need to make sure I satisfy the business requirements." That's fine in and of itself; sometimes business needs impose burdensome constraints, and as long as you (1) understand that your scheme is weak as a result and (2) are willing to tolerate that, you're okay. However, you're also trying to get some reassurance from the Internet that your scheme is somehow still okay, and that's not going to happen.

-
Hi - thanks for your comments. I'm not trying to receive any assurance that my scheme is ok. It meets the requirements of the business and they are happy with it. My original question was if I used this scheme AND the attacker had the key how easy would it be to crack the data ? There are various protection mechanisms around the key itself so it's extremely unlikely an attacker would get access to both the data and the key. The encryption is not the only line of defence here, there are key coded doors and an isolated network segment to contend with. –  bhs Jul 19 '13 at 12:49
So - the requirement is that each value is encrypted in the database and a token is attached to each encrypted value. Further scans of the data MUST return the same token if an encrypted value exists already. Hence the need for the encryption function to produce the same encrypted value for repeating values. How would you implement this without having a static salt ? –  bhs Jul 19 '13 at 12:52
Also, periodically ALL data has to be re-encrypted as the key needs to be rotated. –  bhs Jul 19 '13 at 12:56
"and it sounds like you've used them so poorly as to make them meaningless". Sounds like a challenge ;-) Can you decrypt this value: 6mHdFjxwMWAee4W06x+Yug== –  bhs Jul 19 '13 at 13:00