Tweet
Preamble
HMAC was proposed in [1] and there is a particularly good interpretation at [2]
Effectively, we have
HMAC(K,m) = H( a || H( b || m ) ) ...... (i)
where K is the shared/secret key, m is the message, H is the hash algorithm and || to be read as concatenate.
a = K0 XOR opad and b = K0 XOR ipad where ipad = &H36 and opad = &H5C both repeated B, the block size, times.
Len(K0) = B and
K0 = K if Len(K) = B
= K || 0...0 if K < B
= H(K) || 0...0 if K > B
The block size, B, is 64 bytes for both MD5 and SHA1, and many others for that matter.
A quotation from Microsoft: "A hash can be created in a piece-by-piece way."
H( b || m ) may be computed with b || m as a single stream or we can compute H( b ) and later 'hash in' m.
H( b || m ) could be written H( b ).m where the .m means 'hash in' m.
(i) can now be written HMAC(K,m) = H( a ).H( b ).m ....... (ii)
(i) is the format used when m is the message in text form with b || m treated as a single stream. If we call the resulting hash hBin we then treat a || hBin as a single stream.
(ii) is the format used when m is the message in file form. Here we hash b then hash in m. With the resulting hash as hBin we then, as above, treat a || hBin as a single stream.
D-HMAC, Dynamic HMAC, proposed in [3], calculates an ipad and opad depending upon both the message and a receiver key and the core of the idea is the use of
H(m) XOR R where R is a receiver key ............... (iii)
So, if we send the same message to different receivers then the D-HMAC values will be different. If we send different messages to the same receiver then the D-HMAC values will be different. In the latter case, the HMAC values would be different anyway but they would be determined with static ipad and opad.
I should add that I have got the OK to use the algorithm by Mohannad Najjar one of the authors of D-HMAC.
The algorithm examines (iii) at the bit level. The leftmost bit determines which row of a substitution box to use. The next two bits determine which column to use. The second bit is then used to give the row and the two bits following give the column and so on. Inserted: Didn't finish the story. The process so far gets us an entry for ipad. Whichever row is chosen the other row is used for getting the opad entry. End of insertion. [3] does not indicate what to do when we reach the 127th bit, requiring a further two bits for the row, but the natural thing to do is to simply rotate right and pick up the first bit again; which has only been used once so far. At the 128th bit we rotate twice and pick up the first two bits. This way all bits get used three times, firstly to give the row and then the second or third bit of three in determining the column. The substitution box gives four bits so for MD5 we get 128*4 bits output ie 64 bytes, the same as the block size. With SHA1, being 160 bits, we would exceed the block size. No remedy for this is given in [3]. The implemented code simply restricts the input to 128 bits and if the receiver key exceeds 128 bits then this is hashed down to 128 bits by hashing it with MD5.
Since m plays a part in both (i) and (iii) then we can expect the computational time of D-HMAC to be of the order of twice that of HMAC when the message is significantly larger than 64 bytes. The additional work of D-HMAC over HMAC, excepting (iii), as with the additional work of HMAC over H(ash) is not dependent upon the message size.
With two receivers and one sender it may be worthwhile to examine how much difference there is in the D-HMAC values.
Given two strings, A and B, of the same length we can measure their difference at the bit level by counting the set bits of A Xor B. With A Xor A there are no set bits, not surprising since there is no difference between A and A. With A Xor Not A then we have nothing but set bits because there is nothing in common. If A and B are random then for an infinite of number of pairs we will find an average of 25% set collisions, 25% reset collisions, 25% 0 1 combinations and 25% 1 0 combinations. In other words 50% different and, obviously, 50% in common. Dividing the set count by the string bit length will give a percentage difference.
The following code considers, DHMAC, HMAC and finally H, the standard hash function, implementing the Windows inbuilt MD5 and SHA1. For D-HMAC a sender key plus two receiver keys, all randomly generated, are considered. For each pair of receiver keys a percentage difference is calculated. The percentage difference should fall, on average, between 40% and 60% about 97% of the time for 128 bit strings (MD5) and about 99% of the time for 160 bit string (SHA1). Leaving the machine on overnight for a very thorough test has not been done yet but with a limited test there does not seem to be any signs of a difference different to what we would expect of random strings. Consideration was also given to one receiver and two senders where the sender keys differed only by one bit in the lowest significant byte. Again no unusual differences were found in the resulting D-HMAC pairs.
As expected D-HMAC takes about twice as long as HMAC and H, the latter two being in the same ball park. This was for files ranging from 1MB to 100MB. Less than 1MB on my system sees timings of around 44ms and less, including reading from the hard drive, and the pattern gets distorted. For small messages the code would require optimizing but squeezing every ounce on speed grounds was not a criteria here - getting working code for the principle was the order of the day.
At one point I considered a revised HMAC viz H( a ).H( m ).b ...... (iv)
figuring that H( m ) used in (iii) could be used again in (iv) and thus half the computational time.
However, if we have H( m1 ) = H( m2 ) with m1 <> m2 then we have a collision.
So, H( m1 ).x = H( m2 ).x and H( y ).H( m1 ).x = H( y ).H( m2 ).x
The HMAC will then also collide rendering (iv) as a non-runner as it would have a collision resistance no better than a standard hash.
It is worth noting that H( x ).m1 will probably <> H( x ).m2, the probability being 2^2n to 1 against if the probability of the first collision is 2^n to 1 against.
This is why HMAC uses H( b ).m and not H( m ).b
When Mohannad Najjar wrote me he said "We are doing some changes on the algorithm to make it more powerful; hopefully we will publish the improved algorithm soon."
I would like to see a more heavy duty substitution box and will start a thread in the Programming Forum inviting folk to chip in with their experience - it is not an area that I am well acquainted with. The substitution box used is at the bottom of the GetIpadOpad function.
References
[1] M Bellare, R Canetti and H Krawczyk
Message Authentication using Hash Functions - The HMAC Construction
[2] FIPS PUB 198-1
The Keyed-Hash Message Authentication Code (HMAC)
[3] M Najjar and F Najjar
d-HMAC Dynamic HMAC function
HMAC was proposed in [1] and there is a particularly good interpretation at [2]
Effectively, we have
HMAC(K,m) = H( a || H( b || m ) ) ...... (i)
where K is the shared/secret key, m is the message, H is the hash algorithm and || to be read as concatenate.
a = K0 XOR opad and b = K0 XOR ipad where ipad = &H36 and opad = &H5C both repeated B, the block size, times.
Len(K0) = B and
K0 = K if Len(K) = B
= K || 0...0 if K < B
= H(K) || 0...0 if K > B
The block size, B, is 64 bytes for both MD5 and SHA1, and many others for that matter.
A quotation from Microsoft: "A hash can be created in a piece-by-piece way."
H( b || m ) may be computed with b || m as a single stream or we can compute H( b ) and later 'hash in' m.
H( b || m ) could be written H( b ).m where the .m means 'hash in' m.
(i) can now be written HMAC(K,m) = H( a ).H( b ).m ....... (ii)
(i) is the format used when m is the message in text form with b || m treated as a single stream. If we call the resulting hash hBin we then treat a || hBin as a single stream.
(ii) is the format used when m is the message in file form. Here we hash b then hash in m. With the resulting hash as hBin we then, as above, treat a || hBin as a single stream.
D-HMAC, Dynamic HMAC, proposed in [3], calculates an ipad and opad depending upon both the message and a receiver key and the core of the idea is the use of
H(m) XOR R where R is a receiver key ............... (iii)
So, if we send the same message to different receivers then the D-HMAC values will be different. If we send different messages to the same receiver then the D-HMAC values will be different. In the latter case, the HMAC values would be different anyway but they would be determined with static ipad and opad.
I should add that I have got the OK to use the algorithm by Mohannad Najjar one of the authors of D-HMAC.
The algorithm examines (iii) at the bit level. The leftmost bit determines which row of a substitution box to use. The next two bits determine which column to use. The second bit is then used to give the row and the two bits following give the column and so on. Inserted: Didn't finish the story. The process so far gets us an entry for ipad. Whichever row is chosen the other row is used for getting the opad entry. End of insertion. [3] does not indicate what to do when we reach the 127th bit, requiring a further two bits for the row, but the natural thing to do is to simply rotate right and pick up the first bit again; which has only been used once so far. At the 128th bit we rotate twice and pick up the first two bits. This way all bits get used three times, firstly to give the row and then the second or third bit of three in determining the column. The substitution box gives four bits so for MD5 we get 128*4 bits output ie 64 bytes, the same as the block size. With SHA1, being 160 bits, we would exceed the block size. No remedy for this is given in [3]. The implemented code simply restricts the input to 128 bits and if the receiver key exceeds 128 bits then this is hashed down to 128 bits by hashing it with MD5.
Since m plays a part in both (i) and (iii) then we can expect the computational time of D-HMAC to be of the order of twice that of HMAC when the message is significantly larger than 64 bytes. The additional work of D-HMAC over HMAC, excepting (iii), as with the additional work of HMAC over H(ash) is not dependent upon the message size.
With two receivers and one sender it may be worthwhile to examine how much difference there is in the D-HMAC values.
Given two strings, A and B, of the same length we can measure their difference at the bit level by counting the set bits of A Xor B. With A Xor A there are no set bits, not surprising since there is no difference between A and A. With A Xor Not A then we have nothing but set bits because there is nothing in common. If A and B are random then for an infinite of number of pairs we will find an average of 25% set collisions, 25% reset collisions, 25% 0 1 combinations and 25% 1 0 combinations. In other words 50% different and, obviously, 50% in common. Dividing the set count by the string bit length will give a percentage difference.
The following code considers, DHMAC, HMAC and finally H, the standard hash function, implementing the Windows inbuilt MD5 and SHA1. For D-HMAC a sender key plus two receiver keys, all randomly generated, are considered. For each pair of receiver keys a percentage difference is calculated. The percentage difference should fall, on average, between 40% and 60% about 97% of the time for 128 bit strings (MD5) and about 99% of the time for 160 bit string (SHA1). Leaving the machine on overnight for a very thorough test has not been done yet but with a limited test there does not seem to be any signs of a difference different to what we would expect of random strings. Consideration was also given to one receiver and two senders where the sender keys differed only by one bit in the lowest significant byte. Again no unusual differences were found in the resulting D-HMAC pairs.
As expected D-HMAC takes about twice as long as HMAC and H, the latter two being in the same ball park. This was for files ranging from 1MB to 100MB. Less than 1MB on my system sees timings of around 44ms and less, including reading from the hard drive, and the pattern gets distorted. For small messages the code would require optimizing but squeezing every ounce on speed grounds was not a criteria here - getting working code for the principle was the order of the day.
At one point I considered a revised HMAC viz H( a ).H( m ).b ...... (iv)
figuring that H( m ) used in (iii) could be used again in (iv) and thus half the computational time.
However, if we have H( m1 ) = H( m2 ) with m1 <> m2 then we have a collision.
So, H( m1 ).x = H( m2 ).x and H( y ).H( m1 ).x = H( y ).H( m2 ).x
The HMAC will then also collide rendering (iv) as a non-runner as it would have a collision resistance no better than a standard hash.
It is worth noting that H( x ).m1 will probably <> H( x ).m2, the probability being 2^2n to 1 against if the probability of the first collision is 2^n to 1 against.
This is why HMAC uses H( b ).m and not H( m ).b
When Mohannad Najjar wrote me he said "We are doing some changes on the algorithm to make it more powerful; hopefully we will publish the improved algorithm soon."
I would like to see a more heavy duty substitution box and will start a thread in the Programming Forum inviting folk to chip in with their experience - it is not an area that I am well acquainted with. The substitution box used is at the bottom of the GetIpadOpad function.
References
[1] M Bellare, R Canetti and H Krawczyk
Message Authentication using Hash Functions - The HMAC Construction
[2] FIPS PUB 198-1
The Keyed-Hash Message Authentication Code (HMAC)
[3] M Najjar and F Najjar
d-HMAC Dynamic HMAC function
Comment