I'd like to hear more about the feasibility of this timing attack against GCM: - Is it remote, or local only? - What are the traffic requirements for the ability to launch it (quantity and constitution)? - Is it demonstratable (aka can you show code that would recover GCM key under X number of minutes/hours given Y amount of traffic)?
Sent from my iPad > On Nov 7, 2015, at 15:14, Jean-Pierre Münch <jean-pierre.mue...@web.de> wrote: > > forgot to append the data as usual. Now appended. > Note: "Experimental" is the ADC based code, "Safe / New" is poncho's code. > >> Am 07.11.2015 um 21:07 schrieb Jean-Pierre Münch: >>> Am 05.11.2015 um 21:57 schrieb Jean-Pierre Münch: >>>> Am 05.11.2015 um 04:13 schrieb Jeffrey Walton: >>>> >>>>>>> On Wednesday, November 4, 2015 at 12:56:12 PM UTC-5, jean-pierre.muench >>>>>>> wrote: >>>>>>> Interesting idea, although I fear that a timing side channel may remain >>>>>>> (two dozen carries may take longer than no carry) and thereby not >>>>>>> fixing the problem (if I'm reading things right). >>>>>> >>>>>> Forgot to mention... An ADC will work nicely here >>>>>> (http://www.fermimn.gov.it/linux/quarta/x86/adc.htm). There might even >>>>>> be an intrinsic for it. >>>>> Are you proposing something like the following? >>>>> >>>>> void IncrementCounterByOne(byte *in,byte *out, unsigned int size) >>>>> { >>>>> byte cf = _addcarry_u8(0,1,in[size-1],&in[size-1]); // make the >>>>> initial addition >>>>> for(int i=size-2;i>=0;--i) >>>>> { >>>>> cf = _addcarry_u8(cf,0,in[i],&in[i]); // carry it over until the very >>>>> end >>>>> } >>>>> memmove(out,in,size); >>>>> } >>>>> >>>>> This should run in constant time, assuming _addcarry_u8 runs in constant >>>>> time. I've tested this and it produces correct results. >>>> Yeah, something like that should be fine. In that particular overload, I >>>> *think* `in` is a `const byte*`, so you probably cannot write to it. But >>>> I'd need to check. >>> Yes, indeed I got the header wrong. My (new) proposals are below. As for >>> the speed, we just have to accept O(log(n)) run-time as it looks if we want >>> to provide constant time implementations, as we have to compute no matter >>> if there's a carry or not. Our current implementation is basically o(1). >>> I'll compare our options again in the next few (2-3) days. The proposals >>> use ADC on x86/x64 (still not sure how to do this), use poncho's code for >>> anything without ADC and allow for our old code on override. Furthermore >>> the two argument function is now a special case of the three argument >>> function. BR JPM >> I finally got the promised data. It tells me that using the ADC instruction >> is *slower* than using poncho's approach in most cases (data's attached). So >> I'd propose the below set of functions as mitigation for this issue. However >> I think we need some sort of consensus on the strategy for this, which can >> be summarized as follows: We found the issue that non-constant time >> increments can provide a timing side channel that potentially allows for >> severe attacks on GCM. For the sake of speed our current code is >> non-constant time and thereby depends on the actual values of the bytes. We >> have a piece of code that fixes this issue and runs in constant time, the >> problem is that its run-time grows linearly with the length of the buffer to >> increment and its execution time usually is significantly longer than the >> old one. However the actual execution time of each call is still very short >> as it's a simple function, taking ~26.1 cycles for 8 bytes on an i7 930 and >> ~2922 cycles for 1024 bytes on the same processor. The old code takes about >> 8.72 cycles for every size[1]. The question is now about the API, should we: >> Not mitigate and just keep our old code. >> Mitigate and allow for both codes (constant + non-constant time), default to >> "use non-constant time code" >> Mitigate and allow for both codes (constant + non-constant time), default to >> "use constant time code" >> Mitigate and only allow for constant time code >> My stand-point should be clear. The code for 3 and 4 can be found below, >> with a simple true/false exchange at the correct places. >> >> BR >> >> JPM >> >> [1]: The results were averaged from 2^33 function calls, the actual cycles >> may be a bit higher as TurboBoost frequency wasn't incorporated into the >> calculation. >>> >>> inline void IncrementCounterByOne(byte *output, const byte *input, unsigned >>> int s,bool UseUnsafeIncrement) >>> { >>> if(UseUnsafeIncrement) >>> { >>> int i, carry; >>> for (i=s-1, carry=1; i>=0 && carry; i--) >>> carry = ((output[i] = input[i]+1) == 0); >>> memmove_s(output, s, input, i+1); >>> return; >>> } >>> for (int i=int(size-1), carry=1; i>=0; i--) >>> { >>> int t = input[i] + carry; >>> output[i] = t & 0xff; >>> carry = t >> 8; >>> } >>> } >>> >>> inline void IncrementCounterByOne(byte *output, const byte *input, unsigned >>> int s) >>> { >>> IncrementCounterByOne(output,input,s,false); >>> } >>> >>> inline void IncrementCounterByOne(byte *inout, unsigned int s) >>> { >>> IncrementCounterByOne(inout,inout,s,false); >>> } >>> >>> inline void IncrementCounterByOne(byte *inout, unsigned int s,bool >>> UseUnsafeIncrement) >>> { >>> if(UseUnsafeIncrement) >>> { >>> for (int i=s-1, carry=1; i>=0 && carry; i--) >>> carry = !++inout[i]; >>> return; >>> } >>> IncrementCounterByOne(inout,inout,s,false); // use the safe code >>> } >>> >>> >>>> Jeff >> -- -- You received this message because you are subscribed to the "Crypto++ >> Users" Google Group. To unsubscribe, send an email to >> cryptopp-users-unsubscr...@googlegroups.com. More information about Crypto++ >> and this group is available at http://www.cryptopp.com. --- You received >> this message because you are subscribed to the Google Groups "Crypto++ >> Users" group. To unsubscribe from this group and stop receiving emails from >> it, send an email to cryptopp-users+unsubscr...@googlegroups.com. For more >> options, visit https://groups.google.com/d/optout. > -- > -- > You received this message because you are subscribed to the "Crypto++ Users" > Google Group. > To unsubscribe, send an email to cryptopp-users-unsubscr...@googlegroups.com. > More information about Crypto++ and this group is available at > http://www.cryptopp.com. > --- > You received this message because you are subscribed to the Google Groups > "Crypto++ Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to cryptopp-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > <ResultsIncrementTestADC.txt> -- -- You received this message because you are subscribed to the "Crypto++ Users" Google Group. To unsubscribe, send an email to cryptopp-users-unsubscr...@googlegroups.com. More information about Crypto++ and this group is available at http://www.cryptopp.com. --- You received this message because you are subscribed to the Google Groups "Crypto++ Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to cryptopp-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
smime.p7s
Description: S/MIME cryptographic signature
