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