Hello Niels,
just a reminder for you to take a look at the updated balloon.patch. I
would like to work on the patch until it is in an acceptable state. I don't
want to leave it hanging unfinished.
Kind regards,
Zoltan
On Thu, Sep 1, 2022 at 4:41 PM Zoltan Fridrich <zfrid...@redhat.com> wrote:
> Hello Niels,
>
> I am sending you an updated patch. I have resolved all of the issues
> except for the modulo.
> Can you please take a look again?
>
> Kind regards,
> Zoltan
>
> On Thu, Sep 1, 2022 at 12:56 PM Niels Möller <ni...@lysator.liu.se> wrote:
>
>> Zoltan Fridrich <zfrid...@redhat.com> 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 -- nettle-bugs@lists.lysator.liu.se
To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
