$treeview $search $mathjax $extrastylesheet
librsync
2.3.0
$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 00025 * MD4 message digest algorithm. 00026 * 00027 * \todo Perhaps use the MD4 routine from OpenSSL if it's installed. It's 00028 * probably not worth the trouble. 00029 * 00030 * This was originally written by Andrew Tridgell for use in Samba. It was then 00031 * modified by; 00032 * 00033 * 2002-06-xx: Robert Weber <robert.weber@Colorado.edu> optimisations and fixed 00034 * >512M support. 00035 * 00036 * 2002-06-27: Donovan Baarda <abo@minkirri.apana.org.au> further optimisations 00037 * and cleanups. 00038 * 00039 * 2004-09-09: Simon Law <sfllaw@debian.org> handle little-endian machines that 00040 * can't do unaligned access (e.g. ia64, pa-risc). */ 00041 00042 #include "config.h" 00043 #include <stdlib.h> 00044 #include <stdint.h> 00045 #include <string.h> 00046 #include "librsync.h" 00047 #include "mdfour.h" 00048 00049 #define F(X,Y,Z) (((X)&(Y)) | ((~(X))&(Z))) 00050 #define G(X,Y,Z) (((X)&(Y)) | ((X)&(Z)) | ((Y)&(Z))) 00051 #define H(X,Y,Z) ((X)^(Y)^(Z)) 00052 #define lshift(x,s) (((x)<<(s)) | ((x)>>(32-(s)))) 00053 00054 #define ROUND1(a,b,c,d,k,s) a = lshift(a + F(b,c,d) + X[k], s) 00055 #define ROUND2(a,b,c,d,k,s) a = lshift(a + G(b,c,d) + X[k] + 0x5A827999,s) 00056 #define ROUND3(a,b,c,d,k,s) a = lshift(a + H(b,c,d) + X[k] + 0x6ED9EBA1,s) 00057 00058 /** padding data used for finalising */ 00059 static unsigned char PADDING[64] = { 00060 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00061 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00062 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 00063 }; 00064 00065 static void rs_mdfour_block(rs_mdfour_t *md, void const *p); 00066 00067 /** Update an MD4 accumulator from a 64-byte chunk. 00068 * 00069 * This cannot be used for the last chunk of the file, which must be padded and 00070 * contain the file length. rs_mdfour_tail() is used for that. 00071 * 00072 * \todo Recode to be fast, and to use system integer types. Perhaps if we can 00073 * find an mdfour implementation already on the system (e.g. in OpenSSL) then 00074 * we should use it instead of our own? 00075 * 00076 * \param *m An rs_mdfour_t instance to accumulate with. 00077 * 00078 * \param *p An array of uint32 integers, as 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 UINT64_MAX 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 /* UINT64_MAX */ 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 if ((uintptr_t)p & 3) { 00229 uint32_t M[16]; 00230 00231 memcpy(M, p, 16 * sizeof(uint32_t)); 00232 rs_mdfour64(md, M); 00233 } else { 00234 rs_mdfour64(md, (const uint32_t *)p); 00235 } 00236 } 00237 00238 # endif /* !__i386__ */ 00239 #endif /* WORDS_BIGENDIAN */ 00240 00241 void rs_mdfour_begin(rs_mdfour_t *md) 00242 { 00243 memset(md, 0, sizeof(*md)); 00244 md->A = 0x67452301; 00245 md->B = 0xefcdab89; 00246 md->C = 0x98badcfe; 00247 md->D = 0x10325476; 00248 #ifdef UINT64_MAX 00249 md->totalN = 0; 00250 #else 00251 md->totalN_hi = md->totalN_lo = 0; 00252 #endif 00253 } 00254 00255 /** Handle special behaviour for processing the last block of a file when 00256 * calculating its MD4 checksum. 00257 * 00258 * This must be called exactly once per file. 00259 * 00260 * Modified by Robert Weber to use uint64 in order that we can sum files > 2^29 00261 * = 512 MB. --Robert.Weber@colorado.edu */ 00262 static void rs_mdfour_tail(rs_mdfour_t *m) 00263 { 00264 #ifdef UINT64_MAX 00265 uint64_t b; 00266 #else /* UINT64_MAX */ 00267 uint32_t b[2]; 00268 #endif /* UINT64_MAX */ 00269 unsigned char buf[8]; 00270 size_t pad_len; 00271 00272 /* convert the totalN byte count into a bit count buffer */ 00273 #ifdef UINT64_MAX 00274 b = m->totalN << 3; 00275 copy8(buf, b); 00276 #else /* UINT64_MAX */ 00277 b[0] = m->totalN_lo << 3; 00278 b[1] = ((m->totalN_hi << 3) | (m->totalN_lo >> 29)); 00279 copy4(buf, b[0]); 00280 copy4(buf + 4, b[1]); 00281 #endif /* UINT64_MAX */ 00282 00283 /* calculate length and process the padding data */ 00284 pad_len = (m->tail_len < 56) ? (56 - m->tail_len) : (120 - m->tail_len); 00285 rs_mdfour_update(m, PADDING, pad_len); 00286 /* process the bit count */ 00287 rs_mdfour_update(m, buf, 8); 00288 } 00289 00290 void rs_mdfour_update(rs_mdfour_t *md, void const *in_void, size_t n) 00291 { 00292 unsigned char const *in = (unsigned char const *)in_void; 00293 00294 /* increment totalN */ 00295 #ifdef UINT64_MAX 00296 md->totalN += n; 00297 #else /* UINT64_MAX */ 00298 if ((md->totalN_lo += n) < n) 00299 md->totalN_hi++; 00300 #endif /* UINT64_MAX */ 00301 00302 /* If there's any leftover data in the tail buffer, then first we have to 00303 make it up to a whole block to process it. */ 00304 if (md->tail_len) { 00305 size_t tail_gap = 64 - md->tail_len; 00306 if (tail_gap <= n) { 00307 memcpy(&md->tail[md->tail_len], in, tail_gap); 00308 rs_mdfour_block(md, md->tail); 00309 in += tail_gap; 00310 n -= tail_gap; 00311 md->tail_len = 0; 00312 } 00313 } 00314 /* process complete blocks of input */ 00315 while (n >= 64) { 00316 rs_mdfour_block(md, in); 00317 in += 64; 00318 n -= 64; 00319 } 00320 /* Put remaining bytes onto tail */ 00321 if (n) { 00322 memcpy(&md->tail[md->tail_len], in, n); 00323 md->tail_len += n; 00324 } 00325 } 00326 00327 void rs_mdfour_result(rs_mdfour_t *md, unsigned char *out) 00328 { 00329 rs_mdfour_tail(md); 00330 00331 copy4(out, md->A); 00332 copy4(out + 4, md->B); 00333 copy4(out + 8, md->C); 00334 copy4(out + 12, md->D); 00335 } 00336 00337 void rs_mdfour(unsigned char *out, void const *in, size_t n) 00338 { 00339 rs_mdfour_t md; 00340 00341 rs_mdfour_begin(&md); 00342 rs_mdfour_update(&md, in, n); 00343 rs_mdfour_result(&md, out); 00344 }