Room for Kevin Stefanov and fgrieu

2:30 PM

@fgrieu I've hit another brick wall. My argon2 is really slow when I call it with m=2097000

this is 2 GiB memory. I did 4 threads and it took like a minute to transform a hundredth of a segment

Is this the right memory parameter to call it with? The RFC says m is given in kibibytes, so 2 million kibibytes is the required 2 GiB you said, right?

For reference, I have pretty good hardware: 32 gig ram and Ryzen 9 CPU liquid cooled

fgrieu

3:06 PM

These are standard recommendations: Argon2id with t=1 and 2 GiB memory, or t=3 and 64 MiB memory in memory-constrained environments. That is m=2097152 and t=1 or m=65536 and t=3 by my reading.

Having an implementation optimized for speed is important for security in argon2id (contrary to most other crypto algorithms). The faster an implementation, the more we can increase parameters t and m, about proportionally increasing the protection offered against password search for t. For m, protection increases even faster than m.

Further recommendations with approximate expected times. @KevinStefanov

fgrieu

3:28 PM

I expect m=2097152, t=1, p=2 or more to take a small fraction of a second on modern CPU with >2GiB effectively available memory and an optimized implementation.

I do not get your "transform a hundredth of a segment". Do you mean the one call to Argon2id did 1% of it's job in a minute? That would be slow. @KevinStefanov

Kevin Stefanov

it did 1% of a segment, and there are 4 segments per lane, all lanes being done in parallel by p threads

m=209715 or 2097152?

fgrieu

2097152, sorry. Fixed now.

Kevin Stefanov

I think it could be that my implementation is not optimal and has performance bottlenecks. I already profiled it with GNU Profiler

Weird, 91% of the time was spent in my uint64_roll_right()

fgrieu

Does it pass test vectors? For something that does, in C and compiled without debug or instrumentation, I would not expect that kind of slowness.

Kevin Stefanov

Yes, I got the same result as the RFC test vector for 1 pass

Further passes were wrong for me, but we're only doing 1 pass here, so it should work fine

See, 91% of the time was spent in my uint64_roll_right()

394 seconds did like 0.1% of the total Argon2 work

I definitely have a performance bottleneck somewhere, gotta figure out where

fgrieu

3:49 PM

I don't see any test vector with 1 pass in the RFC. I see results after 1 pass, but not the final output.

Kevin Stefanov

yes my result after pass 1 matched the results in the RFC. After pass 2 they stopped matching. I have a good idea why, if you remember we talked a bit about the ambiguous description of part of the algorithm in the RFC and we tried contacting the authors about it but they never got back to me.

The RFC tells you to access index [-1] of an array, they say "use the previous entry to calculate J for the next entry", but the entry we're calculating for is already index [0], so there's no "previous entry" to use in that case. I never understood exactly what they meant for an implementer to do in this case.

but that's only for passes after the first pass, and my first pass result matched the RFC test vector, and we're only doing 1 pass here so that shouldn't be an issue

fgrieu

OK. As you state it, index[-1] could well be the last index of the array; that's customary in python. But I agree it does not matter. What matters (to correctness, not speed) is that you have not tested the tag production code.

What if you change uint64_roll_right to the standard macro (fixed)?

#define uint64_roll_right(v,n) ((uint64_t)(v)>>(n)|(uint64_t)(v)<<(64-(n)))

At least you won't be spending ANY time into a function with that name! And most modern compilers will recognize the idiom.

Kevin Stefanov

Let me try

n is the number and v is the amount by which we roll?

fgrieu

no, the other way around.

If it's sure that v is an uint64_t, the two (uint64_t) can be removed.

Kevin Stefanov

okay

Crap hahaha

I had it with a pointer to the number, thats why, hold on

#define uint64_roll_right(v,n) (*(v)>>(n)|*(v)<<(64-(n)))

should be like this since I was passing a pointer to the number

Okay, with this macro it's so much faster

but still abysmally slow

[3] 99.6 0.00 27.14 1028 argon2_getJ1J2_for2i [3]

okay so now 99% was in computing J1 and J2

I knew it. I'm doing a whole bunch of dynamic allocations and deallocations there

Then we compute:

q/(128*SL) 1024-byte values
G(ZERO(1024),G(ZERO(1024),
Z || LE64(1) || ZERO(968) )),
G(ZERO(1024),G(ZERO(1024),
Z || LE64(2) || ZERO(968) )),... ,
G(ZERO(1024),G(ZERO(1024),
Z || LE64(q/(128*SL)) || ZERO(968) )),

which are partitioned into q/(SL) 8-byte values X, which are viewed
as X1||X2 and converted to J_1=int32(X1) and J_2=int32(X2).

This part of the RFC is what's slowing me down now.

I think if I precompute the size of the memory block it needs, and pass a pointer to it and clear it each call to argon2_getJ1J2_for2i(), it might speed it up. But it needs a huge speedup still, I don't know if eliminating malloc() and free() calls will provide that big of a boost.

fgrieu

4:15 PM

If you trust me: anything that's called more than a hundred times per second must not allocate memory, except perhaps on the stack (local variable, preferably with constant size). Anything that's called more than 10 thousand times per second must be replaced by a macro, or made inline with a compiler that honors that.

Kevin Stefanov

:O

Yes I definitely trust you haha

hmm it was called 1024 times for 27 seconds

Argon2_P, Argon2_G, Argon2_GB are the ones that are called millions of times

Flat profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
59.28 16.16 16.16 2354832 0.01 0.01 Argon2_G
33.00 25.16 8.99 309896578 0.00 0.00 Argon2_GB
7.34 27.16 2.00 40233878 0.00 0.00 Argon2_P
0.15 27.20 0.04 485 0.08 0.09 Montgomery_MUL
0.11 27.23 0.03 1158 0.03 0.03 bigint_sub2
0.07 27.25 0.02 59680 0.00 0.00 bigint_equate2

so I got this

hold on, it will look better in a screenshot

okay, so I should focus on optimizing my Argon2_G(), Argon2_GB() and Argon2_P()

fgrieu

Optimizing an Argon2id implementation is something I never did. I believe it's hard, especially if starting from the RFC rather than some reference code that already does one hard thing: defining data structures that reduce operations to a bare minimum.

Kevin Stefanov

Well, it's one more challenge I can talk about and be proud of completing

I love optimizing

okay so here's what I concluded from the GPROF report:

fgrieu

By my rule of thumb, Argon2_GB() is a prime candidate for optimization. What if you just declare it inline and insure the compiler honors that (which in my experience is straight antagonist with the kind of profiling tool that you use).

I have had good result with __forceinline instead of inline, but YMMV.

Kevin Stefanov

Of the 27 seconds runtime (to do a very small part of the whole Argon2id work):
- 59% of the time was spent in 2 million calls to my Argon2_G()
- 33% of the time was spent in 309 million calls to my Argon2_GB()
- 7% of the time was spent in 40 million calls to my Argon2_P()

fgrieu

4:29 PM

Yes. See above

Kevin Stefanov

I see

my GB contains only builtin addition, XOR and the uint64_roll_right

no allocations or fancy function calls

Oh wow, my G() has a lot of allocations and free()s

and a lot of memcpy()'s too

Definitely my Argon2_G() is the first target

fgrieu

Does Argon2_GB() use pointers for it's parameters ? These kill optimizations. __forceinline may fix this at low effort.

Kevin Stefanov

Yes, I pass 4 pointers to uint64_t

So I need to put __forceinline at the beginning of the function signature?

Part of GB() is to take the first 32 bits of the uint64_t's, so im still going to need to cast them to a pointer to uint32_t, no?

in GB() there are 4 sets of operations, each containing 3 sub-operations, the first of the 3 is an addition and one of its operands is the 32 least significant bits of uint64_ts

All the malloc()s and free()s in my G() are also slowing things down I think.

github.com/tectonicboy/Rosetta-Secure-Texting/blob/main/src/…

Line 498 is where my Argon2 implementation begins

First 3 functions are GB(), P() and G()

exactly the ones I need to optimize

I need to get rid of the allocations and deallocations in G() somehow, for sure

fgrieu

Uh, that code for Argon2_GB() does endian-dependent pointer casts which makes it non-portable, and often kills optimizations. And I think getting the low-order 32-bit is best done with a cast like (uint32_t). Also, for multiplication, only one of the two arguments needs to be cast from 32 bits to 64 bits. And since you pass pointers, the compiler may have trouble realizing they never point to the same thing.

Macros woudl allow a much cleaner implementation, without any pointer, solving all these issues.

Kevin Stefanov

I see

so I should replace G() and GB() with macros?

or just try inline or passing to GB() uint64_t themselves instead of pointers?

fgrieu

4:47 PM

For Argon2_GB() I think so, with the macro passed a rather than &a. That's safer (from the standpoint of having the compiler generate good code) than even __forceinline, depends much on compiler and settings.

Kevin Stefanov

I'm using GNU C compiler

with -march=native to allow the usage of the intrinsics we used for Montgomery

fgrieu

That will depend on version, and how it's called. If you use an IDE for the profiling, it might tamper with the settings, like -O3.

Kevin Stefanov

I just used gprof

fgrieu

gprof requires tampering with the compiler setting IIRC.

I read it's only for programs that are compiled with the -pg option of "cc", "pc", and "f77"

And that -pg Generate extra code to write profile information suitable for the analysis program gprof.

Kevin Stefanov

Yes

fgrieu

5:00 PM

grpof is useful. but ultimately, hard core optimisation should be with a fully optimized excutable, either externally timed, or that times itself (that's not hard to add).

Kevin Stefanov

-O3 and -O2 make my code act weird, crashing with segfaults and getting weird warnings

fgrieu

That's not supposed to happen. The only two explanations are supposed to be a deviation of the C cannon in the code compiled, or a bug in the compiler.

Kevin Stefanov

okay so:
- Try replacing G() and GB() functions with macros
- pass uint64_t themselves to GB() instead of pointers
- remove allocations in G()

fgrieu

@KevinStefanov Right. Plus try to find why -O2 has adverse effects. That's a really bad sign.

Kevin Stefanov

even -O1 gives the weird warning

fgrieu

5:05 PM

I have had good results compiling the same code with various compilers (especially clang, sometime tcc) with warnings enable, and examining the warnings.

Kevin Stefanov

okay

you know what? It was my mistake

I was copying my old code for testing Argon2, where it had 32-byte password

now for my chat app it will be up to 16 bytes, but I forgot to change the memset() to 16 too, so it was setting 32 bytes in the new 16 byte buffer

thats why it gives the warning

I also forgot to setup the new Salt and Password buffers

My bad. I think Im tired or something

fgrieu

That warning you show seems pretty clear there's a risk of memory overflow. I'd look at the call chain.

Ah glad you found an explanation.

Kevin Stefanov

I will finish setting up the Argon2 call and if it's still that slow, I will try to optimize with the steps you told me and let you know where I get to!

fgrieu

Good compiler's warnings must not be ignored!

C U!

Kevin Stefanov

yup

Transcript for

Room for Kevin Stefanov and fgrieu