Linear security policy look-up

[xonatius]

Problem:

In a lot of places, functions which check a property of a security policy do a linear scan in security policy list like here. These functions are called for every new connection and with the ever-growing list of policies this linear scan will be taking more and more time. Although it's still most likely takes negligible time to lookup it might be worth optimizing it at some point to a constant time lookup.

Solution:

A description of the possible solution in terms of S2N architecture. Highlight and explain any potentially controversial design decisions taken.

• Does this change what S2N sends over the wire? If yes, explain.
• Does this change any public APIs? If yes, explain.
• Which versions of TLS will this impact?

Requirements / Acceptance Criteria:

What must a solution address in order to solve the problem? How do we know the solution is complete?

• RFC links: Links to relevant RFC(s)
• Related Issues: Link any relevant issues
• Will the Usage Guide or other documentation need to be updated?
• Testing: How will this change be tested? Call out new integration tests, functional tests, or particularly interesting/important unit tests.
  • Will this change trigger SAW changes? Changes to the state machine, the s2n_handshake_io code that controls state transitions, the DRBG, or the corking/uncorking logic could trigger SAW failures.
  • Should this change be fuzz tested? Will it handle untrusted input? Create a separate issue to track the fuzzing work.

Out of scope:

Is there anything the solution will intentionally NOT address?

[ma-ilsi]

So we are guaranteed that for every struct s2n_security_policy there is exactly only one struct s2n_security_policy_selection in the struct s2n_security_policy_selection security_policy_selection[] array?

If so, for each policy we can add it's policy_selection index as a member of the struct. This gives constant look-up.
However, we might not want to maintain that rigid constant index being hardcoded. Imagine if the array shifts an element up or down...you will have to re-write every index in the corresponding structs.

Proposal: The security_policy_selection array is not constant! Check this out:

1. Assign a policy_selection_vindex member to every const s2n_security_policy struct.
2. Don't worry; just assign 0 to x and any new s2n_security_policys constants will need to have this member as x + 1 (where x is: ((total number of s2n_security_policy constant structs) - 1 ).
3. Items in the security_policy_selection array can be shifted around and re-ordered by engineers and it won't cause an incorrect index problem because...
4. We already loop through the security_policy_selection array in the s2n_security_policies_init function. In this loop that we always run through anyways, we will re-order the policies in the security_policy_selection array based on the virtual index of the corresponding s2n_security_policy struct.
5. The functions in the security policy API pass us an address to a s2n_security_policy, thus we simply change the linear loops @xonatius has pointed out to something like this: security_policy_selection[addr->policy_selection_vindex] (where addr is the s2n_security_policy address argument the API already currently receives) and we arrive at the correct array item, instantly.
6. Boom. Constant look-up.

If it sounds good I can start working on it.

[lrstewart]

@ma-ilsi Why not just include a pointer on s2n_security_policy instead of an index if you're going to rely on s2n_security_policies_init? Alternatively, just set the flag on s2n_security_policy instead of security_policy_selection so that no lookup is necessary.

[ma-ilsi]

Thank you for reading the write-up. These are engaging questions.

@ma-ilsi Why not just include a pointer on s2n_security_policy instead of an index if you're going to rely on s2n_security_policies_init?

You intend one of two things here:

1. Assigning a pointer member of s2n_security_policy within s2n_security_policies_init. This is not possible since s2n_security_policy structures defined internally are all constant. Pointers can instead be assigned at compile time, but see next point.
2. Or you intend that I should consider replacing the virtual/runtime index (Note: when I say "virtual/runtime index", I mean an index that is valid and correct in runtime, not necessarily correct at compile time) member of the struct with a pointer member that is assigned at compile time. This is worse than a virtual index since if you look at the organization of the security_policy_selection array, when you wish to insert a new s2n_security_policy_selection in to the array, it is very likely it will be inserted somewhere in the middle (as the array is organized in groups of related cipher selections) instead of the end of the array (which you can't anyways because the end of the array must always be the one with version =NULL, see _init loop). In this case, every element after the insertion will have a new index which means re-writing the pointer initializations in the structs that correspond to those elements' whose index changed. Whereas a virtual index insertion looks like: insert the new s2n_security_policy_selection in the array, and initialize the corresponding s2n_security_policy struct's virtual index member to the new length of the array (which is also the previous structs virtual index + 1). This is the overall idea but from an engineering perspective, the implementation of this would be to define these values in an enum, inserting to the end of the enum regardless of where you insert in to the security_policy_selection array, and simply using the enum constants as the initializers in the s2n_security_policy virtual/runtime index member. Very clean maintainable implementation especially since enums are automatically initialized 0 to x. (By the way, as I have mentioned previously, the actual index does not need to correspond to the virtual index. So the ordering of the enum does not need to match the ordering of the array which is what makes the index idea so maintainable in this specific case.) This is why my proposal chooses a virtual/runtime index over a pointer.

The reason of mentioning the _init function was to leverage it to re-order the array such that the virtual indices will point to the correct corresponding array element. It's a one time shift of elements, and it have to be done in a new loop after the original loop of _init.

Alternatively, just set the flag on s2n_security_policy instead of security_policy_selection

We can't. This flag (and the other pq_kem flag) is a mutable member and it gets initialized at runtime (which is why it is a member of the mutable s2n_security_policy_selection), whereas, thes2n_security_policys the code defines are all given the const type qualifier and all the members we declare are to be initialized at compile time.

so that no lookup is necessary.

The code suggests a lookup is always necessary against the "official list". This comment prefaces many routines that were written specifically for the case that the functions are passed a s2n_security_policy that could not be found in the security_policy_selection array. Yes, to me that is weird (I am not convinced, yet, that this code is ever reached) because here we make sure that the user was only able to select a policy that is from the "official list".
Regardless, my proposal aimed to work with the case analysis and always perform the look-up because the engineer who wrote that code/comment (which was you, haha) considered that not finding a match in the list to be a valid case. Which makes me want to support that case analysis instead of throwing it away, so I take it in to consideration and just perform a constant time look-up.