Network Working Group B. Kaliski INTERNET-DRAFT RSA Data Security, Inc. 13 May 1991 The MD2 Message-Digest Algorithm STATUS OF THIS MEMO This draft document will be submitted to the RFC editor as an informational RFC (not as a standards document), and is submitted as a proposed update to current RFC 1115. References within the text of this Internet-Draft to this document as an RFC are not intended to carry any connotation about the progression of this Internet-Draft through the IAB informational RFC review cycle. Distribution of this memo is unlimited. Comments should be sent to or to the author. This document may be referred to, unofficially, as RFC [MD2-A]. 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 4 References 4 Author's Address 5 APPENDIX - Reference Implementation 6 1. Executive Summary This note 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. Kaliski [Page 1] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 1991 License to use MD2 is granted for non-commerical Internet Privacy- Enhanced Mail [1-6]. This RFC is an 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 "md2.doc". 2. Terminology and Notation In this note 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). 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. Kaliski [Page 2] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 1991 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. 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 */ Kaliski [Page 3] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 1991 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. 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. Kaliski [Page 4] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 1991 [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] Linn, J., Privacy Enhancement for Internet Electronic Mail: Part I -- Message Encryption and Authentication Procedures (RFC [1113D]), March 1991. [5] Kent, S., Privacy Enhancement for Internet Electronic Mail: Part II -- Certificate-Based Key Management (RFC [1114B]), February 1991. [6] Balenson, D., Privacy Enhancement for Internet Electronic Mail: Part III -- Algorithms, Modes, and Identifiers (RFC [1115B]), February 1991. 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 13 May 1991 APPENDIX - Reference Implementation This appendix contains the following files: md2.h -- header file for using MD2 implementation md2.c -- the source code for MD2 routines md2driver.c -- sample test routines session -- output of md2driver test suite Kaliski [Page 6] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 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 { /* buffer for forming md into. Actual digest is buf[0]...buf[15] */ unsigned char buf[48]; 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 13 May 1991 /* *********************************************************************** ** md2.c ** ** 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, 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, Kaliski [Page 8] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 1991 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 buffer; 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 M[0..inLen-1] in the message pointed to by inBuf 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] ^= PI_SUBST[0xFF & (*inBuf++ ^ mdContext->lastMac)]); /* Increment mdi */ mdi++; Kaliski [Page 9] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 1991 /* 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 being 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 13 May 1991 /* *********************************************************************** ** md2driver.c -- sample routines to test ** ** 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. Measures wall time required to digest TEST_BLOCKS * TEST_BLOCK_SIZE characters. Kaliski [Page 11] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 1991 */ 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); } /* Computes the message digest for a specified file. Prints out message digest, a space, the file name, and a carriage return. */ Kaliski [Page 12] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 1991 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"); MDString ("abcdefghijklmnopqrstuvwxyz"); MDString ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"); MDString ("1234567890123456789012345678901234567890\ 1234567890123456789012345678901234567890"); Kaliski [Page 13] INTERNET-DRAFT The MD2 Message-Digest Algorithm 13 May 1991 /* 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 13 May 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]