Seconded. I am immediately fascinated by this game.

---

score 1 · canonical

How do you do the sync point in C99?

That’s the thing: I don’t.

The constraints for Monocypher are more or less, dependable C with zero dependencies. For me that’s C89 with volatile, // style comments, and declaring local variables anywhere. My only dependencies are stddef.h and stdint.h, from which I take size_t and the fixed size integers. I have no explicit runtime dependency, not even LibC — though compilers do sometime turn a loop of mine into a memcpy(3) call.

There’s not much I can do under such drastic constraints:

• No networking.
• No I/O.
• No explicit program aborts.
• No heap allocation.
• No multi-threading.

Monocypher does not, and will not, do multithreading. Only support it.

---

The code you see above is what I plan to ship:

• A toolkit for users to write their own implementation of Argon2.
• An single-thread implementation that uses that toolkit. The comments there aren’t pseudocode, they’re just comments, meant to document how one may parallelise Argon2.

Basically, Monocypher will “support” multi-threading by leaving it as an exercise to the user. That’s cheating, I know, but as far as I can tell multi-threading is the easy part. Here’s my pthreads code, minus error handling to reduce clutter:

#include <monocypher.h>
#include <pthread.h>
#include <stdlib.h>

typedef struct {
	pthread_t          thread;
	pthread_barrier_t *barrier;
	crypto_argon2_ctx *ctx;
	uint32_t           lane;
} thread_data;

static void *argon2_lane(void *ptr)
{
	thread_data *data      = ptr;
	uint32_t     lane      = data->lane;
	uint32_t     nb_passes = data->ctx->config.nb_passes;
	for (uint32_t pass = 0; pass < nb_passes; pass++) {
		for (uint32_t slice = 0; slice < 4; slice++) {
			crypto_argon2_segment(data->ctx, pass, slice, lane);
			pthread_barrier_wait(data->barrier);
		}
	}
	return NULL;
}

static int argon2_phtreads(uint8_t *hash, uint32_t hash_size,
                           crypto_argon2_config config,
                           crypto_argon2_inputs inputs,
                           crypto_argon2_extras extras)
{
	size_t       work_size = config.nb_blocks * 1024;
	size_t       data_size = config.nb_lanes  * sizeof(thread_data);
	void        *work_area = malloc(work_size);
	thread_data *lane_data = malloc(data_size);

	crypto_argon2_ctx ctx;
	crypto_argon2_init(&ctx, hash_size, work_area,
	                   config, inputs, extras);

	pthread_barrier_t barrier;
	pthread_barrier_init(&barrier, NULL, config.nb_lanes);

	for (size_t lane = 0; lane < config.nb_lanes; lane++) {
		lane_data[lane].barrier = &barrier;
		lane_data[lane].ctx     = &ctx;
		lane_data[lane].lane    = lane;
		pthread_create(&lane_data[lane].thread, NULL,
		               argon2_lane, lane_data + lane);
	}
	for (size_t lane = 0; lane < config.nb_lanes; lane++) {
		pthread_join(lane_data[lane].thread, NULL);
	}
	pthread_barrier_destroy(&barrier);

	crypto_argon2_final(&ctx, hash);
	free(work_area);
	free(lane_data);
	return 0;
}

I’ll need to add proper error handling, account for EAGAIN where appropriate, and perhaps add a couple asserts to guard the functions that are supposed to never fail. The result will go to the user manual, for users to copy & paste, or adapt to their own multi-threading API.

---

I use a similar approach with EdDSA, by the way. In Monocypher3 I had direct support for an incremental signature API, but the only way I could make it work with both BLAKE2b EdDSA and Ed25519 was a full blows v-table. It did the job, but it ultimately proved very inflexible.

Then one day a company approached me to ad Ed25519ph to Monocypher. Pretty quickly it was clear to me that my incremental interface with swappable hash couldn’t do it. I had to take my source code apart to assemble what they needed. It took me but a day, which they graciously paid full rate for.

That work gave me an idea: what if instead of using a v-table to swap in the parts I want into the full algorithm, I instead cut the algorithm into coarse constituent parts, and then use those parts to assemble whatever variation of the algorithm I, or my users, may need? Sure it falls short of direct support, but who cares, as long as it gives us the capability?

I think I managed to make it work. Heres’ Ed25519 and Ed25519ph, from the toolkit and SHA-512:

void crypto_ed25519_key_pair(u8 secret_key[64], u8 public_key[32], u8 seed[32])
{
	u8 a[64];
	COPY(a, seed, 32);                      // a[ 0..31]  = seed
	crypto_wipe(seed, 32);
	COPY(secret_key, a, 32);                // secret key = seed
	crypto_sha512(a, a, 32);                // a[ 0..31]  = scalar
	crypto_eddsa_trim_scalar(a, a);         // a[ 0..31]  = trimmed scalar
	crypto_eddsa_scalarbase(public_key, a); // public key = [trimmed scalar]B
	COPY(secret_key + 32, public_key, 32);  // secret key includes public half
	WIPE_BUFFER(a);
}

static void hash_reduce(u8 h[32],
                        const u8 *a, size_t a_size,
                        const u8 *b, size_t b_size,
                        const u8 *c, size_t c_size,
                        const u8 *d, size_t d_size)
{
	u8 hash[64];
	crypto_sha512_ctx ctx;
	crypto_sha512_init  (&ctx);
	crypto_sha512_update(&ctx, a, a_size);
	crypto_sha512_update(&ctx, b, b_size);
	crypto_sha512_update(&ctx, c, c_size);
	crypto_sha512_update(&ctx, d, d_size);
	crypto_sha512_final (&ctx, hash);
	crypto_eddsa_reduce(h, hash);
}

static void ed25519_dom_sign(u8 signature[64], const u8 secret_key[64],
                             const u8 *dom,     size_t dom_size,
                             const u8 *message, size_t message_size)
{
	u8 a[64];  // secret scalar and prefix
	u8 r[32];  // secret deterministic "random" nonce
	u8 h[32];  // publicly verifiable hash of the message (not wiped)
	u8 R[32];  // first half of the signature (allows overlapping inputs)
	const u8 *pk = secret_key + 32;

	crypto_sha512(a, secret_key, 32);
	crypto_eddsa_trim_scalar(a, a);
	hash_reduce(r, dom, dom_size, a + 32, 32, message, message_size, 0, 0);
	crypto_eddsa_scalarbase(R, r);
	hash_reduce(h, dom, dom_size, R, 32, pk, 32, message, message_size);
	COPY(signature, R, 32);
	crypto_eddsa_mul_add(signature + 32, h, a, r);

	WIPE_BUFFER(a);
	WIPE_BUFFER(r);
}

void crypto_ed25519_sign(u8 signature [64], const u8 secret_key[64],
                         const u8 *message, size_t message_size)
{
	ed25519_dom_sign(signature, secret_key, 0, 0, message, message_size);
}

int crypto_ed25519_check(const u8 signature[64], const u8 public_key[32],
                         const u8 *msg, size_t msg_size)
{
	u8 h_ram[32];
	hash_reduce(h_ram, signature, 32, public_key, 32, msg, msg_size, 0, 0);
	return crypto_eddsa_check_equation(signature, public_key, h_ram);
}

static const u8 domain[34] = "SigEd25519 no Ed25519 collisions\1";

void crypto_ed25519_ph_sign(uint8_t signature[64], const uint8_t secret_key[64],
                            const uint8_t message_hash[64])
{
	ed25519_dom_sign(signature, secret_key, domain, sizeof(domain),
	                 message_hash, 64);
}

int crypto_ed25519_ph_check(const uint8_t sig[64], const uint8_t pk[32],
                            const uint8_t msg_hash[64])
{
	u8 h_ram[32];
	hash_reduce(h_ram, domain, sizeof(domain), sig, 32, pk, 32, msg_hash, 64);
	return crypto_eddsa_check_equation(sig, pk, h_ram);
}

It’s not trivial. It’s not even easy, which is why it (optionally) ships with Monocypher. But it’s possible: one can look at the Ed25519 and Ed25519ph specs, look at Monocypher’s API (which you will note hides away the elliptic curve stuff), and come up with pretty much this code.

Argon2 by contrast is genuinely easy. I’m very happy about that, because it removes a major weakness from Monocypher. With that, it will get the compatibility and security that comes with processing parallel lanes in parallel. (One thing that makes password hashing & key derivation so tricky, is how its security is directly proportional to the speed of its implementation.)

Now I need to do some vectorisation… In pure C99. Can’t have it all, but I did manage to get significant gains from auto-vectorisation alone. With any luck, I may even saturate the memory bus.

---

score 1 · canonical