Cryptography Reference
In-Depth Information
This seems like a reasonable definition, but there are still several problems with
it. First, often we do not know what the best algorithm for a given attack is. A
prime example is the RSA public-key scheme, which can be broken by factoring
large integers. Even though many factoring algorithms are known, we do not know
whether there exist any better ones. Second, even if a lower bound on the complexity
of one attack is known, we do not know whether any other, more powerful attacks
are possible. We saw this in Sect. 1.2.2 during the discussion about the substitution
cipher: Even though we know the exact computational complexity for an exhaustive
key search, there exist other more powerful attacks. The best we can do in practice
is to design crypto schemes for which it is
assumed
that they are computationally
secure. For symmetric ciphers this usually means one hopes that there is no attack
method with a complexity better than an exhaustive key search.
Let's go back to Fig. 2.5. This design emulates (“behaves like”) a one-time pad.
It has the major advantage over the OTP that Alice and Bob only need to exchange a
secret key that is at most a few 100 bits long, and that does not have to be as long as
the message we want to encrypt. We now have to think carefully about the properties
of the key stream
s
0
,
s
1
,
s
2
,...
that is generated by Alice and Bob. Obviously, we
need some type of random number generator to derive the key stream. First, we note
that we cannot use a TRNG since, by definition, Alice and Bob will not be able to
generate the same key stream. Instead we need deterministic, i.e., pseudorandom,
number generators. We now look at the other two generators that were introduced
in the previous section.
Building Key Streams from PRNGs
Here is an idea that seems promising (but in fact is pretty bad): Many PRNGs pos-
sess good statistical properties, which are necessary for a strong stream cipher. If
we apply statistical tests to the key stream sequence, the output should pretty much
behave like the bit sequence generated by tossing a coin. So it is tempting to assume
that a PRNG can be used to generate the key stream. But all of this is not sufficient
for a stream cipher since our opponent, Oscar, is smart. Consider the following at-
tack:
Example 2.2.
Let's assume a PRNG based on the linear congruential generator:
S
0
= seed
S
i
+1
≡
AS
i
+
B
mod
m
,
i
= 0
,
1
,...
where we choose
m
to be 100 bits long and
S
i
,
A
,
B
∈{
0
,
1
,...,
m
−
}
. Note that this
PRNG can have excellent statistical properties if we choose the parameters carefully.
The modulus
m
is part of the encryption scheme and is publicly known. The secret
key comprises the values (
A
,
B
) and possibly the seed
S
0
, each with a length of 100.
That gives us a key length of 200 bit, which is more than sufficient to protect against
a brute-force attack. Since this is a stream cipher, Alice can encrypt:
1
