Re: [Cfrg] Re-review of the four balanced PAKEs

"Quantum Annoying" was something Steve Thomas coined (IIRC).

It means you have to break an ECDLog problem per attempt. It's O(n) rather
than O(1).

It's not quite post-quantum resistance (where each attempt requires
breaking PQ crypto algorithms). But it does make attacks "annoying" if a
quantum computer is ever developed.

BSPAKE is argued to be quantum annoying. OPAQUE is not. I like both designs.

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com>

On Thu, Oct 24, 2019 at 12:13 PM Paul Grubbs <pag225@cornell.edu> wrote:

> Hey Scott, thanks for your comments. I have a couple questions:
>
> 1. Regarding SPAKE-2, you said this
> > the issue still remains that if someone were to be able to solve a
> single ECDLog problem, they could then perform an on-line dictionary attack
> against anyone using that parameter set.
> I don't quite understand what you mean - can you explain this on-line
> dictionary attack? In general, aren't all PAKEs vulnerable to online
> dictionary attacks?
>
> 2. This 'quantum annoying' property is the subject of much CFRG
> discussion, but it seems ill-specified. Can you explain it in a bit more
> detail, maybe by example (e.g., why does CPace have 'good' quantum
> annoyance)?
>
> On Thu, Oct 24, 2019 at 11:23 AM Scott Fluhrer (sfluhrer) <
> sfluhrer@cisco.com> wrote:
>
>> I re-reviewed the four balanced PAKEs, looking at the more practical
>> issues.
>>
>>
>>
>> Summary: it comes down to the choice between CPace and SPAKE-2 (J-PAKE
>> can be discounted because of the extra round trip needed, and the expense;
>> SPEKE can be discounted because of the lack of a single proposal (and the
>> single proven one is no better than CPace).
>>
>>
>>
>> SPAKE-2 is better than CPACE in the sense that it is a single round
>> protocol (and so can be used as a drop-in replacement for DH, assuming some
>> hooks for exchanging identities), and so would be slightly easier to use in
>> a protocol; CPACE requires a key confirmation to be sent after the exchange
>> (possibly along with the first encrypted message).  On the other hand, I
>> wouldn’t expect that a protocol would have a major issue with the extra
>> message that CPACE requires.
>>
>>
>>
>> SPAKE-2 is better in that it uses only standard (point multiplication)
>> operations, which are more likely to be implemented in crypto libraries in
>> constant time.  CPACE requires a hash-to-curve operation; it is less likely
>> that a crypto library has a constant time implementation of that available.
>>
>>
>>
>> SPAKE-2 is better in that it uses somewhat less message overhead (two
>> hashes less).  However, even with this additional overhead, CPACE is still
>> quite reasonable (perhaps 128 bytes total, not counting overhead).
>>
>>
>>
>> SPAKE-2 (as specified in the RFC) is worse than CPACE in that it relies
>> on global M and N parameters.  While the M and N values in the SPAKE-2 RFC
>> are claimed to be generated in a NUMS manner, the issue still remains that
>> if someone were to be able to solve a single ECDLog problem, they could
>> then perform an on-line dictionary attack against anyone using that
>> parameter set.
>>
>>
>>
>> In terms of other practical issues (computation, message overhead), they
>> are mostly identical.
>>
>>
>>
>> My opinion is that CPACE is better, the single disadvantage that SPAKE-2
>> has (vulnerable if someone somewhere solves just one ECDLog problem) is
>> worse than the three disadvantages of CPACE.
>>
>>
>>
>>
>>
>> A more detailed listing of the comparison:
>>
>>
>>
>>
>>
>> * Fragile is you give an attacker offline password guessing if there is a
>> minor error in the implementation of ECC.
>>
>> * Quantum annoying (“PQ-ish”) is the property that an attacker with a
>> quantum computer needs to solve a DLP per password guess.
>>
>>
>>
>> Balanced PAKE summary
>>
>> Name              | PQ-ish   | Rounds*       | Fragile
>>
>> ------------------+----------+---------------+---------
>>
>> CPace             | Good     | 1.5 (1/2)     | Moderate**
>>
>> J-PAKE            | Bad      | 2   (2/2)***  | Good
>>
>> SPAKE-2           | Bad      | 1   (1/1)     | Good
>>
>> SPEKE (EC based)  | Good     | 1   (1/1)**** | Moderate**
>>
>> SPEKE (ModP based)| Moderate | 1   (1/1)**** | Good
>>
>>
>>
>> * "number of total trips" ("number of messages received before initiator
>> can encrypt"/"number of messages received before responder can encrypt")
>>
>> ** CPace and SPEKE (EC) is listed as moderately fragile because they
>> depend on a hash-to-curve operation based on the secret password; a timing
>> variation there might leak the secret.  While constant-time hash-to-curve
>> algorithms are known, they are less common than standard EC operations, and
>> hence this needs to be considered.
>>
>> *** This assumes that we use the three-pass variant, and we do use the
>> recommended key confirmation.
>>
>> **** Note that SPEKE claims to be secure without an explicit key
>> confirmation pass; we assume the “Patched SPEKE” protocol found in the
>> paper.  See my concerns about this below.
>>
>>
>>
>> Balanced PAKE summary (continued)
>>
>> Name              | Comp per side (*) | Total Message Size (**)
>>
>> ------------------+-------------------|------------------
>>
>> CPace             | H+2x              | 2P+2H
>>
>> J-PAKE            | 2g+3x+3pg+3pv     | 6P+4Z+2H
>>
>> SPAKE-2           | d+x               | 2P
>>
>> SPEKE (EC based)  | H+2x              | 2P
>>
>> SPEKE (ModP based)| 2M                | 2M
>>
>>
>>
>>
>>
>> * In all cases, the initiator and the responder perform the same overall
>> amount of computation, hence we don’t break it down per side.  In addition,
>> we omit the costs of hashes, point additions, modular multiplications, as
>> they are expected to be insignificant compared to the point
>> multiplications/modular exponentiations listed.
>>
>> ** Note that none of the protocols are defined in bits-on-the-wire
>> format; there are likely to be some additional overhead (such as identities
>> and nonces) exchanged, but those are not listed.  This additional overhead
>> would appear to be likely to be similar for all the candidates.
>>
>>
>>
>> Cost:
>>
>> H: Hash to point
>>
>> x: Point multiplication
>>
>> g: Point multiplication of the generator (which is potentially cheaper
>> than a point multiplication of an arbitrary point)
>>
>> d: Double scalar point multiply and add, that is, aB + cD
>>
>> pg: Zero knowledge proof generation (approximately the same as a field
>> multiplication)
>>
>> pv: Zero knowledge proof verification (approximately the same as a double
>> scalar point multiply and add)
>>
>> M: Modular exponentiation
>>
>>
>>
>> Message Size:
>>
>> P: An elliptic curve point
>>
>> H: A hash
>>
>> Z: A zero knowledge proof (an elliptic curve point plus an integer the
>> size of the group)
>>
>> M: An integer of the size of the DH group
>>
>>
>>
>> Notes:
>>
>>
>>
>>    - In general, none of these proposals are defined at the level that I
>>    believe that the CFRG needs.  Most of them do not document bits-on-the-wire
>>    format, or call out required error checking.  I believe that we need to
>>    generate a sufficiently detailed protocol that could be inserted as a
>>    blackbox into real protocols; whichever we pick, there’s some work required
>>    before we get to that point.
>>    - As a reminder, if we go with the SPAKE-2 option, someone would need
>>    to verify the generation of the M and N values specified in the RFC.  I was
>>    able to do a partial validation (which looked good); however, I was unable
>>    to accomplish a complete one.
>>    - The more recent SPEKE paper (https://eprint.iacr.org/2014/585.pdf)
>>    claims that they don’t need an explicit key confirmation step, however I
>>    find their argument unsatisfying.  The claim appears in section 5.3
>>    “Countermeasures and suggested changes to standards”; they give several
>>    suggestions in this section, and it is unclear which is being proposed.
>>    They state that, in the case of multiple concurrent negotiations, the two
>>    sides should use distinct identifiers for each one (e.g. “Alice-1” for the
>>    first session, “Alice-2” for the second); that has obvious practical
>>    problems in the case that the two sides don’t agree on which session is the
>>    first.  In addition, the relevant text is:
>>
>> As long the user identiﬁers are unique between concurrent sessions, the
>> use of the extra session identiﬁer *does not seem* needed. [emphasis
>> added]
>>
>> They give no proof as to the above statement.  This lack of rigor, and
>> the lack of a single concrete proposal leads me to discount SPEKE as a
>> desirable proposal
>>
>>
>>
>>    - Reasoning behind Quantum Annoying statements:
>>       - J-PAKE is not Quantum Annoying, computing three discrete logs
>>       would allow an adversary to perform an off-line dictionary search for the
>>       password (that is, on a recorded session).  In addition, if the password is
>>       known, three discrete logs are sufficient to recover the shared secret on a
>>       recorded session.
>>       - SPAKE-2, as proposed, is not Quantum Annoying, a single discrete
>>       log of the global M (or N) parameters would allow an adversary to perform
>>       an on-line dictionary attack.
>>       - SPEKE (ModP based) is listed as moderate, as an attacker could
>>       attempt to compute a large number of discrete logs in an attempt to form a
>>       factor base (which would allow him to efficiently compute any discrete
>>       log).  However, the number of discrete logs required would be huge, and so
>>       this might not be a practical issue.
>>
>>
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>