$treeview $search $mathjax $extrastylesheet
librsync
2.0.2
$projectbrief
|
$projectbrief
|
$searchbox |
00001 /*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*- 00002 * 00003 * librsync -- the library for network deltas 00004 * 00005 * Copyright (C) 2000, 2001 by Martin Pool <mbp@sourcefrog.net> 00006 * Copyright (C) 1997-1999 by Andrew Tridgell 00007 * Copyright (C) 2002, 2003 by Donovan Baarda <abo@minkirri.apana.org.au> 00008 * 00009 * This program is free software; you can redistribute it and/or modify 00010 * it under the terms of the GNU Lesser General Public License as published by 00011 * the Free Software Foundation; either version 2.1 of the License, or 00012 * (at your option) any later version. 00013 * 00014 * This program is distributed in the hope that it will be useful, 00015 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00017 * GNU Lesser General Public License for more details. 00018 * 00019 * You should have received a copy of the GNU Lesser General Public License 00020 * along with this program; if not, write to the Free Software 00021 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00022 */ 00023 00024 /** \file mdfour.c MD4 message digest algorithm. 00025 * 00026 * \todo Perhaps use the MD4 routine from OpenSSL if it's installed. It's 00027 * probably not worth the trouble. 00028 * 00029 * This was originally written by Andrew Tridgell for use in Samba. It was then 00030 * modified by; 00031 * 00032 * 2002-06-xx: Robert Weber <robert.weber@Colorado.edu> optimisations and fixed 00033 * >512M support. 00034 * 00035 * 2002-06-27: Donovan Baarda <abo@minkirri.apana.org.au> further optimisations 00036 * and cleanups. 00037 * 00038 * 2004-09-09: Simon Law <sfllaw@debian.org> handle little-endian machines that 00039 * can't do unaligned access (e.g. ia64, pa-risc). */ 00040 00041 #include "config.h" 00042 00043 #include <stdlib.h> 00044 #include <string.h> 00045 #include <stdio.h> 00046 00047 #include "librsync.h" 00048 #include "trace.h" 00049 #include "mdfour.h" 00050 00051 #define F(X,Y,Z) (((X)&(Y)) | ((~(X))&(Z))) 00052 #define G(X,Y,Z) (((X)&(Y)) | ((X)&(Z)) | ((Y)&(Z))) 00053 #define H(X,Y,Z) ((X)^(Y)^(Z)) 00054 #define lshift(x,s) (((x)<<(s)) | ((x)>>(32-(s)))) 00055 00056 #define ROUND1(a,b,c,d,k,s) a = lshift(a + F(b,c,d) + X[k], s) 00057 #define ROUND2(a,b,c,d,k,s) a = lshift(a + G(b,c,d) + X[k] + 0x5A827999,s) 00058 #define ROUND3(a,b,c,d,k,s) a = lshift(a + H(b,c,d) + X[k] + 0x6ED9EBA1,s) 00059 00060 /** padding data used for finalising */ 00061 static unsigned char PADDING[64] = { 00062 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00063 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00064 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 00065 }; 00066 00067 static void rs_mdfour_block(rs_mdfour_t *md, void const *p); 00068 00069 /** Update an MD4 accumulator from a 64-byte chunk. 00070 * 00071 * This cannot be used for the last chunk of the file, which must be padded and 00072 * contain the file length. rs_mdfour_tail() is used for that. 00073 * 00074 * \todo Recode to be fast, and to use system integer types. Perhaps if we can 00075 * find an mdfour implementation already on the system (e.g. in OpenSSL) then 00076 * we should use it instead of our own? 00077 * 00078 * \param X A series of integer, read little-endian from the file. */ 00079 static void rs_mdfour64(rs_mdfour_t *m, const void *p) 00080 { 00081 uint32_t AA, BB, CC, DD; 00082 uint32_t A, B, C, D; 00083 const uint32_t *X = (const uint32_t *)p; 00084 00085 A = m->A; 00086 B = m->B; 00087 C = m->C; 00088 D = m->D; 00089 AA = A; 00090 BB = B; 00091 CC = C; 00092 DD = D; 00093 00094 ROUND1(A, B, C, D, 0, 3); 00095 ROUND1(D, A, B, C, 1, 7); 00096 ROUND1(C, D, A, B, 2, 11); 00097 ROUND1(B, C, D, A, 3, 19); 00098 ROUND1(A, B, C, D, 4, 3); 00099 ROUND1(D, A, B, C, 5, 7); 00100 ROUND1(C, D, A, B, 6, 11); 00101 ROUND1(B, C, D, A, 7, 19); 00102 ROUND1(A, B, C, D, 8, 3); 00103 ROUND1(D, A, B, C, 9, 7); 00104 ROUND1(C, D, A, B, 10, 11); 00105 ROUND1(B, C, D, A, 11, 19); 00106 ROUND1(A, B, C, D, 12, 3); 00107 ROUND1(D, A, B, C, 13, 7); 00108 ROUND1(C, D, A, B, 14, 11); 00109 ROUND1(B, C, D, A, 15, 19); 00110 00111 ROUND2(A, B, C, D, 0, 3); 00112 ROUND2(D, A, B, C, 4, 5); 00113 ROUND2(C, D, A, B, 8, 9); 00114 ROUND2(B, C, D, A, 12, 13); 00115 ROUND2(A, B, C, D, 1, 3); 00116 ROUND2(D, A, B, C, 5, 5); 00117 ROUND2(C, D, A, B, 9, 9); 00118 ROUND2(B, C, D, A, 13, 13); 00119 ROUND2(A, B, C, D, 2, 3); 00120 ROUND2(D, A, B, C, 6, 5); 00121 ROUND2(C, D, A, B, 10, 9); 00122 ROUND2(B, C, D, A, 14, 13); 00123 ROUND2(A, B, C, D, 3, 3); 00124 ROUND2(D, A, B, C, 7, 5); 00125 ROUND2(C, D, A, B, 11, 9); 00126 ROUND2(B, C, D, A, 15, 13); 00127 00128 ROUND3(A, B, C, D, 0, 3); 00129 ROUND3(D, A, B, C, 8, 9); 00130 ROUND3(C, D, A, B, 4, 11); 00131 ROUND3(B, C, D, A, 12, 15); 00132 ROUND3(A, B, C, D, 2, 3); 00133 ROUND3(D, A, B, C, 10, 9); 00134 ROUND3(C, D, A, B, 6, 11); 00135 ROUND3(B, C, D, A, 14, 15); 00136 ROUND3(A, B, C, D, 1, 3); 00137 ROUND3(D, A, B, C, 9, 9); 00138 ROUND3(C, D, A, B, 5, 11); 00139 ROUND3(B, C, D, A, 13, 15); 00140 ROUND3(A, B, C, D, 3, 3); 00141 ROUND3(D, A, B, C, 11, 9); 00142 ROUND3(C, D, A, B, 7, 11); 00143 ROUND3(B, C, D, A, 15, 15); 00144 00145 A += AA; 00146 B += BB; 00147 C += CC; 00148 D += DD; 00149 00150 m->A = A; 00151 m->B = B; 00152 m->C = C; 00153 m->D = D; 00154 } 00155 00156 /** These next routines are necessary because MD4 is specified in terms of 00157 * little-endian int32s, but we have a byte buffer. On little-endian platforms, 00158 * I think we can just use the buffer pointer directly. 00159 * 00160 * There are some nice endianness routines in glib, including assembler 00161 * variants. If we ever depended on glib, then it could be good to use them 00162 * instead. */ 00163 inline static void copy4( /* @out@ */ unsigned char *out, uint32_t const x) 00164 { 00165 out[0] = x; 00166 out[1] = x >> 8; 00167 out[2] = x >> 16; 00168 out[3] = x >> 24; 00169 } 00170 00171 /* We need this if there is a uint64 */ 00172 /* --robert.weber@Colorado.edu */ 00173 #ifdef HAVE_UINT64 00174 inline static void copy8( /* @out@ */ unsigned char *out, uint64_t const x) 00175 { 00176 out[0] = x; 00177 out[1] = x >> 8; 00178 out[2] = x >> 16; 00179 out[3] = x >> 24; 00180 out[4] = x >> 32; 00181 out[5] = x >> 40; 00182 out[6] = x >> 48; 00183 out[7] = x >> 56; 00184 } 00185 #endif /* HAVE_UINT64 */ 00186 00187 /* We only need this if we are big-endian */ 00188 #ifdef WORDS_BIGENDIAN 00189 inline static void copy64( /* @out@ */ uint32_t *M, unsigned char const *in) 00190 { 00191 int i = 16; 00192 00193 while (i--) { 00194 *M++ = (in[3] << 24) | (in[2] << 16) | (in[1] << 8) | in[0]; 00195 in += 4; 00196 } 00197 } 00198 00199 /** Accumulate a block, making appropriate conversions for bigendian machines. 00200 */ 00201 inline static void rs_mdfour_block(rs_mdfour_t *md, void const *p) 00202 { 00203 uint32_t M[16]; 00204 00205 copy64(M, p); 00206 rs_mdfour64(md, M); 00207 } 00208 00209 #else /* WORDS_BIGENDIAN */ 00210 00211 # ifdef __i386__ 00212 00213 /* If we are on an IA-32 machine, we can process directly. */ 00214 inline static void rs_mdfour_block(rs_mdfour_t *md, void const *p) 00215 { 00216 rs_mdfour64(md, p); 00217 } 00218 00219 # else /* !WORDS_BIGENDIAN && !__i386__ */ 00220 00221 /* We are little-endian, but not on i386 and therefore may not be able to do 00222 unaligned access safely/quickly. 00223 00224 So if the input is not already aligned correctly, copy it to an aligned 00225 buffer first. */ 00226 inline static void rs_mdfour_block(rs_mdfour_t *md, void const *p) 00227 { 00228 unsigned long ptrval = (unsigned long)p; 00229 00230 if (ptrval & 3) { 00231 uint32_t M[16]; 00232 00233 memcpy(M, p, 16 * sizeof(uint32_t)); 00234 rs_mdfour64(md, M); 00235 } else { 00236 rs_mdfour64(md, (const uint32_t *)p); 00237 } 00238 } 00239 00240 # endif /* !__i386__ */ 00241 #endif /* WORDS_BIGENDIAN */ 00242 00243 void rs_mdfour_begin(rs_mdfour_t *md) 00244 { 00245 memset(md, 0, sizeof(*md)); 00246 md->A = 0x67452301; 00247 md->B = 0xefcdab89; 00248 md->C = 0x98badcfe; 00249 md->D = 0x10325476; 00250 #if HAVE_UINT64 00251 md->totalN = 0; 00252 #else 00253 md->totalN_hi = md->totalN_lo = 0; 00254 #endif 00255 } 00256 00257 /** Handle special behaviour for processing the last block of a file when 00258 * calculating its MD4 checksum. 00259 * 00260 * This must be called exactly once per file. 00261 * 00262 * Modified by Robert Weber to use uint64 in order that we can sum files > 2^29 00263 * = 512 MB. --Robert.Weber@colorado.edu */ 00264 static void rs_mdfour_tail(rs_mdfour_t *m) 00265 { 00266 #ifdef HAVE_UINT64 00267 uint64_t b; 00268 #else /* HAVE_UINT64 */ 00269 uint32_t b[2]; 00270 #endif /* HAVE_UINT64 */ 00271 unsigned char buf[8]; 00272 size_t pad_len; 00273 00274 /* convert the totalN byte count into a bit count buffer */ 00275 #ifdef HAVE_UINT64 00276 b = m->totalN << 3; 00277 copy8(buf, b); 00278 #else /* HAVE_UINT64 */ 00279 b[0] = m->totalN_lo << 3; 00280 b[1] = ((m->totalN_hi << 3) | (m->totalN_lo >> 29)); 00281 copy4(buf, b[0]); 00282 copy4(buf + 4, b[1]); 00283 #endif /* HAVE_UINT64 */ 00284 00285 /* calculate length and process the padding data */ 00286 pad_len = (m->tail_len < 56) ? (56 - m->tail_len) : (120 - m->tail_len); 00287 rs_mdfour_update(m, PADDING, pad_len); 00288 /* process the bit count */ 00289 rs_mdfour_update(m, buf, 8); 00290 } 00291 00292 void rs_mdfour_update(rs_mdfour_t *md, void const *in_void, size_t n) 00293 { 00294 unsigned char const *in = (unsigned char const *)in_void; 00295 00296 /* increment totalN */ 00297 #ifdef HAVE_UINT64 00298 md->totalN += n; 00299 #else /* HAVE_UINT64 */ 00300 if ((md->totalN_lo += n) < n) 00301 md->totalN_hi++; 00302 #endif /* HAVE_UINT64 */ 00303 00304 /* If there's any leftover data in the tail buffer, then first we have to 00305 make it up to a whole block to process it. */ 00306 if (md->tail_len) { 00307 size_t tail_gap = 64 - md->tail_len; 00308 if (tail_gap <= n) { 00309 memcpy(&md->tail[md->tail_len], in, tail_gap); 00310 rs_mdfour_block(md, md->tail); 00311 in += tail_gap; 00312 n -= tail_gap; 00313 md->tail_len = 0; 00314 } 00315 } 00316 /* process complete blocks of input */ 00317 while (n >= 64) { 00318 rs_mdfour_block(md, in); 00319 in += 64; 00320 n -= 64; 00321 } 00322 /* Put remaining bytes onto tail */ 00323 if (n) { 00324 memcpy(&md->tail[md->tail_len], in, n); 00325 md->tail_len += n; 00326 } 00327 } 00328 00329 void rs_mdfour_result(rs_mdfour_t *md, unsigned char *out) 00330 { 00331 rs_mdfour_tail(md); 00332 00333 copy4(out, md->A); 00334 copy4(out + 4, md->B); 00335 copy4(out + 8, md->C); 00336 copy4(out + 12, md->D); 00337 } 00338 00339 void rs_mdfour(unsigned char *out, void const *in, size_t n) 00340 { 00341 rs_mdfour_t md; 00342 00343 rs_mdfour_begin(&md); 00344 rs_mdfour_update(&md, in, n); 00345 rs_mdfour_result(&md, out); 00346 }