Exhaustive key search

Question

Suppose that an attacker has got hold of a piece of ciphertext that has been encrypted by a modern cryptosystem. How effective is an exhaustive key search if: a) The attacker will be trying out each key by hand? b) The attacker does not know the encryption algorithm that was used? c) No previous plaintext / ciphertext pairs are known, and the plaintext is known to be completely random? d) One previous plaintext / ciphertext pair is known, and the plaintext is known to be completely random?

Answer 1

If a blockcypher was used
If the key is sufficiently long(say 128 bits) and completely random then exhaustive keysearch/bruteforce is too slow.

To crack it you need either break the crypto algorithm, or use mistakes in the key generation which result in low key entropy.

If you don't need to recover the key attacks on the cyphermode might be possible too.

If a stream cypher was used
Then your d) scenario will be broken. The attacker can't recover the key. But since a stream cypher is usually used to create a one-time-pad which may only be used once the plaintext of the message can probably recovered.

Answer 2

Suppose that an attacker has got hold of a piece of ciphertext that has been encrypted by a modern cryptosystem.

It doesn't really matter for any of your questions below, but there are a lot of different kinds of crypto systems. Usually the properties guarantee that messages cannot be "decrypted" or "changed"

Let's talk about shared-key cryptosystems. In these systems, we have two machines, let's call them Alice and Bob, trying to communicate. Let's say Alice is trying to send a message to Bob. (Bob can then use the same system to send an algorithm to Alice, so we don't have to worry about two-way communication.) An adversary, let's call him Charlie, tries to "decrypt" messages sent by Alice or "change" them in order to fool Bob into thinking Alice sent something that she did not.

Defining such a system carefully is too subtle to go into detail, but see Chapter 5 of Goldreich's text book for a fuller definition. The upshot is that the adversary is extremely powerful in this model and in any useful cryptographic systems. That is, even very powerful and flexible adversaries should not be able to break these systems. Most of the attacks you can think off of the top of your head are probably already contained by the definition. That is, the system is probably guaranteed to resist your attack.

How effective is an exhaustive key search if:

edit: The rest of your question makes it pretty clear that you want to know how easy it is to break algorithms. Exhaustive key search is only one way to do it, and you always do it the same way. You just cycle through the keys! It doesn't matter what else you know.

a) The attacker will be trying out each key by hand?

There is nothing to guarantee that an attacker couldn't look at ciphertexts work them out by hand. All of the definitions assume the adversary works in an automated way. But if you make the reasonable assumption that people can be simulated by computers, this doesn't really pose a problem. In practice, someone trying to work through the problem by hand is probably just as unlikely to succeed as someone trying to write an automated adversary for the system.

b) The attacker does not know the encryption algorithm that was used?

This won't make any difference.

We always assume that the adversary knows the algorithm. sort of. You can think of a key in the shared-key crypto system above as automatically selecting an appropriate algorithm for encryption and decryption. But it's a good idea to avoid talking about designing "secret" algorithms, which some people call "security by obscurity," for two reasons:

1. Unlike keys, which can be generated quickly and shared between two parties, algorithms take time to develop and are shared among all of them. That means the secrecy of an algorithm is much more likely to be compromised.
2. It is very difficult to know how "secret" an algorithm is. We like to think that we are very clever and unpredictable when we create these algorithms, but we probably are not. Someone reverse-engineering our algorithms may be able to guess what we are doing. In practice, if an algorithm is not already secure on its own, its secrecy will not prevent it from being broken.

In other words, using secret algorithms is unlikely to make a crypto system more secure, either in theory or in practice.

c) No previous plaintext / ciphertext pairs are known, and the plaintext is known to be completely random?

d) One previous plaintext / ciphertext pair is known, and the plaintext is known to be completely random?

In any reasonably defined crypto system, the adversary is allowed to see as many plaintext/ciphertext pairs he wants. In fact, in the shared-key cryptosystem above, there is no guarantee that the plaintext is chosen randomly. No matter how "bad" the distribution of plaintexts are, it's still not possible to "decrypt" the encryption of a new plaintext message.

Without that very robust definition, encryption schemes would be useless. Imagine an encryption scheme that worked on random plaintexts but not on English words. You'd have to be very careful about what kind of plaintext you used it on! It's actually easier to make sure cryptosystems work for all distributions of plaintexts, which is stronger.

Crypto isn't all that difficult, but it is very subtle. Most of the subtlety is due to trying to guarantee that very broadly defined attacks do not break cryptosystems.