Cryptography Reference
In-Depth Information
The next function builds the message variants. The input is a text string, a number
n
such that 0
2
t
≤
<
−
1, where
t
is less than or equal to the number of spaces
in the text string, and a list containing the positions of the spaces in the string (in a
moment, we will see how Eve can build this list). The output is the message variant
in which the spaces corresponding to “1” bits in
n
are replaced by ASCII-160 spaces
as explained above.
n
> variant := proc(n, message, spaceslist)
local bin, v, l, i;
bin := convert(n, base, 2);
v := message;
l := spaceslist;
for i to nops(bin) do
if bin[i] = 1 then
v := replacespace(v, l[i])
end if
end do;
v
end proc:
For example, the variant of
m1
corresponding to the number 1553 is:
> v1553 := variant(1553, m1, [StringTools:-SearchAll(" ", m1)]);
"By signing this statement Eve agrees to pay Alice the amount of $950000
(nine hundred fifty thousand dollars) for the house mentioned below"
Of course, the message looks the same as the original one but four of the spaces
are non-breakable now; we show below which these spaces are.
Observe that the list of space positions is determined by the text string and hence it
would not be necessary to pass it to the
variant
procedure as a separate argument.
But Eve is doing it this way because, when she mounts the birthday attack, she
will have to build many variants of the same message and it would be wasteful to
compute the spaces list when computing each of these variants. On the other hand,
observe also that another way to see that
v1553
and
m1
are really different is just
by computing their hash values and putting them side by side:
> Hash40(m1), Hash40(v1553);
"473c560db9", "17cc0d8ead"
We can check the positions in
v1553
where the ASCII-160 spaces have replaced
the ASCII-32 ones. They correspond to the four “1” bits in the binary expansion of
1553 and are the following:
> StringTools:-SearchAll(StringTools:-Char(160), v1553);
3, 30, 54, 61
Now, Eve is ready to mount her attack. She knows Theorem 5.5 according to
which if she builds 1
2
19
variants of each of the two contracts she already has a
chance approximately equal to 1
.
·
66
/
2 of finding a collision. So she intends to consider
a few more variants and her first idea, aiming to reduce searching to a minimum, is
to build an array indexed by all the possible hash values, i.e., the numbers from 0 to
2
40
1, and then to compute, say, 2
21
hash values of variants of
m1
and store the
−
