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

Björn Haase <bjoern.m.haase@web.de> Sat, 17 August 2019 14:54 UTC

Return-Path: <bjoern.m.haase@web.de>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6261112002E for <cfrg@ietfa.amsl.com>; Sat, 17 Aug 2019 07:54:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=web.de
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7p3MxKsdHAFg for <cfrg@ietfa.amsl.com>; Sat, 17 Aug 2019 07:54:52 -0700 (PDT)
Received: from mout.web.de (mout.web.de [212.227.15.14]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C4E7B120048 for <cfrg@irtf.org>; Sat, 17 Aug 2019 07:54:51 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; 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 [192.168.2.161] ([92.75.65.225]) by smtp.web.de (mrweb001 [213.165.67.108]) with ESMTPSA (Nemesis) id 0M8hhT-1iDD6A1JEh-00wFAq for <cfrg@irtf.org>; Sat, 17 Aug 2019 16:42:01 +0200
To: cfrg@irtf.org
References: <ef4bfaae-41ab-db86-3fa8-60747a24430e@lothar.com> <637616d4-c84c-8085-33e9-bd77745eaca9@web.de>
From: =?UTF-8?Q?Bj=c3=b6rn_Haase?= <bjoern.m.haase@web.de>
Message-ID: <55c8b926-16bb-9351-510e-4b56202cb1f0@web.de>
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: <637616d4-c84c-8085-33e9-bd77745eaca9@web.de>
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: <https://mailarchive.ietf.org/arch/msg/cfrg/s4VcMJfAP-4HymF0_82nK6C48P4>
Subject: Re: [Cfrg] PAKE review / Patent situation for SPAKE2 as used in "Wormhole"
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=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
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:
> 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
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg