If I have the plain text and its output after encryption with a key K1, is it algorithmically feasible to find K1?
I am specifically interested in the cases of DES and AES encryption algorithms.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ The only way to do it would be to encrypt your message with every possible key, and check the result. But that's basically bruteforce $\endgroup$– FaulstCommented Apr 25, 2018 at 11:46
-
1$\begingroup$ As @Faulst mentioned, you would have to bruteforce each key when the cipher is secure. When the cipher is insecure, known plaintext/ciphertext-pairs can allow linear cryptanalysis and similiar known-plaintext-attacks. $\endgroup$– VincBreakerCommented Apr 25, 2018 at 13:24
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
The most cost-effective way to do this is to try each key and see if it works. The expected number of trials is $2^{55}$ with DES, $2^{127}$ with AES-128, and $2^{255}$ with AES-256.
You can speed the search up by making many trials in parallel, e.g. by using a million DES circuits making one trial every microsecond, which will give an answer in a few hours, at most under a day—a task that has even been commercialized (note: I do not endorse this commercial service; I am only mentioning it for practical scale comparison). Note that parallelizing the search doesn't change the overall cost: powering a single circuit for an hour will cost approximately the same energy, and same number of rubles, as powering sixty circuits in parallel for a minute.
If you have many keys $k_i$ which you want to recover any one of given their respective ciphertexts for a common plaintext, then you can do better with a parallel machine that saves repeated effort using Oechslin's rainbow tables. Say you have $n$ target keys. A machine parallelized $n^2$ ways with each parallel circuit not much larger than an AES-128 circuit, with a small constant amount of memory for each circuit, can give you your first answer with probability $p$ in about $2^{128}p/n^3$ time, at the same cost as about $2^{128}p/n$ AES-128 evaluations.
For AES-128, these numbers are large, but not unimaginably so. The Bitcoin network today performs about $30\times10^{18}$ SHA-256 computations every second, about $2^{64}$ per second or $2^{90}$ per year. If we had trillion ($10^{12}$) AES-128 circuits in parallel attacking any one of a million ($10^6$) keys, we would break at least one of them with high probability using a couple hundred thousand times the annual cost of the Bitcoin network (which has been increasing exponentially since about 2015), assuming the cost of one AES-128 evaluation is approximately the same as that of SHA-256.
Can you break AES-128, or any generic 128-bit function, using this method? No. Can humanity? Maybe. But definitely not AES-256 unless there's a cryptanalytic breakthrough. (Quantum computers don't make much of a dent in AES-256 or even AES-192 either.)
answered Apr 25, 2018 at 19:25
$\begingroup$
$\endgroup$
6
In the case of DES and AES, it turns out that having a plaintext/ciphertext pair does not really make finding the key any more feasible than just having a ciphertext.
As you are hopefully already aware, DES does not have a large enough keyspace to be considered secure in practice. It is susceptible to brute force attacks and therefore should not be used. That is irrespective of whether or not the adversary has a plaintext/ciphertext pair or just a ciphertext.
For AES, brute force attacks are not feasible and giving the attacker 1 or many plaintext/ciphertext pairs does not make any known attacks on AES feasible.
This type of attack is generically known as a known plaintext attack. It use to work on classical ciphers, but all modern ciphers used in practice have been specifically designed to thwart such attacks. In fact, we typically assume that attackers have access to plaintext/ciphertext pairs. Consider the encryption of an HTML document, for example. There is a lot of header information there that an attacker would be able to trivially guess.
-
3$\begingroup$ DES is since over 20 years broken for known plaintext attacks. $\endgroup$– NovaCommented Apr 25, 2018 at 13:34
-
1$\begingroup$ @Nova, source? DES is broken. I completely agree with that. But DES is broken (in the practical sense) because it's keyspace is too small, not because of some sort of known plaintext attack. Otherwise why would people use 3DES? See also: this answer and this question and answers. $\endgroup$– mikeazoCommented Apr 25, 2018 at 13:50
-
$\begingroup$ I refer to common brute force for my claim that DES is broken. I don't see a reason to exclude it when it's fast enough to be practical. crypto.stackexchange.com/questions/24320/… - 3DES is more or less another cipher. Attacks on DES don't need to be extendable to 3DES. $\endgroup$– NovaCommented Apr 25, 2018 at 14:03
-
$\begingroup$ @Nova, my point is, the brute force attack on DES has nothing to do with known plaintext/ciphertext pairs. If all I had was a ciphertext I could still run the brute force attack. I might have a hard time telling which output is correct, but I can still run the attack. In practice, if I even know a little bit of information about the plaintext but not the whole thing (maybe just some indirect contextual information about it), I can, with high confidence, pick the right plaintext. $\endgroup$– mikeazoCommented Apr 25, 2018 at 14:12
-
2$\begingroup$ @mikeazo I think the discussion whether brute force should be considered an "attack" is largely irrelevant here (and, arguably, a matter of personal taste). The question was whether it is feasible to recover the key given a plaintext-ciphertext pair, and for DES the answer is clearly yes. That this "attack" is no faster than brute force (since it is brute force) doesn't really matter if your security level was 56 bits to start with, unless you're engaging in a discussion about the meaning of certain words. $\endgroup$– yyyyyyyCommented Apr 25, 2018 at 17:04
$\begingroup$
$\endgroup$
DES: the key length is short enough to brute force it. One known plaintext-ciphertext is enough to get the key(s). There is at least one website which offers to crack one of these for $30 in a few days.
AES: there's currently no practical way to crack a fully random AES key just with known plaintext-ciphertext pairs. Even with some more informations AES appears secure unless things like timing attacks or related keys come into account. (As of 2017)
$\begingroup$
$\endgroup$
One of the main goals in cryptography is to avoid making information known by acquiring the plaintext, ciphertext or both. In both of these encryption techiques each bit in the subkey changes no less then half the bits in the ciphertext (ideally) and after your number of passes through the algorithm it makes any known knowledge no more useful then a brute force attack. Even the number of times it passed through the algorithm respectivley for each DES, and both AES systems is by desing to ensure this. While these aren't the most secure of crypto systems anymore they were at the time of their implementation and were designed in a manner that any known information won't give you any other information about the system. So even today the best attack and probably only attack, is brute force.