Cryptography Reference
In-Depth Information
Exercise 3.17
Write a Maple procedure similar to
OTP
that also includes the pos-
sibility of encrypting and decrypting binary files.
We remark that this implementation is only an approximation to the one-time
pad as there is an important additional requirement that must be met: the key must
be selected at random with uniform probability distribution. It is very difficult to
generate a random key in software and even more so if the key, as happens in this
case, is usually going to be long, but this aspect is crucial if we want the scheme to
be secure. We next discuss the security aspects in more detail.
3.4.3 Practical Security Aspects
We have given an informal argument that shows that the pseudo-random one-time
pad is computationally secure, but there are several aspects that must be taken into
account for this to apply to the preceding construction. The first important point to
observe is that the security argument assumes that the key used is truly random. This
is a source of concern as it is by no means easy to generate truly random seeds to
be used as keys, although we can always resort to the inefficient method of tossing
a coin, using Von Neumann's trick just in case the coin is biased. But there are also
other problems that must be addressed. The PRG security definition is asymptotic
and, in practice, one must be careful, for the notion of “asymptotic hardness” is not
meaningful when applied only to small values.
More concretely, an attacker can always mount a
brute-force attack
against BBS
(or against any PRG for that matter) consisting of running through all possible seeds
and computing the corresponding output strings. If the seed has length
t
, then there
are 2
t
possible seeds and, since this number grows exponentially in the size, the
attack is, in principle, infeasible. But, in practice, it is perfectly feasible if
t
is small
enough. For example, suppose that we use the function
POTP
to encrypt, say, 512-bit
messages using a 32-bit key. There are 2
32
possible keys and it is perfectly feasible—
and even easy—to compute all the corresponding BBS outputs, thus distinguishing
with high probability between these pseudo-random 512-bit strings and truly random
strings of the same length (the former would only be a tiny subset of the latter). In
this case the adversary would not only be able to obtain significant information about
the plaintext but, in fact, it would be able to recover the whole plaintext with high
probability if, for example, it is a text in a natural language. This is because, after the
search, there would be only 2
32
possible candidate plaintexts, one of which is the true
plaintext. Since there are 2
512
possible 512-bit messages, where an overwhelming
majority would be meaningless in the language, the probability of obtaining more
than two meaningful messages in the set of the 2
32
candidate plaintexts would be
very small indeed. We give an example of such an attack below.
To be secure against brute-force attacks we should be careful and choose the length
of the key large enough tomake these attacks infeasible. Computing 2
64
values seems
within reach today so, to be safe, a key of at least 128 bits should be used. In fact, as
