Zoltan Fridrich <[email protected]> writes:
>> + r %= mod;
>
>>Division is a pretty expensive operation. If this loop is in any way
>>performance critical, there are ways to speed up this arithmetic.
>
> How would you recommend speeding it up?
E.g, if m is small enough, you can precompute 0x10000 % m outside of
the loop, something like (totally untested)
uint32_t two16_mod_m = 0x10000 % mod;
uint32_t r = 0;
unsigned i;
for (i = length; i-- > 0; )
{
r = (r << 8) + block[i];
r = (r & 0xffff) + (r >> 16) * two16_mod_m;
}
return r % mod;
(one needs some analys to ensure that r stays in range and never
overflows; the above is probably not quite right).
I think one can gain speed by only keeping r partially reduced in the
loop. It's also possible to reduce it completely, but replace division
by multiplication (see https://gmplib.org/~tege/divcnst-pldi94.pdf,
https://gmplib.org/~tege/division-paper.pdf). If the compiler is clever
enough, it could realize that mod is a loop invariant and do that for
you, but I wouldn't count on that.
The point is that on typical processors, a division instruction can take
50-100 cycles or more, while a multiplication is typicalle done in 5
cycles or less.
>>For consistency, can you see if you can make the interface/function
>>signature closer to the pbkdf2 function (see pbkdf2.h)? It takes a
>>pointer to a mac context, already initialized by the caller (in this
>>case, it would instead be a hash context), function pointers for update
>>and digest, and the digest size.
>
> The closest function signature I can think of would look like this:
>
> void
> balloon(void *hash_ctx,
> nettle_hash_update_func *update,
> nettle_hash_digest_func *digest,
> size_t digest_size, uint *buf,
> size_t s_cost, size_t t_cost,
> size_t passwd_length, const uint8_t *passwd,
> size_t salt_length, const uint8_t *salt,
> size_t length, uint8_t *dst)
>
> But isn't 13 argument function an overkill?
> Would this function signature be ok or would you recommend something else?
I agree it's a bit unwieldy, but ok for a low-level primitive. But I
think you can reduce it to 12, since length and digest_size are always
the same, right?
One can then add wrappers for hash functions of interest, e.g.,
balloon_sha256, which would be a bit simper.
> Good point. I think it might be reasonable for someone to want a buffer
> size of a few GB in extreme cases.
> I can put s_cost and t_cost as size_t. I think there is no harm in doing
> that. Is that ok if I put them as size_t?
I think that is ok. size_t for cost_s makes sense. I don't know what's
the reasonable value is for cost_t? But makes some sense to stick to the
same type for both cost parameters.
Regards,
/Niels
--
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
_______________________________________________
nettle-bugs mailing list -- [email protected]
To unsubscribe send an email to [email protected]
