Cryptography Reference
In-Depth Information
that has (have) been used for encryption or to decrypt a ciphertext for which
he or she does not yet know the corresponding plaintext.
Chosen-plaintext attacks:
In a
chosen-plaintext attack
, the adversary has access
to the encryption function (or the device that implements the function, re-
spectively) and can encrypt any plaintext message unit of his or her choice.
He or she tries either to determine the key(s) that has (have) been used for
encryption or to decrypt ciphertext units for which he or she does not yet know
the corresponding plaintext message units. In a typical setting, the adversary
has to choose the plaintext units in advance (i.e., before the attack begins). In
an
adaptive chosen-plaintext attack
, however, the adversary can dynamically
choose plaintext message units while the attack is going on. Needless to say,
adaptive chosen-plaintext attacks are generally at least as powerful as their
(nonadaptive) counterparts.
Chosen-ciphertext attacks:
In a
chosen-ciphertext attack
, the adversary has ac-
cess to the decryption function (or the device that implements the function,
respectively) and can decrypt any ciphertext unit of his or her choice. He or
she tries either to determine the key(s) that has (have) been used for decryption
or to encrypt plaintext message units for which he or she does not yet know
the corresponding ciphertext units. Again, in a typical setting, the adversary
has to choose the ciphertext units in advance, whereas in an
adaptive chosen-
ciphertext attack
, the adversary can dynamically choose ciphertext units while
the attack is going on. An adaptive chosen-ciphertext attack is again more
powerful than its (nonadaptive) counterpart.
In general, there are many possibilities to implement these attacks. For ex-
ample, if an adversary knows the symmetric encryption system that is in use, he
or she can implement a ciphertext-only attack simply by trying every possible key
to decrypt a given ciphertext unit. This attack can even be parallelized (if many
processors participate in the key search). Let
be the size of the key space (i.e., the
number of possible keys),
t
be the time it takes to test a candidate key, and
p
be the
number of processors performing the key search. Then each processor is responsible
for approximately
|K|
t/p
to test them all. On
the average, one can expect to find the correct key about halfway through the search,
making the expected time approximately
|K|
/p
keys, and hence it takes time
|K|
|K|
t
.
(10.1)
2
p
This attack is known as
brute-force attack
or
exhaustive key search
. The attack
is possible whenever the adversary is able to decide whether he or she has found a
