summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc1186.txt
blob: 5c0d9414eec8c1cb2dd962f7d30e97dd752fc21b (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L
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]
^L