iPXE
md5.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 /** @file
00027  *
00028  * MD5 algorithm
00029  *
00030  */
00031 
00032 #include <stdint.h>
00033 #include <string.h>
00034 #include <byteswap.h>
00035 #include <assert.h>
00036 #include <ipxe/rotate.h>
00037 #include <ipxe/crypto.h>
00038 #include <ipxe/asn1.h>
00039 #include <ipxe/md5.h>
00040 
00041 /** MD5 variables */
00042 struct md5_variables {
00043         /* This layout matches that of struct md5_digest_data,
00044          * allowing for efficient endianness-conversion,
00045          */
00046         uint32_t a;
00047         uint32_t b;
00048         uint32_t c;
00049         uint32_t d;
00050         uint32_t w[16];
00051 } __attribute__ (( packed ));
00052 
00053 /** MD5 constants */
00054 static const uint32_t k[64] = {
00055         0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a,
00056         0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
00057         0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, 0xf61e2562, 0xc040b340,
00058         0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
00059         0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8,
00060         0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
00061         0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, 0x289b7ec6, 0xeaa127fa,
00062         0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
00063         0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92,
00064         0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
00065         0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
00066 };
00067 
00068 /** MD5 shift amounts */
00069 static const uint8_t r[4][4] = {
00070         {  7, 12, 17, 22 },
00071         {  5,  9, 14, 20 },
00072         {  4, 11, 16, 23 },
00073         {  6, 10, 15, 21 },
00074 };
00075 
00076 /**
00077  * f(b,c,d) for steps 0 to 15
00078  *
00079  * @v v         MD5 variables
00080  * @ret f       f(b,c,d)
00081  */
00082 static uint32_t md5_f_0_15 ( struct md5_variables *v ) {
00083         return ( v->d ^ ( v->b & ( v->c ^ v->d ) ) );
00084 }
00085 
00086 /**
00087  * f(b,c,d) for steps 16 to 31
00088  *
00089  * @v v         MD5 variables
00090  * @ret f       f(b,c,d)
00091  */
00092 static uint32_t md5_f_16_31 ( struct md5_variables *v ) {
00093         return ( v->c ^ ( v->d & ( v->b ^ v->c ) ) );
00094 }
00095 
00096 /**
00097  * f(b,c,d) for steps 32 to 47
00098  *
00099  * @v v         MD5 variables
00100  * @ret f       f(b,c,d)
00101  */
00102 static uint32_t md5_f_32_47 ( struct md5_variables *v ) {
00103         return ( v->b ^ v->c ^ v->d );
00104 }
00105 
00106 /**
00107  * f(b,c,d) for steps 48 to 63
00108  *
00109  * @v v         MD5 variables
00110  * @ret f       f(b,c,d)
00111  */
00112 static uint32_t md5_f_48_63 ( struct md5_variables *v ) {
00113         return ( v->c ^ ( v->b | (~v->d) ) );
00114 }
00115 
00116 /** An MD5 step function */
00117 struct md5_step {
00118         /**
00119          * Calculate f(b,c,d)
00120          *
00121          * @v v         MD5 variables
00122          * @ret f       f(b,c,d)
00123          */
00124         uint32_t ( * f ) ( struct md5_variables *v );
00125         /** Coefficient of i in g=ni+m */
00126         uint8_t coefficient;
00127         /** Constant term in g=ni+m */
00128         uint8_t constant;
00129 };
00130 
00131 /** MD5 steps */
00132 static struct md5_step md5_steps[4] = {
00133         /** 0 to 15 */
00134         { .f = md5_f_0_15,      .coefficient = 1,       .constant = 0 },
00135         /** 16 to 31 */
00136         { .f = md5_f_16_31,     .coefficient = 5,       .constant = 1 },
00137         /** 32 to 47 */
00138         { .f = md5_f_32_47,     .coefficient = 3,       .constant = 5 },
00139         /** 48 to 63 */
00140         { .f = md5_f_48_63,     .coefficient = 7,       .constant = 0 },
00141 };
00142 
00143 /**
00144  * Initialise MD5 algorithm
00145  *
00146  * @v ctx               MD5 context
00147  */
00148 static void md5_init ( void *ctx ) {
00149         struct md5_context *context = ctx;
00150 
00151         context->ddd.dd.digest.h[0] = cpu_to_le32 ( 0x67452301 );
00152         context->ddd.dd.digest.h[1] = cpu_to_le32 ( 0xefcdab89 );
00153         context->ddd.dd.digest.h[2] = cpu_to_le32 ( 0x98badcfe );
00154         context->ddd.dd.digest.h[3] = cpu_to_le32 ( 0x10325476 );
00155         context->len = 0;
00156 }
00157 
00158 /**
00159  * Calculate MD5 digest of accumulated data
00160  *
00161  * @v context           MD5 context
00162  */
00163 static void md5_digest ( struct md5_context *context ) {
00164         union {
00165                 union md5_digest_data_dwords ddd;
00166                 struct md5_variables v;
00167         } u;
00168         uint32_t *a = &u.v.a;
00169         uint32_t *b = &u.v.b;
00170         uint32_t *c = &u.v.c;
00171         uint32_t *d = &u.v.d;
00172         uint32_t *w = u.v.w;
00173         uint32_t f;
00174         uint32_t g;
00175         uint32_t temp;
00176         struct md5_step *step;
00177         unsigned int round;
00178         unsigned int i;
00179 
00180         /* Sanity checks */
00181         assert ( ( context->len % sizeof ( context->ddd.dd.data ) ) == 0 );
00182         linker_assert ( &u.ddd.dd.digest.h[0] == a, md5_bad_layout );
00183         linker_assert ( &u.ddd.dd.digest.h[1] == b, md5_bad_layout );
00184         linker_assert ( &u.ddd.dd.digest.h[2] == c, md5_bad_layout );
00185         linker_assert ( &u.ddd.dd.digest.h[3] == d, md5_bad_layout );
00186         linker_assert ( &u.ddd.dd.data.dword[0] == w, md5_bad_layout );
00187 
00188         DBGC ( context, "MD5 digesting:\n" );
00189         DBGC_HDA ( context, 0, &context->ddd.dd.digest,
00190                    sizeof ( context->ddd.dd.digest ) );
00191         DBGC_HDA ( context, context->len, &context->ddd.dd.data,
00192                    sizeof ( context->ddd.dd.data ) );
00193 
00194         /* Convert h[0..3] to host-endian, and initialise a, b, c, d,
00195          * and w[0..15]
00196          */
00197         for ( i = 0 ; i < ( sizeof ( u.ddd.dword ) /
00198                             sizeof ( u.ddd.dword[0] ) ) ; i++ ) {
00199                 le32_to_cpus ( &context->ddd.dword[i] );
00200                 u.ddd.dword[i] = context->ddd.dword[i];
00201         }
00202 
00203         /* Main loop */
00204         for ( i = 0 ; i < 64 ; i++ ) {
00205                 round = ( i / 16 );
00206                 step = &md5_steps[round];
00207                 f = step->f ( &u.v );
00208                 g = ( ( ( step->coefficient * i ) + step->constant ) % 16 );
00209                 temp = *d;
00210                 *d = *c;
00211                 *c = *b;
00212                 *b = ( *b + rol32 ( ( *a + f + k[i] + w[g] ),
00213                                     r[round][ i % 4 ] ) );
00214                 *a = temp;
00215                 DBGC2 ( context, "%2d : %08x %08x %08x %08x\n",
00216                         i, *a, *b, *c, *d );
00217         }
00218 
00219         /* Add chunk to hash and convert back to little-endian */
00220         for ( i = 0 ; i < 4 ; i++ ) {
00221                 context->ddd.dd.digest.h[i] =
00222                         cpu_to_le32 ( context->ddd.dd.digest.h[i] +
00223                                       u.ddd.dd.digest.h[i] );
00224         }
00225 
00226         DBGC ( context, "MD5 digested:\n" );
00227         DBGC_HDA ( context, 0, &context->ddd.dd.digest,
00228                    sizeof ( context->ddd.dd.digest ) );
00229 }
00230 
00231 /**
00232  * Accumulate data with MD5 algorithm
00233  *
00234  * @v ctx               MD5 context
00235  * @v data              Data
00236  * @v len               Length of data
00237  */
00238 static void md5_update ( void *ctx, const void *data, size_t len ) {
00239         struct md5_context *context = ctx;
00240         const uint8_t *byte = data;
00241         size_t offset;
00242 
00243         /* Accumulate data a byte at a time, performing the digest
00244          * whenever we fill the data buffer
00245          */
00246         while ( len-- ) {
00247                 offset = ( context->len % sizeof ( context->ddd.dd.data ) );
00248                 context->ddd.dd.data.byte[offset] = *(byte++);
00249                 context->len++;
00250                 if ( ( context->len % sizeof ( context->ddd.dd.data ) ) == 0 )
00251                         md5_digest ( context );
00252         }
00253 }
00254 
00255 /**
00256  * Generate MD5 digest
00257  *
00258  * @v ctx               MD5 context
00259  * @v out               Output buffer
00260  */
00261 static void md5_final ( void *ctx, void *out ) {
00262         struct md5_context *context = ctx;
00263         uint64_t len_bits;
00264         uint8_t pad;
00265 
00266         /* Record length before pre-processing */
00267         len_bits = cpu_to_le64 ( ( ( uint64_t ) context->len ) * 8 );
00268 
00269         /* Pad with a single "1" bit followed by as many "0" bits as required */
00270         pad = 0x80;
00271         do {
00272                 md5_update ( ctx, &pad, sizeof ( pad ) );
00273                 pad = 0x00;
00274         } while ( ( context->len % sizeof ( context->ddd.dd.data ) ) !=
00275                   offsetof ( typeof ( context->ddd.dd.data ), final.len ) );
00276 
00277         /* Append length (in bits) */
00278         md5_update ( ctx, &len_bits, sizeof ( len_bits ) );
00279         assert ( ( context->len % sizeof ( context->ddd.dd.data ) ) == 0 );
00280 
00281         /* Copy out final digest */
00282         memcpy ( out, &context->ddd.dd.digest,
00283                  sizeof ( context->ddd.dd.digest ) );
00284 }
00285 
00286 /** MD5 algorithm */
00287 struct digest_algorithm md5_algorithm = {
00288         .name           = "md5",
00289         .ctxsize        = sizeof ( struct md5_context ),
00290         .blocksize      = sizeof ( union md5_block ),
00291         .digestsize     = sizeof ( struct md5_digest ),
00292         .init           = md5_init,
00293         .update         = md5_update,
00294         .final          = md5_final,
00295 };
00296 
00297 /** "md5" object identifier */
00298 static uint8_t oid_md5[] = { ASN1_OID_MD5 };
00299 
00300 /** "md5" OID-identified algorithm */
00301 struct asn1_algorithm oid_md5_algorithm __asn1_algorithm = {
00302         .name = "md5",
00303         .digest = &md5_algorithm,
00304         .oid = ASN1_OID_CURSOR ( oid_md5 ),
00305 };