Keyed Digest Authentication Algorithms

This document is an Internet-Draft.  Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its
areas, and its working groups.  Note that other groups may also
distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time.  It is inappropriate to use Internet-
Drafts as reference material or to cite them other than as
``work in progress.''

To learn the current status of any Internet-Draft, please check
the ``1id-abstracts.txt'' listing contained in the Internet-
Drafts Shadow Directories on (Africa), (Europe), (Pacific Rim), (US East Coast), or (US West Coast).

Executive Summary

A number of algorithms for authenticating a message based on the use of a shared secret are presented. These algorithms are based upon cryptographicaly secure message digest functions.


The cryptographic requirements are expressed here in terms of the "difficulty" of obtaining a value. This may be understood to mean that the problem of obtaining the value is at least computationaly infeasable and preferably insoluble.

Protection of key information

Given c = KD(s, m) and m it must be difficult to obtain s.

Message transformation attack.

Given c = KD(s, m) it must be difficult to find a c' such that c' = KD(s, m') where m' is an arbitrary transformation of m.

There are a number important cases of message transformation attack:

Key transformation attack

Given c = KD(s,m) it should be difficult to obtain c' = KD(s',m) where s' is some transformation of s.

The importance of suceptability to key transformation attacks will depend upon the protocol in which the keyed digest is employed. Such a weakness might be an issue in protocols for payments for example.

The key complementation property of DES by which E(s,d) = ~E(~s,d) means that a number of keyed digest functions based upon DES are susceptable to such an attack.

Combined transformation attack.

Given c = KD(s, m) and a c' = KD(s', m') it must be difficult to find a c' such that where m' and s' are strict functions of m and s respectively.

Properties intended to guard against key and message transformation attacks should also guard against the possibility of combined relationships.

Systems level attack from correlated data.

Care must be taken when constructing security systems from components which individually provide strong guarantees of cryptographic integrity but in combination may fail. A common reason for such failures is use of shared secret information to ensure both authenticity and privacy.

A simple example of a correlated data attack is a disclosure attack on multiple digest values under the same key.

Given c_0 = KD(s, m_0), c_1 = KD(s, m_1), ... and m_0, m1, ... it must be difficult to obtain s.

Schemes designed to provide unconditional security of a keyed digest often fail if shared secret information is reused thus permitting this type of attack. For example it is possible to prevent cryptanalisis of individual tokens, even by exhaustive cryptanalysis through incorporation of random values to `blind' the constraint network, that is ensure that the visible portion is under-constrained.

A more complex form of attack might involve cryptanalysis of related data involving multiple cryptographic processes. For instance use of the same shared secret information for encryption and a keyed digest. It is recommended that cryptographically secure functions be used to ensure that exploitation of such correlations is infeasible. This requirement may be visualised by considering a constraint network is partitioned such that all paths between cryptographic products of the same confidential information involve a cryptographically difficult process.

The requirement of resistance to correlated data attacks may be formalized thus:

Given a message m, c = KD(s, m) and e = CF(s, m) it must be difficult to determine s, where e is data revealed as part of a protocol and CF is a cryptographic function such that it is difficult to determine s from m and e.

It is not possible to give specific guarantees as to the security of a keyed digest in combination with a number of arbitary operations providing additional correlated data. It is just as important to perform threat analysis of complete systems as it is of components. It is however possible to identify specific cases where provision of specific correlated danger compromises the system.

Possible weakening of message digest function requirements.

An important requirement for many message digest applications is that the probability of two digests producing the same value by chance should be low. If the sole purpose of a keyed digest is to authenticate a sequence of bits the fact that two sequences of bits generate equal digest values may not be significant.

The statistical collision avoidance property is clearly desirable for certain message digest applications however. For example providing an opaque indexing function which allows items to be retrieved without knowledge of the actual indexing term itself.

Closure of the attack model.

The attack model has been constructed using the following risk taxonomy:

Keyed Digest Algorithm proposals.

The construction of a keyed digest function from cryptographic primitives such as hash functions and ciphers is in general concerned with preventing the exploitation of specific weaknesses in specific algorithms. As a consequence it is not usefull to separate consideration of the underlying hash function from the mode of operation employed to construct a keyed digest function.

It is therefore considered undesirable to specify modes of operation for cryptographic primitives in a manner analagous to DES. Although such a modular approach would be of assistance in building libraries the security of M1(H1) and M2(H2) does not imply the security of M1(H2) or M2(H1).

As a practical matter it is usefull to incorporate proposals that represent current practice. Consequently two keyed digest functions employed by Kerberos are names as KD1 and KD2 and the keyed digest function employed in the proposed Message Digest Authentication protocol of HTTP is named here KD3.

DES-CBC (k, iv, m)
DES in Cypher Block Chaining mode with key k, initialisation vector iv and message m.
DES-CBC-R (k, iv, m)
Residue from DES in Cypher Block Chaining mode with key k, initialisation vector iv and message m.
DES-CFB (k, iv, m)
DES in Cypher FeedBack mode with key k, initialisation vector iv and message m.
MD5 (m)
RSA-MD5 cryptographic hash of m.
hex (m)
The bytes of m represented as a sequence of hexadecimal values in ASCII with the lower case letters a-h used for the digits 10-15. [1]
KD1 (Kerberos rsa-md5-des mode)
KD1(s,m) = DES-CBC (s, 0, (r.MD5 (r.m))), where r is a 64 bit pseudo random value.
KD2 (Kerberos des-mac)
KD2(s,m) = DES-CBC (s', 0, (r.DES-CBC-R(s, 0, (r.m)))) where r is a 64 bit pseudo random value and s' is given by s' = s XOR 0xF0F0F0F0F0F0F0F0.
KD3(s,m) = MD5(s.hex(MD5(m)))
KD4(s,m) = MD5(s.MD5(s.m)) where s is a 128 bit key.
KD5(s,m) = MD5(s1.MD5(s2.m)) where s is a 256 bit key such that s = s1.s2.
KD5(s,m) = MD5(s.p.m.s)) where s is a 128 bit key and p is 384 bits of zero bytes padding.

Case by case description


This keyed digest fuction is deployed in a significant number of World Wide Web products. The correspondence with the HTTP specification is given through the mapping s = hex(A1).":".N.":"

The spurious incorporation of the function hex(x) in this specification was caused by an ambiguity in a specification introduced through use of ASCII based email. This function should be regarded as technologically obsolete.


Summary of assurances and work factor lower limits.


TBS (this are placeholders).