Cryptography Reference
In-Depth Information
applying
RandomTools:-MersenneTwister:-GenerateInteger
to
obtain a 100-digit key. Eve checks the current value returned by
randomize()
(or, equivalently, by the absolute value of
iolib(25)
) and finds that:
> randomize();
1243047833
Now Eve knows that if the seed was chosen by
randomize()
it will be a value
lower than this number. She also knows (Kerckhoffs' principle!) that the message is
an English text and was encrypted with
POTP
, so she mounts the attack using the
following function:
> POTPAttack := proc(ciphertext::string, startpoint::posint)
local i, found, m, l;
uses RandomTools:-MersenneTwister, StringTools;
l := iquo(Length(ciphertext), 2);
i := startpoint;
found := false;
while not found do
SetState(state = i);
m := POTP(GenerateInteger(':-range' = 10ˆ99 .. 10ˆ100), ciphertext, decrypt);
if Length(m) = l then
found := IsPrintable(m)
end if;
i:=i-1
end do;
m
end proc:
Note that themessage is recognized by the fact that all its characters are printable in
the sense that the function
StringTools:-Isprintable
returns
true
when
applied to the string. Out of the 255 characters of Maple's 8-bit ASCII alphabet,
only 95 have this property and these include all the alphanumeric characters and
punctuation characters used in English text. This means that if the plaintext is not
too short then it will be recognized with high probability as the other candidates will
almost surely contain non-printable symbols. Before checking whether a candidate
plaintext is printable, Eve also checks that the recovered message has the expected
length. This is because Maple does not have a character corresponding to the 0 byte
and the function
convert/bytes
used in
POTP
truncates the message when it
finds a byte 0 in the byte list. Thus if this check is omitted, it could happen that a
zero byte would appear near the beginning of the decrypted message and if all the
previous characters were printable this could easily give a false positive.
Now Eve attacks the ciphertext she intercepted:
> POTPAttack(c, 1243047833);
"We are challenging Eve to decrypt this plaintext"
The message was recovered very quickly because the key had been set up only
about nine hours earlier. But it is important to notice that this attack would also have
been successful—perhaps requiring more powerful resources—if the key had been
established months or years earlier or if the system clock was not on time when
randomize()
was called, or even if the key was randomly chosen in
31
{
0
,
1
}
