[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

IP Authentication using Keyed MD5


The following note contains a short description of MD5-MAC, which is 
a simple and efficient way to derive a Message Authentication Code 
from MD5. 
We believe that the Internet Draft on IP Authentication should contain 
the most robust algorithm currently available, which meets the 
performance constraints, and which requires only a very small 
implementation effort.   
We thus propose that MD5-MAC be included in the Internet Draft
on Authentication Using Keyed MD5.  

The rationale behind this scheme can be found in the reference 
[crypto95]. 


A short description of MD5-MAC 
------------------------------

MD5-MAC is a conservative construction for a MAC based on MD5. 
MD5 itself is specified in [RFC-1321].  The key size is 128 bits, 
(provision can be made to extend a key less than 128 bits up to 
128 bits) and the MAC size is 64 bits. For an extensive motivation 
of the design (including the weaknesses observed in other 
constructions), the reader is referred to [crypto95].

The 16-byte key K is used to derive three 16-byte keys K0, K1, and K2.  
K1 is split into four 32-bit substrings K1[0], K1[1], K1[2], and K1[3].
MD5-MAC(x) is computed in a similar way as MD5(x), with the following
modifications:
  1 the initial value IV of MD5 is replaced by K0;
  2 the value K1[i] is added modulo 2**32 to the all the constants
    in round i (the rounds are numbered 0,1,2,3), i.e. effectively 
    to the result of each of the 64 steps, immediately prior to the 
    circular shift;
  3 after the last block (which contains the padding and the appended 
    length), the following 64-byte block is inserted:
         K2 ; K2 + T0 ; K2 + T1 ; K2 + T2
    (here T0, T1, and T2 are 16-byte constant strings defined below,
     ; denotes concatenation, and + denotes XOR, i.e. bitwise addition 
     modulo 2);
   4 the MD5-MAC value consists of the leftmost 64 bits of the hash value.

The computational overhead of MD5-MAC is a single MD5 block operation for 
each message (step 3); the basic operation can become slightly slower, 
since the constants are replaced by variables. MD5-MAC is only 5% to 20% 
slower than MD5 (depending on the processor and the implementation).
Code for MD5-MAC can be obtained by some small and easy modifications
to existing code for MD5. 

When the 16-byte key K is installed, K0, K1, and K2 are computed as follows:
   K0 := MD5*( K ; U0 ; K)
   K1 := MD5*( K ; U1 ; K)
   K2 := MD5*( K ; U2 ; K)
Here  - U0, U1, and U2 are 96-byte constant strings defined below;
      - MD5* is the MD5 hash function without postprocessing
        (.e. omitting padding and appended length).
This computation has to be done only once and requires in total
6 MD5 block operations.

The 16-byte `magic' strings T0, T1, and T2 (given in hexadecimal):
   T0 =  97 ef 45 ac 29 0f 43 cd 45 7e 1b 55 1c 80 11 34
   T1 =  b1 77 ce 96 2e 72 8e 7c 5f 5a ab 0a 36 43 be 18
   T2 =  9d 21 b4 21 bc 87 b9 4d a2 9d 27 bd c7 5b d7 c3

The 96-byte strings U0, U1, and U2:
   U0 =  T0 ; T1 ; T2 ; T0 ; T1 ; T2
   U1 =  T1 ; T2 ; T0 ; T1 ; T2 ; T0
   U2 =  T2 ; T0 ; T1 ; T2 ; T0 ; T1

[crypto95] Bart Preneel, Paul C. van Oorschot,
   ``MDx-MAC and Building Fast MACs from Hash Functions,''
   Proc. Crypto'95, Springer-Verlag LNCS (to appear, Aug. 1995).
   {ftp: ftp.esat.kuleuven.ac.be, directory pub/COSIC/preneel}