E-MailRelay
gmd5.cpp
1 //
2 // Copyright (C) 2001-2018 Graeme Walker <graeme_walker@users.sourceforge.net>
3 //
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 // ===
17 //
18 // gmd5.cpp
19 //
20 
21 #include "gdef.h"
22 #include "gmd5.h"
23 #include "ghashstate.h"
24 #include "gassert.h"
25 #include <string> // std::string
26 #include <cstdlib> // std::size_t
27 
28 namespace md5
29 {
30  typedef G::Md5::digest_state digest_state ;
31  typedef G::Md5::small_t small_t ;
32  typedef G::Md5::big_t big_t ;
33  class digest ;
34  class format ;
35  class block ;
36 }
37 
38 /// \class md5::digest
39 /// A class that calculates an md5 digest from one or more 64-byte blocks of
40 /// data using the algorithm described by RFC-1321.
41 ///
42 /// A digest can be calculated in one go from an arbitrarily-sized block of
43 /// data, or incrementally from a series of 64-byte blocks. The 64-byte
44 /// blocks must be passed as md5::block objects.
45 ///
47 {
48 public:
49  digest() ;
50  // Default constructor. The message to be digested
51  // should be add()ed in 64-byte blocks.
52 
53  explicit digest( const std::string & s ) ;
54  // Constuctor. Calculates a digest for the given
55  // message string. Do not use add() with this
56  // constructor.
57 
58  explicit digest( digest_state ) ;
59  // Constructor taking the result of an earlier call
60  // to state(). This allows calculation of a digest
61  // from a stream of 64-byte blocks to be suspended
62  // mid-stream and then resumed using a new digest
63  // object.
64 
65  digest_state state() const ;
66  // Returns the internal state. Typically passed to
67  // the md5::format class.
68 
69  void add( const block & ) ;
70  // Adds a 64-byte block of the message.
71 
72 private:
73  typedef big_t (*aux_fn_t)( big_t , big_t , big_t ) ;
74  enum Permutation { ABCD , DABC , CDAB , BCDA } ;
75 
76 private:
77  explicit digest( const block & ) ;
78  void add( const digest & ) ;
79  void init() ;
80  void calculate( const block & ) ;
81  static big_t T( small_t i ) ;
82  static big_t rot32( small_t places , big_t n ) ;
83  void operator()( const block & , aux_fn_t , Permutation , small_t , small_t , small_t ) ;
84  static big_t op( const block & , aux_fn_t , big_t , big_t , big_t , big_t , small_t , small_t , small_t ) ;
85  void round1( const block & ) ;
86  void round2( const block & ) ;
87  void round3( const block & ) ;
88  void round4( const block & ) ;
89  static big_t F( big_t x , big_t y , big_t z ) ;
90  static big_t G( big_t x , big_t y , big_t z ) ;
91  static big_t H( big_t x , big_t y , big_t z ) ;
92  static big_t I( big_t x , big_t y , big_t z ) ;
93 } ;
94 
95 /// \class md5::format
96 /// A thin veneer over G::HashState.
97 ///
99 {
100 public:
101  static std::string encode( const digest_state & ) ;
102  // Returns the digest state as a string typically
103  // containing non-printing characters.
104 
105  static std::string encode( const digest_state & , big_t n ) ;
106  // Returns the digest state and a stream-size
107  // in the encode() format.
108 
109  static digest_state decode( const std::string & , small_t & ) ;
110  // Converts a encode() string back into a digest
111  // state and a stream-size.
112 
113 private:
114  format() ; // not implemented
115 } ;
116 
117 /// \class md5::block
118 /// A helper class used by the md5::digest implementation to represent a
119 /// 64-character data block.
120 ///
122 {
123 public:
124  block( const std::string & s , small_t block_offset , big_t end_value ) ;
125  // Constructor. Unusually, the string reference is
126  // kept, so beware of binding temporaries.
127  //
128  // The 'block-offset' indicates, in units of 64-character
129  // blocks, how far down 's' the current block's data is.
130  //
131  // The string must hold at least 64 bytes beyond the
132  // 'block-offset' point, except for the last block in
133  // a message sequence. Note that this is the number
134  // of blocks, not the number of bytes.
135  //
136  // The 'end-value' is derived from the length of the
137  // full message (not just the current block). It is only
138  // used for the last block. See end().
139 
140  static big_t end( small_t data_length ) ;
141  // Takes the total number of bytes in the input message and
142  // returns a value which can be passed to the constructor's
143  // third parameter. This is used for the last block in
144  // the sequence of blocks that make up a complete message.
145 
146  static small_t blocks( small_t data_length ) ;
147  // Takes the total number of bytes in the input message and
148  // returns the number of 64-byte blocks, allowing for
149  // padding. In practice 0..55 maps to 1, 56..119 maps to
150  // 2, etc.
151 
152  big_t X( small_t ) const ;
153  // Returns a value from within the block. See RFC-1321.
154 
155 private:
156  block( const block & ) ; // not implemented
157  void operator=( const block & ) ; // not implemented
158  small_t x( small_t ) const ;
159  static small_t rounded( small_t n ) ;
160 
161 private:
162  const std::string & m_s ;
163  small_t m_block ;
164  big_t m_end_value ;
165 } ;
166 
167 // ==
168 
169 md5::digest::digest()
170 {
171  init() ;
172 }
173 
174 md5::digest::digest( const std::string & s )
175 {
176  init() ;
177  small_t n = block::blocks( s.length() ) ;
178  for( small_t i = 0U ; i < n ; ++i )
179  {
180  block blk( s , i , block::end(s.length()) ) ;
181  add( blk ) ;
182  }
183 }
184 
185 md5::digest::digest( digest_state d_in )
186 {
187  a = d_in.a ;
188  b = d_in.b ;
189  c = d_in.c ;
190  d = d_in.d ;
191 }
192 
193 void md5::digest::init()
194 {
195  a = 0x67452301UL ;
196  b = 0xefcdab89UL ;
197  c = 0x98badcfeUL ;
198  d = 0x10325476UL ;
199 }
200 
201 md5::digest::digest_state md5::digest::state() const
202 {
203  big_t mask = 0 ;
204  small_t thirty_two = 32U ;
205  small_t sizeof_thirty_two_bits = 4U ; // 4x8=32
206  if( sizeof(mask) > sizeof_thirty_two_bits )
207  {
208  mask = ~0U ;
209  mask <<= thirty_two ; // ignore warnings here
210  }
211  digest_state result = { a & ~mask , b & ~mask , c & ~mask , d & ~mask } ;
212  return result ;
213 }
214 
215 void md5::digest::add( const block & blk )
216 {
217  digest old( *this ) ;
218  round1( blk ) ;
219  round2( blk ) ;
220  round3( blk ) ;
221  round4( blk ) ;
222  add( old ) ;
223 }
224 
225 void md5::digest::add( const digest & other )
226 {
227  a += other.a ;
228  b += other.b ;
229  c += other.c ;
230  d += other.d ;
231 }
232 
233 void md5::digest::round1( const block & m )
234 {
235  digest & r = *this ;
236  r(m,F,ABCD, 0, 7, 1); r(m,F,DABC, 1,12, 2); r(m,F,CDAB, 2,17, 3); r(m,F,BCDA, 3,22, 4);
237  r(m,F,ABCD, 4, 7, 5); r(m,F,DABC, 5,12, 6); r(m,F,CDAB, 6,17, 7); r(m,F,BCDA, 7,22, 8);
238  r(m,F,ABCD, 8, 7, 9); r(m,F,DABC, 9,12,10); r(m,F,CDAB,10,17,11); r(m,F,BCDA,11,22,12);
239  r(m,F,ABCD,12, 7,13); r(m,F,DABC,13,12,14); r(m,F,CDAB,14,17,15); r(m,F,BCDA,15,22,16);
240 }
241 
242 void md5::digest::round2( const block & m )
243 {
244  digest & r = *this ;
245  r(m,G,ABCD, 1, 5,17); r(m,G,DABC, 6, 9,18); r(m,G,CDAB,11,14,19); r(m,G,BCDA, 0,20,20);
246  r(m,G,ABCD, 5, 5,21); r(m,G,DABC,10, 9,22); r(m,G,CDAB,15,14,23); r(m,G,BCDA, 4,20,24);
247  r(m,G,ABCD, 9, 5,25); r(m,G,DABC,14, 9,26); r(m,G,CDAB, 3,14,27); r(m,G,BCDA, 8,20,28);
248  r(m,G,ABCD,13, 5,29); r(m,G,DABC, 2, 9,30); r(m,G,CDAB, 7,14,31); r(m,G,BCDA,12,20,32);
249 }
250 
251 void md5::digest::round3( const block & m )
252 {
253  digest & r = *this ;
254  r(m,H,ABCD, 5, 4,33); r(m,H,DABC, 8,11,34); r(m,H,CDAB,11,16,35); r(m,H,BCDA,14,23,36);
255  r(m,H,ABCD, 1, 4,37); r(m,H,DABC, 4,11,38); r(m,H,CDAB, 7,16,39); r(m,H,BCDA,10,23,40);
256  r(m,H,ABCD,13, 4,41); r(m,H,DABC, 0,11,42); r(m,H,CDAB, 3,16,43); r(m,H,BCDA, 6,23,44);
257  r(m,H,ABCD, 9, 4,45); r(m,H,DABC,12,11,46); r(m,H,CDAB,15,16,47); r(m,H,BCDA, 2,23,48);
258 }
259 
260 void md5::digest::round4( const block & m )
261 {
262  digest & r = *this ;
263  r(m,I,ABCD, 0, 6,49); r(m,I,DABC, 7,10,50); r(m,I,CDAB,14,15,51); r(m,I,BCDA, 5,21,52);
264  r(m,I,ABCD,12, 6,53); r(m,I,DABC, 3,10,54); r(m,I,CDAB,10,15,55); r(m,I,BCDA, 1,21,56);
265  r(m,I,ABCD, 8, 6,57); r(m,I,DABC,15,10,58); r(m,I,CDAB, 6,15,59); r(m,I,BCDA,13,21,60);
266  r(m,I,ABCD, 4, 6,61); r(m,I,DABC,11,10,62); r(m,I,CDAB, 2,15,63); r(m,I,BCDA, 9,21,64);
267 }
268 
269 void md5::digest::operator()( const block & m , aux_fn_t aux , Permutation p , small_t k , small_t s , small_t i )
270 {
271  if( p == ABCD ) a = op( m , aux , a , b , c , d , k , s , i ) ;
272  if( p == DABC ) d = op( m , aux , d , a , b , c , k , s , i ) ;
273  if( p == CDAB ) c = op( m , aux , c , d , a , b , k , s , i ) ;
274  if( p == BCDA ) b = op( m , aux , b , c , d , a , k , s , i ) ;
275 }
276 
277 md5::big_t md5::digest::op( const block & m , aux_fn_t aux , big_t a , big_t b , big_t c , big_t d ,
278  small_t k , small_t s , small_t i )
279 {
280  return b + rot32( s , ( a + (*aux)( b , c , d ) + m.X(k) + T(i) ) ) ;
281 }
282 
283 md5::big_t md5::digest::rot32( small_t places , big_t n )
284 {
285  // circular rotate of 32 LSBs, with corruption of higher bits
286  big_t overflow_mask = ( 1UL << places ) - 1UL ; // in case big_t is more than 32 bits
287  big_t overflow = ( n >> ( 32U - places ) ) ;
288  return ( n << places ) | ( overflow & overflow_mask ) ;
289 }
290 
291 md5::big_t md5::digest::F( big_t x , big_t y , big_t z )
292 {
293  return ( x & y ) | ( ~x & z ) ;
294 }
295 
296 md5::big_t md5::digest::G( big_t x , big_t y , big_t z )
297 {
298  return ( x & z ) | ( y & ~z ) ;
299 }
300 
301 md5::big_t md5::digest::H( big_t x , big_t y , big_t z )
302 {
303  return x ^ y ^ z ;
304 }
305 
306 md5::big_t md5::digest::I( big_t x , big_t y , big_t z )
307 {
308  return y ^ ( x | ~z ) ;
309 }
310 
311 md5::big_t md5::digest::T( small_t i )
312 {
313  // T = static_cast<big_t>( 4294967296.0 * std::fabs(std::sin(static_cast<double>(i))) ) for 1 <= i <= 64
314  //
315  static big_t t_map[] =
316  {
317  0xd76aa478UL ,
318  0xe8c7b756UL ,
319  0x242070dbUL ,
320  0xc1bdceeeUL ,
321  0xf57c0fafUL ,
322  0x4787c62aUL ,
323  0xa8304613UL ,
324  0xfd469501UL ,
325  0x698098d8UL ,
326  0x8b44f7afUL ,
327  0xffff5bb1UL ,
328  0x895cd7beUL ,
329  0x6b901122UL ,
330  0xfd987193UL ,
331  0xa679438eUL ,
332  0x49b40821UL ,
333  0xf61e2562UL ,
334  0xc040b340UL ,
335  0x265e5a51UL ,
336  0xe9b6c7aaUL ,
337  0xd62f105dUL ,
338  0x02441453UL ,
339  0xd8a1e681UL ,
340  0xe7d3fbc8UL ,
341  0x21e1cde6UL ,
342  0xc33707d6UL ,
343  0xf4d50d87UL ,
344  0x455a14edUL ,
345  0xa9e3e905UL ,
346  0xfcefa3f8UL ,
347  0x676f02d9UL ,
348  0x8d2a4c8aUL ,
349  0xfffa3942UL ,
350  0x8771f681UL ,
351  0x6d9d6122UL ,
352  0xfde5380cUL ,
353  0xa4beea44UL ,
354  0x4bdecfa9UL ,
355  0xf6bb4b60UL ,
356  0xbebfbc70UL ,
357  0x289b7ec6UL ,
358  0xeaa127faUL ,
359  0xd4ef3085UL ,
360  0x04881d05UL ,
361  0xd9d4d039UL ,
362  0xe6db99e5UL ,
363  0x1fa27cf8UL ,
364  0xc4ac5665UL ,
365  0xf4292244UL ,
366  0x432aff97UL ,
367  0xab9423a7UL ,
368  0xfc93a039UL ,
369  0x655b59c3UL ,
370  0x8f0ccc92UL ,
371  0xffeff47dUL ,
372  0x85845dd1UL ,
373  0x6fa87e4fUL ,
374  0xfe2ce6e0UL ,
375  0xa3014314UL ,
376  0x4e0811a1UL ,
377  0xf7537e82UL ,
378  0xbd3af235UL ,
379  0x2ad7d2bbUL ,
380  0xeb86d391UL } ;
381  return t_map[i-1UL] ;
382 }
383 
384 // ===
385 
386 std::string md5::format::encode( const digest_state & state )
387 {
388  const big_t state_array[] = { state.a , state.b , state.c , state.d } ;
389  return G::HashState<16,big_t,small_t>::encode( state_array ) ;
390 }
391 
392 std::string md5::format::encode( const digest_state & state , big_t n )
393 {
394  const big_t state_array[] = { state.a , state.b , state.c , state.d } ;
395  return G::HashState<16,big_t,small_t>::encode( state_array , n ) ;
396 }
397 
398 md5::digest_state md5::format::decode( const std::string & str , small_t & n )
399 {
400  big_t state_array[] = { 0 , 0 , 0 , 0 } ;
401  G::HashState<16,big_t,small_t>::decode( str , state_array , n ) ;
402  digest_state result ;
403  result.a = state_array[0] ;
404  result.b = state_array[1] ;
405  result.c = state_array[2] ;
406  result.d = state_array[3] ;
407  return result ;
408 }
409 
410 // ===
411 
412 md5::block::block( const std::string & s , small_t block , big_t end_value ) :
413  m_s(s) ,
414  m_block(block) ,
415  m_end_value(end_value)
416 {
417 }
418 
419 md5::big_t md5::block::end( small_t length )
420 {
421  big_t result = length ;
422  result *= 8UL ;
423  return result ;
424 }
425 
426 md5::small_t md5::block::rounded( small_t raw_byte_count )
427 {
428  small_t n = raw_byte_count + 64U ;
429  return n - ( ( raw_byte_count + 8U ) % 64U ) ;
430 }
431 
432 md5::small_t md5::block::blocks( small_t raw_byte_count )
433 {
434  small_t byte_count = rounded(raw_byte_count) + 8U ;
435  return byte_count / 64UL ;
436 }
437 
438 md5::big_t md5::block::X( small_t dword_index ) const
439 {
440  small_t byte_index = ( m_block * 64U ) + ( dword_index * 4U ) ;
441  big_t result = x( byte_index + 3U ) ;
442  result <<= 8U ; result += x( byte_index + 2U ) ;
443  result <<= 8U ; result += x( byte_index + 1U ) ;
444  result <<= 8U ; result += x( byte_index + 0U ) ;
445  return result ;
446 }
447 
448 md5::small_t md5::block::x( small_t i ) const
449 {
450  small_t length = m_s.length() ;
451  if( i < length )
452  {
453  return static_cast<unsigned char>(m_s[i]) ;
454  }
455  else if( i < rounded(length) )
456  {
457  return i == length ? 128U : 0U ;
458  }
459  else
460  {
461  small_t byte_shift = i - rounded(length) ;
462  if( byte_shift >= sizeof(big_t) )
463  {
464  return 0U ;
465  }
466  else
467  {
468  small_t bit_shift = byte_shift * 8U ;
469 
470  big_t end_value = m_end_value >> bit_shift ;
471  return static_cast<small_t>( end_value & 0xffUL ) ;
472  }
473  }
474 }
475 
476 // ==
477 
479  m_n(0U)
480 {
481  md5::digest dd ;
482  m_d = dd.state() ;
483 }
484 
485 G::Md5::Md5( const std::string & str_state )
486 {
487  G_ASSERT( str_state.size() == (valuesize()+4U) ) ;
488  m_d = md5::format::decode( str_state , m_n ) ;
489 }
490 
491 std::string G::Md5::state() const
492 {
493  G_ASSERT( md5::format::encode(m_d,m_n).size() == (valuesize()+4U) ) ;
494  return md5::format::encode( m_d , m_n ) ;
495 }
496 
497 void G::Md5::add( const std::string & data )
498 {
499  // add complete blocks and keep the residue in m_s
500  md5::digest dd( m_d ) ;
501  m_s.append( data ) ; // could do better
502  m_n += data.length() ;
503  while( m_s.length() >= 64U )
504  {
505  md5::block blk( m_s , 0U , 0UL ) ;
506  dd.add( blk ) ;
507  m_s.erase( 0U , 64U ) ;
508  }
509  m_d = dd.state() ;
510 }
511 
512 std::string G::Md5::value()
513 {
514  md5::digest dd( m_d ) ;
515  md5::block blk( m_s , 0U , md5::block::end(m_n) ) ;
516  dd.add( blk ) ;
517  m_s.erase() ;
518  m_d = dd.state() ;
519  return md5::format::encode( m_d ) ;
520 }
521 
522 std::string G::Md5::digest( const std::string & input )
523 {
524  md5::digest dd( input ) ;
525  return md5::format::encode( dd.state() ) ;
526 }
527 
528 std::string G::Md5::digest( const std::string & input_1 , const std::string & input_2 )
529 {
530  G::Md5 x ;
531  x.add( input_1 ) ;
532  x.add( input_2 ) ;
533  return x.value() ;
534 }
535 
536 std::string G::Md5::digest2( const std::string & input_1 , const std::string & input_2 )
537 {
538  return digest( input_1 , input_2 ) ;
539 }
540 
541 std::string G::Md5::predigest( const std::string & input )
542 {
543  G::Md5 x ;
544  x.add( input ) ;
545  G_ASSERT( input.size() == blocksize() ) ;
546  return x.state().substr(0U,valuesize()) ; // strip off the size; added back in postdigest()
547 }
548 
549 std::string G::Md5::postdigest( const std::string & state_pair , const std::string & message )
550 {
551  std::string _64( "\x40\0\0\0" , 4U ) ; // state size suffix
552  std::string state_i = state_pair.substr( 0U , state_pair.size()/2 ) + _64 ;
553  std::string state_o = state_pair.substr( state_pair.size()/2 ) + _64 ;
554 
555  G::Md5 xi( state_i ) ;
556  xi.add( message ) ;
557 
558  G::Md5 xo( state_o ) ;
559  xo.add( xi.value() ) ;
560 
561  return xo.value() ;
562 }
563 
565 {
566  return 64U ;
567 }
568 
570 {
571  return 16U ;
572 }
573 
575 {
576  return 20U ;
577 }
578 
std::string state() const
Returns the current intermediate state as a 20 character string, although this requires the size of t...
Definition: gmd5.cpp:491
void add(const std::string &data)
Adds more data.
Definition: gmd5.cpp:497
static size_t blocksize()
Returns the block size in bytes (64).
Definition: gmd5.cpp:564
static void decode(const std::string &, uint_type *, size_type &)
Converts an encode()d string back into a hash state of N integers and a data size returned by referen...
Definition: ghashstate.h:91
Md5()
Default constructor.
Definition: gmd5.cpp:478
Low-level classes.
Definition: garg.h:29
A helper class used by the md5::digest implementation to represent a 64-character data block...
Definition: gmd5.cpp:121
A thin veneer over G::HashState.
Definition: gmd5.cpp:98
std::string value()
Returns the hash value as a 16-character string.
Definition: gmd5.cpp:512
static std::string postdigest(const std::string &state_pair, const std::string &message)
A convenience function that returns the value() from an outer digest that is initialised with the sec...
Definition: gmd5.cpp:549
A class that calculates an md5 digest from one or more 64-byte blocks of data using the algorithm des...
Definition: gmd5.cpp:46
static std::string digest(const std::string &input)
A convenience function that returns a digest from one input.
Definition: gmd5.cpp:522
Definition: gmd5.cpp:28
static std::string predigest(const std::string &padded_key)
A convenience function that add()s the given string of length blocksize() (typically a padded key) an...
Definition: gmd5.cpp:541
static size_t valuesize()
Returns the value() size in bytes (16).
Definition: gmd5.cpp:569
static std::string encode(const uint_type *)
Returns the hash state as a string, typically containing non-printing characters. ...
Definition: ghashstate.h:68
static size_t statesize()
Returns the size of the state() string (20).
Definition: gmd5.cpp:574
static std::string digest2(const std::string &input_1, const std::string &input_2)
A non-overloaded name for the digest() overload taking two parameters.
Definition: gmd5.cpp:536
MD5 message digest class.
Definition: gmd5.h:48
Holds the four parts of the md5 state.
Definition: gmd5.h:54