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. 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.
Current buffer size: 1 bytes. Old method time: 17818494µs. Safe method time: 16435418µs. Test method time: 17469064µs. Overhead by new method: -7.76203% Overhead by experimental method: -1.96105% Current buffer size: 2 bytes. Old method time: 26753134µs. Safe method time: 48109188µs. Test method time: 20938651µs. Overhead by new method: 79.8264% Overhead by experimental method: -21.7338% Current buffer size: 4 bytes. Old method time: 26445330µs. Safe method time: 40338735µs. Test method time: 49429638µs. Overhead by new method: 52.5363% Overhead by experimental method: 86.9125% Current buffer size: 8 bytes. Old method time: 26490806µs. Safe method time: 80018675µs. Test method time: 95708675µs. Overhead by new method: 202.062% Overhead by experimental method: 261.29% Current buffer size: 16 bytes. Old method time: 26618494µs. Safe method time: 159927735µs. Test method time: 188630680µs. Overhead by new method: 500.814% Overhead by experimental method: 608.645% Current buffer size: 32 bytes. Old method time: 26373319µs. Safe method time: 299822817µs. Test method time: 381609562µs. Overhead by new method: 1036.84% Overhead by experimental method: 1346.95% Current buffer size: 64 bytes. Old method time: 26369753µs. Safe method time: 591267432µs. Test method time: 762786294µs. Overhead by new method: 2142.22% Overhead by experimental method: 2792.66% Current buffer size: 128 bytes. Old method time: 26379620µs. Safe method time: 1176066488µs. Test method time: 1545594497µs. Overhead by new method: 4358.24% Overhead by experimental method: 5759.05% Current buffer size: 256 bytes. Old method time: 26398974µs. Safe method time: 2294413860µs. Test method time: 3035768316µs. Overhead by new method: 8591.3% Overhead by experimental method: 11399.6% Current buffer size: 512 bytes. Old method time: 26365764µs. Safe method time: 4516061779µs. Test method time: 5997060977µs. Overhead by new method: 17028.5% Overhead by experimental method: 22645.6% Current buffer size: 1024 bytes. Old method time: 26372286µs. Safe method time: 8964378849µs. Test method time: 11937839065µs. Overhead by new method: 33891.7% Overhead by experimental method: 45166.6%
