19.6 Attacks on encryption schemes

If Eve attacks an encryption scheme utilizing available ciphertext, she can try to recover either the plaintext of the encrypted messages or the secret key itself used by the encryption scheme.

Recovery of the secret key is typically considered a stronger attack (or, equivalently, a more severe security compromise) than deducing plaintext from the ciphertext. As an example, if Alice and Bob use some standard, pre-defined messages that significantly vary in size – that is, to an extent that is not compensated by padding – Eve can easily guess the plaintext for a given ciphertext even if the encryption scheme is perfectly secret.

On the other hand, to determine the secret key, Eve must find statistical relations between the plaintext and the ciphertext. As far as we know, this is practically impossible for standardized ciphers, let alone for perfectly secret encryption schemes.

19.6.1 Brute-force attack

A brute-force attack is simply an exhaustive key search. If Eve attacks a b-bit block cipher that uses an n-bit key and she is given a small number – say, (n + 4)∕b – of plaintext-ciphertext pairs encrypted under key k, she can expect to determine k using a brute-force attack after about 2k−1 encryption operations on average.

How come Eve needs 2k−1 encryption operations on average? This is because Eve progresses through the entire key space and, as a result, can expect to find the right key after searching half the key space [117].

19.6.2 Forward search attack

A forward search attack can be thought of as a special case of a brute-force attack. If the message space used by Alice and Bob is small or predictable – that is, if the number of plaintext messages that Alice and Bob can possibly send is small or their messages are predictable – Eve can recover the plaintext corresponding to a ciphertext c she observes simply by encrypting all plaintext candidates until she obtains c.

Note that a secure cipher alone does not protect Alice and Bob against this vulnerability. As an example, while AES is considered to be a strong encryption algorithm, the use of AES in ECB mode with a small or predictable message space is nevertheless susceptible to a forward search attack. To protect the confidentiality of their messages, Alice and Bob must instead use probabilistic encryption where two identical plaintexts are never encrypted to the same ciphertext.

19.6.3 Ciphertext-only attack

In a ciphertext-only attack (sometimes referred to as a known ciphertext attack), Eve tries to deduce either the plaintext or the key used during encryption based solely on the ciphertext she observes. In other words, Eve has no information about the corresponding plaintext. If an encryption scheme is vulnerable to a ciphertext-only attack, it is considered completely insecure.