[PATCH] Add NTRUEncrypt public key encryption algorithm

Mon Sep 14 15:37:20 CEST 2015

Hi Opal, Werner and all,

Thanks a lot for your feedback.
I see there are three major concerns from you.
Please let me try to address those.

++++++++++++++++++++++++++++++++++++++++++++++++++++
*On NTRU itself and post-quantum cryptography

> it's not yet proven to be secure against quantum cryptanalysis

>From theoretic point of view, the semantic security of NTRU can be reduced
to a unique shortest vector problem (uSVP) over a specific ideal lattice,
called NTRU ideal lattice.
Unique shortest vector problem of general lattice is conjectured to be
secure against quantum computer. However, to provide efficient crypto, one
usually relies on a relaxed version of the problem: uSVP over ideal
lattices. To date, there is no algorithm that solves uSVP over NTRU ideal
lattice that is asymptotically faster than uSVP over general lattices. So
it is safe to assume NTRU is quantum-safe.

>From a practical point of view, NTRU has been proposed for almost 20 years.
It survived many cryptanalsys. The current parameter that we are
recommending has been stable since 2007, despite of the great improvement
in lattice reduction algorithms in the recent years.

Also, you cannot claim that a crypto scheme is secure against quantum
cryptanalysis as there might be potential attacks/algorithms that people
have not invented yet. People usually claim that either a cryptosystem is
*proven* to be insecure/broken due to (quantum) attacks; or there is no
known (quantum) attack against this cryptosystem, and thus the cryptosystem
is *conjectured* to be secure. Also note that RSA and ECC are proven to be
*insecure* against quantum cryptanalysis due to Shor's algorithm.

>  there is a problem with performance.

NTRU is actually one of the fastest public key encryption scheme there is.
NTRU with parameter eess401ep2 delivers 112 bits security and is 92 times
faster than RSA-2048
at the same security level, according to the SUPERCOP benchmark:
http://bench.cr.yp.to/supercop.html
And with the increase of the security level, the advantage of NTRU gets
larger.

Also in 2009, NIST wrote a survey on post-quantum cryptography.
http://www.nist.gov/customcf/get_pdf.cfm?pub_id=901595
According to them:
“Of the various lattice based cryptographic schemes that have been
developed, the NTRU family of cryptographic algorithms appears to be the
most practical... They are viable alternatives for both public key
encryption and signatures that are not vulnerable to Shor’s Algorithm.”

> What I read about the attacks doesn't make me happy either.

On wiki (and almost on every academic paper of an encryption scheme), there
is always a section discussing the state-of-art attacks on the
cryptosystem.
For example on RSA's wiki page, there are 7 different cryptanalytic
methods, under the section "Security and practical considerations":
https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Security_and_practical_considerations
Through those attacks cryptographers grow their confidence in the system,
and derive the most practical parameter set that is robust against those
best known attacks.

As for NTRU, there were two attacks on wiki page: a brute force attack and
a lattice attack. The original NTRU design in 1996 has already considered
those two attacks. We revised our parameter set in 2007 due to the hybrid
attack of meet-in-the-middle attack (a variant of brute force attack) and
the lattice attack from N. Howgrave-Graham, which combines the strength of
both attacks on the wiki page.

Since then, there are various paper claiming to attack NTRU, including the
famous BKZ 2.0 from Y. Chen and P. Nguyen. Other paper has to assume
different (very large) parameters for the attack to be successful.  None of
those is able to break our current parameter.

We have wrote this preprint to show how every single parameter is derived
from all those attacks
https://eprint.iacr.org/2015/708
We actually put up a challenge this year awarding people who can break
NTRU, where parameters are derived with the same principle, but with less
strength (so that they may actually be breakable)
https://www.securityinnovation.com/products/encryption-libraries/ntru-crypto/ntru-challenge/
Both Howgrave-Graham and Nguyen's group have participated and they were
only able to solve some toy challenges. Those timing results for solving
toy challenge also fall in our estimation.

> algorithm is not a formal standard, as far as I can tell.

In fact it is. NTRU is standardized by IEEE std 1363.1 and ANSI X9.98. NTRU
is the only standardized post-quantum crypto to the best of my knowledge.

> - Post quantum crypto is quite young and as of now mostly an academic
>   exercise.

It is not clear when quantum computers will become available.  The EU has
expressed in their Horizon 2020 project a desire for systems to be
"quantum-ready" by 2020.  See the presentation from Tanja Lange:
http://pqcrypto.eu.org/slides/20150403.pdf
Google have optimistically predicted practical and powerful quantum
computer could become available by the 2020 to 2025. See the following
article:
http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/
NSA advised people to move away from ECC and prepare for quantum-safe
crypto in their recent announcement:
https://www.nsa.gov/ia/programs/suiteb_cryptography/
TLS working group and Tor community are also considering quantum-safe
handshake approaches.

I think those imply a valid demand of post quantum crypto in the industry.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

*On licensing

There are two piece of codes in this patch that are under GPL.

- The base64 code is under GPL. We will rewrite those code so it will be
free to use.

- The NTRU source code is under GPL. We can make patent exemptions for
libgcrypt, if it is Okey. We have already made such an exemption for open
source licenses, see
https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/FOSS%20Exception.md
Please let me know if this kind of exemption for libgcrypt is good enough.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

*On implementation/code

dependencies issue:
NTRU source code has a small footprint. We are happy to remove the
dependency of libntruencrypt, and include ntru source code within the
libgrcrypt/cipher.

code quality:
This is my bad. Thanks again for the invaluable comments.
I will address those comment in a short future.

Cheers,
Zhenfei

On Wed, Sep 9, 2015 at 4:39 AM, Werner Koch <wk at gnupg.org> wrote:

> On Tue,  8 Sep 2015 20:45, zzhang at securityinnovation.com said:
>
> > Can I please ask what is the right approach to get this patch included
> in a
> > release?
>
> One question is whether we want to include this algorithm.  I see
> several reasons not to do this:
>
>  - Post quantum crypto is quite young and as of now mostly an academic
>    exercise.  However, inclusion in a general purpose crypto library
>    might be worth for algorithms which are likely going to be used in
>    some future.  I can't decide on this and would for example ask Tanja
>    Lange for her opinion on NTRU.
>
>  - The code implementing the algorithm is under the GPL and thus can't
>    be used by Libgcrypt because that would change Libgcrypt from LGPLv2+
>    to GPLv2+ which we do not want.
>
>  - The patent exception for that algorithm may work for GPL code but
>    needs a closer look by a lawyer.  But GPL excludes its use anyway.
>
>
> Another question is whether this implementation is techincal okay to be
> included:
>
> > +  libntruencrypt 1.0.0
>
> A dependency on an external library implementing the agorithm is not
> going to work.  We want the algorithm implementation in Libgcrypt proper.
>
> > --- a/autogen.sh
> > +++ b/autogen.sh
> > @@ -277,7 +277,7 @@ if [ "$myhost" = "amd64" ]; then
> >          fi
> >      fi
> >
> > -    $tsdir/configure --enable-maintainer-mode ${SILENT} \
> > +    $tsdir/configure --enable-maintainer-mode --enable-ntru ${SILENT} \
>
> Extra options need to go into autogen.rc.  In any case only options
> required to build on a specific platform should be added to autogen.rc.
>
> > diff --git a/cipher/base64.c b/cipher/base64.c
>
> > + *  This program is free software; you can redistribute it and/or modify
> > + *  it under the terms of the GNU General Public License as published by
>
> You can't put GPL code into Libgcrypt which is under the LGPL.
>
> > +int base64_encode( unsigned char *dst, size_t *dlen,
> > +                   const unsigned char *src, size_t slen )
>
> GNU coding standard please.
>
> > +     GCRY_PK_USAGE_ENCR,         //  int use;
>
> No C++ comments please.
>
> > +{
> > +    fprintf (stderr,"NTRU compute keygrip function not
> required/implemented\n");
>
> Libgcrypt has its own log functions - do not use printf.
>
> > +    uint8_t                     *public_key;
> /* sized for EES401EP2 */
> > +    uint16_t                    public_key_len;
>
> Do not use these C99 types - we stick to C90.  Use unsigned char or byte
> instead of uint8_t and our u16 type instead of uint16_t.
>
> > +    pers_str    = (uint8_t*)_gcry_random_bytes (32, GCRY_WEAK_RANDOM);
>
> There is no need to case a void * - we are not doing C++.
>
> > +    public_key  = (uint8_t *) malloc (_MAX_NTRU_BUF_SIZE_);
> > +    private_key = (uint8_t *) malloc (_MAX_NTRU_BUF_SIZE_);
> > +
> > +    memset(public_key, 0, _MAX_NTRU_BUF_SIZE_);
> > +    memset(private_key, 0, _MAX_NTRU_BUF_SIZE_);
>
> Ditto.  You also missed to check for errors.
>
> [...]
>
>
>
> Salam-Shalom,
>
>    Werner
>
>
> --
> Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20150914/d10eb0f9/attachment-0001.html>