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?
I assume you follow Kerckhoffs' 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.