Cryptography Reference
In-Depth Information
But the message Eve would like Alice to sign is a little different. It is as follows:
> m2 := "By signing this statement Eve agrees to pay Alice the amount of $150000
(one hundred fifty thousand dollars) for the house mentioned below"
Eve wants to find a variant of
m2
with the same hash value as a variant of
m1
,
so that these variants have the same meaning as
m2
and
m1
, respectively. Later she
will claim that they signed the variant of the fraudulent message
m2
, so that she
only has to pay Alice $150000. To build the variants of the messages Eve can just
identify several places in which the wording of the message can be changed without
changing the meaning. If there are
t
positions in which a change can be made, then
by making/not making the possible change she will obtain 2
t
variants of the message,
all with the same meaning. In order to automatize the construction of these variants,
Eve has the following idea. The involved messages have a number of spaces (ASCII-
32 characters) and it is possible to replace some of them by another character that
looks the same when printed or displayed on a computer screen. That character is
ASCII-160 (or the character with hex code 0xA0 in the ISO/IEC 8859 standard)
which is a “no-break space”, i.e., a space used to prevent line breaks at its position.
So Eve is going to do the following. She is going to build the required variants of
m1
and
m2
by just replacing some of the ASCII-32 spaces by ASCII-160 spaces. All
the variants of each one of the two messages
m1
and
m2
look the same and keep the
meaning of the original message but actually they are different and they will have
different hash values. Since
m1
and
m2
have 22 spaces each, this method allows Eve
to take
t
22 and to build up to 2
22
variants of each of these two messages.
Each message variant will be associated with a number between 0 and 2
t
=
1
(we will call this number the "message number") and will have an ASCII-32 space
replaced by an ASCII-160 one at the
i
th space position if the corresponding bit in
the binary expansion of this number (starting from the least significant one) is a “1”
while the space will not be changed if the corresponding bit is a “0”. Note that the
ASCII-160 spaces in a message variant could make it look slightly odd when printed
as they could force line breaks to occur at unexpected places. On average one expects
half of the spaces in the first
t
space positions to be replaced by non breaking spaces
so this would not be a problemmost of the time. However, if the message to be signed
is sufficiently long, Eve can prevent the undesired side effects by selecting the space
positions where ASCII-32 spaces can be replaced by ASCII-160 ones in such a way
that no two consecutive spaces in the message can be replaced by ASCII-160 spaces.
An even more effective way to prevent uneven line breaking would be to select the
replaceable space positions so that, when the message is printed in a more or less
standard size, the replaceable space positions do not appear near the final positions
of each line.
The function to replace a character (the one in the
n
th position) in a string by an
ASCII-160 space is the following:
−
> replacespace := proc(str, n)
StringTools:-Delete(StringTools:-Insert(str, n, StringTools:-Char(160)), n .. n)
end proc:
