Cryptography Reference
In-Depth Information
Remarks 4.3
1. The preceding theoremcompletes the picture of the reasons why block ciphers and
modes of operation have such a relevant role in modern cryptography. The main
idea may be summarized as follows: block ciphers plus modes of operation is the
best way known so far to obtain private-key encryption schemes that are both very
efficient in practice and likely secure. We do not have security assurance because
we do not have a proof that a block cipher is a pseudo-random permutation but this
shows that, leaving aside attacks against implementations (such as side-channel
attacks which are, of course, very important in practice), the natural way to attack
such a scheme is to attack the pseudo-randomness of the block cipher.
2. From a practical point of view, the proof of the preceding theorem gives us some
relevant information about how the expected level of security of the scheme varies
as a function of the block size
n
. The advantage
ε(
n
)
of the adversary is close
to
ν(
n
)
(since the difference between them is a negligible function) and
ν(
n
)
is
2
n
−
1
. When a 128-bit block size is used, as in the
case of AES and, say, 2
32
queries about 2
32
-block messages are made (so that the
adversary advantage is maximized), the value of the latter function is 1
2
bounded by the function
q
(
n
)
/
2
63
, which
is close to 10
−
19
. The adversary advantage is then close to this number and hence
we may conclude that the AES-based CTR encryption scheme is secure against
such an adversary (provided that the AES function is pseudo-random). However,
suppose that we use a block cipher with a 64-bit block length (such as, for example,
DES). Then the value of the function
q
/
2
n
−
1
is equal to 2 for an adversary
making 2
32
queries and hence the bound on the advantage of such an adversary
becomes meaningless. Each message queried would be 64
2
(
n
)
/
2
38
bits long,
which is just above 34GB and hence such an attack is not unimaginable taking
into account today's storage capabilities. This suggests that using a block cipher
with a 64-bit block length or less may not be secure in practice.
2
32
·
=
Exercise 4.9
Give an informal argument showing that, if the underlying block cipher
is a pseudo-random permutation, then OFB mode gives a CPA secure encryption
scheme if and only if the IV is never repeated under the same key except possibly
with negligible probability. (Hint: Show that if the IV is never repeated, then the
probability of a repeated value in the keystreams arising from adversary queries is
negligible and argue as in the proof of Theorem 4.1.)
4.3.2.1 The Modes of Operation Do Not Yield CCA Secure Schemes
We have not seen so far any example of a CCA secure scheme and sowemight wonder
whether the CPA secure CTR scheme is also CCA secure. However, it is easy to show
that this is not the case. If
is the challenge ciphertext corresponding to the
message
m
(where
ctr
denotes the initial counter value), then a CCA adversary may
construct a new ciphertext by just flipping one bit—say, the
i
th bit—of
c
and query
the decryption oracle about this new ciphertext. Since this ciphertext is different from
the challenge ciphertext, the oracle will answer the query and return a message
m
(
ctr
,
c
)
