Support 96 bit "sequence" in aead_init

[huitema]

AEAD encryption requires a new nonce for each message. The current code obtains that by mixing the variable length IV with an 8 bytes "sequence number". There are scenarios in which a longer "sequence number" is needed, e.g.:

1. Scenarios in which the sequence number is picked at random. The birthday paradox predicts 50% chances of key collisions if more than 2^32 messages are encrypted, which is not a very large number.

2. Scenarios in which the message numbers belong to several different "number spaces". In that case, the nonce should be derived from both the identifier of the number space and the sequence number itself.

Technically, all AEAD algorithms support at least a 12 byte IV, so it would make sense to update the API and allow at least 12 bytes. The current definition is:

void (*do_encrypt_init)(struct st_ptls_aead_context_t *ctx, uint64_t seq, const void *aad, size_t aadlen);

A revised definition could be either:

void (*do_encrypt_init)(struct st_ptls_aead_context_t *ctx, uint32_t seq_space, uint64_t seq, const void *aad, size_t aadlen);

Or:

void (*do_encrypt_init)(struct st_ptls_aead_context_t *ctx, const void * seq, size_t seq_len, const void *aad, size_t aadlen);

I am willing to prepare a PR for that, but maybe we should discuss the issue first.

[kazuho]

Thank you for opening the issue. I agree that we need to solve this problem, and we have to decide the design to adopt.

I think there are three choices. Option a and b are what you have suggested.

Option a) Create variants of ptls_aead_encrypt_init, ptls_aead_encrypt_init, ptls_aead_decrypt that accept nonce as uint128_t (or some integer that is greater than 64 bits). It is a natural extension of our existing API, but the downside is that we cannot support AEAD algorithms with N_MAX > 16.

Option b) Create variants of ptls_aead_encrypt_init, ptls_aead_encrypt_init, ptls_aead_decrypt that accept full-size nonce as vectors. This is a natural way of reflecting the model specified in RFC 5116. Length of the nonce does not have to be

Option c) Create a separate function that sets the full nonce to ptls_aead_context_t. To give an example, when sending multipath QUIC datagrams using CID n, the sender will do something like:

// prepare a vector used to update 
uint8_t iv[aead->algo.iv_size] = {0};
store_bigendian_uint32(iv + sizeof(iv) - 8, n);
ptls_aead_set_iv(aead, iv);
ptls_aead_encrypt(...);

Actual nonce that is being used can be an XOR of the full nonce being set and the sequence number being passed. Upside of this approach is that we do not need to create variants for every function, and that we can retain the optimized handling for 64-bit sequence numbers. The downside is that it might be confusing to have two ways of setting the nonce (i.e. set_iv function and the sequence number).

@huitema What do you think? I am slightly leaning towards option c, but would like to hear your thoughts.

[huitema]

I have two concerns: the workflow, and the stability of the code. The workflow is:

1. Once: Set key and IV based on secret
2. For each packet: Set nonce based on IV and sequence number for packet; encrypt (or decrypt) packet.

Currently, (*do_encrypt_init) does the set up of the nonce. The IV does not change. In your proposal, the IV would change (XOR with 32 bit ID). So maybe you would need something like:

1. Once: Set key and IV based on secret
2. For each packet:
   2.1) Modify IV in place (XOR with 32 bit ID)
   2.2) Perfom do_encrypt_int, do_encrypt, etc.
   2.3) Restore IV to previous value.

The 3 steps can indeed be wrapped in a single API, something like "ptls_encrypt_with_extra_32bits(aead, unit32_t x, ...).

Is that what you have in mind?

[kazuho]

@huitema Yes, what option c is something along those lines.

Yeah, I think my distaste against using vector as the only way of passing the nonce is that it requires endian conversion twice when using an optimized cipher like fusion (because AESNI uses little endian; I'm not sure about ARMv8).

I wouldn't have opposed to changing seq to a 128-bit value and calling it a day, though it is my understanding that MSVC does not support uint128_t.

Maybe I need to work on actually writing down something to see if there's a good way forward.

[huitema]

I sort of like option C, because I don't want to change the implementations of the AEAD algorithms. If we do change it, it would make sense to separate "set nonce" from "init and encrypt".

[kazuho]

So as to make progress in small steps, I wrote 42cd35a. It's only for the openssl backend, I've not tested the code, though.

With the patch, when you send something, you would do like:

// permute the upper 32-bits of static IV to include the CID sequence number
uint8_t nonce_upper32[4];
store_bigendian_uint32(nonce_upper32, (uint32_t)cid.seqnum);
ptls_aead_xor_iv(aead, nonce_upper32, sizeof(nonce_upper32));

// use the existing AEAD code to supply the lower 64-bits
ptls_aead_encrypt(aead, packet_number, ...);

// reset the upper 32-bits of static IV
ptls_aead_xor_iv(aead, nonce_upper32, sizeof(nonce_upper32));

This API is a terrible hack, but maybe we can start from here.

[huitema]

@kazuho please check PR #331

[huitema]

The API is OK. It is a compromise between performance and code complexity. If people are really concerned about performance for multipath, they can create and maintain a separate aead context for each path ID.