Block Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 111

One primary use for cryptographic hash functions, which require all of the above security, is in digital signa-
tures. As we learned above, performing public key operations can be very time-consuming (such as when taking
exponentials of very large integers). These operations become more difficult and time-consuming as the input
size increases: To encrypt a 16,384-bit block with an RSA key would require finding primes larger than 16,384,
as well as a key, and then performing thousands of arithmetic operations.
Aproperlydesignedcryptographichashcanbearepresentativeoftheentireinputblockbecauseoftheabove
properties; there is neither a way to correlate the input and the hash, nor to find similar blocks with the same
hash. Hence, we could encrypt the smaller hash using a public-key mechanism.
If a person uses a private key to encrypt the hash of a message, then anyone with the public key can decrypt
and verify the hash (since the hash algorithm must be well known). Furthermore, only the holder of the private
key could possibly have created the encrypted ( signed ) hash; thus, we can verify that the message is authentic.
This is the essence of a digital signature .
In the following sections I discuss checksums and cyclic redundancy checks and then go into the details of
the two most popular hash algorithms: MD5 and SHA-1.
4.12.1 Checksums
Checksums are very simple measurements of ciphers. Typically, they are implemented with simple arithmetic
or bitwise operators, usually addition or XOR.
For example, to calculate an 8-bit additive checksum of a series of bytes, simply add together the bytes and
calculate theresultmodulo256.ForanXOR-basedchecksum,simplyusethebitwiseXORoneachofthebytes,
which will return an 8-bit value.
Other checksums use similar methods. The key thing to note here is that they are not made for security. They
are designed to check for simple errors, such as transmission or transcription errors. Their simple implementa-
tion on processors in very few instructions allows them to be used often in communications protocols.
It is fairly easy to defeat a checksum if it is used for security: Either simply modify the checksum itself, or
modify a single portion of the message with the appropriate value to make the checksum come out correctly.
For example, with an 8-bit XOR checksum, it is necessary to change just one byte to manipulate the checksum
to be whatever is desired. Take the current checksum, XOR it with the desired checksum, and XOR this value
with any byte in the message. The new message will now have the desired checksum.
4.12.2 Cyclic Redundancy Checks
A cyclic redundancy check (CRC) is a bit-centric method of error checking that is more robust than normal
checksums against many types of errors, but is a tad more difficult to implement.
A CRC takes the original message and does bitwise (XOR-based) long division of it by a fixed, known poly-
nomial. The remainder after the division is then transmitted, which the receiving end can easily verify by also
dividing by the fixed polynomial.
CRCs vary in size, with the remainders having bit sizes between 5 and 32 being the most common.
For example, we can calculate a 5-bit CRC of the binary message 011011011 with the 6-bit divisor 101101 :