Network Working Group B. Kaliski INTERNET-DRAFT RSA Data Security, Inc. 1 July 1991 The MD2 Message-Digest Algorithm STATUS OF THIS MEMO This draft document will be submitted to the RFC editor as a protocol specification. Comments should be sent to or to the author. Distribution of this memo is unlimited. ACKNOWLEDGEMENT The description of MD2 is based on material prepared by John Linn and Ron Rivest. Their permission to incorporate that material is greatly appreciated. Table of Contents 1. Executive Summary 1 2. Terminology and Notation 2 3. MD2 Algorithm Description 2 4. Summary 4 5. Security Considerations 5 References 5 Author's Address 5 APPENDIX - Reference Implementation 6 1. Executive Summary This document describes the MD2 message digest algorithm. The algorithm takes as input an input message of arbitrary length and produces as output a 128-bit "fingerprint" or "message digest" of the input. It is conjectured that it is computationally infeasible to produce two messages having the same message digest, or to produce any message having a given prespecified target message digest. The MD2 algorithm is intended for digital signature applications, where a large file must be "compressed" in a secure manner before being signed with a private (secret) key under a public-key cryptosystem such as RSA. License to use MD2 is granted for non-commerical Internet Privacy- Enhanced Mail [1-3]. Kaliski [Page 1] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 This RFC is a proposed update to the August 1989 RFC 1115 [3], which also gives a reference implementation of MD2. The main differences are that a textual description of MD2 is included, and that the reference implementation of MD2 is more portable. A version of this document including the C source code in the ap- pendix is available by FTP from RSA.COM in the file "pub/md2.doc". This document may be referred to, unofficially, as Internet draft [MD2-B]. For OSI-based applications, MD2's object identifier is md2 OBJECT IDENTIFIER ::= {iso(2) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 2} In the X.509 type AlgorithmIdentifier [4], the parameters for MD2 should have type NULL. 2. Terminology and Notation In this document a "byte" is an eight-bit quantity. Let x_i denote "x sub i". If the subscript is an expression, we surround it in braces, as in x_{i+1}. Similarly, we use ^ for superscripts (exponentiation), so that x^i denotes x to the i-th power. Let X xor Y denote the bit-wise XOR of X and Y. 3. MD2 Algorithm Description We begin by supposing that we have a b-byte message as input, and that we wish to find its message digest. Here b is an arbitrary nonnegative integer; b may be zero, and it may be arbitrarily large. We imagine the bytes of the message written down as follows: m_0 m_1 ... m_{b-1} The following five steps are performed to compute the message digest of the message. 3.1 Step 1. Append Padding Bytes The message is "padded" (extended) so that its length (in bytes) is congruent to 0, modulo 16. That is, the message is extended so that it is a multiple of 16 bytes long. Padding is always performed, even if the length of the message is already congruent to 0, modulo 16 (in which case 16 bytes of padding are added). Kaliski [Page 2] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 Padding is performed as follows: "i" bytes of value "i" are appended to the message so that the length in bytes of the padded message becomes congruent to 0, modulo 16. At this point the resulting message (after padding with bytes) has a length that is an exact multiple of 16 bytes. Let M[0 ... N-1] denote the bytes of the resulting message, where N is a multiple of 16. 3.2 Step 2. Append Checksum A 16-byte checksum of the message is appended to the result of the previous step. This step uses a 256-byte "random" permutation constructed from the digits of pi. Let S[i] denote the i-th element of this table. The table is given in the appendix. Do the following: /* Clear checksum. */ For i = 0 to 15 do: Set C[i] to 0. end /* of loop on i */ Set L to 0. /* Process each 16-word block. */ For i = 0 to N/16-1 do /* Checksum block i. */ For j = 0 to 15 do Set c to M[i*16+j]. Set C[i] to S[c xor L]. Set L to C[i]. end /* of loop on j */ end /* of loop on i */ The 16-byte checksum C[0 ... 15] is appended to the message. Let M[0 ... N'-1] denote the bytes of the resulting message (after padding with checksum), where N' = N + 16. 3.3 Step 3. Initialize MD Buffer A 48-byte buffer X is used to compute the message digest. The buffer is initialized to zero. 3.4 Step 4. Process Message in 16-Byte Blocks This step uses the same 256-byte permutation S as step 2 does. Kaliski [Page 3] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 Do the following: /* Process each 16-word block. */ For i = 0 to N'/16-1 do /* Copy block i into X. */ For j = 0 to 15 do Set X[16+j] to M[i*16+j]. Set X[32+j] to (X[16+j] xor X[j]). end /* of loop on j */ Set t to 0. /* Do 18 rounds. */ For j = 0 to 17 do /* Round j. */ For k = 0 to 47 do Set t and X[k] to (X[k] xor S[t]). end /* of loop on k */ Set t to (t+j) modulo 256. end /* of loop on j */ end /* of loop on i */ 3.5 Step 5. Output The message digest produced as output is X[0 ... 15]. That is, we begin with X[0], and end with X[15]. This completes the description of MD2. A reference implementation in C is given in the Appendix. 4. Summary The MD2 message digest algorithm is simple to implement, and provides a "fingerprint" or message digest of a message of arbitrary length. It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations. The MD2 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the case with any new proposal of this sort. Kaliski [Page 4] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 5. Security Considerations The level of security discussed in this memo is considered to be sufficient for implementing very high security hybrid digital signature schemes based on MD2 and a public-key cryptosystem. References [1] Linn, J., Privacy Enhancement for Internet Electronic Mail: Part I -- Message Encipherment and Authentication Procedures (RFC 1113), August 1989. [2] Kent, S., and J. Linn, Privacy Enhancement for Internet Electronic Mail: Part II -- Certificate-Based Key Management (RFC 1114), August 1989. [3] Linn, J., Privacy Enhancement for Internet Electronic Mail: Part III -- Algorithms, Modes, and Identifiers (RFC 1115), August 1989. [4] CCITT, The Directory---Authentication Framework (Recommendation X.509), 1988. Author's Address Burton S. Kaliski Jr. RSA Data Security, Inc. 10 Twin Dolphin Drive Redwood City, CA 94065 Phone: (415) 595-8782 FAX: (415) 595-1873 EMail: kaliski@rsa.com Kaliski [Page 5] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 APPENDIX - Reference Implementation This appendix contains the following files: md2.h -- header file for implementation of MD2 md2.c -- the source code for MD2 routines md2driver.c -- sample test routines session -- sample results of running md2driver Kaliski [Page 6] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 /* *********************************************************************** ** md2.h -- header file for implementation of MD2 ** ** RSA Data Security, Inc. MD2 Message-Digest Algorithm ** ** Created: 10/1/88 RLR ** ** Revised: 12/27/90 SRD,BSK,JT Reference C version ** *********************************************************************** */ /* *********************************************************************** ** Copyright (C) 1990, RSA Data Security, Inc. All rights reserved. ** ** ** ** License to copy and use this software is granted for ** ** non-commercial Internet privacy-enhanced mail provided that it ** ** is identified as the "RSA Data Security, Inc. MD2 Message-Digest ** ** Algorithm" in all material mentioning or referencing this ** ** software or this function. ** ** ** ** RSA Data Security, Inc. makes no representations concerning ** ** either the merchantability of this software or the suitability ** ** of this software for any particular purpose. It is provided "as ** ** is" without express or implied warranty of any kind. ** ** ** ** These notices must be retained in any copies of any part of this ** ** documentation and/or software. ** *********************************************************************** */ /* Data structure for MD2 (Message-Digest) computation */ typedef struct { unsigned char buf[48]; /* buffer for forming md into. Actual digest is buf[0]...buf[15] */ unsigned char mac[16]; /* mac register */ unsigned char i; /* number of bytes handled, modulo 16 */ unsigned char lastMac; /* last mac value saved */ } MD2_CTX; void MD2Init (); void MD2Update (); void MD2Final (); /* *********************************************************************** ** End of md2.h ** ******************************** (cut) ******************************** */ Kaliski [Page 7] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 /* *********************************************************************** ** md2.c -- the source code for MD2 routines ** ** RSA Data Security, Inc. MD2 Message-Digest Algorithm ** ** Created: 10/1/88 RLR ** ** Revised: 12/27/90 SRD,BSK,JT Reference C version ** *********************************************************************** */ /* *********************************************************************** ** Copyright (C) 1990, RSA Data Security, Inc. All rights reserved. ** ** ** ** License to copy and use this software is granted for ** ** non-commercial Internet privacy-enhanced mail provided that it ** ** is identified as the "RSA Data Security, Inc. MD2 Message-Digest ** ** Algorithm" in all material mentioning or referencing this ** ** software or this function. ** ** ** ** RSA Data Security, Inc. makes no representations concerning ** ** either the merchantability of this software or the suitability ** ** of this software for any particular purpose. It is provided "as ** ** is" without express or implied warranty of any kind. ** ** ** ** These notices must be retained in any copies of any part of this ** ** documentation and/or software. ** *********************************************************************** */ #include "md2.h" /* *********************************************************************** ** Message-digest routines: ** ** To form the message digest for a message M ** ** (1) Initialize a context buffer mdContext using MD2Init ** ** (2) Call MD2Update on mdContext and M ** ** (3) Call MD2Final on mdContext ** ** The message digest is now in mdContext->buf[0...15] ** *********************************************************************** */ /* *********************************************************************** ** The table given below is a permutation of 0...255 constructed ** ** from the digits of pi. It is a "random" nonlinear byte ** ** substitution operation. ** *********************************************************************** */ static unsigned char PI_SUBST[256] = { 41, 46, 67,201,162,216,124, 1, 61, 54, 84,161,236,240, 6, 19, 98,167, 5,243,192,199,115,140,152,147, 43,217,188, 76,130,202, Kaliski [Page 8] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 30,155, 87, 60,253,212,224, 22,103, 66,111, 24,138, 23,229, 18, 190, 78,196,214,218,158,222, 73,160,251,245,142,187, 47,238,122, 169,104,121,145, 21,178, 7, 63,148,194, 16,137, 11, 34, 95, 33, 128,127, 93,154, 90,144, 50, 39, 53, 62,204,231,191,247,151, 3, 255, 25, 48,179, 72,165,181,209,215, 94,146, 42,172, 86,170,198, 79,184, 56,210,150,164,125,182,118,252,107,226,156,116, 4,241, 69,157,112, 89,100,113,135, 32,134, 91,207,101,230, 45,168, 2, 27, 96, 37,173,174,176,185,246, 28, 70, 97,105, 52, 64,126, 15, 85, 71,163, 35,221, 81,175, 58,195, 92,249,206,186,197,234, 38, 44, 83, 13,110,133, 40,132, 9,211,223,205,244, 65,129, 77, 82, 106,220, 55,200,108,193,171,250, 36,225,123, 8, 12,189,177, 74, 120,136,149,139,227, 99,232,109,233,203,213,254, 59, 0, 29, 57, 242,239,183, 14,102, 88,208,228,166,119,114,248,235,117, 75, 10, 49, 68, 80,180,143,237, 31, 26,219,153,141, 51,159, 17,131, 20, }; /* The routine MD2Init initializes the message-digest context mdContext. All fields are set to zero. */ void MD2Init (mdContext) MD2_CTX *mdContext; { int i; for (i = 0; i < 16; i++) mdContext->buf[i] = mdContext->mac[i] = 0; mdContext->i = 0; mdContext->lastMac = 0; } /* The routine MD2Update updates the message digest context to account for the presence of each of the characters inBuf[0..inLen-1] in the message whose digest is being computed. */ void MD2Update (mdContext, inBuf, inLen) MD2_CTX *mdContext; unsigned char *inBuf; unsigned int inLen; { unsigned char mdi, t, j, ix; /* put mdContext->i into local variable for efficiency */ mdi = mdContext->i; while (inLen--) { /* Add new character to buffer */ mdContext->buf[16+mdi] = *inBuf; mdContext->buf[32+mdi] = *inBuf ^ mdContext->buf[mdi]; /* Update MAC */ mdContext->lastMac = (mdContext->mac[mdi] ^= Kaliski [Page 9] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 PI_SUBST[0xFF & (*inBuf++ ^ mdContext->lastMac)]); /* Increment mdi */ mdi++; /* Encrypt if necessary */ if (mdi == 16) { t = 0; for (j = 0; j < 18; j++) { for (ix = 0; ix < 48; ix++) t = mdContext->buf[ix] = mdContext->buf[ix] ^ PI_SUBST[t]; t = t + j; } mdi = 0; } /* New digest is in mdContext->buf[0]..mdContext->buf[15] */ } mdContext->i = mdi; } /* The routine MD2Final terminates the message-digest computation and ends with the desired message digest in mdContext->buf[0...15]. */ void MD2Final (mdContext) MD2_CTX *mdContext; { int i; unsigned char padLen; padLen = (unsigned char) 16 - mdContext->i; /* pad out to multiple of 16 */ for (i = 0; i < (int)padLen; i++) MD2Update (mdContext, &padLen, 1); /* extend with MAC. Note that even though mac is updated with each char, the mac added in is what it was at the end of the padding operation */ MD2Update (mdContext, mdContext->mac, 16); } /* *********************************************************************** ** End of md2.c ** ******************************** (cut) ******************************** */ Kaliski [Page 10] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 /* *********************************************************************** ** md2driver.c -- sample test routines ** ** RSA Data Security, Inc. MD2 Message-Digest Algorithm ** ** Created: 2/16/90 RLR ** ** Updated: 12/27/90 SRD ** *********************************************************************** */ /* *********************************************************************** ** Copyright (C) 1990, RSA Data Security, Inc. All rights reserved. ** ** ** ** RSA Data Security, Inc. makes no representations concerning ** ** either the merchantability of this software or the suitability ** ** of this software for any particular purpose. It is provided "as ** ** is" without express or implied warranty of any kind. ** ** ** ** These notices must be retained in any copies of any part of this ** ** documentation and/or software. ** *********************************************************************** */ #include #include #include #include #include "md2.h" /* Prints message digest buffer in mdContext as 32 hexadecimal digits. Order is from low-order byte to high-order byte of buffer. Each byte is printed with high-order hexadecimal digit first. */ static void MDPrint (mdContext) MD2_CTX *mdContext; { int i; for (i = 0; i < 16; i++) printf ("%02x", mdContext->buf[i]); } /* size of test block */ #define TEST_BLOCK_SIZE 1000 /* number of blocks to process */ #define TEST_BLOCKS 1000 /* number of test bytes = TEST_BLOCK_SIZE * TEST_BLOCKS */ static long TEST_BYTES = (long)TEST_BLOCK_SIZE * (long)TEST_BLOCKS; /* A time trial routine, to measure the speed of MD2. Kaliski [Page 11] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 Measures wall time required to digest TEST_BLOCKS * TEST_BLOCK_SIZE characters. */ static void MDTimeTrial () { MD2_CTX mdContext; time_t endTime, startTime; unsigned char data[TEST_BLOCK_SIZE]; unsigned int i; /* initialize test data */ for (i = 0; i < TEST_BLOCK_SIZE; i++) data[i] = (unsigned char) (i & 0xFF); /* start timer */ printf ("MD2 time trial. Processing %ld characters...\n", TEST_BYTES); time (&startTime); /* digest data in TEST_BLOCK_SIZE byte blocks */ MD2Init (&mdContext); for (i = TEST_BLOCKS; i > 0; i--) MD2Update (&mdContext, data, TEST_BLOCK_SIZE); MD2Final (&mdContext); /* stop timer, get time difference */ time (&endTime); MDPrint (&mdContext); printf (" is digest of test input.\n"); printf ("Seconds to process test input: %ld\n", (long)(endTime-startTime)); printf ("Characters processed per second: %ld\n", TEST_BYTES/(endTime-startTime)); } /* Computes the message digest for string inString. Prints out message digest, a space, the string (in quotes) and a carriage return. */ static void MDString (inString) char *inString; { MD2_CTX mdContext; unsigned int len = strlen (inString); MD2Init (&mdContext); MD2Update (&mdContext, inString, len); MD2Final (&mdContext); MDPrint (&mdContext); printf (" \"%s\"\n", inString); } Kaliski [Page 12] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 /* Computes the message digest for a specified file. Prints out message digest, a space, the file name, and a carriage return. */ static void MDFile (filename) char *filename; { FILE *inFile = fopen (filename, "rb"); MD2_CTX mdContext; int bytes; unsigned char data[1024]; if (inFile == NULL) { printf ("%s can't be opened.\n", filename); return; } MD2Init (&mdContext); while ((bytes = fread (data, 1, 1024, inFile)) != 0) MD2Update (&mdContext, data, bytes); MD2Final (&mdContext); MDPrint (&mdContext); printf (" %s\n", filename); fclose (inFile); } /* Writes the message digest of the data from stdin onto stdout, followed by a carriage return. */ static void MDFilter () { MD2_CTX mdContext; int bytes; unsigned char data[16]; MD2Init (&mdContext); while ((bytes = fread (data, 1, 16, stdin)) != 0) MD2Update (&mdContext, data, bytes); MD2Final (&mdContext); MDPrint (&mdContext); printf ("\n"); } /* Runs a standard suite of test data. */ static void MDTestSuite () { printf ("MD2 test suite results:\n"); MDString (""); MDString ("a"); MDString ("abc"); MDString ("message digest"); Kaliski [Page 13] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 MDString ("abcdefghijklmnopqrstuvwxyz"); MDString ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"); MDString ("1234567890123456789012345678901234567890\ 1234567890123456789012345678901234567890"); /* Contents of file foo are "abc" */ MDFile ("foo"); } void main (argc, argv) int argc; char *argv[]; { int i; /* For each command line argument in turn: ** filename -- prints message digest and name of file ** -sstring -- prints message digest and contents of string ** -t -- prints time trial statistics for 1M characters ** -x -- execute a standard suite of test data ** (no args) -- writes messages digest of stdin onto stdout */ if (argc == 1) MDFilter (); else for (i = 1; i < argc; i++) if (argv[i][0] == '-' && argv[i][1] == 's') MDString (argv[i] + 2); else if (strcmp (argv[i], "-t") == 0) MDTimeTrial (); else if (strcmp (argv[i], "-x") == 0) MDTestSuite (); else MDFile (argv[i]); } /* *********************************************************************** ** End of md2driver.c ** ******************************** (cut) ******************************** */ Kaliski [Page 14] INTERNET-DRAFT The MD2 Message-Digest Algorithm 1 July 1991 ------------------------------------------------------------------------ -- Sample session output obtained by running md2driver test suite -- ------------------------------------------------------------------------ MD2 test suite results: 8350e5a3e24c153df2275c9f80692773 "" 32ec01ec4a6dac72c0ab96fb34c0b5d1 "a" da853b0d3f88d99b30283a69e6ded6bb "abc" ab4f496bfb2a530b219ff33031fe06b0 "message digest" 4e8ddff3650292ab5a4108c3aa47940b "abcdefghijklmnopqrstuvwxyz" da33def2a42df13975352846c30338cd "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijk\ lmnopqrstuvwxyz0123456789" d5976f79d83d3a0dc9806c3c66f3efd8 "1234567890123456789012345678901234567\ 8901234567890123456789012345678901234567890" da853b0d3f88d99b30283a69e6ded6bb foo ------------------------------------------------------------------------ -- End of sample session -- -------------------------------- (cut) --------------------------------- Kaliski [Page 15]