1 /*
2 * Copyright (C) 2017 Michael Brown <mbrown@fensystems.co.uk>.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; either version 2 of the
7 * License, or any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17 * 02110-1301, USA.
18 *
19 * You can also choose to distribute this program under the terms of
20 * the Unmodified Binary Distribution Licence (as given in the file
21 * COPYING.UBDL), provided that you have satisfied its requirements.
22 */
23
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25
26 /** @file
27 *
28 * MD4 algorithm
29 *
30 */
31
32 #include <stdint.h>
33 #include <string.h>
34 #include <byteswap.h>
35 #include <assert.h>
36 #include <ipxe/rotate.h>
37 #include <ipxe/crypto.h>
38 #include <ipxe/asn1.h>
39 #include <ipxe/md4.h>
40
41 /** MD4 variables */
42 struct md4_variables {
43 /* This layout matches that of struct md4_digest_data,
44 * allowing for efficient endianness-conversion,
45 */
46 uint32_t a;
47 uint32_t b;
48 uint32_t c;
49 uint32_t d;
50 uint32_t w[16];
51 } __attribute__ (( packed ));
52
53 /** MD4 shift amounts */
54 static const uint8_t r[3][4] = {
55 { 3, 7, 11, 19 },
56 { 3, 5, 9, 13 },
57 { 3, 9, 11, 15 },
58 };
59
60 /**
61 * f(b,c,d,w) for steps 0 to 15
62 *
63 * @v v MD4 variables
64 * @v i Index within round
65 * @ret f f(b,c,d,w)
66 */
md4_f_0_15(struct md4_variables * v,unsigned int i)67 static uint32_t md4_f_0_15 ( struct md4_variables *v, unsigned int i ) {
68 return ( ( ( v->b & v->c ) | ( ~v->b & v->d ) ) + v->w[i] );
69 }
70
71 /**
72 * f(b,c,d,w) for steps 16 to 31
73 *
74 * @v v MD4 variables
75 * @v i Index within round
76 * @ret f f(b,c,d,w)
77 */
md4_f_16_31(struct md4_variables * v,unsigned int i)78 static uint32_t md4_f_16_31 ( struct md4_variables *v, unsigned int i ) {
79 return ( ( ( v->b & v->c ) | ( v->b & v->d ) | ( v->c & v->d ) ) +
80 v->w[ ( ( i << 2 ) | ( i >> 2 ) ) % 16 ] );
81 }
82
83 /**
84 * f(b,c,d,w) for steps 32 to 47
85 *
86 * @v v MD4 variables
87 * @v i Index within round
88 * @ret f f(b,c,d,w)
89 */
md4_f_32_47(struct md4_variables * v,unsigned int i)90 static uint32_t md4_f_32_47 ( struct md4_variables *v, unsigned int i ) {
91 static const uint8_t reverse[16] = {
92 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
93 };
94 return ( ( v->b ^ v->c ^ v->d ) + v->w[reverse[i]] );
95 }
96
97 /** An MD4 step function */
98 struct md4_step {
99 /**
100 * Calculate f(b,c,d,w)
101 *
102 * @v v MD4 variables
103 * @v i Index within round
104 * @ret f f(b,c,d,w)
105 */
106 uint32_t ( * f ) ( struct md4_variables *v, unsigned int i );
107 /** Constant */
108 uint32_t constant;
109 };
110
111 /** MD4 steps */
112 static struct md4_step md4_steps[4] = {
113 /** 0 to 15 */
114 { .f = md4_f_0_15, .constant = 0x00000000UL },
115 /** 16 to 31 */
116 { .f = md4_f_16_31, .constant = 0x5a827999UL },
117 /** 32 to 47 */
118 { .f = md4_f_32_47, .constant = 0x6ed9eba1UL },
119 };
120
121 /**
122 * Initialise MD4 algorithm
123 *
124 * @v ctx MD4 context
125 */
md4_init(void * ctx)126 static void md4_init ( void *ctx ) {
127 struct md4_context *context = ctx;
128
129 context->ddd.dd.digest.h[0] = cpu_to_le32 ( 0x67452301 );
130 context->ddd.dd.digest.h[1] = cpu_to_le32 ( 0xefcdab89 );
131 context->ddd.dd.digest.h[2] = cpu_to_le32 ( 0x98badcfe );
132 context->ddd.dd.digest.h[3] = cpu_to_le32 ( 0x10325476 );
133 context->len = 0;
134 }
135
136 /**
137 * Calculate MD4 digest of accumulated data
138 *
139 * @v context MD4 context
140 */
md4_digest(struct md4_context * context)141 static void md4_digest ( struct md4_context *context ) {
142 union {
143 union md4_digest_data_dwords ddd;
144 struct md4_variables v;
145 } u;
146 uint32_t *a = &u.v.a;
147 uint32_t *b = &u.v.b;
148 uint32_t *c = &u.v.c;
149 uint32_t *d = &u.v.d;
150 uint32_t *w = u.v.w;
151 uint32_t f;
152 uint32_t temp;
153 struct md4_step *step;
154 unsigned int round;
155 unsigned int i;
156
157 /* Sanity checks */
158 assert ( ( context->len % sizeof ( context->ddd.dd.data ) ) == 0 );
159 linker_assert ( &u.ddd.dd.digest.h[0] == a, md4_bad_layout );
160 linker_assert ( &u.ddd.dd.digest.h[1] == b, md4_bad_layout );
161 linker_assert ( &u.ddd.dd.digest.h[2] == c, md4_bad_layout );
162 linker_assert ( &u.ddd.dd.digest.h[3] == d, md4_bad_layout );
163 linker_assert ( &u.ddd.dd.data.dword[0] == w, md4_bad_layout );
164
165 DBGC ( context, "MD4 digesting:\n" );
166 DBGC_HDA ( context, 0, &context->ddd.dd.digest,
167 sizeof ( context->ddd.dd.digest ) );
168 DBGC_HDA ( context, context->len, &context->ddd.dd.data,
169 sizeof ( context->ddd.dd.data ) );
170
171 /* Convert h[0..3] to host-endian, and initialise a, b, c, d,
172 * and x[0..15]
173 */
174 for ( i = 0 ; i < ( sizeof ( u.ddd.dword ) /
175 sizeof ( u.ddd.dword[0] ) ) ; i++ ) {
176 le32_to_cpus ( &context->ddd.dword[i] );
177 u.ddd.dword[i] = context->ddd.dword[i];
178 }
179
180 /* Main loop */
181 for ( i = 0 ; i < 48 ; i++ ) {
182 round = ( i / 16 );
183 step = &md4_steps[round];
184 f = step->f ( &u.v, ( i % 16 ) );
185 temp = *d;
186 *d = *c;
187 *c = *b;
188 *b = rol32 ( ( *a + f + step->constant ), r[round][ i % 4 ] );
189 *a = temp;
190 DBGC2 ( context, "%2d : %08x %08x %08x %08x\n",
191 i, *a, *b, *c, *d );
192 }
193
194 /* Add chunk to hash and convert back to little-endian */
195 for ( i = 0 ; i < 4 ; i++ ) {
196 context->ddd.dd.digest.h[i] =
197 cpu_to_le32 ( context->ddd.dd.digest.h[i] +
198 u.ddd.dd.digest.h[i] );
199 }
200
201 DBGC ( context, "MD4 digested:\n" );
202 DBGC_HDA ( context, 0, &context->ddd.dd.digest,
203 sizeof ( context->ddd.dd.digest ) );
204 }
205
206 /**
207 * Accumulate data with MD4 algorithm
208 *
209 * @v ctx MD4 context
210 * @v data Data
211 * @v len Length of data
212 */
md4_update(void * ctx,const void * data,size_t len)213 static void md4_update ( void *ctx, const void *data, size_t len ) {
214 struct md4_context *context = ctx;
215 const uint8_t *byte = data;
216 size_t offset;
217
218 /* Accumulate data a byte at a time, performing the digest
219 * whenever we fill the data buffer
220 */
221 while ( len-- ) {
222 offset = ( context->len % sizeof ( context->ddd.dd.data ) );
223 context->ddd.dd.data.byte[offset] = *(byte++);
224 context->len++;
225 if ( ( context->len % sizeof ( context->ddd.dd.data ) ) == 0 )
226 md4_digest ( context );
227 }
228 }
229
230 /**
231 * Generate MD4 digest
232 *
233 * @v ctx MD4 context
234 * @v out Output buffer
235 */
md4_final(void * ctx,void * out)236 static void md4_final ( void *ctx, void *out ) {
237 struct md4_context *context = ctx;
238 uint64_t len_bits;
239 uint8_t pad;
240
241 /* Record length before pre-processing */
242 len_bits = cpu_to_le64 ( ( ( uint64_t ) context->len ) * 8 );
243
244 /* Pad with a single "1" bit followed by as many "0" bits as required */
245 pad = 0x80;
246 do {
247 md4_update ( ctx, &pad, sizeof ( pad ) );
248 pad = 0x00;
249 } while ( ( context->len % sizeof ( context->ddd.dd.data ) ) !=
250 offsetof ( typeof ( context->ddd.dd.data ), final.len ) );
251
252 /* Append length (in bits) */
253 md4_update ( ctx, &len_bits, sizeof ( len_bits ) );
254 assert ( ( context->len % sizeof ( context->ddd.dd.data ) ) == 0 );
255
256 /* Copy out final digest */
257 memcpy ( out, &context->ddd.dd.digest,
258 sizeof ( context->ddd.dd.digest ) );
259 }
260
261 /** MD4 algorithm */
262 struct digest_algorithm md4_algorithm = {
263 .name = "md4",
264 .ctxsize = sizeof ( struct md4_context ),
265 .blocksize = sizeof ( union md4_block ),
266 .digestsize = sizeof ( struct md4_digest ),
267 .init = md4_init,
268 .update = md4_update,
269 .final = md4_final,
270 };
271
272 /** "md4" object identifier */
273 static uint8_t oid_md4[] = { ASN1_OID_MD4 };
274
275 /** "md4" OID-identified algorithm */
276 struct asn1_algorithm oid_md4_algorithm __asn1_algorithm = {
277 .name = "md4",
278 .digest = &md4_algorithm,
279 .oid = ASN1_OID_CURSOR ( oid_md4 ),
280 };
281