summaryrefslogtreecommitdiffstats
path: root/src/lib/crypto
diff options
context:
space:
mode:
authorTheodore Tso <tytso@mit.edu>1993-06-03 19:29:40 +0000
committerTheodore Tso <tytso@mit.edu>1993-06-03 19:29:40 +0000
commit746386f12e01102acbe5637aac6f1259c74bb552 (patch)
tree715df6527f739854dc978c588047607e1907e9e9 /src/lib/crypto
parentacbed92e113f54d33789d427e697a23a0f07ab64 (diff)
Initial revision
git-svn-id: svn://anonsvn.mit.edu/krb5/trunk@2611 dc483132-0cff-0310-8789-dd5450dbe970
Diffstat (limited to 'src/lib/crypto')
-rw-r--r--src/lib/crypto/des/.rconf8
-rw-r--r--src/lib/crypto/des/FUNCTIONS26
-rw-r--r--src/lib/crypto/des/doc/libdes.doc208
-rw-r--r--src/lib/crypto/des/keytest.data171
-rw-r--r--src/lib/crypto/md4/.rconf2
-rw-r--r--src/lib/crypto/md4/RFC1186.TXT1011
-rw-r--r--src/lib/crypto/md4/RFC1186B.TXT1041
7 files changed, 2467 insertions, 0 deletions
diff --git a/src/lib/crypto/des/.rconf b/src/lib/crypto/des/.rconf
new file mode 100644
index 000000000..b88696486
--- /dev/null
+++ b/src/lib/crypto/des/.rconf
@@ -0,0 +1,8 @@
+ignore fp.c
+ignore ip.c
+ignore key_perm.h
+ignore odd.h
+ignore p.c
+ignore p_table.h
+ignore s_table.h
+ignore doc
diff --git a/src/lib/crypto/des/FUNCTIONS b/src/lib/crypto/des/FUNCTIONS
new file mode 100644
index 000000000..7ed082e32
--- /dev/null
+++ b/src/lib/crypto/des/FUNCTIONS
@@ -0,0 +1,26 @@
+File Function Where?
+
+weak_key.c mit_des_is_weak_key crypto
+string2key.c mit_des_string_to_key ?
+random_key.c mit_des_random_key ?
+process_ky.c mit_des_process_key ?
+new_rn_key.c mit_des_new_random_key ?
+ mit_des_init_random_number_generator ?
+ mit_des_set_random_generator_seed ?
+ mit_des_set_sequence_number ?
+ mit_des_generate_random_block ?
+krb_glue.c mit_des_encrypt_func ?
+ mit_des_decrypt_func ?
+key_sched.c mit_des_key_sched crypto
+key_parity.c mit_des_fixup_key_parity crypto
+ mit_des_check_key_parity crypto
+init_rkey.c mit_des_init_random_key crypto
+finish_key.c mit_des_finish_key crypto
+fin_rndkey.c mit_des_finish_random_key crypto
+enc_dec.c mit_des_cbc_encrypt crypto
+des.c mit_des_ecb_encrypt crypto
+cs_entry.c (var) mit_des_cryptosystem_entry krb5
+ (var) krb5_des_cst_entry krb5
+ (var) mit_des_cbc_cksumtable_entry krb5
+cksum.c mit_des_cbc_cksum crypto
+cbc_cksum.c mit_des_cbc_checksum crypto
diff --git a/src/lib/crypto/des/doc/libdes.doc b/src/lib/crypto/des/doc/libdes.doc
new file mode 100644
index 000000000..70f9f336a
--- /dev/null
+++ b/src/lib/crypto/des/doc/libdes.doc
@@ -0,0 +1,208 @@
+
+ How to use the Kerberos encryption library.
+
+ Revised 10/15/85 spm
+
+1) The following include file is needed:
+
+ /projects/auth/include/des.h (VAX)
+ --------------- (PC8086)
+
+2) The encryption library that should be linked to is:
+
+ /projects/auth/lib/libdes.a (VAX)
+| /projects/auth/ibm/lib/libdes.a (PC8086 cross-compilation environment)
+
+3) For each key that may be simultaneously active,
+ allocate (either compile or malloc) a "Key_schedule" struct,
+ defined in "des.h"
+
+4) Create key schedules, as needed, prior to using the encryption
+ routines, via "des_set_key()".
+
+5) Setup the input and output areas. Make sure to note the restrictions
+ on lengths being multiples of eight bytes.
+
+6) Invoke the encryption/decryption routines, "ecb_encrypt()"
+ or "cbc_encrypt()"
+
+7) To generate a cryptographic checksum, use "cbc_cksum()"
+/* ---------------------------------------------------------------- */
+
+ Routine Interfaces--
+
+/* ----------------------------------------------------------------- */
+
+int
+ des_set_key(k,schedule)
+ C_Block *k;
+ Key_schedule schedule;
+
+ Calculates a key schedule from (all) eight bytes of the input key, and
+ puts it into the indicated "Key_schedule" struct;
+
+ Make sure to pass valid eight bytes, no padding or other processing
+ it done.
+
+ The key schedule is then used in subsequent encryption/decryption
+ operations. Many key schedules may be created and cached for later
+ use.
+
+ The user is responsible to clear keys and schedules no longer needed
+ to prevent their disclosure.
+
+| Checks the parity of the key provided, to make sure it is odd per
+| FIPS spec. Returns 0 value for key ok, 1 for key_parity error.
+
+/* ---------------------------------------------------------------- */
+
+int
+ ecb_encrypt(input,output,schedule,encrypt)
+ C_Block *input; /* ptr to eight byte input value */
+ C_Block *output; /* ptr to eight byte output value */
+ int encrypt; /* 0 ==> decrypt, else encrypt */
+ Key_schedule schedule; /* addr of key schedule */
+
+This is the low level routine that encrypts or decrypts a single 8-byte
+block in electronic code book mode. Always transforms the input
+data into the output data.
+
+If encrypt is non-zero, the input (cleartext) is encrypted into the
+output (ciphertext) using the specified key_schedule, pre-set via "des_set_key".
+
+If encrypt is zero, the input (now ciphertext) is decrypted into
+the output (now cleartext).
+
+Input and output may be the same space.
+
+Does not return any meaningful value. Void is not used for compatibility
+with other compilers.
+
+/* -------------------------------------------------------------- */
+
+int
+ cbc_encrypt(input,output,length,schedule,ivec,encrypt)
+
+ C_Block *input; /* ptr to input data */
+ C_Block *output; /* ptr to output data */
+ int length; /* desired length, in bytes */
+ Key_schedule schedule; /* addr of precomputed schedule */
+ C_Block *ivec; /* pointer to 8 byte initialization
+ * vector
+ */
+ int encrypt /* 0 ==> decrypt; else encrypt*/
+
+
+ If encrypt is non-zero, the routine cipher-block-chain encrypts
+ the INPUT (cleartext) into the OUTPUT (ciphertext) using the provided
+ key schedule and initialization vector. If the length is not an integral
+ multiple of eight bytes, the last block is copied to a temp and zero
+ filled (highest addresses). The output is ALWAYS an integral multiple
+ of eight bytes.
+
+ If encrypt is zero, the routine cipher-block chain decrypts the INPUT
+ (ciphertext) into the OUTPUT (cleartext) using the provided key schedule
+ and initialization vector. Decryption ALWAYS operates on integral
+ multiples of 8 bytes, so will round the length provided up to the
+ appropriate multiple. Consequently, it will always produce the rounded-up
+ number of bytes of output cleartext. The application must determine if
+ the output cleartext was zero-padded due to cleartext lengths not integral
+ multiples of 8.
+
+ No errors or meaningful value are returned. Void is not used for
+ compatibility with other compilers.
+
+
+/* cbc checksum (MAC) only routine ---------------------------------------- */
+int
+ cbc_cksum(input,output,length,schedule,ivec)
+
+ C_Block *input; /* >= length bytes of inputtext */
+ C_Block *output; /* >= length bytes of outputtext */
+ int length; /* in bytes */
+ Key_schedule schedule; /* precomputed key schedule */
+ C_Block *ivec; /* 8 bytes of ivec */
+
+
+ Produces a cryptographic checksum, 8 bytes, by cipher-block-chain
+ encrypting the input, discarding the ciphertext output, and only retaining
+ the last ciphertext 8-byte block. Uses the provided key schedule and ivec.
+ The input is effectively zero-padded to an integral multiple of
+ eight bytes, though the original input is not modified.
+
+ No meaningful value is returned. Void is not used for compatibility
+ with other compilers.
+
+
+/* random_key ----------------------------------------*/
+int
+ random_key(key)
+
+ C_Block *key;
+
+ The start for the random number generated is set from the current time
+ in microseconds, then the random number generator is invoked
+ to create an eight byte output key (not a schedule). The key
+ generated is set to odd parity per FIPS spec.
+
+ The caller must supply space for the output key, pointed to
+ by "*key", then after getting a new key, call the des_set_key()
+ routine when needed.
+
+ No meaningfull value is returned. Void is not used for compatibility
+ with other compilers.
+
+
+/* string_to_key --------------------------------------------*/
+
+int
+ string_to_key(str,key)
+ register char *str;
+ register C_Block *key;
+
+ This routines converts an arbitrary length, null terminated string
+ to an 8 byte DES key, with each byte parity set to odd, per FIPS spec.
+
+ The algorithm is as follows:
+
+| Take the first 8 bytes and remove the parity (leaving 56 bits).
+| Do the same for the second 8 bytes, and the third, etc. Do this for
+| as many sets of 8 bytes as necessary, filling in the remainder of the
+| last set with nulls. Fold the second set back on the first (i.e. bit
+| 0 over bit 55, and bit 55 over bit 0). Fold the third over the second
+| (bit 0 of the third set is now over bit 0 of the first set). Repeat
+| until you have done this to all sets. Xor the folded sets. Break the
+| result into 8 7 bit bytes, and generate odd parity for each byte. You
+| now have 64 bits. Note that DES takes a 64 bit key, and uses only the
+| non parity bits.
+
+
+/* read_password -------------------------------------------*/
+
+read_password(k,prompt,verify)
+ C_Block *k;
+ char *prompt;
+ int verify;
+
+This routine issues the supplied prompt, turns off echo, if possible, and
+reads an input string. If verify is non-zero, it does it again, for use
+in applications such as changing a password. If verify is non-zero, both
+versions are compared, and the input is requested repeatedly until they
+match. Then, the input string is mapped into a valid DES key, internally
+using the string_to_key routine. The newly created key is copied to the
+area pointed to by parameter "k".
+
+No meaningful value is returned. If an error occurs trying to manipulate
+the terminal echo, the routine forces the process to exit.
+
+/* get_line ------------------------*/
+long get_line(p,max)
+ char *p;
+ long max;
+
+Reads input characters from standard input until either a newline appears or
+else the max length is reached. The characters read are stuffed into
+the string pointed to, which will always be null terminated. The newline
+is not inserted in the string. The max parameter includes the byte needed
+for the null terminator, so allocate and pass one more than the maximum
+string length desired.
diff --git a/src/lib/crypto/des/keytest.data b/src/lib/crypto/des/keytest.data
new file mode 100644
index 000000000..7ff34eedc
--- /dev/null
+++ b/src/lib/crypto/des/keytest.data
@@ -0,0 +1,171 @@
+0101010101010101 95F8A5E5DD31D900 8000000000000000
+0101010101010101 DD7F121CA5015619 4000000000000000
+0101010101010101 2E8653104F3834EA 2000000000000000
+0101010101010101 4BD388FF6CD81D4F 1000000000000000
+0101010101010101 20B9E767B2FB1456 0800000000000000
+0101010101010101 55579380D77138EF 0400000000000000
+0101010101010101 6CC5DEFAAF04512F 0200000000000000
+0101010101010101 0D9F279BA5D87260 0100000000000000
+0101010101010101 D9031B0271BD5A0A 0080000000000000
+0101010101010101 424250B37C3DD951 0040000000000000
+0101010101010101 B8061B7ECD9A21E5 0020000000000000
+0101010101010101 F15D0F286B65BD28 0010000000000000
+0101010101010101 ADD0CC8D6E5DEBA1 0008000000000000
+0101010101010101 E6D5F82752AD63D1 0004000000000000
+0101010101010101 ECBFE3BD3F591A5E 0002000000000000
+0101010101010101 F356834379D165CD 0001000000000000
+0101010101010101 2B9F982F20037FA9 0000800000000000
+0101010101010101 889DE068A16F0BE6 0000400000000000
+0101010101010101 E19E275D846A1298 0000200000000000
+0101010101010101 329A8ED523D71AEC 0000100000000000
+0101010101010101 E7FCE22557D23C97 0000080000000000
+0101010101010101 12A9F5817FF2D65D 0000040000000000
+0101010101010101 A484C3AD38DC9C19 0000020000000000
+0101010101010101 FBE00A8A1EF8AD72 0000010000000000
+0101010101010101 750D079407521363 0000008000000000
+0101010101010101 64FEED9C724C2FAF 0000004000000000
+0101010101010101 F02B263B328E2B60 0000002000000000
+0101010101010101 9D64555A9A10B852 0000001000000000
+0101010101010101 D106FF0BED5255D7 0000000800000000
+0101010101010101 E1652C6B138C64A5 0000000400000000
+0101010101010101 E428581186EC8F46 0000000200000000
+0101010101010101 AEB5F5EDE22D1A36 0000000100000000
+0101010101010101 E943D7568AEC0C5C 0000000080000000
+0101010101010101 DF98C8276F54B04B 0000000040000000
+0101010101010101 B160E4680F6C696F 0000000020000000
+0101010101010101 FA0752B07D9C4AB8 0000000010000000
+0101010101010101 CA3A2B036DBC8502 0000000008000000
+0101010101010101 5E0905517BB59BCF 0000000004000000
+0101010101010101 814EEB3B91D90726 0000000002000000
+0101010101010101 4D49DB1532919C9F 0000000001000000
+0101010101010101 25EB5FC3F8CF0621 0000000000800000
+0101010101010101 AB6A20C0620D1C6F 0000000000400000
+0101010101010101 79E90DBC98F92CCA 0000000000200000
+0101010101010101 866ECEDD8072BB0E 0000000000100000
+0101010101010101 8B54536F2F3E64A8 0000000000080000
+0101010101010101 EA51D3975595B86B 0000000000040000
+0101010101010101 CAFFC6AC4542DE31 0000000000020000
+0101010101010101 8DD45A2DDF90796C 0000000000010000
+0101010101010101 1029D55E880EC2D0 0000000000008000
+0101010101010101 5D86CB23639DBEA9 0000000000004000
+0101010101010101 1D1CA853AE7C0C5F 0000000000002000
+0101010101010101 CE332329248F3228 0000000000001000
+0101010101010101 8405D1ABE24FB942 0000000000000800
+0101010101010101 E643D78090CA4207 0000000000000400
+0101010101010101 48221B9937748A23 0000000000000200
+0101010101010101 DD7C0BBD61FAFD54 0000000000000100
+0101010101010101 2FBC291A570DB5C4 0000000000000080
+0101010101010101 E07C30D7E4E26E12 0000000000000040
+0101010101010101 0953E2258E8E90A1 0000000000000020
+0101010101010101 5B711BC4CEEBF2EE 0000000000000010
+0101010101010101 CC083F1E6D9E85F6 0000000000000008
+0101010101010101 D2FD8867D50D2DFE 0000000000000004
+0101010101010101 06E7EA22CE92708F 0000000000000002
+0101010101010101 166B40B44ABA4BD6 0000000000000001
+8001010101010101 0000000000000000 95A8D72813DAA94D
+4001010101010101 0000000000000000 0EEC1487DD8C26D5
+2001010101010101 0000000000000000 7AD16FFB79C45926
+1001010101010101 0000000000000000 D3746294CA6A6CF3
+0801010101010101 0000000000000000 809F5F873C1FD761
+0401010101010101 0000000000000000 C02FAFFEC989D1FC
+0201010101010101 0000000000000000 4615AA1D33E72F10
+0180010101010101 0000000000000000 2055123350C00858
+0140010101010101 0000000000000000 DF3B99D6577397C8
+0120010101010101 0000000000000000 31FE17369B5288C9
+0110010101010101 0000000000000000 DFDD3CC64DAE1642
+0108010101010101 0000000000000000 178C83CE2B399D94
+0104010101010101 0000000000000000 50F636324A9B7F80
+0102010101010101 0000000000000000 A8468EE3BC18F06D
+0101800101010101 0000000000000000 A2DC9E92FD3CDE92
+0101400101010101 0000000000000000 CAC09F797D031287
+0101200101010101 0000000000000000 90BA680B22AEB525
+0101100101010101 0000000000000000 CE7A24F350E280B6
+0101080101010101 0000000000000000 882BFF0AA01A0B87
+0101040101010101 0000000000000000 25610288924511C2
+0101020101010101 0000000000000000 C71516C29C75D170
+0101018001010101 0000000000000000 5199C29A52C9F059
+0101014001010101 0000000000000000 C22F0A294A71F29F
+0101012001010101 0000000000000000 EE371483714C02EA
+0101011001010101 0000000000000000 A81FBD448F9E522F
+0101010801010101 0000000000000000 4F644C92E192DFED
+0101010401010101 0000000000000000 1AFA9A66A6DF92AE
+0101010201010101 0000000000000000 B3C1CC715CB879D8
+0101010180010101 0000000000000000 19D032E64AB0BD8B
+0101010140010101 0000000000000000 3CFAA7A7DC8720DC
+0101010120010101 0000000000000000 B7265F7F447AC6F3
+0101010110010101 0000000000000000 9DB73B3C0D163F54
+0101010108010101 0000000000000000 8181B65BABF4A975
+0101010104010101 0000000000000000 93C9B64042EAA240
+0101010102010101 0000000000000000 5570530829705592
+0101010101800101 0000000000000000 8638809E878787A0
+0101010101400101 0000000000000000 41B9A79AF79AC208
+0101010101200101 0000000000000000 7A9BE42F2009A892
+0101010101100101 0000000000000000 29038D56BA6D2745
+0101010101080101 0000000000000000 5495C6ABF1E5DF51
+0101010101040101 0000000000000000 AE13DBD561488933
+0101010101020101 0000000000000000 024D1FFA8904E389
+0101010101018001 0000000000000000 D1399712F99BF02E
+0101010101014001 0000000000000000 14C1D7C1CFFEC79E
+0101010101012001 0000000000000000 1DE5279DAE3BED6F
+0101010101011001 0000000000000000 E941A33F85501303
+0101010101010801 0000000000000000 DA99DBBC9A03F379
+0101010101010401 0000000000000000 B7FC92F91D8E92E9
+0101010101010201 0000000000000000 AE8E5CAA3CA04E85
+0101010101010180 0000000000000000 9CC62DF43B6EED74
+0101010101010140 0000000000000000 D863DBB5C59A91A0
+0101010101010120 0000000000000000 A1AB2190545B91D7
+0101010101010110 0000000000000000 0875041E64C570F7
+0101010101010108 0000000000000000 5A594528BEBEF1CC
+0101010101010104 0000000000000000 FCDB3291DE21F0C0
+0101010101010102 0000000000000000 869EFD7F9F265A09
+1046913489980131 0000000000000000 88D55E54F54C97B4
+1007103489988020 0000000000000000 0C0CC00C83EA48FD
+10071034C8980120 0000000000000000 83BC8EF3A6570183
+1046103489988020 0000000000000000 DF725DCAD94EA2E9
+1086911519190101 0000000000000000 E652B53B550BE8B0
+1086911519580101 0000000000000000 AF527120C485CBB0
+5107B01519580101 0000000000000000 0F04CE393DB926D5
+1007B01519190101 0000000000000000 C9F00FFC74079067
+3107915498080101 0000000000000000 7CFD82A593252B4E
+3107919498080101 0000000000000000 CB49A2F9E91363E3
+10079115B9080140 0000000000000000 00B588BE70D23F56
+3107911598080140 0000000000000000 406A9A6AB43399AE
+1007D01589980101 0000000000000000 6CB773611DCA9ADA
+9107911589980101 0000000000000000 67FD21C17DBB5D70
+9107D01589190101 0000000000000000 9592CB4110430787
+1007D01598980120 0000000000000000 A6B7FF68A318DDD3
+1007940498190101 0000000000000000 4D102196C914CA16
+0107910491190401 0000000000000000 2DFA9F4573594965
+0107910491190101 0000000000000000 B46604816C0E0774
+0107940491190401 0000000000000000 6E7E6221A4F34E87
+19079210981A0101 0000000000000000 AA85E74643233199
+1007911998190801 0000000000000000 2E5A19DB4D1962D6
+10079119981A0801 0000000000000000 23A866A809D30894
+1007921098190101 0000000000000000 D812D961F017D320
+100791159819010B 0000000000000000 055605816E58608F
+1004801598190101 0000000000000000 ABD88E8B1B7716F1
+1004801598190102 0000000000000000 537AC95BE69DA1E1
+1004801598190108 0000000000000000 AED0F6AE3C25CDD8
+1002911598100104 0000000000000000 B3E35A5EE53E7B8D
+1002911598190104 0000000000000000 61C79C71921A2EF8
+1002911598100201 0000000000000000 E2F5728F0995013C
+1002911698100101 0000000000000000 1AEAC39A61F0A464
+7CA110454A1A6E57 01A1D6D039776742 690F5B0D9A26939B
+0131D9619DC1376E 5CD54CA83DEF57DA 7A389D10354BD271
+07A1133E4A0B2686 0248D43806F67172 868EBB51CAB4599A
+3849674C2602319E 51454B582DDF440A 7178876E01F19B2A
+04B915BA43FEB5B6 42FD443059577FA2 AF37FB421F8C4095
+0113B970FD34F2CE 059B5E0851CF143A 86A560F10EC6D85B
+0170F175468FB5E6 0756D8E0774761D2 0CD3DA020021DC09
+43297FAD38E373FE 762514B829BF486A EA676B2CB7DB2B7A
+07A7137045DA2A16 3BDD119049372802 DFD64A815CAF1A0F
+04689104C2FD3B2F 26955F6835AF609A 5C513C9C4886C088
+37D06BB516CB7546 164D5E404F275232 0A2AEEAE3FF4AB77
+1F08260D1AC2465E 6B056E18759F5CCA EF1BF03E5DFA575A
+584023641ABA6176 004BD6EF09176062 88BF0DB6D70DEE56
+025816164629B007 480D39006EE762F2 A1F9915541020B56
+49793EBC79B3258F 437540C8698F3CFA 6FBF1CAFCFFD0556
+4FB05E1515AB73A7 072D43A077075292 2F22E49BAB7CA1AC
+49E95D6D4CA229BF 02FE55778117F12A 5A6B612CC26CCE4A
+018310DC409B26D6 1D9D5C5018F728C2 5F4C038ED12B2E41
+1C587F1C13924FEF 305532286D6F295A 63FAC0D034D9F793
diff --git a/src/lib/crypto/md4/.rconf b/src/lib/crypto/md4/.rconf
new file mode 100644
index 000000000..de30fd8c9
--- /dev/null
+++ b/src/lib/crypto/md4/.rconf
@@ -0,0 +1,2 @@
+ignore RFC1186.TXT
+ignore RFC1186B.TXT
diff --git a/src/lib/crypto/md4/RFC1186.TXT b/src/lib/crypto/md4/RFC1186.TXT
new file mode 100644
index 000000000..5c0d9414e
--- /dev/null
+++ b/src/lib/crypto/md4/RFC1186.TXT
@@ -0,0 +1,1011 @@
+
+
+
+
+
+
+Network Working Group R. Rivest
+Request for Comments: 1186 MIT Laboratory for Computer Science
+ October 1990
+
+
+ The MD4 Message Digest Algorithm
+
+Status of this Memo
+
+ This RFC is the specification of the MD4 Digest Algorithm. If you
+ are going to implement MD4, it is suggested you do it this way. This
+ memo is for informational use and does not constitute a standard.
+ Distribution of this memo is unlimited.
+
+Table of Contents
+
+ 1. Abstract .................................................... 1
+ 2. Terminology and Notation .................................... 2
+ 3. MD4 Algorithm Description ................................... 2
+ 4. Extensions .................................................. 6
+ 5. Summary ..................................................... 7
+ 6. Acknowledgements ............................................ 7
+ APPENDIX - Reference Implementation ............................. 7
+ Security Considerations.......................................... 18
+ Author's Address................................................. 18
+
+1. Abstract
+
+ This note describes the MD4 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 MD4 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.
+
+ The MD4 algorithm is designed to be quite fast on 32-bit machines.
+ On a SUN Sparc station, MD4 runs at 1,450,000 bytes/second. On a DEC
+ MicroVax II, MD4 runs at approximately 70,000 bytes/second. On a
+ 20MHz 80286, MD4 runs at approximately 32,000 bytes/second. In
+ addition, the MD4 algorithm does not require any large substitution
+ tables; the algorithm can be coded quite compactly.
+
+ The MD4 algorithm is being placed in the public domain for review and
+ possible adoption as a standard.
+
+
+
+
+Rivest [Page 1]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ (Note: The document supersedes an earlier draft. The algorithm
+ described here is a slight modification of the one described in the
+ draft.)
+
+2. Terminology and Notation
+
+ In this note a "word" is a 32-bit quantity and a byte is an 8-bit
+ quantity. A sequence of bits can be interpreted in a natural manner
+ as a sequence of bytes, where each consecutive group of 8 bits is
+ interpreted as a byte with the high-order (most significant) bit of
+ each byte listed first. Similarly, a sequence of bytes can be
+ interpreted as a sequence of 32-bit words, where each consecutive
+ group of 4 bytes is interpreted as a word with the low-order (least
+ significant) byte given first.
+
+ 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 the symbol "+" denote addition of words (i.e., modulo- 2^32
+ addition). Let X <<< s denote the 32-bit value obtained by circularly
+ shifting (rotating) X left by s bit positions. Let not(X) denote the
+ bit-wise complement of X, and let X v Y denote the bit-wise OR of X
+ and Y. Let X xor Y denote the bit-wise XOR of X and Y, and let XY
+ denote the bit-wise AND of X and Y.
+
+3. MD4 Algorithm Description
+
+ We begin by supposing that we have a b-bit message as input, and that
+ we wish to find its message digest. Here b is an arbitrary
+ nonnegative integer; b may be zero, it need not be a multiple of 8,
+ and it may be arbitrarily large. We imagine the bits 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.
+
+ Step 1. Append padding bits
+
+ The message is "padded" (extended) so that its length (in bits)
+ is congruent to 448, modulo 512. That is, the message is
+ extended so that it is just 64 bits shy of being a multiple of
+ 512 bits long. Padding is always performed, even if the length
+ of the message is already congruent to 448, modulo 512 (in
+ which case 512 bits of padding are added).
+
+
+
+Rivest [Page 2]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ Padding is performed as follows: a single "1" bit is appended
+ to the message, and then enough zero bits are appended so that
+ the length in bits of the padded message becomes congruent to
+ 448, modulo 512.
+
+ Step 2. Append length
+
+ A 64-bit representation of b (the length of the message before
+ the padding bits were added) is appended to the result of the
+ previous step. In the unlikely event that b is greater than
+ 2^64, then only the low-order 64 bits of b are used. (These
+ bits are appended as two 32-bit words and appended low-order
+ word first in accordance with the previous conventions.)
+
+ At this point the resulting message (after padding with bits
+ and with b) has a length that is an exact multiple of 512 bits.
+ Equivalently, this message has a length that is an exact
+ multiple of 16 (32-bit) words. Let M[0 ... N-1] denote the
+ words of the resulting message, where N is a multiple of 16.
+
+ Step 3. Initialize MD buffer
+
+ A 4-word buffer (A,B,C,D) is used to compute the message
+ digest. Here each of A,B,C,D are 32-bit registers. These
+ registers are initialized to the following values in
+ hexadecimal, low-order bytes first):
+
+ word A: 01 23 45 67
+ word B: 89 ab cd ef
+ word C: fe dc ba 98
+ word D: 76 54 32 10
+
+ Step 4. Process message in 16-word blocks
+
+ We first define three auxiliary functions that each take
+ as input three 32-bit words and produce as output one
+ 32-bit word.
+
+ f(X,Y,Z) = XY v not(X)Z
+ g(X,Y,Z) = XY v XZ v YZ
+ h(X,Y,Z) = X xor Y xor Z
+
+ In each bit position f acts as a conditional: if x then y else
+ z. (The function f could have been defined using + instead of
+ v since XY and not(X)Z will never have 1's in the same bit
+ position.) In each bit position g acts as a majority function:
+ if at least two of x, y, z are on, then g has a one in that bit
+ position, else g has a zero. It is interesting to note that if
+
+
+
+Rivest [Page 3]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ the bits of X, Y, and Z are independent and unbiased, the each
+ bit of f(X,Y,Z) will be independent and unbiased, and similarly
+ each bit of g(X,Y,Z) will be independent and unbiased. The
+ function h is the bit-wise "xor" or "parity" function; it has
+ properties similar to those of f and g.
+
+ 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[j] to M[i*16+j].
+ end /* of loop on j */
+ Save A as AA, B as BB, C as CC, and D as DD.
+
+ [Round 1]
+ Let [A B C D i s] denote the operation
+ A = (A + f(B,C,D) + X[i]) <<< s .
+ Do the following 16 operations:
+ [A B C D 0 3]
+ [D A B C 1 7]
+ [C D A B 2 11]
+ [B C D A 3 19]
+ [A B C D 4 3]
+ [D A B C 5 7]
+ [C D A B 6 11]
+ [B C D A 7 19]
+ [A B C D 8 3]
+ [D A B C 9 7]
+ [C D A B 10 11]
+ [B C D A 11 19]
+ [A B C D 12 3]
+ [D A B C 13 7]
+ [C D A B 14 11]
+ [B C D A 15 19]
+
+ [Round 2]
+ Let [A B C D i s] denote the operation
+ A = (A + g(B,C,D) + X[i] + 5A827999) <<< s .
+ (The value 5A..99 is a hexadecimal 32-bit
+ constant, written with the high-order digit
+ first. This constant represents the square
+ root of 2. The octal value of this constant
+ is 013240474631. See Knuth, The Art of
+ Programming, Volume 2 (Seminumerical
+ Algorithms), Second Edition (1981),
+ Addison-Wesley. Table 2, page 660.)
+ Do the following 16 operations:
+ [A B C D 0 3]
+
+
+
+Rivest [Page 4]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ [D A B C 4 5]
+ [C D A B 8 9]
+ [B C D A 12 13]
+ [A B C D 1 3]
+ [D A B C 5 5]
+ [C D A B 9 9]
+ [B C D A 13 13]
+ [A B C D 2 3]
+ [D A B C 6 5]
+ [C D A B 10 9]
+ [B C D A 14 13]
+ [A B C D 3 3]
+ [D A B C 7 5]
+ [C D A B 11 9]
+ [B C D A 15 13]
+
+ [Round 3]
+ Let [A B C D i s] denote the operation
+ A = (A + h(B,C,D) + X[i] + 6ED9EBA1) <<< s .
+ (The value 6E..A1 is a hexadecimal 32-bit
+ constant, written with the high-order digit
+ first. This constant represents the square
+ root of 3. The octal value of this constant
+ is 015666365641. See Knuth, The Art of
+ Programming, Volume 2 (Seminumerical
+ Algorithms), Second Edition (1981),
+ Addison-Wesley. Table 2, page 660.)
+ Do the following 16 operations:
+ [A B C D 0 3]
+ [D A B C 8 9]
+ [C D A B 4 11]
+ [B C D A 12 15]
+ [A B C D 2 3]
+ [D A B C 10 9]
+ [C D A B 6 11]
+ [B C D A 14 15]
+ [A B C D 1 3]
+ [D A B C 9 9]
+ [C D A B 5 11]
+ [B C D A 13 15]
+ [A B C D 3 3]
+ [D A B C 11 9]
+ [C D A B 7 11]
+ [B C D A 15 15]
+
+ Then perform the following additions:
+ A = A + AA
+ B = B + BB
+
+
+
+Rivest [Page 5]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ C = C + CC
+ D = D + DD
+ (That is, each of the four registers is incremented by
+ the value it had before this block was started.)
+
+ end /* of loop on i */
+
+ Step 5. Output
+
+ The message digest produced as output is A,B,C,D. That is, we
+ begin with the low-order byte of A, and end with the high-order
+ byte of D.
+
+ This completes the description of MD4. A reference
+ implementation in C is given in the Appendix.
+
+4. Extensions
+
+ If more than 128 bits of output are required, then the following
+ procedure is recommended to obtain a 256-bit output. (There is no
+ provision made for obtaining more than 256 bits.)
+
+ Two copies of MD4 are run in parallel over the input. The first copy
+ is standard as described above. The second copy is modified as
+ follows.
+
+ The initial state of the second copy is:
+ word A: 00 11 22 33
+ word B: 44 55 66 77
+ word C: 88 99 aa bb
+ word D: cc dd ee ff
+
+ The magic constants in rounds 2 and 3 for the second copy of MD4 are
+ changed from sqrt(2) and sqrt(3) to cuberoot(2) and cuberoot(3):
+
+ Octal Hex
+ Round 2 constant 012050505746 50a28be6
+ Round 3 constant 013423350444 5c4dd124
+
+ Finally, after every 16-word block is processed (including the last
+ block), the values of the A registers in the two copies are
+ exchanged.
+
+ The final message digest is obtaining by appending the result of the
+ second copy of MD4 to the end of the result of the first copy of MD4.
+
+
+
+
+
+
+Rivest [Page 6]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+5. Summary
+
+ The MD4 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 MD4
+ 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 MD4 should be sufficient for
+ implementing very high security hybrid digital signature schemes
+ based on MD4 and the RSA public-key cryptosystem.
+
+6. Acknowledgements
+
+ I'd like to thank Don Coppersmith, Burt Kaliski, Ralph Merkle, and
+ Noam Nisan for numerous helpful comments and suggestions.
+
+APPENDIX - Reference Implementation
+
+This appendix contains the following files:
+
+ md4.h -- header file for using MD4 implementation
+ md4.c -- the source code for MD4 routines
+ md4driver.c -- a sample "user" routine
+ session -- sample results of running md4driver
+
+ /*
+ ** ********************************************************************
+ ** md4.h -- Header file for implementation of **
+ ** MD4 Message Digest Algorithm **
+ ** Updated: 2/13/90 by Ronald L. Rivest **
+ ** (C) 1990 RSA Data Security, Inc. **
+ ** ********************************************************************
+ */
+
+ /* MDstruct is the data structure for a message digest computation.
+ */
+ typedef struct {
+ unsigned int buffer[4]; /* Holds 4-word result of MD computation */
+ unsigned char count[8]; /* Number of bits processed so far */
+ unsigned int done; /* Nonzero means MD computation finished */
+ } MDstruct, *MDptr;
+
+ /* MDbegin(MD)
+
+
+
+Rivest [Page 7]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ ** Input: MD -- an MDptr
+ ** Initialize the MDstruct prepatory to doing a message digest
+ ** computation.
+ */
+ extern void MDbegin();
+
+ /* MDupdate(MD,X,count)
+ ** Input: MD -- an MDptr
+ ** X -- a pointer to an array of unsigned characters.
+ ** count -- the number of bits of X to use (an unsigned int).
+ ** Updates MD using the first "count" bits of X.
+ ** The array pointed to by X is not modified.
+ ** If count is not a multiple of 8, MDupdate uses high bits of
+ ** last byte.
+ ** This is the basic input routine for a user.
+ ** The routine terminates the MD computation when count < 512, so
+ ** every MD computation should end with one call to MDupdate with a
+ ** count less than 512. Zero is OK for a count.
+ */
+ extern void MDupdate();
+
+ /* MDprint(MD)
+ ** Input: MD -- an MDptr
+ ** Prints message digest buffer MD as 32 hexadecimal digits.
+ ** Order is from low-order byte of buffer[0] to high-order byte
+ ** of buffer[3].
+ ** Each byte is printed with high-order hexadecimal digit first.
+ */
+ extern void MDprint();
+
+ /*
+ ** End of md4.h
+ ****************************(cut)***********************************/
+
+ /*
+ ** ********************************************************************
+ ** md4.c -- Implementation of MD4 Message Digest Algorithm **
+ ** Updated: 2/16/90 by Ronald L. Rivest **
+ ** (C) 1990 RSA Data Security, Inc. **
+ ** ********************************************************************
+ */
+
+ /*
+ ** To use MD4:
+ ** -- Include md4.h in your program
+ ** -- Declare an MDstruct MD to hold the state of the digest
+ ** computation.
+ ** -- Initialize MD using MDbegin(&MD)
+
+
+
+Rivest [Page 8]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ ** -- For each full block (64 bytes) X you wish to process, call
+ ** MDupdate(&MD,X,512)
+ ** (512 is the number of bits in a full block.)
+ ** -- For the last block (less than 64 bytes) you wish to process,
+ ** MDupdate(&MD,X,n)
+ ** where n is the number of bits in the partial block. A partial
+ ** block terminates the computation, so every MD computation
+ ** should terminate by processing a partial block, even if it
+ ** has n = 0.
+ ** -- The message digest is available in MD.buffer[0] ...
+ ** MD.buffer[3]. (Least-significant byte of each word
+ ** should be output first.)
+ ** -- You can print out the digest using MDprint(&MD)
+ */
+
+ /* Implementation notes:
+ ** This implementation assumes that ints are 32-bit quantities.
+ ** If the machine stores the least-significant byte of an int in the
+ ** least-addressed byte (e.g., VAX and 8086), then LOWBYTEFIRST
+ ** should be set to TRUE. Otherwise (e.g., SUNS), LOWBYTEFIRST
+ ** should be set to FALSE. Note that on machines with LOWBYTEFIRST
+ ** FALSE the routine MDupdate modifies has a side-effect on its input
+ ** array (the order of bytes in each word are reversed). If this is
+ ** undesired a call to MDreverse(X) can reverse the bytes of X back
+ ** into order after each call to MDupdate.
+
+ */
+ #define TRUE 1
+ #define FALSE 0
+ #define LOWBYTEFIRST FALSE
+
+ /* Compile-time includes
+ */
+ #include <stdio.h>
+ #include "md4.h"
+
+ /* Compile-time declarations of MD4 "magic constants".
+ */
+ #define I0 0x67452301 /* Initial values for MD buffer */
+ #define I1 0xefcdab89
+ #define I2 0x98badcfe
+ #define I3 0x10325476
+ #define C2 013240474631 /* round 2 constant = sqrt(2) in octal */
+ #define C3 015666365641 /* round 3 constant = sqrt(3) in octal */
+ /* C2 and C3 are from Knuth, The Art of Programming, Volume 2
+ ** (Seminumerical Algorithms), Second Edition (1981), Addison-Wesley.
+ ** Table 2, page 660.
+ */
+
+
+
+Rivest [Page 9]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ #define fs1 3 /* round 1 shift amounts */
+ #define fs2 7
+ #define fs3 11
+ #define fs4 19
+ #define gs1 3 /* round 2 shift amounts */
+ #define gs2 5
+ #define gs3 9
+ #define gs4 13
+ #define hs1 3 /* round 3 shift amounts */
+ #define hs2 9
+ #define hs3 11
+ #define hs4 15
+
+ /* Compile-time macro declarations for MD4.
+ ** Note: The "rot" operator uses the variable "tmp".
+ ** It assumes tmp is declared as unsigned int, so that the >>
+ ** operator will shift in zeros rather than extending the sign bit.
+ */
+ #define f(X,Y,Z) ((X&Y) | ((~X)&Z))
+ #define g(X,Y,Z) ((X&Y) | (X&Z) | (Y&Z))
+ #define h(X,Y,Z) (X^Y^Z)
+ #define rot(X,S) (tmp=X,(tmp<<S) | (tmp>>(32-S)))
+ #define ff(A,B,C,D,i,s) A = rot((A + f(B,C,D) + X[i]),s)
+ #define gg(A,B,C,D,i,s) A = rot((A + g(B,C,D) + X[i] + C2),s)
+ #define hh(A,B,C,D,i,s) A = rot((A + h(B,C,D) + X[i] + C3),s)
+
+ /* MDprint(MDp)
+ ** Print message digest buffer MDp as 32 hexadecimal digits.
+ ** Order is from low-order byte of buffer[0] to high-order byte of
+ ** buffer[3].
+ ** Each byte is printed with high-order hexadecimal digit first.
+ ** This is a user-callable routine.
+ */
+ void
+ MDprint(MDp)
+ MDptr MDp;
+ { int i,j;
+ for (i=0;i<4;i++)
+ for (j=0;j<32;j=j+8)
+ printf("%02x",(MDp->buffer[i]>>j) & 0xFF);
+ }
+
+ /* MDbegin(MDp)
+ ** Initialize message digest buffer MDp.
+ ** This is a user-callable routine.
+ */
+ void
+ MDbegin(MDp)
+
+
+
+Rivest [Page 10]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ MDptr MDp;
+ { int i;
+ MDp->buffer[0] = I0;
+ MDp->buffer[1] = I1;
+ MDp->buffer[2] = I2;
+ MDp->buffer[3] = I3;
+ for (i=0;i<8;i++) MDp->count[i] = 0;
+ MDp->done = 0;
+ }
+
+ /* MDreverse(X)
+ ** Reverse the byte-ordering of every int in X.
+ ** Assumes X is an array of 16 ints.
+ ** The macro revx reverses the byte-ordering of the next word of X.
+ */
+ #define revx { t = (*X << 16) | (*X >> 16); \
+ *X++ = ((t & 0xFF00FF00) >> 8) | ((t & 0x00FF00FF) << 8); }
+ MDreverse(X)
+ unsigned int *X;
+ { register unsigned int t;
+ revx; revx; revx; revx; revx; revx; revx; revx;
+ revx; revx; revx; revx; revx; revx; revx; revx;
+ }
+
+ /* MDblock(MDp,X)
+ ** Update message digest buffer MDp->buffer using 16-word data block X.
+ ** Assumes all 16 words of X are full of data.
+ ** Does not update MDp->count.
+ ** This routine is not user-callable.
+ */
+ static void
+ MDblock(MDp,X)
+ MDptr MDp;
+ unsigned int *X;
+ {
+ register unsigned int tmp, A, B, C, D;
+ #if LOWBYTEFIRST == FALSE
+ MDreverse(X);
+ #endif
+ A = MDp->buffer[0];
+ B = MDp->buffer[1];
+ C = MDp->buffer[2];
+ D = MDp->buffer[3];
+ /* Update the message digest buffer */
+ ff(A , B , C , D , 0 , fs1); /* Round 1 */
+ ff(D , A , B , C , 1 , fs2);
+ ff(C , D , A , B , 2 , fs3);
+ ff(B , C , D , A , 3 , fs4);
+
+
+
+Rivest [Page 11]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ ff(A , B , C , D , 4 , fs1);
+ ff(D , A , B , C , 5 , fs2);
+ ff(C , D , A , B , 6 , fs3);
+ ff(B , C , D , A , 7 , fs4);
+ ff(A , B , C , D , 8 , fs1);
+ ff(D , A , B , C , 9 , fs2);
+ ff(C , D , A , B , 10 , fs3);
+ ff(B , C , D , A , 11 , fs4);
+ ff(A , B , C , D , 12 , fs1);
+ ff(D , A , B , C , 13 , fs2);
+ ff(C , D , A , B , 14 , fs3);
+ ff(B , C , D , A , 15 , fs4);
+ gg(A , B , C , D , 0 , gs1); /* Round 2 */
+ gg(D , A , B , C , 4 , gs2);
+ gg(C , D , A , B , 8 , gs3);
+ gg(B , C , D , A , 12 , gs4);
+ gg(A , B , C , D , 1 , gs1);
+ gg(D , A , B , C , 5 , gs2);
+ gg(C , D , A , B , 9 , gs3);
+ gg(B , C , D , A , 13 , gs4);
+ gg(A , B , C , D , 2 , gs1);
+ gg(D , A , B , C , 6 , gs2);
+ gg(C , D , A , B , 10 , gs3);
+ gg(B , C , D , A , 14 , gs4);
+ gg(A , B , C , D , 3 , gs1);
+ gg(D , A , B , C , 7 , gs2);
+ gg(C , D , A , B , 11 , gs3);
+ gg(B , C , D , A , 15 , gs4);
+ hh(A , B , C , D , 0 , hs1); /* Round 3 */
+ hh(D , A , B , C , 8 , hs2);
+ hh(C , D , A , B , 4 , hs3);
+ hh(B , C , D , A , 12 , hs4);
+ hh(A , B , C , D , 2 , hs1);
+ hh(D , A , B , C , 10 , hs2);
+ hh(C , D , A , B , 6 , hs3);
+ hh(B , C , D , A , 14 , hs4);
+ hh(A , B , C , D , 1 , hs1);
+ hh(D , A , B , C , 9 , hs2);
+ hh(C , D , A , B , 5 , hs3);
+ hh(B , C , D , A , 13 , hs4);
+ hh(A , B , C , D , 3 , hs1);
+ hh(D , A , B , C , 11 , hs2);
+ hh(C , D , A , B , 7 , hs3);
+ hh(B , C , D , A , 15 , hs4);
+ MDp->buffer[0] += A;
+ MDp->buffer[1] += B;
+ MDp->buffer[2] += C;
+ MDp->buffer[3] += D;
+
+
+
+Rivest [Page 12]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ }
+
+ /* MDupdate(MDp,X,count)
+ ** Input: MDp -- an MDptr
+ ** X -- a pointer to an array of unsigned characters.
+ ** count -- the number of bits of X to use.
+ ** (if not a multiple of 8, uses high bits of last byte.)
+ ** Update MDp using the number of bits of X given by count.
+ ** This is the basic input routine for an MD4 user.
+ ** The routine completes the MD computation when count < 512, so
+ ** every MD computation should end with one call to MDupdate with a
+ ** count less than 512. A call with count 0 will be ignored if the
+ ** MD has already been terminated (done != 0), so an extra call with
+ ** count 0 can be given as a "courtesy close" to force termination
+ ** if desired.
+ */
+ void
+ MDupdate(MDp,X,count)
+ MDptr MDp;
+ unsigned char *X;
+ unsigned int count;
+ { unsigned int i, tmp, bit, byte, mask;
+ unsigned char XX[64];
+ unsigned char *p;
+ /* return with no error if this is a courtesy close with count
+ ** zero and MDp->done is true.
+ */
+ if (count == 0 && MDp->done) return;
+ /* check to see if MD is already done and report error */
+ if (MDp->done)
+ { printf("\nError: MDupdate MD already done."); return; }
+ /* Add count to MDp->count */
+ tmp = count;
+ p = MDp->count;
+ while (tmp)
+ { tmp += *p;
+ *p++ = tmp;
+ tmp = tmp >> 8;
+ }
+ /* Process data */
+ if (count == 512)
+ { /* Full block of data to handle */
+ MDblock(MDp,(unsigned int *)X);
+ }
+ else if (count > 512) /* Check for count too large */
+ { printf("\nError: MDupdate called with illegal count value %d."
+ ,count);
+ return;
+
+
+
+Rivest [Page 13]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ }
+ else /* partial block -- must be last block so finish up */
+ { /* Find out how many bytes and residual bits there are */
+ byte = count >> 3;
+ bit = count & 7;
+ /* Copy X into XX since we need to modify it */
+ for (i=0;i<=byte;i++) XX[i] = X[i];
+ for (i=byte+1;i<64;i++) XX[i] = 0;
+ /* Add padding '1' bit and low-order zeros in last byte */
+ mask = 1 << (7 - bit);
+ XX[byte] = (XX[byte] | mask) & ~( mask - 1);
+ /* If room for bit count, finish up with this block */
+ if (byte <= 55)
+ { for (i=0;i<8;i++) XX[56+i] = MDp->count[i];
+ MDblock(MDp,(unsigned int *)XX);
+ }
+ else /* need to do two blocks to finish up */
+ { MDblock(MDp,(unsigned int *)XX);
+ for (i=0;i<56;i++) XX[i] = 0;
+ for (i=0;i<8;i++) XX[56+i] = MDp->count[i];
+ MDblock(MDp,(unsigned int *)XX);
+ }
+ /* Set flag saying we're done with MD computation */
+ MDp->done = 1;
+ }
+ }
+
+ /*
+ ** End of md4.c
+ ****************************(cut)***********************************/
+
+ /*
+ ** ********************************************************************
+ ** md4driver.c -- sample routines to test **
+ ** MD4 message digest algorithm. **
+ ** Updated: 2/16/90 by Ronald L. Rivest **
+ ** (C) 1990 RSA Data Security, Inc. **
+ ** ********************************************************************
+ */
+
+ #include <stdio.h>
+ #include "md4.h"
+
+ /* MDtimetrial()
+ ** A time trial routine, to measure the speed of MD4.
+ ** Measures speed for 1M blocks = 64M bytes.
+ */
+ MDtimetrial()
+
+
+
+Rivest [Page 14]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ { unsigned int X[16];
+ MDstruct MD;
+ int i;
+ double t;
+ for (i=0;i<16;i++) X[i] = 0x01234567 + i;
+ printf
+ ("MD4 time trial. Processing 1 million 64-character blocks...\n");
+ clock();
+ MDbegin(&MD);
+ for (i=0;i<1000000;i++) MDupdate(&MD,X,512);
+ MDupdate(&MD,X,0);
+ t = (double) clock(); /* in microseconds */
+ MDprint(&MD); printf(" is digest of 64M byte test input.\n");
+ printf("Seconds to process test input: %g\n,t/1e6);
+ printf("Characters processed per second: %ld.\n,(int)(64e12/t));
+ }
+
+ /* MDstring(s)
+ ** Computes the message digest for string s.
+ ** Prints out message digest, a space, the string (in quotes) and a
+ ** carriage return.
+ */
+ MDstring(s)
+ unsigned char *s;
+ { unsigned int i, len = strlen(s);
+ MDstruct MD;
+ MDbegin(&MD);
+ for (i=0;i+64<=len;i=i+64) MDupdate(&MD,s+i,512);
+ MDupdate(&MD,s+i,(len-i)*8);
+ MDprint(&MD);
+ printf(" \"%s\"\n",s);
+ }
+
+ /* MDfile(filename)
+ ** Computes the message digest for a specified file.
+ ** Prints out message digest, a space, the file name, and a
+ ** carriage return.
+ */
+ MDfile(filename)
+ char *filename;
+ { FILE *f = fopen(filename,"rb");
+ unsigned char X[64];
+ MDstruct MD;
+ int b;
+ if (f == NULL)
+ { printf("%s can't be opened.\n",filename); return; }
+ MDbegin(&MD);
+ while ((b=fread(X,1,64,f))!=0) MDupdate(&MD,X,b*8);
+
+
+
+Rivest [Page 15]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ MDupdate(&MD,X,0);
+ MDprint(&MD);
+ printf(" %s\n",filename);
+ fclose(f);
+ }
+
+ /* MDfilter()
+ ** Writes the message digest of the data from stdin onto stdout,
+ ** followed by a carriage return.
+ */
+ MDfilter()
+ { unsigned char X[64];
+ MDstruct MD;
+ int b;
+ MDbegin(&MD);
+ while ((b=fread(X,1,64,stdin))!=0) MDupdate(&MD,X,b*8);
+ MDupdate(&MD,X,0);
+ MDprint(&MD);
+ printf("\n");
+ }
+
+ /* MDtestsuite()
+ ** Run a standard suite of test data.
+ */
+ MDtestsuite()
+ {
+ printf("MD4 test suite results:\n");
+ MDstring("");
+ MDstring("a");
+ MDstring("abc");
+ MDstring("message digest");
+ MDstring("abcdefghijklmnopqrstuvwxyz");
+ MDstring
+ ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");
+ MDfile("foo"); /* Contents of file foo are "abc" */
+ }
+
+ 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 64M bytes
+ ** -x -- execute a standard suite of test data
+ ** (no args) -- writes messages digest of stdin onto stdout
+ */
+
+
+
+Rivest [Page 16]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ 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 md4driver.c
+ ****************************(cut)***********************************/
+
+
+ --------------------------------------------------------------------
+ --- Sample session. Compiling and using MD4 on SUN Sparcstation ---
+ --------------------------------------------------------------------
+ >ls
+ total 66
+ -rw-rw-r-- 1 rivest 3 Feb 14 17:40 abcfile
+ -rwxrwxr-x 1 rivest 24576 Feb 17 12:28 md4
+ -rw-rw-r-- 1 rivest 9347 Feb 17 00:37 md4.c
+ -rw-rw-r-- 1 rivest 25150 Feb 17 12:25 md4.doc
+ -rw-rw-r-- 1 rivest 1844 Feb 16 21:21 md4.h
+ -rw-rw-r-- 1 rivest 3497 Feb 17 12:27 md4driver.c
+ >
+ >cc -o md4 -O4 md4.c md4driver.c
+ md4.c:
+ md4driver.c:
+ Linking:
+ >
+ >md4 -x
+ MD4 test suite results:
+ 31d6cfe0d16ae931b73c59d7e0c089c0 ""
+ bde52cb31de33e46245e05fbdbd6fb24 "a"
+ a448017aaf21d8525fc10ae87aa6729d "abc"
+ d9130a8164549fe818874806e1c7014b "message digest"
+ d79e1c308aa5bbcdeea8ed63df412da9 "abcdefghijklmnopqrstuvwxyz"
+ 043f8582f241db351ce627e153e7f0e4
+ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
+ a448017aaf21d8525fc10ae87aa6729d abcfile
+ >
+ >md4 -sabc -shi
+ a448017aaf21d8525fc10ae87aa6729d "abc"
+ cfaee2512bd25eb033236f0cd054e308 "hi"
+ >
+ >md4 *
+ a448017aaf21d8525fc10ae87aa6729d abcfile
+
+
+
+Rivest [Page 17]
+
+RFC 1186 MD4 Message Digest Algorithm October 1990
+
+
+ d316f994da0e951cf9502928a1f73300 md4
+ 379adb39eada0dfdbbdfdcd0d9def8c4 md4.c
+ 9a3f73327c65954198b1f45a3aa12665 md4.doc
+ 37fe165ac177b461ff78b86d10e4ff33 md4.h
+ 7dcba2e2dc4d8f1408d08beb17dabb2a md4.o
+ 08790161bfddc6f5788b4353875cb1c3 md4driver.c
+ 1f84a7f690b0545d2d0480d5d3c26eea md4driver.o
+ >
+ >cat abcfile | md4
+ a448017aaf21d8525fc10ae87aa6729d
+ >
+ >md4 -t
+ MD4 time trial. Processing 1 million 64-character blocks...
+ 6325bf77e5891c7c0d8104b64cc6e9ef is digest of 64M byte test input.
+ Seconds to process test input: 44.0982
+ Characters processed per second: 1451305.
+ >
+ >
+ ------------------------ end of sample session --------------------
+
+ Note: A version of this document including the C source code is
+ available for FTP from THEORY.LSC.MIT.EDU in the file "md4.doc".
+
+Security Considerations
+
+ The level of security discussed in this memo by MD4 is considered to
+ be sufficient for implementing very high security hybrid digital
+ signature schemes based on MD4 and the RSA public-key cryptosystem.
+
+Author's Address
+
+ Ronald L. Rivest
+ Massachusetts Institute of Technology
+ Laboratory for Computer Science
+ NE43-324
+ 545 Technology Square
+ Cambridge, MA 02139-1986
+
+ Phone: (617) 253-5880
+
+ EMail: rivest@theory.lcs.mit.edu
+
+
+
+
+
+
+
+
+
+
+Rivest [Page 18]
+ \ No newline at end of file
diff --git a/src/lib/crypto/md4/RFC1186B.TXT b/src/lib/crypto/md4/RFC1186B.TXT
new file mode 100644
index 000000000..6be1a29eb
--- /dev/null
+++ b/src/lib/crypto/md4/RFC1186B.TXT
@@ -0,0 +1,1041 @@
+*** Note: This is a revised version of "md4.doc", obtained as "md4.doc"
+*** by anonymous ftp from theory.lcs.mit.edu. The original version is
+*** still available as "md4.doc.old". The MD4 algorithm is unchanged, but
+*** the newer version of the code is somewhat more portable, although slightly
+*** slower. [Ronald L. Rivest 1/13/91]
+
+Network Working Group R. Rivest
+Request for Comments: 1186B MIT Laboratory for Computer Science
+Updates: RFC 1186 S. Dusse
+ RSA Data Security, Inc.
+ 9 January 1991
+
+
+
+ The MD4 Message Digest Algorithm
+
+
+STATUS OF THIS MEMO
+
+ This RFC is the specification of the MD4 Digest Algorithm. If you
+ are going to implement MD4, it is suggested you do it this way. This
+ memo is for informational use and does not constitute a standard.
+ Distribution of this memo is unlimited.
+
+Table of Contents
+
+ 1. Executive Summary 1
+ 2. Terminology and Notation 2
+ 3. MD4 Algorithm Description 2
+ 4. Extensions 6
+ 5. Summary 6
+ 6. Acknowledgements 7
+ Security Considerations 7
+ References 7
+ APPENDIX - Reference Implementation 7
+
+1. Executive Summary
+
+ This note describes the MD4 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 MD4 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.
+
+ The MD4 algorithm is designed to be quite fast on 32-bit machines.
+ In addition, the MD4 algorithm does not require any large
+ substitution tables; the algorithm can be coded quite compactly.
+
+ The MD4 algorithm is being placed in the public domain for review and
+ possible adoption as a standard.
+
+ This RFC is a revision of the October 1990 RFC 1186. The main
+ difference is that the reference implementation of MD4 in the
+ appendix is more portable.
+
+
+Rivest [Page 1]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+2. Terminology and Notation
+
+ In this note a "word" is a 32-bit quantity and a byte is an 8-bit
+ quantity. A sequence of bits can be interpreted in a natural manner
+ as a sequence of bytes, where each consecutive group of 8 bits is
+ interpreted as a byte with the high-order (most significant) bit of
+ each byte listed first. Similarly, a sequence of bytes can be
+ interpreted as a sequence of 32-bit words, where each consecutive
+ group of 4 bytes is interpreted as a word with the low-order (least
+ significant) byte given first.
+
+ 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 the symbol "+" denote addition of words (i.e., modulo- 2^32
+ addition). Let X <<< s denote the 32-bit value obtained by
+ circularly shifting (rotating) X left by s bit positions. Let not(X)
+ denote the bit-wise complement of X, and let X v Y denote the bit-
+ wise OR of X and Y. Let X xor Y denote the bit-wise XOR of X and Y,
+ and let XY denote the bit-wise AND of X and Y.
+
+
+3. MD4 Algorithm Description
+
+ We begin by supposing that we have a b-bit message as input, and that
+ we wish to find its message digest. Here b is an arbitrary
+ nonnegative integer; b may be zero, it need not be a multiple of 8,
+ and it may be arbitrarily large. We imagine the bits 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 bits) is
+ congruent to 448, modulo 512. That is, the message is extended so
+ that it is just 64 bits shy of being a multiple of 512 bits long.
+ Padding is always performed, even if the length of the message is
+ already congruent to 448, modulo 512 (in which case 512 bits of
+ padding are added).
+
+ Padding is performed as follows: a single "1" bit is appended to the
+ message, and then enough zero bits are appended so that the length in
+ bits of the padded message becomes congruent to 448, modulo 512.
+
+
+
+
+Rivest [Page 2]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+3.2 Step 2. Append length
+
+ A 64-bit representation of b (the length of the message before the
+ padding bits were added) is appended to the result of the previous
+ step. In the unlikely event that b is greater than 2^64, then only
+ the low-order 64 bits of b are used. (These bits are appended as two
+ 32-bit words and appended low-order word first in accordance with the
+ previous conventions.)
+
+ At this point the resulting message (after padding with bits and with
+ b) has a length that is an exact multiple of 512 bits. Equivalently,
+ this message has a length that is an exact multiple of 16 (32-bit)
+ words. Let M[0 ... N-1] denote the words of the resulting message,
+ where N is a multiple of 16.
+
+
+3.3 Step 3. Initialize MD buffer
+
+ A 4-word buffer (A,B,C,D) is used to compute the message digest.
+ Here each of A,B,C,D are 32-bit registers. These registers are
+ initialized to the following values in hexadecimal, low-order bytes
+ first):
+
+ word A: 01 23 45 67
+ word B: 89 ab cd ef
+ word C: fe dc ba 98
+ word D: 76 54 32 10
+
+
+3.4 Step 4. Process message in 16-word blocks
+
+ We first define three auxiliary functions that each take as input
+ three 32-bit words and produce as output one 32-bit word.
+
+ f(X,Y,Z) = XY v not(X)Z
+ g(X,Y,Z) = XY v XZ v YZ
+ h(X,Y,Z) = X xor Y xor Z
+
+ In each bit position f acts as a conditional: if x then y else z.
+ (The function f could have been defined using + instead of v since XY
+ and not(X)Z will never have 1's in the same bit position.) In each
+ bit position g acts as a majority function: if at least two of x, y,
+ z are on, then g has a one in that bit position, else g has a zero.
+ It is interesting to note that if the bits of X, Y, and Z are
+ independent and unbiased, the each bit of f(X,Y,Z) will be
+ independent and unbiased, and similarly each bit of g(X,Y,Z) will be
+ independent and unbiased. The function h is the bit-wise "xor" or
+ "parity" function; it has properties similar to those of f and g.
+
+ 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[j] to M[i*16+j].
+Rivest [Page 3]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+ end /* of loop on j */
+ Save A as AA, B as BB, C as CC, and D as DD.
+
+ [Round 1]
+ Let [A B C D i s] denote the operation
+ A = (A + f(B,C,D) + X[i]) <<< s .
+
+ Do the following 16 operations:
+ [A B C D 0 3]
+ [D A B C 1 7]
+ [C D A B 2 11]
+ [B C D A 3 19]
+ [A B C D 4 3]
+ [D A B C 5 7]
+ [C D A B 6 11]
+ [B C D A 7 19]
+ [A B C D 8 3]
+ [D A B C 9 7]
+ [C D A B 10 11]
+ [B C D A 11 19]
+ [A B C D 12 3]
+ [D A B C 13 7]
+ [C D A B 14 11]
+ [B C D A 15 19]
+
+ [Round 2]
+ Let [A B C D i s] denote the operation
+ A = (A + g(B,C,D) + X[i] + 5A827999) <<< s .
+
+ (The value 5A..99 is a hexadecimal 32-bit
+ constant, written with the high-order digit
+ first. This constant represents the square
+ root of 2. The octal value of this constant
+ is 013240474631. See Knuth, The Art of
+ Programming, Volume 2 (Seminumerical
+ Algorithms), Second Edition (1981),
+ Addison-Wesley. Table 2, page 660.)
+
+ Do the following 16 operations:
+ [A B C D 0 3]
+ [D A B C 4 5]
+ [C D A B 8 9]
+ [B C D A 12 13]
+ [A B C D 1 3]
+ [D A B C 5 5]
+ [C D A B 9 9]
+ [B C D A 13 13]
+ [A B C D 2 3]
+ [D A B C 6 5]
+ [C D A B 10 9]
+ [B C D A 14 13]
+ [A B C D 3 3]
+ [D A B C 7 5]
+ [C D A B 11 9]
+Rivest [Page 4] [B C D A 15 13]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+
+ [Round 3]
+ Let [A B C D i s] denote the operation
+ A = (A + h(B,C,D) + X[i] + 6ED9EBA1) <<< s .
+
+ (The value 6E..A1 is a hexadecimal 32-bit
+ constant, written with the high-order digit
+ first. This constant represents the square
+ root of 3. The octal value of this constant
+ is 015666365641. See Knuth, The Art of
+ Programming, Volume 2 (Seminumerical
+ Algorithms), Second Edition (1981),
+ Addison-Wesley. Table 2, page 660.)
+
+ Do the following 16 operations:
+ [A B C D 0 3]
+ [D A B C 8 9]
+ [C D A B 4 11]
+ [B C D A 12 15]
+ [A B C D 2 3]
+ [D A B C 10 9]
+ [C D A B 6 11]
+ [B C D A 14 15]
+ [A B C D 1 3]
+ [D A B C 9 9]
+ [C D A B 5 11]
+ [B C D A 13 15]
+ [A B C D 3 3]
+ [D A B C 11 9]
+ [C D A B 7 11]
+ [B C D A 15 15]
+
+ Then perform the following additions:
+ A = A + AA
+ B = B + BB
+ C = C + CC
+ D = D + DD
+
+ (That is, each of the four registers is
+ incremented by the value it had before
+ this block was started.)
+
+ end /* of loop on i */
+
+
+3.5 Step 5. Output
+
+ The message digest produced as output is A,B,C,D. That is, we begin
+ with the low-order byte of A, and end with the high-order byte of D.
+
+ This completes the description of MD4. A reference implementation in
+ C is given in the Appendix.
+
+
+Rivest [Page 5]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+4. Extensions
+
+ If more than 128 bits of output are required, then the following
+ procedure is recommended to obtain a 256-bit output. (There is no
+ provision made for obtaining more than 256 bits.)
+
+ Two copies of MD4 are run in parallel over the input. The first copy
+ is standard as described above. The second copy is modified as
+ follows.
+
+ The initial state of the second copy is:
+
+ word A: 00 11 22 33
+ word B: 44 55 66 77
+ word C: 88 99 aa bb
+ word D: cc dd ee ff
+
+ The magic constants in rounds 2 and 3 for the second copy of MD4 are
+ changed from sqrt(2) and sqrt(3) to cuberoot(2) and cuberoot(3):
+
+ Octal Hex
+ Round 2 constant 012050505746 50a28be6
+ Round 3 constant 013423350444 5c4dd124
+
+ Finally, after every 16-word block is processed (including the last
+ block), the values of the A registers in the two copies are
+ exchanged.
+
+ The final message digest is obtaining by appending the result of the
+ second copy of MD4 to the end of the result of the first copy of MD4.
+
+
+5. Summary
+
+ The MD4 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 MD4
+ 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 MD4 should be sufficient for
+ implementing very high security hybrid digital signature schemes
+ based on MD4 and the RSA public-key cryptosystem.
+
+
+6. Acknowledgements
+
+ We would like to thank Don Coppersmith, Burt Kaliski, Ralph Merkle,
+ and Noam Nisan for numerous helpful comments and suggestions.
+
+
+Rivest [Page 6]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+Security Considerations
+
+ The level of security discussed in this memo by MD4 is considered to
+ be sufficient for implementing very high security hybrid digital
+ signature schemes based on MD4 and the RSA public-key cryptosystem.
+
+
+Authors' Addresses
+
+ Ronald L. Rivest
+ Massachusetts Institute of Technology
+ Laboratory for Computer Science
+ NE43-324
+ 545 Technology Square
+ Cambridge, MA 02139-1986
+ Phone: (617) 253-5880
+ EMail: rivest@theory.lcs.mit.edu
+
+ Steve Dusse
+ RSA Data Security, Inc.
+ 10 Twin Dolphin Dr.
+ Redwood City, CA 94065
+ Phone: (415) 595-8782
+ EMail: dusse@rsa.com
+
+
+References
+
+ [1] Rivest, R.L. The MD4 message digest algorithm. Presented at
+ CRYPTO '90 (Santa Barbara, CA, August 11-15, 1990).
+
+
+APPENDIX - Reference Implementation
+
+ This appendix contains the following files:
+
+ md4.h -- header file for using MD4 implementation
+
+ md4.c -- the source code for MD4 routines
+
+ md4driver.c -- a sample "user" routine
+
+ session -- sample results of running md4driver
+
+ The implementation of MD4 given in this appendix differs from the one
+ given in [1] and again in RFC 1186. The main difference is that this
+ version should compile and run correctly on more platforms than the
+ other ones. We have sacrificed performance for portability. MD4
+ speeds given in [1] and RFC 1186 are not necessarily the same as
+ those one might obtain with this reference implementation. However,
+ it is not difficult to improve this implementation on particular
+ platforms, an exercise left to the reader. Following are some
+ suggestions:
+
+Rivest [Page 7]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+ 1. Change MD4Block so that the context is not used at all if
+ it is empty (mdi == 0) and 64 or more bytes remain (inLen
+ >= 64). In other words, call Transform with inBuf in this
+ case. (This requires that byte ordering is correct in
+ inBuf.)
+
+ 2. Implement a procedure MD4BlockLong modeled after MD4Block
+ where inBuf is UINT4 * instead of unsigned char *.
+ MD4BlockLong would call Transform directly with 16 word
+ blocks from inBuf. Call this instead of MD4Block in
+ general. This works well if you have an I/O procedure that
+ can read long words from a file.
+
+ 3. On "little-endian" platforms where the lowest-address byte
+ in a long word is the least significant (and there are no
+ alignment restrictions), change MD4Block to call Transform
+ directly with 64-byte blocks from inBuf (casted to a UINT4
+ *).
+
+/*
+ **********************************************************************
+ ** md4.h -- Header file for implementation of MD4 **
+ ** RSA Data Security, Inc. MD4 Message Digest Algorithm **
+ ** Created: 2/17/90 RLR **
+ ** Revised: 12/27/90 SRD,AJ,BSK,JT Reference C version **
+ **********************************************************************
+ */
+
+/*
+ **********************************************************************
+ ** Copyright (C) 1990, RSA Data Security, Inc. All rights reserved. **
+ ** **
+ ** License to copy and use this software is granted provided that **
+ ** it is identified as the "RSA Data Security, Inc. MD4 Message **
+ ** Digest Algorithm" in all material mentioning or referencing this **
+ ** software or this function. **
+ ** **
+ ** License is also granted to make and use derivative works **
+ ** provided that such works are identified as "derived from the RSA **
+ ** Data Security, Inc. MD4 Message Digest Algorithm" in all **
+ ** material mentioning or referencing the derived work. **
+ ** **
+ ** 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. **
+ **********************************************************************
+ */
+
+/* typedef a 32 bit type */
+typedef unsigned long int UINT4;
+Rivest [Page 8]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+
+/* Data structure for MD4 (Message Digest) computation */
+typedef struct {
+ UINT4 i[2]; /* number of _bits_ handled mod 2^64 */
+ UINT4 buf[4]; /* scratch buffer */
+ unsigned char in[64]; /* input buffer */
+ unsigned char digest[16]; /* actual digest after MD4Final call */
+} MD4_CTX;
+
+void MD4Init ();
+void MD4Update ();
+void MD4Final ();
+
+/*
+ **********************************************************************
+ ** End of md4.h **
+ ******************************* (cut) ********************************
+ */
+
+/*
+ **********************************************************************
+ ** md4.c **
+ ** RSA Data Security, Inc. MD4 Message Digest Algorithm **
+ ** Created: 2/17/90 RLR **
+ ** Revised: 1/91 SRD,AJ,BSK,JT Reference C Version **
+ **********************************************************************
+ */
+
+/*
+ **********************************************************************
+ ** Copyright (C) 1990, RSA Data Security, Inc. All rights reserved. **
+ ** **
+ ** License to copy and use this software is granted provided that **
+ ** it is identified as the "RSA Data Security, Inc. MD4 Message **
+ ** Digest Algorithm" in all material mentioning or referencing this **
+ ** software or this function. **
+ ** **
+ ** License is also granted to make and use derivative works **
+ ** provided that such works are identified as "derived from the RSA **
+ ** Data Security, Inc. MD4 Message Digest Algorithm" in all **
+ ** material mentioning or referencing the derived work. **
+ ** **
+ ** 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 "md4.h"
+
+Rivest [Page 9]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+/* forward declaration */
+static void Transform ();
+
+static unsigned char PADDING[64] = {
+ 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
+};
+
+/* F, G and H are basic MD4 functions: selection, majority, parity */
+#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
+#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
+#define H(x, y, z) ((x) ^ (y) ^ (z))
+
+/* ROTATE_LEFT rotates x left n bits */
+#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
+
+/* FF, GG and HH are MD4 transformations for rounds 1, 2 and 3 */
+/* Rotation is separate from addition to prevent recomputation */
+#define FF(a, b, c, d, x, s) \
+ {(a) += F ((b), (c), (d)) + (x); \
+ (a) = ROTATE_LEFT ((a), (s));}
+#define GG(a, b, c, d, x, s) \
+ {(a) += G ((b), (c), (d)) + (x) + (UINT4)013240474631; \
+ (a) = ROTATE_LEFT ((a), (s));}
+#define HH(a, b, c, d, x, s) \
+ {(a) += H ((b), (c), (d)) + (x) + (UINT4)015666365641; \
+ (a) = ROTATE_LEFT ((a), (s));}
+
+void MD4Init (mdContext)
+MD4_CTX *mdContext;
+{
+ mdContext->i[0] = mdContext->i[1] = (UINT4)0;
+
+ /* Load magic initialization constants.
+ */
+ mdContext->buf[0] = (UINT4)0x67452301;
+ mdContext->buf[1] = (UINT4)0xefcdab89;
+ mdContext->buf[2] = (UINT4)0x98badcfe;
+ mdContext->buf[3] = (UINT4)0x10325476;
+}
+
+void MD4Update (mdContext, inBuf, inLen)
+MD4_CTX *mdContext;
+unsigned char *inBuf;
+unsigned int inLen;
+{
+ UINT4 in[16];
+ int mdi;
+Rivest [Page 10]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+ unsigned int i, ii;
+
+ /* compute number of bytes mod 64 */
+ mdi = (int)((mdContext->i[0] >> 3) & 0x3F);
+
+ /* update number of bits */
+ if ((mdContext->i[0] + ((UINT4)inLen << 3)) < mdContext->i[0])
+ mdContext->i[1]++;
+ mdContext->i[0] += ((UINT4)inLen << 3);
+ mdContext->i[1] += ((UINT4)inLen >> 29);
+
+ while (inLen--) {
+ /* add new character to buffer, increment mdi */
+ mdContext->in[mdi++] = *inBuf++;
+
+ /* transform if necessary */
+ if (mdi == 0x40) {
+ for (i = 0, ii = 0; i < 16; i++, ii += 4)
+ in[i] = (((UINT4)mdContext->in[ii+3]) << 24) |
+ (((UINT4)mdContext->in[ii+2]) << 16) |
+ (((UINT4)mdContext->in[ii+1]) << 8) |
+ ((UINT4)mdContext->in[ii]);
+ Transform (mdContext->buf, in);
+ mdi = 0;
+ }
+ }
+}
+
+void MD4Final (mdContext)
+MD4_CTX *mdContext;
+{
+ UINT4 in[16];
+ int mdi;
+ unsigned int i, ii;
+ unsigned int padLen;
+
+ /* save number of bits */
+ in[14] = mdContext->i[0];
+ in[15] = mdContext->i[1];
+
+ /* compute number of bytes mod 64 */
+ mdi = (int)((mdContext->i[0] >> 3) & 0x3F);
+
+ /* pad out to 56 mod 64 */
+ padLen = (mdi < 56) ? (56 - mdi) : (120 - mdi);
+ MD4Update (mdContext, PADDING, padLen);
+
+ /* append length in bits and transform */
+ for (i = 0, ii = 0; i < 14; i++, ii += 4)
+ in[i] = (((UINT4)mdContext->in[ii+3]) << 24) |
+ (((UINT4)mdContext->in[ii+2]) << 16) |
+ (((UINT4)mdContext->in[ii+1]) << 8) |
+ ((UINT4)mdContext->in[ii]);
+ Transform (mdContext->buf, in);
+Rivest [Page 11]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+
+ /* store buffer in digest */
+ for (i = 0, ii = 0; i < 4; i++, ii += 4) {
+ mdContext->digest[ii] = (unsigned char)(mdContext->buf[i] & 0xFF);
+ mdContext->digest[ii+1] =
+ (unsigned char)((mdContext->buf[i] >> 8) & 0xFF);
+ mdContext->digest[ii+2] =
+ (unsigned char)((mdContext->buf[i] >> 16) & 0xFF);
+ mdContext->digest[ii+3] =
+ (unsigned char)((mdContext->buf[i] >> 24) & 0xFF);
+ }
+}
+
+/* Basic MD4 step. Transform buf based on in.
+ */
+static void Transform (buf, in)
+UINT4 *buf;
+UINT4 *in;
+{
+ UINT4 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
+
+ /* Round 1 */
+ FF (a, b, c, d, in[ 0], 3);
+ FF (d, a, b, c, in[ 1], 7);
+ FF (c, d, a, b, in[ 2], 11);
+ FF (b, c, d, a, in[ 3], 19);
+ FF (a, b, c, d, in[ 4], 3);
+ FF (d, a, b, c, in[ 5], 7);
+ FF (c, d, a, b, in[ 6], 11);
+ FF (b, c, d, a, in[ 7], 19);
+ FF (a, b, c, d, in[ 8], 3);
+ FF (d, a, b, c, in[ 9], 7);
+ FF (c, d, a, b, in[10], 11);
+ FF (b, c, d, a, in[11], 19);
+ FF (a, b, c, d, in[12], 3);
+ FF (d, a, b, c, in[13], 7);
+ FF (c, d, a, b, in[14], 11);
+ FF (b, c, d, a, in[15], 19);
+
+ /* Round 2 */
+ GG (a, b, c, d, in[ 0], 3);
+ GG (d, a, b, c, in[ 4], 5);
+ GG (c, d, a, b, in[ 8], 9);
+ GG (b, c, d, a, in[12], 13);
+ GG (a, b, c, d, in[ 1], 3);
+ GG (d, a, b, c, in[ 5], 5);
+ GG (c, d, a, b, in[ 9], 9);
+ GG (b, c, d, a, in[13], 13);
+ GG (a, b, c, d, in[ 2], 3);
+ GG (d, a, b, c, in[ 6], 5);
+ GG (c, d, a, b, in[10], 9);
+ GG (b, c, d, a, in[14], 13);
+ GG (a, b, c, d, in[ 3], 3);
+ GG (d, a, b, c, in[ 7], 5);
+Rivest [Page 12]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+ GG (c, d, a, b, in[11], 9);
+ GG (b, c, d, a, in[15], 13);
+
+ /* Round 3 */
+ HH (a, b, c, d, in[ 0], 3);
+ HH (d, a, b, c, in[ 8], 9);
+ HH (c, d, a, b, in[ 4], 11);
+ HH (b, c, d, a, in[12], 15);
+ HH (a, b, c, d, in[ 2], 3);
+ HH (d, a, b, c, in[10], 9);
+ HH (c, d, a, b, in[ 6], 11);
+ HH (b, c, d, a, in[14], 15);
+ HH (a, b, c, d, in[ 1], 3);
+ HH (d, a, b, c, in[ 9], 9);
+ HH (c, d, a, b, in[ 5], 11);
+ HH (b, c, d, a, in[13], 15);
+ HH (a, b, c, d, in[ 3], 3);
+ HH (d, a, b, c, in[11], 9);
+ HH (c, d, a, b, in[ 7], 11);
+ HH (b, c, d, a, in[15], 15);
+
+ buf[0] += a;
+ buf[1] += b;
+ buf[2] += c;
+ buf[3] += d;
+}
+
+/*
+ **********************************************************************
+ ** End of md4.c **
+ ******************************* (cut) ********************************
+ */
+
+/*
+ **********************************************************************
+ ** md4driver.c -- sample routines to test **
+ ** RSA Data Security, Inc. MD4 message digest algorithm. **
+ ** Created: 2/16/90 RLR **
+ ** Updated: 1/91 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. **
+ **********************************************************************
+Rivest [Page 13]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+ */
+
+#include <stdio.h>
+#include <sys/types.h>
+#include <time.h>
+#include <string.h>
+#include "md4.h"
+
+/* Prints message digest buffer in mdContext as 32 hexadecimal digits.
+ Order is from low-order byte to high-order byte of digest.
+ Each byte is printed with high-order hexadecimal digit first.
+ */
+static void MDPrint (mdContext)
+MD4_CTX *mdContext;
+{
+ int i;
+
+ for (i = 0; i < 16; i++)
+ printf ("%02x", mdContext->digest[i]);
+}
+
+/* size of test block */
+#define TEST_BLOCK_SIZE 1000
+
+/* number of blocks to process */
+#define TEST_BLOCKS 2000
+
+/* 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 MD4.
+ Measures wall time required to digest TEST_BLOCKS * TEST_BLOCK_SIZE
+ characters.
+ */
+static void MDTimeTrial ()
+{
+ MD4_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 ("MD4 time trial. Processing %ld characters...\n", TEST_BYTES);
+ time (&startTime);
+
+ /* digest data in TEST_BLOCK_SIZE byte blocks */
+ MD4Init (&mdContext);
+ for (i = TEST_BLOCKS; i > 0; i--)
+ MD4Update (&mdContext, data, TEST_BLOCK_SIZE);
+ MD4Final (&mdContext);
+Rivest [Page 14]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+
+ /* 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;
+{
+ MD4_CTX mdContext;
+ unsigned int len = strlen (inString);
+
+ MD4Init (&mdContext);
+ MD4Update (&mdContext, inString, len);
+ MD4Final (&mdContext);
+ MDPrint (&mdContext);
+ printf (" \"%s\"\n\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");
+ MD4_CTX mdContext;
+ int bytes;
+ unsigned char data[1024];
+
+ if (inFile == NULL) {
+ printf ("%s can't be opened.\n", filename);
+ return;
+ }
+
+ MD4Init (&mdContext);
+ while ((bytes = fread (data, 1, 1024, inFile)) != 0)
+ MD4Update (&mdContext, data, bytes);
+ MD4Final (&mdContext);
+ MDPrint (&mdContext);
+ printf (" %s\n", filename);
+ fclose (inFile);
+}
+Rivest [Page 15]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+
+/* Writes the message digest of the data from stdin onto stdout,
+ followed by a carriage return.
+ */
+static void MDFilter ()
+{
+ MD4_CTX mdContext;
+ int bytes;
+ unsigned char data[16];
+
+ MD4Init (&mdContext);
+ while ((bytes = fread (data, 1, 16, stdin)) != 0)
+ MD4Update (&mdContext, data, bytes);
+ MD4Final (&mdContext);
+ MDPrint (&mdContext);
+ printf ("\n");
+}
+
+/* Runs a standard suite of test data.
+ */
+static void MDTestSuite ()
+{
+ printf ("MD4 test suite results:\n\n");
+ MDString ("");
+ MDString ("a");
+ MDString ("abc");
+ MDString ("message digest");
+ 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++)
+Rivest [Page 16]
+
+
+RFC 1186B The MD4 Message Digest Algorithm 9 January 1991
+
+
+
+ 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 md4driver.c **
+ ******************************* (cut) ********************************
+ */
+
+-----------------------------------------------------------------------
+-- Sample session output obtained by running md4driver test suite --
+-----------------------------------------------------------------------
+
+ MD4 test suite results:
+
+ 31d6cfe0d16ae931b73c59d7e0c089c0 ""
+
+ bde52cb31de33e46245e05fbdbd6fb24 "a"
+
+ a448017aaf21d8525fc10ae87aa6729d "abc"
+
+ d9130a8164549fe818874806e1c7014b "message digest"
+
+ d79e1c308aa5bbcdeea8ed63df412da9 "abcdefghijklmnopqrstuvwxyz"
+
+ 043f8582f241db351ce627e153e7f0e4 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghij
+ klmnopqrstuvwxyz0123456789"
+
+ e33b4ddc9c38f2199c3e7b164fcc0536 "123456789012345678901234567890123456
+ 78901234567890123456789012345678901234567890"
+
+ a448017aaf21d8525fc10ae87aa6729d 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 "md4.doc".
+
+
+
+
+
+
+
+Rivest [Page 17]
+
+
+
+
generated by cgit (git 2.34.1) at 2026-03-06 23:05:37 +0000