Cryptography Reference
In-Depth Information
because, in all these cases, the attack would only have to run over at most 2
31
seeds. A similar remark applies in case Mersenne Twister is seeded by means of
SetState()
.
Exercise 3.18
Modify the function
POTPAttack
to make it output, in addition to
the recovered plaintext, the key used to encrypt the message with
POTP
.
An encryption scheme such as the one implemented by means of
POTP
is usually
called a
stream cipher
: encryption is done by generating a
stream
of pseudo-random
bits by means of a PRG (BBS in our case) and then Xor-ing this stream with the
plaintext to obtain the ciphertext (sometimes the term stream cipher is used to des-
ignate the PRG itself). As happens with the one-time pad, the cipher implemented
in
POTP
is not secure if the key is reused, i.e., if multiple messages are encrypted
with the same pseudo-random stream. If
c
1
=
POTP
(
)
then the result of Xor-ing
c
1
and
c
2
is the same as that of Xor-ing
m
1
and
m
2
and
this may give the adversary a lot of information about
m
1
and
m
2
and even allow
recovery of these messages (see, for example [64] where an attack of this kind is
described in detail). A weakness of this type in an implementation of the stream
cipher RC4—which is the most popular stream cipher and is regarded as reasonably
secure if properly implemented—is described in [200].
Let us now briefly analyze the security of
OTP
by means of an example that may
be helpful to better understand the differences with
POTP
. We know that if we use
fixed-length messages and random keys that are never reused then the system has
perfect secrecy (see Sect.
3.2
). To illustrate the intuitive meaning of perfect secrecy,
let's have a look at the problem an attacker faces when trying to break this scheme:
m
1
,
k
)
and
c
2
=
POTP
(
m
2
,
k
Example 3.7
Suppose that there are only three possible messages that Alice may
send to Bob:
> m1 := "We will attack tomorrow at 11.55am":
m2 := "We will surrender tomorrow at noon":
m3 := "We will retire tomorrow at 11:55am":
Observe that all these messages have the same length (34 bytes):
> map(StringTools:-Length, [m1, m2, m3]);
[34, 34, 34]
Now, suppose that Alice encrypts message
m1
with the following 34-byte hex
key:
> k1 := "b0f29e2253072462e85da1b4864f33ab073e42ab688705f3cb440e50a2c87eb8b9c0":
The ciphertext that Alice sends to Bob is then:
> c1 := OTP(k1, m1);
"e797be553a6b48428929d5d5e52413df68532dd91ae872d3aa302e6193e64b8dd8ad"
Suppose that Eve is an enemy eavesdropper who observes this ciphertext. We
may assume that Eve knows the three possible messages that Alice can send to
