=======================				Revision 2014-11-28
MARSCHALL HASH 2 (MHA2)				Daniel Marschall, ViaThinkSoft
=======================				Public

Usage
=====

	MHA2 is a method to strengten a weak hash function, e.g. in case that
	the development environment or hardware does not allow using a new
	implementation of a modern hash variant like SHA256 or SHA3.

Definition
==========

	MHA2(i,s,x) := A(i,s,x) xor B(i,s,x) xor C(i,s,x)

	with:
		A(j,s,x) := j>=0: H(P & A(j-1, s, x) & x & s & Q)
		            j=-1: ''

		B(j,s,x) := j<=0: H(Q & s & x & B(j-1, s, x) & P)
		            j=-1: ''

		C(j,s,x) := H( (K&x&s)*(j+1) )

		K := 0x24 & 0x12 & 0x19 & 0x87
		P := 0x12 & 0x24 & 0x19 & 0x87
		Q := 0x19 & 0x87 & 0x12 & 0x24

	where:

		i is the number of iterations, i <= 0.
		j is a number <= -1 .

		s is the salt.

		x is the input data.

		0xd is a single byte with the hexadecimal value d.

		H(z) is an existing hash function.

		All hash operations have a binary output; no string conversation is done.

		x*z are z repetitions (concatenations) of x.

		& is concatenation.

Examples
========

	- MHA2(1, '', x) = H(P & H(P&x&Q) & x & Q) xor H(Q & x & H(Q&x&P) & P) xor H(K&x&s & K&x&s)

	- MHA2(1,  s, x) = H(P & H(P&x&s&Q) & x & s & Q) xor H(Q & s & x & H(Q&s&x&P) & P) xor H(K&x&s & K&x&s)

Security considerations
=======================

	- The output length of MHA2(i, s, x) is equal to the output length of H(z)

	- MHA2(i, '', s & x) != MHA2(i, s, x) != MHA2(i, '', x & s)

	- It is recommended not to use i=0.

	- P, Q and K are chosen to arbitary data . It can be chosen to a different value, but should not be empty.

	- P should never be equal to Q, otherwise, A(i,s,x) could become equal to B(i,s,x).
		Possible "optimizations" (vulnerabilities) can be done if P&Q = Q&P:
			a) If i = 0 and s&x = x&s:
			   => A(0, s, x) = B(0, s, x)
			   => MHA2(0, s, x) = H(K&x&s)
			b) If s&x='' (s='' and x=''):
			   => A(i, '', '') = B(i, '', '')
			   => MHA2(i, '', '') = H('')
			c) If z := s&x = x&s:
			   => H(s&x) = H(x&s) = H(z)
			   => H(s&x) = A(0,s,x) = H(z) = B(0,s,x) = H(P&x&s&Q) = H(Q&s&x&P)
			   => in A(i,s,x) and B(i,s,x), this embedded value H(z) has to be calculated only once.

		Note: s&x = x&s is true if one of the following conditions is true:
			x = '' or
			s = '' or
			x = s

	- If H(x) is compromised, MHA2 (even unsalted) would be still safe.
	  Examples:
		i = 0, unsalted (s=''):
		H(P&x&Q) = H(P&y&Q) = c
			=> MHA2(0, '', x) = c xor c xor H(K&x) = c xor c xor H(K&y) = MHA2(0, '', y)
			=> H(K&x) ?= H(K&y)

		i = 1, unsalted (s=''):
		H(P&x&Q) = H(P&y&Q) = c
			=> MHA2(1, '', x) = H(P&c&x&Q) xor H(Q&x&c&P) xor H(K&x&K&x) = H(P&c&y&Q) xor H(Q&y&c&P) xor H(K&y&K&y) = MHA2(1, '', y)
			=> H(P&c&x&Q) xor H(Q&x&c&P) xor H(K&x&K&x) ?= H(P&c&y&Q) xor H(Q&y&c&P) xor H(K&y&K&y)

		i = 2, unsalted (s=''):
		H(P&x&Q) = H(P&y&Q) = c
			=> MHA2(2, '', x) = H(P&H(P&c&x&Q)&x&Q) xor H(Q&x&H(Q&x&c&P)&P) xor H(K&x&K&x&K&x) = H(P&H(P&c&y&Q)&y&Q) xor H(&Qx&H(&Qy&c&P)&P) xor H(K&y&K&y&K&y) = MHA2(2, '', y)
			=> H(P&H(P&c&x&Q)&x&Q) xor H(Q&x&H(Q&x&c&P)&P) xor H(K&x&K&x&K&x) ?= H(P&H(P&c&y&Q)&y&Q) xor H(Q&x&H(Q&y&c&P)&P) xor H(K&y&K&y&K&y)

	- If a high value for i is chosen, the hash will be slow.
	  Therefore, the creation of a rainbow table or brute force attacks will be slow (see runtime section).
	  On the other hand, a brute force attack could result in a DoS if the CPU of the server is too weak.

	- The salt should always be set.
	  The salt should be a merge of an individual (random unique) user-specific salt, a service-specific salt and server-specific salt.
		s = userSalt & serviceSalt & serverSalt

	- For the third xor argument "xor C(i,s,x)" is not required, but does probably strengten the algorithm in case that
	  an attack can be found where A(i,s,x) = B(i,s,x) can be enforced.

Runtime complexity
==================

	The following table will show the required executions of the
	hash function H(z) on given number of differnt i values:

	------------------
	i	H(z)-calls
	------------------
	0	3
	1	5
	2	7
	3	9
	n	2n+3
	------------------

Naming convention
=================

	Naming proposal for documentations
	----------------------------------

	If you want to describe the algorithm used in a documentation, you can use following simplified notation:

	MHA2-SHA1-1987-salted
	^    ^    ^    ^
	|    |    |    |
	|    |    |    +------ salted (s!='') or unsalted (s='')
	|    |    +----------- number of iterations (i)
	|    +---------------- base hash function H(z)
	+--------------------- MHA2 algorithm


	Hash storage in heterogenous systems
	------------------------------------

	If a hash is stored together with other hashes of different algorithms (e.g. in a .htpasswd file)
	or transfered between heterogenous systems, it is recommended to
	store the hash in following notation:

	<mha2-oid>$<base-hash>$<iterations>$<salt-base64>$<hash-base64>

	-  <mha2-oid> is the OID for a MHA2 algorithm in its dot-notation without leading dot,
	   which is 1.3.6.1.4.1.37476.3.2.1.2

	   This OID has ASN.1 Notation:
	   { iso(1) identified-organization(3) dod(6) internet(1) private(4) enterprise(1)
	     37476 specification(3) algorithm(2) hash(1) mha2-family(2) }

	-  <base-hash> should be an OID which represents the base hash ("H") algorithm used.

	   The following table shows the OIDs which have been assigned
	   for exchange between heterogenous systems. If you want to use a different
	   hash algorithm or a derivate of it, please define your own OID
	   (you can use an UUID OID, get a free IANA PEN OID, or a free ViaThinkSoft OID),
	   but please do not use this arc, since only ViaThinkSoft may maintain it.

	   --------------------------------------------------------------------------------------------
	   Algorithm                                  OID proposal
	   --------------------------------------------------------------------------------------------
	   Message Digest 4 (MD4)                     { 1 3 6 1 4 1 37476 3 2 1 99 md4(1) }
	   Message Digest 5 (MD5)                     { 1 3 6 1 4 1 37476 3 2 1 99 md5(2) }
	   RIPEMD-160                                 { 1 3 6 1 4 1 37476 3 2 1 99 ripemd160(3) }
	   Secure Hash Algorithm                      { 1 3 6 1 4 1 37476 3 2 1 99 sha0(4) }
	   Secure Hash Algorithm 1                    { 1 3 6 1 4 1 37476 3 2 1 99 sha1(5) }
	   Secure Hash Algorithm 2 (224 bits)         { 1 3 6 1 4 1 37476 3 2 1 99 sha2(6) 224 }
	   Secure Hash Algorithm 2 (256 bits)         { 1 3 6 1 4 1 37476 3 2 1 99 sha2(6) 256 }
	   Secure Hash Algorithm 2 (384 bits)         { 1 3 6 1 4 1 37476 3 2 1 99 sha2(6) 384 }
	   Secure Hash Algorithm 2 (512 bits)         { 1 3 6 1 4 1 37476 3 2 1 99 sha2(6) 512 }
	   Secure Hash Algorithm 3 (224 bits)         { 1 3 6 1 4 1 37476 3 2 1 99 sha3(7) 224 }
	   Secure Hash Algorithm 3 (256 bits)         { 1 3 6 1 4 1 37476 3 2 1 99 sha3(7) 256 }
	   Secure Hash Algorithm 3 (384 bits)         { 1 3 6 1 4 1 37476 3 2 1 99 sha3(7) 384 }
	   Secure Hash Algorithm 3 (512 bits)         { 1 3 6 1 4 1 37476 3 2 1 99 sha3(7) 512 }
	   --------------------------------------------------------------------------------------------

	-  <iterations> is the number of iterations, e.g. 1987.

	-  <salt-base64> is the iterated salt used for MHA2, encoded in Base64.

	-  <hash-base64> is the resulting hash, encoded in Base64.

Test vectors
============

	In normal hex notation (without salt in its output)
	---------------------------------------------------

	mha2_sha1(0, '', '', false) = 3cc116cf55ddfe7ddec0a7ea28260f0cb72b4eb2
	mha2_sha1(1, '', '', false) = 46a92a6c32b35d8c2cbf6a7ea3bb3e8c2bbf3721
	mha2_sha1(2, '', '', false) = dff5bb8e80d20756e0c9ab3ae6cb597f81404933

	mha2_sha1(0, 'salt', '', false) = fdb95f4142aa7ae1c84abd748eba9a48d42190ff
	mha2_sha1(1, 'salt', '', false) = 0e63283ea431306baef209bc1be642b456776f40
	mha2_sha1(2, 'salt', '', false) = 0097300de469e770ba1b058c5a1d3179d8b73354

	mha2_sha1(0, '', 'The quick brown fox jumps over the lazy dog', false) = d6a183874c35646c9a02ddf89ca9e6d3ac9827ca
	mha2_sha1(1, '', 'The quick brown fox jumps over the lazy dog', false) = 07f753ad21f3fa0faa2e5da68027ceae565fc703
	mha2_sha1(2, '', 'The quick brown fox jumps over the lazy dog', false) = 88812408426332c6e23c7fefac7feea5e30e1155

	mha2_sha1(0, 'salt', 'The quick brown fox jumps over the lazy dog', false) = 187c1c7eb9595bf94b0cf5e16c9534912d747cee
	mha2_sha1(1, 'salt', 'The quick brown fox jumps over the lazy dog', false) = 84ea5cb6374b5f5647b3f47902ff532c67c930be
	mha2_sha1(2, 'salt', 'The quick brown fox jumps over the lazy dog', false) = 7c610d96643e4c5131ed805253a4a8e5b8994e3e

	In heterogenous storage notation (including salt in the output)
	---------------------------------------------------------------

	mha2_sha1(0, '', '', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$0$$PMEWz1Xd/n3ewKfqKCYPDLcrTrI=
	mha2_sha1(1, '', '', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$1$$RqkqbDKzXYwsv2p+o7s+jCu/NyE=
	mha2_sha1(2, '', '', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$2$$3/W7joDSB1bgyas65stZf4FASTM=

	mha2_sha1(0, 'salt', '', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$0$c2FsdA==$/blfQUKqeuHISr10jrqaSNQhkP8=
	mha2_sha1(1, 'salt', '', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$1$c2FsdA==$DmMoPqQxMGuu8gm8G+ZCtFZ3b0A=
	mha2_sha1(2, 'salt', '', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$2$c2FsdA==$AJcwDeRp53C6GwWMWh0xedi3M1Q=

	mha2_sha1(0, '', 'The quick brown fox jumps over the lazy dog', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$0$$1qGDh0w1ZGyaAt34nKnm06yYJ8o=
	mha2_sha1(1, '', 'The quick brown fox jumps over the lazy dog', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$1$$B/dTrSHz+g+qLl2mgCfOrlZfxwM=
	mha2_sha1(2, '', 'The quick brown fox jumps over the lazy dog', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$2$$iIEkCEJjMsbiPH/vrH/upeMOEVU=

	mha2_sha1(0, 'salt', 'The quick brown fox jumps over the lazy dog', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$0$c2FsdA==$GHwcfrlZW/lLDPXhbJU0kS10fO4=
	mha2_sha1(1, 'salt', 'The quick brown fox jumps over the lazy dog', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$1$c2FsdA==$hOpctjdLX1ZHs/R5Av9TLGfJML4=
	mha2_sha1(2, 'salt', 'The quick brown fox jumps over the lazy dog', true) = 1.3.6.1.4.1.37476.3.2.1.2$1.3.6.1.4.1.37476.3.2.1.99.5$2$c2FsdA==$fGENlmQ+TFEx7YBSU6So5biZTj4=

Reference implementation in PHP with H=SHA1
===========================================

    <?php

    define
('MHA2_K',   chr(0x24).chr(0x12).chr(0x19).chr(0x87));
    
define('MHA2_P',   chr(0x12).chr(0x24).chr(0x19).chr(0x87));
    
define('MHA2_Q',   chr(0x19).chr(0x87).chr(0x12).chr(0x24));
    
define('OID_MHA2''1.3.6.1.4.1.37476.3.2.1.2');
    
define('OID_SHA1''1.3.6.1.4.1.37476.3.2.1.99.5');

    function 
sha1_bin($message) {
        return 
hex2bin(sha1($message));
    }

    function 
mha2_sha1_bin($iterations$salt$message) {
        if (
$iterations 0) return false;

        
$a '';
        
$b '';
        
$c '';
        for (
$i=0$i<=$iterations$i++) { // run $iterations+1 times
            
$a  sha1_bin(MHA2_P.$a.$message.$salt.MHA2_Q);
            
$b  sha1_bin(MHA2_Q.$salt.$message.$b.MHA2_P);
            
$c .= MHA2_K.$message.$salt;
        }
        
$c sha1_bin($c);

        return (
$a $b $c);
    }

    function 
mha2_sha1($iterations$salt$message$heterogenous) {
        
$hash mha2_sha1_bin($iterations$salt$message);
        if (
$hash === false) return false;

        if (
$heterogenous) {
            return 
OID_MHA2.'$'.OID_SHA1.'$'.$iterations.'$'.base64_encode($salt).'$'.base64_encode($hash);
        } else {
            return 
bin2hex($hash);
        }
    }

    
// Print test vectors
    
echo "mha2_sha1(0, '', '', false) = ".mha2_sha1(0''''false)."\n";
    echo 
"mha2_sha1(1, '', '', false) = ".mha2_sha1(1''''false)."\n";
    echo 
"mha2_sha1(2, '', '', false) = ".mha2_sha1(2''''false)."\n";
    echo 
"\n";
    echo 
"mha2_sha1(0, 'salt', '', false) = ".mha2_sha1(0'salt'''false)."\n";
    echo 
"mha2_sha1(1, 'salt', '', false) = ".mha2_sha1(1'salt'''false)."\n";
    echo 
"mha2_sha1(2, 'salt', '', false) = ".mha2_sha1(2'salt'''false)."\n";
    echo 
"\n";
    echo 
"mha2_sha1(0, '', 'The quick brown fox jumps over the lazy dog', false) = ".mha2_sha1(0'''The quick brown fox jumps over the lazy dog'false)."\n";
    echo 
"mha2_sha1(1, '', 'The quick brown fox jumps over the lazy dog', false) = ".mha2_sha1(1'''The quick brown fox jumps over the lazy dog'false)."\n";
    echo 
"mha2_sha1(2, '', 'The quick brown fox jumps over the lazy dog', false) = ".mha2_sha1(2'''The quick brown fox jumps over the lazy dog'false)."\n";
    echo 
"\n";
    echo 
"mha2_sha1(0, 'salt', 'The quick brown fox jumps over the lazy dog', false) = ".mha2_sha1(0'salt''The quick brown fox jumps over the lazy dog'false)."\n";
    echo 
"mha2_sha1(1, 'salt', 'The quick brown fox jumps over the lazy dog', false) = ".mha2_sha1(1'salt''The quick brown fox jumps over the lazy dog'false)."\n";
    echo 
"mha2_sha1(2, 'salt', 'The quick brown fox jumps over the lazy dog', false) = ".mha2_sha1(2'salt''The quick brown fox jumps over the lazy dog'false)."\n";
    echo 
"\n";
    echo 
"\n";
    echo 
"mha2_sha1(0, '', '', true) = ".mha2_sha1(0''''true)."\n";
    echo 
"mha2_sha1(1, '', '', true) = ".mha2_sha1(1''''true)."\n";
    echo 
"mha2_sha1(2, '', '', true) = ".mha2_sha1(2''''true)."\n";
    echo 
"\n";
    echo 
"mha2_sha1(0, 'salt', '', true) = ".mha2_sha1(0'salt'''true)."\n";
    echo 
"mha2_sha1(1, 'salt', '', true) = ".mha2_sha1(1'salt'''true)."\n";
    echo 
"mha2_sha1(2, 'salt', '', true) = ".mha2_sha1(2'salt'''true)."\n";
    echo 
"\n";
    echo 
"mha2_sha1(0, '', 'The quick brown fox jumps over the lazy dog', true) = ".mha2_sha1(0'''The quick brown fox jumps over the lazy dog'true)."\n";
    echo 
"mha2_sha1(1, '', 'The quick brown fox jumps over the lazy dog', true) = ".mha2_sha1(1'''The quick brown fox jumps over the lazy dog'true)."\n";
    echo 
"mha2_sha1(2, '', 'The quick brown fox jumps over the lazy dog', true) = ".mha2_sha1(2'''The quick brown fox jumps over the lazy dog'true)."\n";
    echo 
"\n";
    echo 
"mha2_sha1(0, 'salt', 'The quick brown fox jumps over the lazy dog', true) = ".mha2_sha1(0'salt''The quick brown fox jumps over the lazy dog'true)."\n";
    echo 
"mha2_sha1(1, 'salt', 'The quick brown fox jumps over the lazy dog', true) = ".mha2_sha1(1'salt''The quick brown fox jumps over the lazy dog'true)."\n";
    echo 
"mha2_sha1(2, 'salt', 'The quick brown fox jumps over the lazy dog', true) = ".mha2_sha1(2'salt''The quick brown fox jumps over the lazy dog'true)."\n";

    
?>