Subject: [Cfrg] Question about the order of hashing

From: Yoav Nir <[email-masked]>
Date: Thu, 5 Jan 2012 09:29:35 +0200

Hi.

When using keyed hash functions such as HMAC, GHash, and CBC-MAC, does the order of the items being concatenated and hashed make any difference to the security properties of the keyed hash?

IOW, does changing HMAC(k, a||b) into HMAC(k, b||a) change the security properties.

My motivation for this question is that I would like to propose a variant for IPsec where the sequence numbers are hashed after the payload rather than before it. Different size packets take different times to hash, so if we try to parallelize IPsec processing, arbitrarily many packets may finish processing before a large single packet has finished processing. 

IPsec emitters are required to emit the packets in order of the sequence numbers, but since the sequence numbers (which are sent in the clear) are hashed first, they have to be allocated before hashing begins. By moving them to the end of the hash, I can allocate the sequence number after having hashed most of the packet, and have nearly constant-time processing after allocating the sequence number.

So is this scheme I'm proposing save, or would it introduce some major vulnerability.

Thanks

Yoav

---

From: Steven Bellovin <[email-masked]>
Date: Thu, 5 Jan 2012 04:10:10 -0500

> So is this scheme I'm proposing save, or would it introduce some major vulnerability.
What is your traffic model?  If it's a single TCP stream, I think you'll introduce
performance problems at that layer if you're sending packets out of TCP order.

		--Steve Bellovin, https://www.cs.columbia.edu/~smb

---

From: Yoav Nir <[email-masked]>
Date: Thu, 5 Jan 2012 11:19:15 +0200

> performance problems at that layer if you're sending packets out of TCP order.

With a single TCP stream that is transferring a lot of data, all packets tend to be the same size - that of the MSS. My model is a lot of packets, some UDP, some TCP, belonging to multiple streams.

My implementation would place every TCP stream on a single processor, but that's because my implementation is also a firewall. This won't help cases where all (or most) traffic is a single TCP stream, but parallelizing can help where you have multiple streams or packets under the same SA.

---

From: Thomas Pornin <[email-masked]>
Date: Thu, 5 Jan 2012 08:08:31 -0500

> IOW, does changing HMAC(k, a||b) into HMAC(k, b||a) change the security properties.

As long as the concatenation can be unambiguously undone, the security properties are maintained.

The trouble with concatenation is that, when done carelessly, it can introduce ambiguities. For instance, if you take a protocol which concatenates the user name and his password directly, then user 'steven' with password 'cipher', and user 'steve' with password 'ncipher', end up with the same concatenation result: 'stevencipher'. That can be a problem for the security properties. In the case of users and passwords, a common solution is to add a separator character, which is forbidden in user names (hence 'steven:cipher' and 'steve:ncipher').

By swapping your 'a' and 'b', you might introduce ambiguities. For instance, suppose that 'a' is a self-terminated structure (i.e. it begins with a header which defines its length, so the end of 'a' and the start of 'b' can be reliably located within 'a||b' by looking at the first bytes), but 'b' is not. Then 'a||b' can always be split back into a single, well-defined (a,b) pair. On the other hand, 'b||a' might not be unambiguously split, so you could have distinct pairs 'b1||a1' and 'b2||a2' which both match the 'b||a' string (and yield the same MAC).

As long as you take care of that point, i.e. do not introduce the possibility of a 'stevencipher', then you can choose whichever conventional order you like, it will not impact the security of HMAC (of course, sender and receiver must both agree on the same, single, well-defined order).

	--Thomas Pornin

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 5 Jan 2012 08:26:53 -0800

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
Of
> Yoav Nir
> Sent: Thursday, January 05, 2012 4:19 AM
> To: Steven Bellovin
> Cc: [email-masked]
> Subject: Re: [Cfrg] Question about the order of hashing
> 
> 
> >> When using keyed hash functions such as HMAC, GHash, and CBC-MAC,
> does the order of the items being concatenated and hashed make any
> difference to the security properties of the keyed hash?
> >>
> >> My motivation for this question is that I would like to propose a
> variant for IPsec where the sequence numbers are hashed after the
> payload rather than before it. Different size packets take different
> times to hash, so if we try to parallelize IPsec processing,
> arbitrarily many packets may finish processing before a large single
> packet has finished processing.
> >>
> >> IPsec emitters are required to emit the packets in order of the
> sequence numbers, but since the sequence numbers (which are sent in
the
> clear) are hashed first, they have to be allocated before hashing
> begins. By moving them to the end of the hash, I can allocate the
> sequence number after having hashed most of the packet, and have
nearly
> constant-time processing after allocating the sequence number.
> >>
> With a single TCP stream that is transferring a lot of data, all
> packets tend to be the same size - that of the MSS. My model is a lot
> of packets, some UDP, some TCP, belonging to multiple streams.
> 
> My implementation would place every TCP stream on a single processor,
> but that's because my implementation is also a firewall. This won't
> help cases where all (or most) traffic is a single TCP stream, but
> parallelizing can help where you have multiple streams or packets
under
> the same SA.

Yoav, might I point out that with ESP-GCM (and GMAC), you can actually
compute things out of order.  That is, you can compute the entire
encrypted data and ICV field assuming a sequence number of 0, and
afterwards figure out how to adjust the ICV for the actual sequence
number.

This adjustment does involve computing H**n (where H is an internal GCM
value derived from the key, and n is the packet length in 16 byte
increments, and the multiplications are GF(2**128) field
multiplications).  Computing this is logarithmic time, not constant
(unless you precompute all the possible H**n values; there's about 100
of them for standard MTU sizes), but is certainly closer to constant
what you're originally looking at with the standard HMAC authentication.

So, what's the benefit of putting up with this complexity?  Well, you
can basically get what you want with standard (RFC-compliant) protocols.
So, you can implement what you want without asking anyone else to do
anything (well, other than implement the GCM RFC, I suppose).  I share
Steve's concerns about sending packets out of order (my personal worry
would be video), but you can implement it yourself, and see in practice
if it works well.

---

From: David McGrew <[email-masked]>
Date: Thu, 5 Jan 2012 10:22:32 -0800

Thanks Scott for pointing out that the use of the "incremental"  
property can be used here.  Yoav, there are more details on that  
property in <http://www.mindspring.com/~dmcgrew/gmac-incr-c-00.pdf>  
from IEEE SIS 2005, if you are interested.   As far as I know, there  
are no intellectual property considerations that are specific to  
incremental MACs or the use of GCM/GMAC in that manner.

David

On Jan 5, 2012, at 8:26 AM, Scott Fluhrer (sfluhrer) wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 5 Jan 2012 16:11:29 -0500

The security properties of HMAC do not change by the order of the data
items. However, the change of order may affect the security of a
cryptographic protocol that uses HMAC. Particularly, ambiguous parsing as
in Thomas example can break a protocol. Or think of a DH key exchange that
is authenticated with a preshared key K by transmitting HMAC(K, g^a||g^b)
from A to B and HMAC(K, g^b||g^a) from B to A (and assume the parties check
that g^a \noteq g^b to prevent reflection attacks). Now, if you change the
order of arguments in the B to A flow, you create a reflection attack
opportunity that did not exist in the original protocol.

I would assume that if the only thing that you change is the position of
the sequence number and in the new ordering the position and length of this
number is uniquely determined (e.g., last 4 bytes of the message) then you
should be ok, but it is just an assumption. You should look more carefully
at your specific protocol/usage.

Hugo

On Thu, Jan 5, 2012 at 2:29 AM, Yoav Nir <[email-masked]> wrote:

> Hi.
>
> When using keyed hash functions such as HMAC, GHash, and CBC-MAC, does the
> order of the items being concatenated and hashed make any difference to the
> security properties of the keyed hash?
>
> My motivation for this question is that I would like to propose a variant
> for IPsec where the sequence numbers are hashed after the payload rather
> than before it. Different size packets take different times to hash, so if
> we try to parallelize IPsec processing, arbitrarily many packets may finish
> processing before a large single packet has finished processing.
>
> IPsec emitters are required to emit the packets in order of the sequence
> numbers, but since the sequence numbers (which are sent in the clear) are
> hashed first, they have to be allocated before hashing begins. By moving
> them to the end of the hash, I can allocate the sequence number after
> having hashed most of the packet, and have nearly constant-time processing
> after allocating the sequence number.
>