Subject: [Cfrg] PAKE review

From: Brian Warner <[email-masked]>
Date: Thu, 15 Aug 2019 10:38:55 -0700

Dear CFRG,

Nick Sullivan asked me to participate in the PAKE selection process. My
specific use case is a tool/protocol I've developed named "Magic
Wormhole" (https://github.com/warner/magic-wormhole/), which uses PAKE
to let two humans introduce their computers to each other, for the
purpose of transferring a file, text message, or other secrets. I'm
encouraging its use as a provisioning protocol, to connect two
applications without the use of long-term human-memorized passwords. For
example, two users of a secure messenger could use it to safely exchange
their public keys and other address-book data by just speaking and
transcribing a short single-use phrase.

The magic-wormhole protocol currently uses SPAKE2 (a symmetric PAKE) on
an Ed25519 group, with an additional form of symmetry: the two sides do
not have to decide ahead of time which role they are playing. In SPAKE2
terms, the "M" and "N" elements are equal, which saves a roundtrip. This
program was inspired by work I did on Firefox Sync, back when it used
J-PAKE pairing codes (around 2009) to connect two browsers owned by the
same user.

Nick suggested that I might be able to help evaluate the four symmetric
PAKE nominations, both for their applicability to other contexts, but
particularly for magic-wormhole and other "provisioning" -style
applications, in which the codes are randomly generated and single-use.
I think augmented PAKEs are great, but they aren't as useful for these
kinds of protocols.

I'm happy to help out any way I can.

cheers,
 -Brian

---

From: Björn Haase <[email-masked]>
Date: Sat, 17 Aug 2019 15:08:54 +0200

Dear Brian,

>terms, the "M" and "N" elements are equal, which saves a roundtrip.

IIUC the proofs for SPAKE2 assume that "M != N" but this most probably could be addressed by a somewhat modified security proof. IMO it should suffice to blind one of the Diffie-Hellman points: IIRC this is also what is done in the PAK-Family of protocols.

When using this approach in a product, I'd recommend you to have a look on the patent applications/patents on the PAK protocol family. Using distinct M and N and blinding two points might have been one component necessary/helpful for the patent circumvention strategy that was in mind when designing the SPAKE2 construction.

Yours,

Björn.

---

From: Björn Haase <[email-masked]>
Date: Sat, 17 Aug 2019 16:41:56 +0200

Dear Brian,

as a starting point for an assessment of the patent situation, it might
be worth to have a look at the valid US patent US 7,047.408 B1 which has
the following first claim:

"We claim:

1. A method for communication via a data network, between two parties
that share a password, using a Diffie Hellman type key exchange on a
particular group to generate a shared secret g', where g is the group
generator known to 5 both parties and X is an index known to one party
and y is an index known to the other party, said group having a group
operation and an inverse group operation, said method comprising the
steps of one party generating a parameter m by performing the 10 group
operation on g and a function of at least said password, and
transmitting m to the other party, whereby the other party may perform
the inverse group operation on m and said function of at least said
password to extract g and further calculate said shared 15 secret g”.

In my opinion even un-modified SPAKE2 might be covered by this Lucent
patent!

I recall that some years ago we identified some patent issue that drew
us away from SPAKE2 and towards the PACE patent circumvention approach
for SPEKE-like constructions. We never actually analyzed the patent
situation for SPAKE2 and PAK in more detail, given that we had a more
efficient alternative ...

Yours,

Björn.

Am 17.08.2019 um 15:08 schrieb Björn Haase:
> IIUC the proofs for SPAKE2 assume that "M != N" but this most probably
> could be addressed by a somewhat modified security proof. IMO it
> should suffice to blind one of the Diffie-Hellman points: IIRC this is
> also what is done in the PAK-Family of protocols.
>
> When using this approach in a product, I'd recommend you to have a
> look on the patent applications/patents on the PAK protocol family.
> Using distinct M and N and blinding two points might have been one
> component necessary/helpful for the patent circumvention strategy that
> was in mind when designing the SPAKE2 construction.
>
> Yours,
>
> Björn.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg