Ordering requirements/flexibility in PAKE operations

[athoelke]

At the moment the PAKE operations for J-PAKE and SPAKE2+ present an ordering of the calls to the API to perform the PAKE protocol. However, the specification is not clear about whether these are strict requirements relating to the call sequence (which restricts the application behavior), or if there is some flexibility.

There seems to be a reasonable case for documenting where an implementation must provide some flexibility in the ordering, to satisfy application use cases; as well as making it clear where the ordering is essential to preserve the correct operation and protocol behavior.

J-PAKE

As an example of where flexibility would be valuable for applications, consider J-PAKE being conducted between participants A and B, trying to minimize the number of messages. (The following description refers to steps as numbered in p40-42 of the Beta.2 Release candidate PDF in #141)

• A sets up a PAKE operation (step 1 in the specification) and extracts the six round-1 output values (step 2).
• A then sends these values to B.
• When B receives the message from A, it sets up its own PAKE operation (step 1). What happens next:
  • MUST B extract the six round-1 outputs (step 2), and only then provide the six round-1 inputs received from A (step 3)? - OR
  • Is B permitted (instead) to first provide the six round-1 inputs received from A (step 3), and then extract the six round-1 outputs (step 2)?
• B now also extracts the six round-2 outputs (step 4).
• B sends all of its round-1 and round-2 outputs to A.
• When A receives the message from B, it MUST input the round-1 values (step 3) before extracting the six round-2 values (step 4), as the latter are [computationally] dependent on the round-1 inputs. However:
  • MUST A extract the six round-2 outputs (step 4), and only then provide the six round-2 inputs received from B (step 5)? - OR
  • Is A permitted (instead) to first provide the six round-2 inputs received from B (step 5), and then extract the six round-2 outputs (step 4)?
• A sends its round-2 outputs to B.
• When B receives the message from A, it inputs the round-2 values (step 5).
• Both A and B can now extract the shared key (step 6)

From an application point of view, it is helpful to be able to input data received in a message before extracting data to send in a reply - even when the outputs do not depend on the inputs. I.e. Application developers would benefit from the flexibility to carry out step 3 before step 2, and/or step 5 before step 4; note that the API depends on inputs being provided in-order (step 2 before step 4), and outputs extracted in-order (step 3 before step 5), and the protocol requires step 3 before step 4, and steps 4 and 5 before step 6.

SPAKE2+

There is a similar issue for SPAKE2+. In this case the flow in the specification (p48-51) shows the round-1 shareP from the Prover/Client being input the Verifier/Server operation before extracting the Verifier round-1 shareV. Is this ordering mandated, or can the Verifier application extract shareV before input of shareP?

There is another related issue for SPAKE2+, although in this case, the argument is about which participant might need more protection against online dictionary attacks. The operational flow (in p48-51 of the same document) matches the SPAKE2+ RFC, where it shows a 3-message protocol, where shareV and confirmV are transmitted together by the Verifier/Server. It can be imagined that for some uses of the SPAKE2+ algorithm, it is more important to protect the Verifier/Server from an online dictionary attack, and have the Prover/Client send it's confirmP value to the Verifier before the Verifier sends confirmV. In that case, the Prover operation must be output confirmP, before confirmV is input (in contrast to the order shown in the specification).

[bheeb]

In general, allowing more flexibility than really needed adds considerable complexity to the library implementation and might need additional buffering memory.

J-PAKE
B should be allowed to input the received data before it outputs the data for the next round.
This simplifies the client implementation and does not add complexity in the library.
So the permitted sequences of steps should be:
1-2-3-4-5-6
1-3-2-4-5-6
1-2-3-5-4-6
1-3-2-5-4-6

SPAKE2+
Swapping shareP input and shareV output on server side is hardly justified here. Any activity on server side is triggered by the shareP message. It is therefore always better to input shareP before outputting shareV. Allowing to swap shareP and shareV is hard to implement and adds buffer memory because the sequence of the two in the TT hash is fixed.
swapping confirmV and confirmP is technically feasible but it is still questionable whether the additional effort is justified given the fact that shareV and confirmV are usually transferred in the same data packet.

[athoelke]

swapping confirmV and confirmP is technically feasible but it is still questionable whether the additional effort is justified given the fact that shareV and confirmV are usually transferred in the same data packet.

That is a fair point - given that the RFC, and the Matter protocol both show/use a 3-message flow, there is reasonable justification for requiring that the Verifier application outputs confirmV before it inputs confirmP.

If a SPAKE2+-based protocol variation is used in future, that requires 4 messages, in order to ensure that the Verifier checks confirmP, prior to sending confirmV - then we could implement this in the API as a new PAKE algorithm identifier.

What about the Prover side?

On the Prover side, the specification currently shows a slightly different flow in the sequence diagram (page 49: output confirmP before input confirmV), to the text description/demonstration of the flow (page 50: input confirmV before output confirmP).

Does your implementation rely on a specific ordering? - if so:

• Which ordering is used?
• Is requiring this sequence from the Prover application both a natural ordering and a justifiable constraint?

[bheeb]

The 3 message - 4 message question is the same on Prover and Verifier side.
If we fix the sequence to
output confirmV - input confirmP
on Verifier side, we should fix it to
input confirmV - output confirmP
on Prover side.

The flow diagram on page 49 should be changed to consequently use the 3 message variant. Currently it shows the message flow of the 3 message variant but the Prover call sequence of the 4 message variant. This is confusing and such an implementation hardly makes sense.
The call sequence on page 50 is OK and should be the only one allowed.
There is, however, a small typo there: The comment in the last Verifier block should be "// Set confirmP".

[athoelke]

The flow diagram on page 49 should be changed to consequently use the 3 message variant. Currently it shows the message flow of the 3 message variant but the Prover call sequence of the 4 message variant. This is confusing and such an implementation hardly makes sense.

The diagram only shows three messages. I think the ordering of inputs and outputs in the Prover probably arose because there is no computation dependency between confirmP and confirmV, so "why not?". The RFC states that all of the shared secrets and confirmation keys can be computed once both participants have shareP and shareV, prior to confirmation.

However, the RFC states that the Prover MUST verify the confirmation message from the Verifier prior to sending confirmP. If the API is relaxed to permit the Prover to output confirmP prior to input of confirmV, then it becomes possible to create a Prover application that does follow the RFC and is vulnerable to an online-dictionary attack (which is not the case if confirmV must be input first).

Thank you - I think there is enough justification to constrain the application and implementation to precisely the flow on page 50, and thus change the flow shown in the sequence diagram on page 49.