1 /******************************************************************************* 2 copyright: Copyright (c) 2006 Tango. All rights reserved 3 4 license: BSD style: see doc/license.txt for details 5 6 version: Initial release: Feb 2006 7 8 author: Regan Heath, Oskar Linde 9 10 This module implements a generic Merkle-Damgard hash function 11 12 *******************************************************************************/ 13 14 module tango.util.digest.MerkleDamgard; 15 16 public import tango.core.ByteSwap; 17 18 public import tango.util.digest.Digest; 19 20 /******************************************************************************* 21 22 Extending MerkleDamgard to create a custom hash function requires 23 the implementation of a number of abstract methods. These include: 24 --- 25 public uint digestSize(); 26 protected void reset(); 27 protected void createDigest(ubyte[] buf); 28 protected uint blockSize(); 29 protected uint addSize(); 30 protected void padMessage(ubyte[] data); 31 protected void transform(ubyte[] data); 32 --- 33 34 In addition there exist two further abstract methods; these methods 35 have empty default implementations since in some cases they are not 36 required$(CLN) 37 --- 38 protected abstract void padLength(ubyte[] data, ulong length); 39 protected abstract void extend(); 40 --- 41 42 The method padLength() is required to implement the SHA series of 43 Hash functions and also the Tiger algorithm. Method extend() is 44 required only to implement the MD2 digest. 45 46 The basic sequence of internal events is as follows: 47 $(UL 48 $(LI transform(), 0 or more times) 49 $(LI padMessage()) 50 $(LI padLength()) 51 $(LI transform()) 52 $(LI extend()) 53 $(LI createDigest()) 54 $(LI reset()) 55 ) 56 57 *******************************************************************************/ 58 59 package class MerkleDamgard : Digest 60 { 61 private uint bytes; 62 private ubyte[] buffer; 63 64 /*********************************************************************** 65 66 Constructs the digest 67 68 Params: 69 buf = a buffer with enough space to hold the digest 70 71 Remarks: 72 Constructs the digest. 73 74 ***********************************************************************/ 75 76 protected abstract void createDigest(ubyte[] buf); 77 78 /*********************************************************************** 79 80 Digest block size 81 82 Returns: 83 the block size 84 85 Remarks: 86 Specifies the size (in bytes) of the block of data to pass to 87 each call to transform(). 88 89 ***********************************************************************/ 90 91 protected abstract uint blockSize(); 92 93 /*********************************************************************** 94 95 Length padding size 96 97 Returns: 98 the length padding size 99 100 Remarks: 101 Specifies the size (in bytes) of the padding which 102 uses the length of the data which has been fed to the 103 algorithm, this padding is carried out by the 104 padLength method. 105 106 ***********************************************************************/ 107 108 @property protected abstract uint addSize(); 109 110 /*********************************************************************** 111 112 Pads the digest data 113 114 Params: 115 data = a slice of the digest buffer to fill with padding 116 117 Remarks: 118 Fills the passed buffer slice with the appropriate 119 padding for the final call to transform(). This 120 padding will fill the message data buffer up to 121 blockSize()-addSize(). 122 123 ***********************************************************************/ 124 125 protected abstract void padMessage(ubyte[] data); 126 127 /*********************************************************************** 128 129 Performs the length padding 130 131 Params: 132 data = the slice of the digest buffer to fill with padding 133 length = the length of the data which has been processed 134 135 Remarks: 136 Fills the passed buffer slice with addSize() bytes of padding 137 based on the length in bytes of the input data which has been 138 processed. 139 140 ***********************************************************************/ 141 142 protected void padLength(ubyte[] data, ulong length) {} 143 144 /*********************************************************************** 145 146 Performs the digest on a block of data 147 148 Params: 149 data = the block of data to digest 150 151 Remarks: 152 The actual digest algorithm is carried out by this method on 153 the passed block of data. This method is called for every 154 blockSize() bytes of input data and once more with the remaining 155 data padded to blockSize(). 156 157 ***********************************************************************/ 158 159 protected abstract void transform(const(ubyte[]) data); 160 161 /*********************************************************************** 162 163 Final processing of digest. 164 165 Remarks: 166 This method is called after the final transform just prior to 167 the creation of the final digest. The MD2 algorithm requires 168 an additional step at this stage. Future digests may or may not 169 require this method. 170 171 ***********************************************************************/ 172 173 protected void extend() {} 174 175 /*********************************************************************** 176 177 Construct a digest 178 179 Remarks: 180 Constructs the internal buffer for use by the digest, the buffer 181 size (in bytes) is defined by the abstract method blockSize(). 182 183 ***********************************************************************/ 184 185 this() 186 { 187 buffer = new ubyte[blockSize()]; 188 reset(); 189 } 190 191 /*********************************************************************** 192 193 Initialize the digest 194 195 Remarks: 196 Returns the digest state to its initial value 197 198 ***********************************************************************/ 199 200 protected void reset() 201 { 202 bytes = 0; 203 } 204 205 /*********************************************************************** 206 207 Digest additional data 208 209 Params: 210 input = the data to digest 211 212 Remarks: 213 Continues the digest operation on the additional data. 214 215 ***********************************************************************/ 216 217 override MerkleDamgard update (const(void[]) input) 218 { 219 auto block = blockSize(); 220 uint i = bytes & (block-1); 221 const(ubyte[]) data = cast(const(ubyte[])) input; 222 223 bytes += data.length; 224 225 if (data.length+i < block) 226 buffer[i..i+data.length] = data[]; 227 else 228 { 229 buffer[i..block] = data[0..block-i]; 230 transform (buffer); 231 232 for (i=block-i; i+block-1 < data.length; i += block) 233 transform(data[i..i+block]); 234 235 buffer[0..data.length-i] = data[i..data.length]; 236 } 237 return this; 238 } 239 240 /*********************************************************************** 241 242 Complete the digest 243 244 Returns: 245 the completed digest 246 247 Remarks: 248 Concludes the algorithm producing the final digest. 249 250 ***********************************************************************/ 251 252 override ubyte[] binaryDigest (ubyte[] buf = null) 253 { 254 auto block = blockSize(); 255 uint i = bytes & (block-1); 256 257 if (i < block-addSize) 258 padMessage (buffer[i..block-addSize]); 259 else 260 { 261 padMessage (buffer[i..block]); 262 transform (buffer); 263 buffer[] = 0; 264 } 265 266 padLength (buffer[block-addSize..block], bytes); 267 transform (buffer); 268 269 extend (); 270 271 if (buf.length < digestSize()) 272 buf.length = digestSize(); 273 274 createDigest (buf); 275 276 reset (); 277 return buf; 278 } 279 280 /*********************************************************************** 281 282 Converts 8 bit to 32 bit Little Endian 283 284 Params: 285 input = the source array 286 output = the destination array 287 288 Remarks: 289 Converts an array of ubyte[] into uint[] in Little Endian byte order. 290 291 ***********************************************************************/ 292 293 static protected final void littleEndian32(const(ubyte[]) input, uint[] output) 294 { 295 assert(output.length == input.length/4); 296 output[] = (cast(uint[]) input)[]; 297 298 version (BigEndian) 299 ByteSwap.swap32 (output.ptr, output.length * uint.sizeof); 300 } 301 302 /*********************************************************************** 303 304 Converts 8 bit to 32 bit Big Endian 305 306 Params: 307 input = the source array 308 output = the destination array 309 310 Remarks: 311 Converts an array of ubyte[] into uint[] in Big Endian byte order. 312 313 ***********************************************************************/ 314 315 static protected final void bigEndian32(const(ubyte[]) input, uint[] output) 316 { 317 assert(output.length == input.length/4); 318 output[] = (cast(uint[]) input)[]; 319 320 version(LittleEndian) 321 ByteSwap.swap32 (output.ptr, output.length * uint.sizeof); 322 } 323 324 /*********************************************************************** 325 326 Converts 8 bit to 64 bit Little Endian 327 328 Params: 329 input = the source array 330 output = the destination array 331 332 Remarks: 333 Converts an array of ubyte[] into ulong[] in Little Endian byte order. 334 335 ***********************************************************************/ 336 337 static protected final void littleEndian64(const(ubyte[]) input, ulong[] output) 338 { 339 assert(output.length == input.length/8); 340 output[] = (cast(ulong[]) input)[]; 341 342 version (BigEndian) 343 ByteSwap.swap64 (output.ptr, output.length * ulong.sizeof); 344 } 345 346 /*********************************************************************** 347 348 Converts 8 bit to 64 bit Big Endian 349 350 Params: input = the source array 351 output = the destination array 352 353 Remarks: 354 Converts an array of ubyte[] into ulong[] in Big Endian byte order. 355 356 ***********************************************************************/ 357 358 static protected final void bigEndian64(const(ubyte[]) input, ulong[] output) 359 { 360 assert(output.length == input.length/8); 361 output[] = (cast(ulong[]) input)[]; 362 363 version (LittleEndian) 364 ByteSwap.swap64 (output.ptr, output.length * ulong.sizeof); 365 } 366 367 /*********************************************************************** 368 369 Rotate left by n 370 371 Params: 372 x = the value to rotate 373 n = the amount to rotate by 374 375 Remarks: 376 Rotates a 32 bit value by the specified amount. 377 378 ***********************************************************************/ 379 380 static protected final uint rotateLeft(uint x, uint n) 381 { 382 /+version (D_InlineAsm_X86) 383 version (DigitalMars) 384 { 385 asm { 386 naked; 387 mov ECX,EAX; 388 mov EAX,4[ESP]; 389 rol EAX,CL; 390 ret 4; 391 } 392 } 393 else 394 return (x << n) | (x >> (32-n)); 395 else +/ 396 return (x << n) | (x >> (32-n)); 397 } 398 } 399 400