Re: [Cfrg] Patents and the new elliptic curves

Michael Hamburg <mike@shiftleft.org> Tue, 16 September 2014 23:30 UTC

Return-Path: <mike@shiftleft.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id AEFB81A01F7 for <cfrg@ietfa.amsl.com>; Tue, 16 Sep 2014 16:30:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.557
X-Spam-Level: *
X-Spam-Status: No, score=1.557 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, LOTS_OF_MONEY=0.001, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
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 94FLv4xBild0 for <cfrg@ietfa.amsl.com>; Tue, 16 Sep 2014 16:30:19 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1E64A1A004D for <cfrg@irtf.org>; Tue, 16 Sep 2014 16:30:19 -0700 (PDT)
Received: from [10.184.148.249] (unknown [209.36.6.242]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 4105B3AA13; Tue, 16 Sep 2014 16:30:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1410910216; bh=Mu2yxcLyr+6czOCqjJniFe3bqaZHESWNsNpa09r1nNo=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=TS+jGkHbq3cocmFMkxcBgUyqadqX88GUtGEzybRYbFq6S+/wTfy/7lbHxSSQWSyfL +0sDp0mxyZqkyaQc5EPVqRDbFjuD9naJnvohIIY3mEnSL2aRPSFqbK4FkEOeBxhn12 8Mzg7mUnJYjkYSJVT/p0yJOwpA5DMflDOhbvmvoE=
Content-Type: multipart/alternative; boundary="Apple-Mail=_3A511B2B-C25B-4A2B-AFF9-4DC184CEB179"
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1985.3\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <CA+Vbu7zsRnEFVo-kFHgCgxkNXpmPkcDjN56m58JG862MHox3cg@mail.gmail.com>
Date: Tue, 16 Sep 2014 16:30:14 -0700
Message-Id: <D2104ECF-716E-4C8D-940A-339AE87CBAF0@shiftleft.org>
References: <2145381D-E1C4-4CFC-A26F-879D775E6558@shiftleft.org> <CA+Vbu7zsRnEFVo-kFHgCgxkNXpmPkcDjN56m58JG862MHox3cg@mail.gmail.com>
To: Benjamin Black <b@b3k.us>
X-Mailer: Apple Mail (2.1985.3)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/evCkbqxf2TpZNVOxpBntbgrQuic
Cc: IRTF Crypto Forum Research Group <cfrg@irtf.org>
Subject: Re: [Cfrg] Patents and the new elliptic curves
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 16 Sep 2014 23:30:21 -0000

Hi b,

I’m sorry that email.  I should have phrased this less aggressively, and I should also have mentioned that you have asked legal to review US7602907.  However, that review will answer at most one of the questions I asked, and you have resolutely refused to help with the others.

Please understand that my goal here isn’t to bash Microsoft or its NUMS proposal, but to make sure that new curves can be efficiently implemented in a way that avoids the patent minefield.  To do that, we need to know where the mines are.

I expect (though I am not sure) that any patents that may turn up will not affect which curves should be chosen, either because they can be worked around or because they apply equally to all curves.  However, it is likely that patents will influence protocols and internal algorithms, and perhaps also things coordinate choice or point encoding.  Conceivably the result could be relevant to the Montgomery vs Edwards discussion, particularly if there is no IPR-free version of the comb algorithm.

To my knowledge, there are exactly two open-source implementations available of the newer (i.e. non-25519) curves: Goldilocks and NUMS.  It is likely that if one of those curves is chosen, those packages may be used as a starting point in TLS libraries.  It is therefore necessary to determine whether they are patent encumbered, and how.

The Apache2 license grant is very helpful, but as you are aware it is not sufficient for this purpose; we need to be able to remove any code which may implement patented procedures.

I admit to having the less helpful MIT license on my source code.  At the same time, I do not believe that it implements any patented algorithms, and I would like to be more sure that this is true.

Your accusation of hypocrisy is, of course, inaccurate.  I have spent many hours searching for patents which may impact elliptic curve implementations, because I want to make sure I and other implementers can create unencumbered implementations.  This is why I know about US7602907.

However, I cannot claim to have combed through all possibly relevant patents, and I cannot claim to know that any particular technique is OK.  This is why I hedged my statement about searches, and why I have asked the CFRG for help.

It is not appropriate to compare my concern that I have missed something with a determined ignorance of even your own company’s patents.

I have additional thoughts regarding BCP 79, but I will discuss them with you off list first to avoid causing more trouble.

Cheers,
— Mike

> On Sep 16, 2014, at 3:32 PM, Benjamin Black <b@b3k.us> wrote:
> 
> Mike,
> 
> As I explained in that formerly private discussion, we have asked for an internal legal review on US7602907 as we were unaware of it at the time the code and drafts were written. I am not in a position to comment on whether it is a concern, and until that review is complete there is nothing for anyone to confirm or deny. 
> 
> Large companies work this way, including that avoidance of reading patents to limit exposure in the event of IP litigation. While bashing Microsoft and its employees seems to never go out of fashion, it is not merely unhelpful, but counterproductive and inappropriate here. We are participating in this process in good faith and assume everyone else is, as well, even if there are points of disagreement.
> 
> It does strike me as odd you are criticizing us for not doing extensive patent searches when you haven't done so and BCP 79 does not require it. I hope everyone will be held to the same standard here, whatever it is.
> 
> 
> b
> 
> 
> 
> On Tue, Sep 16, 2014 at 2:56 PM, Michael Hamburg <mike@shiftleft.org <mailto:mike@shiftleft.org>> wrote:
> Hello CFRG,
> 
> I’m concerned about patent issues which may affect the new elliptic curve standards.
> 
> There has been a side discussion involving several members of this list, including some Microsoft researchers, on the subject of what patents may apply to proposed curves and their implementations and in particular to the NUMS curves.
> 
> Microsoft has a policy of avoiding patent searches, not reading patents, not commenting on patents etc, so they have not been particularly helpful.  However, I am concerned that the Microsoft-held US7602907 (and possibly foreign equivalents) may apply to their implementation, covering the mLSB combs algorithm.  Benjamin Black has refused to confirm or deny this.  The NUMS code itself is still usable under the Apache2 license, but it has a "mutually assured destruction” clause, and other implementations might infringe.
> 
> So I have a few questions for the list.  First, am I right to be concerned that US7602907 reads against the NUMS code?  How does this interact with the BCP, since the curve’s spec does not require the patent, but the reference implementation does?
> 
> Second, is anyone aware of other patents that may read on SafeCurves-style Montgomery or (twisted) Edwards implementations, especially of the proposed curves (\w+)25519, Curve41417, MS NUMS, Ed448-Goldilocks or E-521?  It is required that new curves be efficiently and securely implementable without stepping on such patents, so it is critical to know what they are.
> 
> Third, given that mLSB combs may be encumbered, does anyone have information on the patent status of other state-of-the-art comb algorithms?  I’m particularly hoping that the signed all bits set (SABS) combs algorithm used in Goldilocks is patent-free, but I have only conducted a limited search.
> 
> Thanks,
> — Mike Hamburg
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org <mailto:Cfrg@irtf.org>
> http://www.irtf.org/mailman/listinfo/cfrg <http://www.irtf.org/mailman/listinfo/cfrg>
>