Following the Kerckhoff’s principle we assume henceforth that all
designs are known to the attacker; defense is only provided via the secret
keys. Therefore, one simple attack strategy is to try to decrypt ciphertext
message using all possible keys, and detect the key or keys – where the
decryption seems to result in possible plaintext, and discard keys which
result in clearly-incorrect plaintext. For example, if we know that the
plaintext is the text in English we can test candidate plaintext, e.g. by
being reasonable-close to the distribution of letters in English. (Figure 3).
This attack is called exhaustive key search, exhaustive cryptanalysis or
brute force attack.
Fig.3. Distribution of letters in typical English texts
Like others CTO attacks, exhaustive search has some requirements on
the plaintext space; for exhaustive search it should be possible to
efficiently identify valid plaintext. In addition, exhaustive search may not
work for stateful ciphers, since decryption depends on the state and not
only on the key. Finally, decoding of an arbitrary plaintext with an
incorrect key should usually result in clearly-invalid plaintext. Exhaustive
search can be applied whenever these properties hold, i.e., it is a generic
CTO attack.
Exhaustive search is practical only when the key space is not too
large. It is very computation-intensive; it finds the key, on the average,
after testing half of the key space. On the other hand, its storage
requirements are very modest, and always independent of the key space.
To facilitate CTO attacks, the attacker must have some knowledge
about the distribution of plaintexts. In practice, such knowledge is
typically due to the specific application or scenario, when it is known that
the message is in English, and hence the attacker can apply known
statistics such as the letter-distribution histogram Fig.3. We refer to such
attacks as chosen-plaintext attacks (CPA).
There are two additional common attack models for encryption
schemes, which represent two different variants of the CPA attack. The
first is the known-plaintext attack (KPA) model, where the attacker
receives one or multiple pairs of plaintext and the corresponding
ciphertext, but the plaintext being chosen randomly.
The last of these four common attack models, is the chosen-ciphertext
attack (CCA) attack model. A CCA attacker has the ability to receive the
decryption of arbitrary ciphertexts, chosen by the attacker
The use of longer keys, e.g., 128 bits, is not a sufficient condition for
security. Normally, we select sufficient key length to ensure security
against any conceivable adversary, e.g., leaving a reasonable margin above
effective key length of say 100 bits; a larger margin is required when the
sensitivity period of the plaintext is longer. The cost of using slightly
longer key is usually well justified, considering the damages of loss of
security and of having to change in a hurry to a cipher with longer
effective key length.
Principle 3. Deployed cryptosystems should have sufficient
effective key length to foil feasible attacks, considering the maximal
expected adversary resources, as well as cryptoanalysis and speed
improvements expected over the sensitivity period of the plaintext.
Experts and different standardization and security organizations,
publish estimates of the required key length of different cryptosystems.
Упражнение 7. Ответьте на вопросы к тексту.
1. What is Kerckhoff’s principle about?
2. By what means is the defense provided?
3. What is the goal of a simple attack strategy?
4. Like others CTO attacks, exhaustive search has some requirements on
the plaintext space, hasn't it?
5. Why doesn't exhaustive security search work for stateful ciphers?
6. Should decoding of an arbitrary plaintext with an incorrect key usually
result in original information or in clearly-invalid plaintext?
7. What must the attacker know to facilitate CTO attacks?
8. What is the difference between chosen-plaintext attacks and known-
plaintext attacks?
9. Do you really think that the cost of using slightly longer key is usually
well justified?
10. What is the main idea of Principal 3?