Cryptography Reference
In-Depth Information
return sum;
}
Here, the message “abc” sums to 294 because, in ASCII,
a
97,
b
98 and
c
99; “abd” sums to 295. Because you just ignore overfl ow, you can compute a
digest of any arbitrarily sized message.
The problem with this approach is that it can be easily reversed. Consider
the following scenario: I want to send a message that says, “Please transfer
$100 to account 123,” to my bank. My bank wants to ensure that this message
came from me, so I digitally sign it. First I compute the checksum of this
message: 2,970. I then use my private key to compute the signature. Using the
mini-key pair
e
79,
d
1019,
n
3337 from Chapter 3, this encodes (without
any padding) to 2970
1019
% 3337
2552. The bank receives the message, com-
putes the same checksum, decodes 2552 using the public key and computes
2552
79
% 3337
2970. Because the computed checksum matches the encrypted
checksum, the message can be accepted as authentic because nobody else can
solve x
79
% 3337
2970.
However, there's a problem with this simple checksum digest routine. Although
an attacker who might want to submit, “Please transfer $1,000,000 to account
3789,” which sums to 3171, is not able to solve x
79
% 3337
3171, he can instead
look for ways to change the message itself so that it sums to 2970. Remember that
the signature itself is public, transmitted over a clear channel. If the attacker can
do this, he can reuse my original signature of 2552. As it turns out, it's not hard
to work backward from 2970 to engineer a
collision
by changing the message to
“Transfer $1,000,000 to account 3789 now!” (Notice that I dropped the “please”
from the beginning and inserted “now!”) A bank employee might consider this
rude, but the signature matches. You may have to play tricks with null termina-
tors and backspace characters to get the messages to collide this way, but for
$1,000,000, an attacker would consider it well worth the effort. Note that this
would have been a vulnerability even if you had encoded the whole message
rather than the output of the digest algorithm.
Therefore, for cryptographic security, you need a more secure message digest
algorithm. Although it may seem that cryptography would be the hardest cat-
egory of secure algorithms to get right, message digests actually are. The history
of secure message digest algorithms is littered with proposals that were later
found to be insecure — that is, not properly collision resistant.
Implementing the MD5 Digest Algorithm
One of the earliest secure message digest algorithms in the literature is MD2
(MD1 appears never to have been released). It was followed by MD4 (rather than
MD3), which was fi nally followed by MD5 and is the last of the MD series of
Search WWH ::
Custom Search