Re: [Cfrg] Question about the order of hashing

[David McGrew <[e-mail]>]

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:

>
>
>> -----Original Message-----
>> From: [e-mail] [mailto:[e-mail]] On Behalf
> Of
>> Yoav Nir
>> Sent: Thursday, January 05, 2012 4:19 AM
>> To: Steven Bellovin
>> Cc: [e-mail]
>> Subject: Re: [Cfrg] Question about the order of hashing
>>
>>
>> On Jan 5, 2012, at 11:10 AM, Steven Bellovin wrote:
>>
>>>
>>> On Jan 5, 2012, at 2:29 35AM, Yoav Nir 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?
>>>>
>>>> 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.
>>>>
>>> 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.
>>
>> 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.
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg