Page 555 - StudyBook.pdf

Basis of Cryptography • Chapter 9 539

Understanding One-way Functions
What does it mean for a function to be considered one-way? First, con-
Head of the Class… known as a modulus, or mod for short, and is easy to calculate in one
sider the calculation of remainders in long division. Specifically, let’s say
that 5 divided by 2 equals 2 with a remainder of 1. The remainder part is

direction. But suppose the problem was “The remainder is 1, find the divi-
sion problem.” How would you know the correct answer? This is what is
meant by a non-reversible function.
There is also a slightly more complex set of problems know as “clock
arithmetic.” Suppose that instead of having an infinite linear number line
(i.e., 1, 2, 3…100, 101…) you had a number line that connected back on
itself like a clock (i.e., 11, 12, 1, 2…10). On a clock, 5 + 3 is 8, but so is 5 +
15 and 5 – 9. Given the answer, you cannot derive a unique problem.
Thus, clock arithmetic is another example of a one-way function.

Sometimes it is not necessary or even desirable to encrypt a complete set of
data. Suppose someone wants to transmit a large amount of data, such as a CD
image. If the data on the CD is not sensitive, they may not care that it is openly
transmitted, but when the transfer is complete, they want to make sure the image
you have is identical to the original image.The easiest way to make this compar-
ison is to calculate a hash value on both images and compare results. If there is a
discrepancy of even a single bit, the hash value of each will be radically different.
Provided they are using a suitable hashing function, no two inputs will result in an
identical output, or collision.The hashes created, usually referred to as digital finger-
prints, are usually of a small, easily readable fixed size. Sometimes these hashes are
referred to as secure checksums, because they perform similar functions as normal
checksums, but are inherently more resistant to tampering.
Encrypted passwords are often stored as hashes.When a password is set for a
system, it is generally passed through a hashing function and only the encrypted
hash is stored.When a person later attempts to authenticate, the password is hashed
and that hash is compared to the stored hash. If these are the same, they are authen-
ticated, otherwise access is rejected. In theory, if someone were to obtain a pass-
word list for a system, it would be useless, since by definition it is impossible to
recover the original information from its hashed value. However, attackers can use
dictionary and brute-force attacks by methodically comparing the output hash of a
known input string to the stolen hash. If they match, the password has been cracked.
Thus, proper password length and selection is highly desirable.
There are several different types of hashing, including division-remainder, digit
rearrangement, folding, and radix transformation.These classifications refer to the

www.syngress.com