Network Working Group B. Kaliski Request for Comments: [MD2] RSA Data Security, Inc. Supersedes: RFC 1115 18 December 1990 The MD2 Message Digest Algorithm STATUS OF THIS MEMO (to be supplied) 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 1 3. MD2 Algorithm Description 2 4. Summary 4 APPENDIX - Reference Implementation 4 Security Considerations 12 Author's Address 13 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 thus ideal for digital signature applications, where a large file must be "compressed" in a secure manner before being signed with the RSA public-key cryptosystem. MD2 may be used in support of privacy-enhanced mail, free of licensing restrictions. 2. Terminology and Notation In this note a byte is an 8-bit quantity. Kaliski [Page 1] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 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 bits The message is "padded" (extended) so that its length (in bytes) is congruent to 0, modulo 16. 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. 3.2 Step 2. Append checksum A 16-byte checksum of the message is appended to the result of the previous step. 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. 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: For i = 0 to 15 do: Set C[i] to 0. end /* of loop on i */ Kaliski [Page 2] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 Set L to 0. For i = 0 to N/16-1 do: /* process each 16-word block */ For j = 0 to 15 do: /* checksum block i */ 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: For i = 0 to N'/16-1 do: /* process each 16-word block */ For j = 0 to 15 do: /* copy block i into X */ 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. 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]. Kaliski [Page 3] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 This completes the description of MD4. 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. The level of security provided by MD2 should be sufficient for implementing very high security hybrid digital signature schemes based on MD2 and the RSA public-key cryptosystem. 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 /* ********************************************************************** ** 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 ** Kaliski [Page 4] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 ** 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 MD2Block (); void MD2Final (); /* ********************************************************************** ** End of md2.h ** *************************** (cut) ************************************ */ /* ********************************************************************** ** 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. ** Kaliski [Page 5] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 ** ** ** 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 MD2Block 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, 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; Kaliski [Page 6] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 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 MD2Block 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 MD2Block (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++; /* 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; } Kaliski [Page 7] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 /* 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++) MD2Block (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 */ MD2Block (mdContext, mdContext->mac, 16); } /* ********************************************************************** ** End of md2.c ** *************************** (cut) ************************************ */ /* ********************************************************************** ** 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. ** ** ** Kaliski [Page 8] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 ** 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 TESTBYTES = (long)TEST_BLOCK_SIZE * (long)TEST_BLOCKS; /* A time trial routine, to measure the speed of MD2. Measures wall time required to digest TESTBLOCKS*TESTBLOCKSIZE 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 = TEST_BLOCK_SIZE; i > 0; i--) data[i] = (unsigned char) (i & 0xFF); /* start timer */ printf ("MD2 time trial. Processing %ld characters...\n", (long) TESTBYTES); Kaliski [Page 9] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 time (&startTime); /* digest data in TEST_BLOCK_SIZE byte blocks */ MD2Init (&mdContext); for (i = TEST_BLOCKS; i > 0; i--) MD2Block (&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", (long)TESTBYTES/(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) unsigned char *inString; { MD2_CTX mdContext; unsigned int len = strlen(inString); MD2Init (&mdContext); MD2Block (&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. */ 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; Kaliski [Page 10] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 } MD2Init (&mdContext); while ((bytes = fread (data, 1, 1024, inFile)) != 0) MD2Block (&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) MD2Block (&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"); /* 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 Kaliski [Page 11] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 ** -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) ************************************ */ ----------------------------------------------------------------------- -- Sample session output obtained by running md2driver test suite -- ----------------------------------------------------------------------- MD2 test suite results: 8350e5a3e24c153df2275c9f80692773 "" 32ec01ec4a6dac72c0ab96fb34c0b5d1 "a" da853b0d3f88d99b30283a69e6ded6bb "abc" ab4f496bfb2a530b219ff33031fe06b0 "message digest" 4e8ddff3650292ab5a4108c3aa47940b "abcdefghijklmnopqrstuvwxyz" da33def2a42df13975352846c30338cd "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghij\ klmnopqrstuvwxyz0123456789" da853b0d3f88d99b30283a69e6ded6bb foo ----------------------------------------------------------------------- -- End of sample session -- ---------------------------- (cut) ------------------------------------ Note: A version of this document including the C source code is available for FTP from RSA.COM in the file "md2.doc". Security Considerations (to be supplied) Kaliski [Page 12] RFC [MD2] The MD2 Message Digest Algorithm 18 December 1990 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: burt@rsa.com Kaliski [Page 13]