This is all I got: http://crypto.stackexchange.com/a/30263/23623 The rest here is mainly me trying to interpret / summarize this answer.
It only occurs if you have nonces which aren't 12 bytes. At a maximum you can recover the hash key H and not the cipher key (still allowing for forgeries). You'll have to distinguish a (or multiple) ~2 cycles call(s) to the function from a ~3 cycles call (in order to see if a carry has taken place). This may be feasible remotely, depending on the surrounding code, there's no demonstration I'm aware of, it's mainly theoretical at this point. I don't know about the requirements (although some over at Crypto.SE may know or may be able to figure it out). But I guess the following: If you observe a carry (after at most 256 bytes), then you know that at this point the lower 8 bits are zero, if you observe a double carry after at most 256^2 invocations you know the 16 lowest bits must be zero. At some point (and maybe using some more advanced skills) you'll be able to fully recover the complete counter or brute-force the remaining parts. In worst case (using my simple approach) this would allow you to find H after 2^64 invocations using 2^64 work. BR JPM Am 08.11.2015 um 17:58 schrieb Mobile Mouse: > 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 > <mailto: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: >>> >>> 1. Not mitigate and just keep our old code. >>> 2. Mitigate and allow for both codes (constant + non-constant >>> time), default to "use non-constant time code" >>> 3. Mitigate and allow for both codes (constant + non-constant >>> time), default to "use constant time code" >>> 4. 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 >>> <mailto: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 >> <mailto: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 >> <mailto: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 > <mailto: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.
