Re: [Cfrg] PAKE review / Patent situation for SPAKE2 as used in "Wormhole"

Björn Haase <> Sat, 17 August 2019 14:54 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6261112002E for <>; Sat, 17 Aug 2019 07:54:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, LOTS_OF_MONEY=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 7p3MxKsdHAFg for <>; Sat, 17 Aug 2019 07:54:52 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id C4E7B120048 for <>; Sat, 17 Aug 2019 07:54:51 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;; s=dbaedf251592; t=1566053686; bh=G9dPwziy46Rai1I77hAk5CJT2gCHgbMs1cPTJ5Fmi+c=; h=X-UI-Sender-Class:Subject:To:References:From:Date:In-Reply-To; b=Z3R4A61jiv4JZV2L+uCqnx3xS1RkdCrIJKfcFj1UFYmeLY6iESd4f2ynPBpX/+NK2 0BI+PInsNWxL0q0quCXI7iiqJ1Y4ArX6O6AluiSH5PJkOyIrV7hlRC5K1uk2XIDSJ1 7dxLbYXB042leBSCc7g9s4m4V3hrIT3BZLVk90So=
X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9
Received: from [] ([]) by (mrweb001 []) with ESMTPSA (Nemesis) id 0M8hhT-1iDD6A1JEh-00wFAq for <>; Sat, 17 Aug 2019 16:42:01 +0200
References: <> <>
From: =?UTF-8?Q?Bj=c3=b6rn_Haase?= <>
Message-ID: <>
Date: Sat, 17 Aug 2019 16:41:56 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.8.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: quoted-printable
X-Provags-ID: V03:K1:VmDUcfso1xCvQG87eSp/Hu9siSCxVJ2KvTwp1vnxekF9KtO6Gs6 FhhZgbwD9WAyuRa2UfX+KSY659XPt9CBMluUYt9kwlTxHPseRih7jK/kYtOhdmkDhhwrs/t 17pb/8cT42G6WJLGTBE2k/hu8vmeh4IoGZPHRmUzCSI2QyjRtohMP0fEgzm64Of3NICZTvv XYKfeBDadxB3EWNg980ZA==
X-UI-Out-Filterresults: notjunk:1;V03:K0:0U5HfFNY//Q=:+rlNGdXRi7rShfg1GCjOzi wimTYeIU0XBVHMN8ervytUFLae7im97jYBCuj53itHlhjI9rbbybTYmPlvVKYShiLUfgJgb94 Fo+ADFqndQpC8UwkoBowD1C3VJkVcF6eAVu8UZ0MNEyKFYHC/GXKDXMOJhb4BBHJCpIO5/9fY jLtfPbiclBj5NQWzHAHtskoPYDh3TpHLuNH5HHscqlzyUTmu1N4vpTsS1aMsCdXdC292w/0+w troA6VPqF5uQUF0Q84iHf5WhSw9+Ntv3jYER2M8dahD0K4IjOm7O5R3p5TE94saBaI6s1CuAq 1Fhx3WiUYdlSAzUwEo8P73Sh1FexbyEngOtIMoY2vnWJfxSlzPlCzwRvztNaIZNiRN9UPY6rh LfIDT/RJin/WRQL6OQYAAIWxUev++7Sl4GFC3JATN6ZZoreaD2Eq1OBKaKz5n2RLBfPhnBeGM EXG7hjGxGDC/sCvmRbGCNdq42GAr9QvpitfhfHYUjQwrqy9vbVEdo55/SXxpB6pOcuwg3KoJp /N4A+0KSAvUQJGjrUoeRtsJwmwhFj5l1Lq+C9WtygerTWn1piMadsCHL3F58sFPArHMY/bpfH Ga7q/SNVddSGZ5yoJTTxrHDiWrJdKB63JYfPq0MiPt3C2wtrGPzdLBS8lKsP3iPi7pkCrPe5w mdNasjlyW824hnjMDTlF2jrVuOBiLDdBcm+bZh/ixNraFC9KdBYSDo/Zcrbf+98xXIKqkAhWk zSSJbClRZ+IKa2dMPXdlsGup7g5qcwLbaNHIunOZqpCQ9lqjvcLL0nwJ5un6DmfDRhvg1JhJo MGXH+KVGqrswYM2cVVXlfvT0XSABK/ZB5zCNuUIorcAYwVmXH3WnKd0MG9cPXzj+Ao3s6IaQQ 5PJjsaOU1gs00NImgQJyWvtoVKYMyuWWZykJsu8Oc/FUhtOWRHFyC3WqVWDxaYcnrphsqtIzX 6RgU8UDXyf6aGe5afTjngbQ8L3TCopdPJbR1G4kb8otP0KQs43QiUDTjgRmI7vtAdOwEB8fUK EMPmvLrS2S4w1xS8kK/BSzmwtcuUCGvaOQxvNinM8BrYN3/kobsz7YPbbQaULWtIqajSl5OZ1 B4WBJ3IDZD1DAU5nspz4s+C4aGoxiwQoYyvN6rAYn4Q3MUJgPauDH9dYXXGQGzBLdlcRl9Tll WCU4c=
Archived-At: <>
Subject: Re: [Cfrg] PAKE review / Patent situation for SPAKE2 as used in "Wormhole"
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 17 Aug 2019 14:54:54 -0000

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

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 ...



Am 17.08.2019 um 15:08 schrieb Björn Haase:
> Dear Brian,
>> 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.
> 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