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
>> <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
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;
}
#ifdef CRYPTOPP_BOOL_X64 || CRYPTOPP_BOOL_X86 // make a better check for the
ADC intrinsic and run-time availability here
|byte cf = _addcarry_u8(0,1,||input[size-1],&||output[size-1]); // make the
initial addition for(int i=size-2;i>=0;--i)
cf = |||_addcarry_u8(cf,0,||||input[i],&||||output[i]); // carry it over until
the very end #else ||
|||for (int i=int(size-1), carry=1; i>=0; i--) { int t = input[i] +
carry; output[i] = t & 0xff; carry = t >> 8; } |#endif ||}
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]
> <mailto:[email protected]>. 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 [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.
