Cryptography Reference
In-Depth Information
to look for a certain checksum, and only accept messages with that checksum, then the communicating parties
would have a little more confidence in their communications.
But what if an intruder wanted to break through this confidence and send a false message? How difficult is
that? Just using random messages, then we can use the birthday paradox to look at the problem statistically. A
random message is going to have a (hopefully) random checksum. Ignoring any possible patterns to be found
or other clever ways to circumvent this problem, we want to know how many of these we need to calculate to
have a match for a message.
Since this hash is 8 bits long, for a total of 256 values, then the birthday paradox says that if we have
or about 19 hashes, then we have a better than half chance of having a repeated hash of the random messages.
Unfortunately, this doesn't give us any particular value — it will be random. However, sometimes the goal is
merely to demonstrate the weakness of the algorithm by finding random messages that have the same hash —
this is called a
collision attack.
Getting messages that hash to a
particular
value is, in general, a bit harder. This is the goal if we wanted
to spoof the preceding message, but knowing only its hash value (this is called a
preimage attack).
A clever
reader should be able to figure out how to spoof a message that has the same checksum as before.
Owing to the insecurity of this simple hash algorithm, it is not used for secure communications, although
similar additive checksums are used to check the message for errors in transmission, since a message that has
been corrupted will, we hope, have a different checksum. For hash algorithms with a little more robustness, we
need to turn to MD5 and SHA-1, two of the leading
cryptographic hash algorithms,
with digest sizes of 128
bits and 160 bits, respectively. A
cryptographic hash algorithm
is one that is not based on a simple trick, but
tries to obfuscate all of the information so that the outputted digest is as random as possible, with no possible
way to figure out much of anything in the original message. It is their goal to be true
one-way
hashes, where it
is impossible to extract any information about the original input from the hash's output.
For example, MD5 (see Section 4.12.3), which is the fifth in a series of message digest algorithms created
by Ronald Rivest, works on messages represented as bits, of arbitrarily large (and small) length. It then does
some pre-processing, and finally, on each 512-bit block, it churns through 64 operations to make it as much of
an unrecognizable mush as possible, including using the output of the previous operation of 512 bits. SHA-1
works in a similar fashion (see Section 4.12.4).
Both hashes take a lot longer than our previous additive sum. However, the confidence in both algorithms
is also incredibly higher, since both are still used to protect value information. Cryptographic sums are often
powerful enough to be combined with some of the forms of cryptography (covered below in this chapter), to
provide assurances of the authenticity and integrity of the message without having the message itself encrypted,
providing a form of digital signature. (This is because doing mathematical operations on a very large input text
can be cumbersome, but the hashes are a small, fixed size.)
2.2 Number Theory Refresher Course
We have now covered some basic knowledge of probability. Fortunately, we need to know a bit more math to
understand a lot of cryptanalysis, so we get the pleasure of a run-through of number theory, and later algebra, as
well.
The foundation of many modern cryptographic algorithms lies in
number theory
— the mathematical study
of integers, especially relating to topics in divisibility (such as prime numbers). Cryptanalysts definitely need
Search WWH ::
Custom Search