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
|