On 28/05/12 22:22, chip...@gmx.de wrote:
Hi,
Thank you for your answer it helped me and gives me a plausible explanation.
But I didn't understand some things when I look at the source code. I will
explain my conditions more in detail.
I have for example to bignums which I want to add modulo another bignumber.
This BN can be as you said of an arbitrary length. But normaly they have an
length of 224 bit, sometimes 223-bits and often 1 or 0-bits. They will be
calculated on a 32-bit system. I want now that an addition of an 224-bit to an
0-bit number (thus 0), an addition of two 224-bit nummbers, or an addition of
two 0-bit numbers take equal time, because it is a security requirement.
You said, you can use BN_FLG_CONSTTIME, but how do I do it. Is it just a define
statement which I have to insert in my code, and how does it looks like?
I looked in the bn.h and see a function, which is called BN_set_flags(b,n), but
what are the two parameters? I didn't find a hint in the OpenSSL Documentation
or an example. Do I have to call the function for every Bignum or every
operation?
BIGNUM *mynum;
mynum = BN_new();
BN_set_flags(mynum, BN_FLG_CONSTIME);
You just need to set it once on each BIGNUM. The library will check the
BIGNUMs involved in each operation - as long as one of them has the flag
then it will treat the operation as constant time.
I run a debugger in order to get information which steps my program make when I
for example add to Bignums modulo a number (BN_mod_add).
First it goes in the BN_add_funtion.
I see that the bigger result, which takes more time run into the BN_expand
(BN_expand2) function, and then there call other functions like OpenSSL_malloc
and so on, so I think this is what you mean with the size of the Bignumber. The
other Bignums, which are smaller (not much), did not run in these functions. So
this could explain a little time difference.
After that it goes in the BN_mod function, but there I see no difference in the
steps which the debugger does. It doesn't matter if the number is bigger then
the modul or not. The function always make the same steps. This is what I don't
understand. Do you have a hint?
But in total the time consumption is very different as you said. It depends if
the result is bigger or smaller then the modul.
BN_mod is just a macro that uses BN_div defined in bn_div.c
It is these lines where the number is compared with the divisor
(modulus). If it is less then it just copies the number straight into
the result and returns. Notice the "!no_branch", check on this if. This
is set to TRUE if BN_FLG_CONSTTIME is set for one of the BIGNUMs.
if (!no_branch && BN_ucmp(num,divisor) < 0)
{
if (rm != NULL)
{ if (BN_copy(rm,num) == NULL) return(0); }
if (dv != NULL) BN_zero(dv);
return(1);
}
Another thing which I find interresting, when I call for example the operation
BN_mod_add(r,a,b,m,ctx1) very early in the code, then it takes more time than
if do it late. First I thought it would be the cache, but I do not use any of
these variables in other operations before. I just created and set space for
them with BN_new, like with the other variables too. I tested this operations
in a loop, and the phenomena is the same.
How can this be?
The context is used to cache temporary variables for later reuse - so
this is possibly due to reuse of those temporary variables?
I have also a general question about context variables. Is it ok, to use the
same context variable for all calculating operations one after another? Or
should each operation have a different one? I measured the time with different
context variables, but it has no consequences. The caculating results also stay
the same.
You can reuse the same one. In fact its better to reuse, as you will
benefit from the caching of temporary variables.
Thank you for your answer.
-------- Original-Nachricht --------
Datum: Tue, 15 May 2012 00:04:16 +0100
Von: "Matt Caswell (fr...@baggins.org)"<fr...@baggins.org>
An: openssl-users@openssl.org
Betreff: Re: Problems with OpenSSl BN
On 14/05/12 15:48, chip...@gmx.de wrote:
Hello,
I am using the OpenSSL BN functions. Wenn I measure the time which a BN
function needs, then I see that for example BN_mod_add, needs for every
calling different times. Shouldn't it be the same timeconsumption, every time
I call for example BN_mod_add?
The deviation is up to 300%.
Thank you!
You don't say how you did your testing or under what conditions you
expect responses to be constant time.
There are a couple of reasons that I can think of why BN_mod_add would
provide different results for different invocations.
1) Different bit lengths of the parameters.
Obviously the BN functions are designed to work with integers of
arbitrary length. Under the covers BN_mod_add will add these by looping
through a word at a time. Obviously adding together integers that are 1
word long each is going to give you significantly different results to
integers that are 10 words long each. Also the time for the addition is
largely related to size of the *smallest* integer. So for example adding
a 1 word integer to a 10 word integer will be quicker than adding a 10
word integer to another 10 word integer.
2) The mod operation
In order to calculate the "mod" part of BN_mod_add essentially a
division operation is performed with the result being the remainder.
However a short cut is if the result of the add is less than the mod
value. In that case no division is necessary, and therefore this
operation can be avoided. Therefore if you are comparing BN_mod_adds
that require a division with those that do not then you are likely to
see different performance results.
If constant time is important to you, I believe it is possible to force
certain operations within the BN library to respond in a more
predictable response time by setting the BN_FLG_CONSTTIME flag. However
this does not apply to all function calls and removes certain
optimizations from the code.
Hope that helps
Matt
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager majord...@openssl.org
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager majord...@openssl.org
