Cryptography Reference
In-Depth Information
which may well have been chosen at random. This extreme example shows that block
lengthmust be taken into account when analyzing the security of a block cipher which
is naively used as an encryption scheme. In fact, as we will see later on, even using a
mode of operation which provides a CPA secure scheme, block length must be taken
into account for practical security purposes and a 64-bit block length is regarded as
insufficient to provide this practical security (see Remarks 4.3). For this reason, most
modern encryption schemes based on block ciphers use, as a minimum, a 128-bit
block length. So, returning to our ideal block cipher in which all the permutations in
{
n
would appear among the
F
k
, let us see what this would mean for a 128-bit
block length.
The order of the symmetric group
S
0
,
1
}
n
is 2
n
128, this number is
so huge that we cannot write it down in positional notation, not even using Maple. To
understand why, we will compute an approximation of the binary logarithm of this
number. This is highly meaningful for our purposes because if we were to enumerate
all these permutations, we could use the binary form of the corresponding numbers
as keys and so this binary logarithm would give the length of the bin
ary s
trings
representing keys in this case. We will use Stirling's formula,
n
(
{
0
,
1
}
)
!
. When
n
=
n
n
e
n
!∼
√
2
π
2
n
2
n
e
2
n
!≈
√
2
([94]) which, in this case, gives the following approximation: 2
n
π
.
This, in turn, gives for the binary logarithm:
√
2
n
2
+
2
n
2
n
2
n
log
2
(
!
)
≈
log
2
(
π)
+
(
n
−
log
2
(
e
))
≈
(
n
−
1
.
44
).
Thus we see that the use of random permutations implies that the key length grows
exponentially as a function of the block length. Now we use Maple to compute this
value for
n
=
128:
> 2ˆ128*(128-1.44);
4.306613635*10ˆ40
This number would be the length of the binary strings used to code keys for this
scheme. To better appreciate the enormous amount of storage that a single key would
require, let us use large information storage units. In SI units of information, we have
the following equivalences:
1 petabyte = 10
3
terabytes = 10
6
gigabytes = 10
9
megabytes = 10
15
bytes
Then one key for the scheme would require:
> 4.306613635*10ˆ40/(8*10ˆ15);
5.383267044*10ˆ24
petabytes of storage. For comparison, K. Kelly in an article published in 2006 in
The New York Times
estimated that,
“the entire works of humankind, from the begin-
ning of recorded history, in all languages”
would amount to 50petabytes of data in
compressed form. So it is clear that these keys would be completely unmanageable.
