стр. 2 |

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 |