<<

. 2
( 2)



part of the European Open Shop Information-TeleTrust project [1221], quoted in
CCITT X.509 13041,and adopted in IS0 10118 [764,765]. Unfortunately, Copper-
smith has broken this scheme as well [376]. There has been some research using
exponents other than 2 [603], but none of it has been promising.

RIPE-MAC
RIPE-MAC was invented by Bart Preneel [1262] and adopted by the RIPE project
[1305] (see Section 18.8). It is based on IS0 9797 [763], and uses DES as a block
encryption function. RIPE-MAC has two flavors: one using normal DES, called
Page 457
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

18 One- Way Hash Functions
CHAPTER



RIPE-MACl, and another using triple-DES for even greater security, called RIPE-
MAC3. RIPE-MAC 1 uses one DES encryption per 64-bit message block; RIPE-MAC3
uses three.
The algorithm consists of three parts. First, the message is expanded to a length
that is a multiple of 64 bits. Next, the expanded message is divided up into 64-bit
blocks. A keyed compression function is used to hash these blocks, under the con-
trol of a secret key, into a single block of 64 bits. This is the step that uses either
DES or triple-DES. Finally, the output of this compression is subjected to another
DES-based encryption with a different key, derived from the key used in the com-
pression. See [ 13051 for details.
IBC-Hash
IBC-Hash is another MAC adopted by the RIPE project [1305] (see Section 18.8). It
is interesting because it is provably secure; the chance of successful attack can be
quantified. Unfortunately, every message must be hashed with a different key. The
chosen level of security puts constraints on the maximum message size that can be
hashed-something no other function in this chapter does. Given these considera-
tions, the RIPE report recommends that IBC-Hash be used only for long, infre-
quently sent messages.
The heart of the function is
h, = ((Ml mod p) + v) mod 2”
The secret key is the pair p and v, where p is an n-bit prime and v is a random num-
ber less than 2”. The M, values are derived by a carefully specified padding procedure.
The probabilities of breaking both the one-wayness and the collision-resistance can
be quantified, and users can choose their security level by changing the parameters.
One-Way Hash Function MAC
A one-way hash function can also be used as a MAC [ 15371.Assume Alice and Bob
share a key K, and Alice wants to send Bob a MAC for message M. Alice concate-
nates K and M, and computes the one-way hash of the concatenation: H(K,M). This
hash is the MAC. Since Bob knows K, he can reproduce Alice™s result. Mallory, who
does not know K, can™t.
This method works with MD-strengthening techniques, but has serious prob-
lems. Mallory can always add new blocks to the end of the message and compute a
valid MAC. This attack can be thwarted if you put the message length at the begin-
ning, but Preneel is suspicious of this scheme [ 12651.It is better to put the key at the
end of the message, H(M,K), but this has some problems as well [ 12651. If H is one-
way but not collision-free, Mallory can forge messages. Still better is H(K,M,K), or
H(K,,M,K,), where KI and K2 are different [1537]. Preneel is still suspicious [ 12651.
The following constructions seem secure:



H(K,p,M,K), where p pads K to a full message block.
Page 458
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




1
v CSPRNG




Figure 18.15 Stream cipher MAC.


The best approach is to concatenate at least 64 bits of the key with each message
block. This makes the one-way hash function less efficient, because the message
blocks are smaller, but it is much more secure [ 12651.
Alternatively, use a one-way hash function and a symmetric algorithm. Hash the
file, then encrypt the hash. This is more secure than first encrypting the file and
then hashing the encrypted file, but it is vulnerable to the same attack as the H(M,K)
approach [ 12651.
Stream Cipher MAC
This MAC scheme uses stream ciphers (see Figure 18.15) [932]. A cryptographi-
cally secure pseudo-random-bit generator demultiplexes the message stream into
two substreams. If the output bit of the bit generator ki, is 1, then the current mes-
sage bit m,, is routed to the first substream; if the k, is 0, the mi is routed to the sec-
ond substream. The substreams are each fed into a different LFSR (see Section 16.2).
The output of the MAC is simply the final states of the shift registers.
Unfortunately, this method is not secure against small changes in the message
[1523]. For example, if you alter the last bit of the message, then only 2 bits in the
corresponding MAC value need to be altered to create a fake MAC; this can be done
with reasonable probability. The author presents a more secure, and more compli-
cated, alternative.

<<

. 2
( 2)