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