Cryptography Reference
In-Depth Information
because of the 'birthday attack', to at least 256. This requirement makes the problem
of obtaining truly random bits even harder, since a few bits are not sufficient.
The methods offered by Maple to automatically seed its pseudo-random algo-
rithms are not satisfactory from the cryptographic point of view because they
give too few bits which, in addition, are not really random. Of course, Maple
warns at appropriate places that, for cryptographic purposes, truly random seeds
must be provided by the user. For this reason, automatic seeding is not available
in Maple's function
NewBitGenerator
, which is the one we used in
POTP
.
Maple also warns that its default pseudo-random algorithm, Mersenne Twister,
is not adequate for cryptographic use, in consonance with the fact that it is not
a PRG in the sense of Definition 3.4. However, the BBS-based Maple function
RandomTools:-BlumBlumShub:-NewGenerator
allows automatic seed-
ing, with the seed being provided by Mersenne Twister, itself automatically seeded
(again, Maple warns that this is not secure). One might be tempted to use a similar
method to provide a seed for the Blum-Blum-Shub PRG (for example, to provide a
key for POTP) but, as we show in Example 3.6 below, this would be highly insecure
even disregarding the fact that Mersenne Twister does not satisfy Definition 3.4.
The Mersenne Twister algorithm can be seeded automatically by Maple in two
different ways. One of these methods uses the function
randomize()
which calls
the kernel function
iolib(25)
to obtain a seed. This seed is the absolute value
of the current value of
iolib(25)
and is equal to
mods
(
2
32
where
n
is the
number of seconds passed since January 1, 1970 (the value returned by
iolib(25)
is a 32-bit signed integer). This seeding method is far from satisfactory for several
reasons. The first is that the seed is currently too small at 31bits, (and it will never
get past 2
31
, a value that will be reached on January 19, 2038, at the same time as
the so-called “2038 problem” which is related to computers storing system time in
the same way as
iolib(25)
)
5
so the above outlined brute-force attack is perfectly
viable against a generator seeded this way. On top of this, taking the number of
seconds passed since a fixed date is anything but random and an adversary that can
approximately guess the date in which the algorithm was seeded, can also accurately
guess most of the bits of the seed used, making the brute-force attack even easier.
There is an alternative way to automatically seed Mersenne Twister, through
the use of the function
RandomTools:-MersenneTwister:-SetState()
,
which calls the function
MTKernelInterface(1)
(local to the module
RandomTools:-MersenneTwister
) which, in turn, calls the undocumented
kernel function
RandNumberInterface
. This function, again, only produces a
32-bit seed, which is insufficient to prevent a brute-force attack. This problem might
be alleviated by collecting several outputs of this function at different times but we
shall not go into these details.
n
,
)
Example 3.6
A brute-force attack against
POTP
when an inadequate key is used.
In this example, we start by performing a couple of simple experiments to show what
5
See, e.g.,
http://en.wikipedia.org/wiki/Year_2038_problem
for a description of this problem.
