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 [email protected].
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 [email protected].
For more options, visit https://groups.google.com/d/optout.
