Cryptography Reference
In-Depth Information
naturally regarded as defined over the alphabet consisting of bytes (i.e., 8-bit
strings). For this reason the (binary) block length, as well as the key length, must
bemultiples of 8 in this case but, otherwise, this is just a trivial matter of re-scaling.
It is clear that the definition of block cipher given above is too general for cryp-
tographic use. As an extreme example, one could define a block cipher by setting
F
k
(
t
and it is obvious that an encryption scheme based on it
would not be too secure. But even if we require the map
k
x
)
=
x
for all
k
∈{
0
,
1
}
F
k
to be injective, we
are still far from anything resembling reasonable security. For example, if we look
at the Hill cipher and its cryptanalysis, we immediately see that the reason it was so
easily broken is that the maps
F
k
are linear. Thus they are uniquely determined by
their action on a basis of the vector space formed by the blocks (if, as in the example
we gave, the alphabet is not a field, the blocks do not form a vector space in the strict
sense of the term but they form a free module, which also has a basis, and the linear
algebra works the same). A basis is a small subset of the message space (it has only
n
members where the message space has 2
n
or, more generally,
→
n
members) and
a polynomially bounded adversary can recover the key and hence completely break
the system by just mounting a chosen plaintext attack (even a known plaintext attack
may often be sufficient) on this subset.
In view of this example, we want to use block ciphers where the permutations
F
k
are far from structured, i.e., we would like that these maps would be random or,
to express it a little more precisely, that the
F
k
corresponding to randomly chosen
k
|
Σ
|
t
n
. This could be
∈{
0
,
1
}
behave like randomly chosen permutations of
{
0
,
1
}
t
{
F
k
|
∈{
,
}
}
accomplished by taking the family
k
0
1
equal to the entire symmetric
n
and taking the key space large enough so that it can be bijectively
mapped to this symmetric group (thus, randomly choosing a key would be equivalent
to randomly choosing a permutation of
group of
{
0
,
1
}
n
). Strictly speaking this would not fit
the previous definition since the number of permutations of
{
0
,
1
}
n
{
0
,
1
}
is not a power of
t
for a given value of
t
,
but this is only a minor technical matter as the key space could be, more generally,
a subset of
2 and hence does not correspond bijectively to the set
{
0
,
1
}
t
.
This construction may be regarded as an attempt to obtain maximum security
through randomness (as in the case of perfect secrecy) but here things are a little
different, for even with these random permutations as encryption functions we would
not necessarily obtain an encryption scheme with indistinguishable encryptions in
the presence of an eavesdropper—not to mention the fact that an encryption scheme
that directly uses these permutations to encrypt cannot be CPA secure because the
encryption functions are deterministic. Indeed, we have seen how substitution ciphers
are highly vulnerable to ciphertext-only attacks—by means of frequency analysis—
and substitution ciphers are nothing but block ciphers with block length 1 (we used
the English alphabet in our example and, since the number of symbols was less
than 2
5
, these symbols could have been encoded as binary strings in
{
0
,
1
}
5
,so
this particular cipher can be regarded as a block cipher of length 5 over the binary
alphabet). Moreover, note that for this attack to be successful it is not necessary
to make any special assumption about the key, i.e., the permutation of the alphabet,
{
0
,
1
}
