Trevor Perrin

2016-09-23 18:15:57 UTC

Hi all,

Last January we discussed elliptic curves for pairing-based crypto

("Curves and code for Identity-based Encryption" [1]).

People recommended 256-bit Barreto-Naehrig ("BN") curves [2] for ~128

bits security, and code such as:

- RELIC from Diego Aranha [3,4]

- DCLXVI from Naehrig et al [5]

- Golang's version, from Adam Langley [6]

- MIRACL from Michael Scott [7]

- herumi/ate-pairing from Shigeo and Tadanori [8]

Mike Hamburg's comment was insightful [9]:

"""

BN curves only really shine at the ~WF128 level, where a 256-bit curve

matches a 256*12-bit extension field discrete log problem (EFDLP). At

higher WFs (or if you’re worried about improvements in EFDLP), you

need a higher embedding degree so that the EFDLP will be harder, or

else a very large base field.

"""

It also seemed like 256-bit BN curves were becoming popular, at least

in experimental systems like:

- Pond [10], using BBS signatures to prevent message spam

- SNARKs [11] as used by Zerocash [12], using pairings for

zero-knowledge proofs of correct program execution

- Apache Milagro [13,14], which proposes ID-based crypto instead of

Certificate Authorities

- "Puncturable encryption" [15,16], which proposes Attribute-Based

Encryption and Hierarchical IBE for message forward secrecy

- (maybe?) Intel SGX, which uses "EPID" group signatures for remote

attestation [17,18]

Unfortunately, "improvements in EFDLP" (as Mike called it) have

seemingly happened, in the last several months.

Kim and Barbulescu's "Extended Tower Number Field Sieve" [19] improves

the efficiency of calculating "finite field" (i.e. NOT elliptic curve)

discrete logs mod p^n, where p is large-ish and n is certain values,

like 6 or 12.

There was a great writeup by Aurore Guillevic on the ellipticnews blog

[20], and in a recent presentation [21]. I'll try to boil it down

even more:

The attack is relevant to pairing-friendly curves (like BN) that

support a "pairing" operation. A pairing maps points on the elliptic

curve to values in some "extension field". Security depends on both

the EC-DLP for the elliptic curve, and also DLP on the extension

field.

256-bit BN curves have a field prime p of 256 bits and an "embedding

degree" of 12, so the extension field is mod p^12, where p^12 has 3072

bits. The hope was that 256-bit EC-DLP and 3072-bit DLP would both

have security ~128 bits, so this would be nicely matched.

However, Kim and Barbulescu showed that DLP where the modulus is a

3072-bit (prime^12) is easier than DLP for a 3072-bit prime. How much

easier isn't clear, though by a "crude and naive estimation" they

suggest increasing the size of relevant curves by a third (Section 6).

Mehdi Tibouchi has a similar estimate [22]: "after this attack,

256-bit Barreto-Naehrig curves no longer offer 128 bits of security,

but perhaps closer to 96 or so".

Which raises questions:

* How reliable are the security estimates?

* Is this attack likely to be improved?

* Can the attacks benefit from precalculation (like Logjam [23]), or

does the work have to be repeated for each discrete log?

* What curves should new systems be based on?

I believe Voltage was using supersingular curves with embedding degree

2 (over a prime field) for Identity-Based Encryption [24]. GCHQ has

been promoting the "SAKKE" IBE scheme for various uses [25,26,27], and

I believe that uses similar curves [28]. However, IIUC, an embedding

degree of 2 means that ~128 bits of security requires a ~1536 bit

elliptic curve (to get a 3072 bit extension field). That seems pretty

slow, e.g. if a BN pairing is an order-of-magnitude slower than a

"regular" elliptic curve scalarmult, this seems like it would be

another order of magnitude slower.

Are there better options, for ~128 bits security?

[1] https://moderncrypto.org/mail-archive/curves/2015/#402

[2] https://eprint.iacr.org/2005/133

[3] https://github.com/relic-toolkit

[4] https://eprint.iacr.org/2013/722

[5] http://polycephaly.org/projects/dclxvi/

[6] https://godoc.org/golang.org/x/crypto/bn256

[7] https://github.com/miracl/MIRACL/

[8] https://github.com/herumi/ate-pairing

[9] https://moderncrypto.org/mail-archive/curves/2015/000405.html

[10] https://github.com/agl/pond

[11] https://eprint.iacr.org/2013/507

[12] http://zerocash-project.org/media/pdf/zerocash-oakland2014.pdf

[13] https://milagro.apache.org/

[14] http://docs.milagro.io/en/amcl/milagro-crypto-library-white-paper.html

[15] https://github.com/imichaelmiers/libforwardsec/

[16] https://www.computer.org/csdl/proceedings/sp/2015/6949/00/6949a305.pdf

[17] https://eprint.iacr.org/2009/095

[18] https://www.blackhat.com/docs/us-16/materials/us-16-Aumasson-SGX-Secure-Enclaves-In-Practice-Security-And-Crypto-Review-wp.pdf

[19] https://eprint.iacr.org/2015/1027

[20] https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/

[21] https://www.lorentzcenter.nl/lc/web/2016/834/presentations/Guillevic

[22] https://ellipticnews.wordpress.com/2016/09/02/crypto-and-ches-2016-santa-barbara-ca-usa/

[23] https://weakdh.org/

[24] https://tools.ietf.org/html/rfc5091

[25] https://www.benthamsgaze.org/wp-content/uploads/2016/01/SA3LI10_099.pdf

[26] https://tools.ietf.org/html/draft-barnes-mikey-sakke-mcptt-00

[27] http://www.securechorus.com/

[28] https://tools.ietf.org/html/rfc6508

Trevor

Last January we discussed elliptic curves for pairing-based crypto

("Curves and code for Identity-based Encryption" [1]).

People recommended 256-bit Barreto-Naehrig ("BN") curves [2] for ~128

bits security, and code such as:

- RELIC from Diego Aranha [3,4]

- DCLXVI from Naehrig et al [5]

- Golang's version, from Adam Langley [6]

- MIRACL from Michael Scott [7]

- herumi/ate-pairing from Shigeo and Tadanori [8]

Mike Hamburg's comment was insightful [9]:

"""

BN curves only really shine at the ~WF128 level, where a 256-bit curve

matches a 256*12-bit extension field discrete log problem (EFDLP). At

higher WFs (or if you’re worried about improvements in EFDLP), you

need a higher embedding degree so that the EFDLP will be harder, or

else a very large base field.

"""

It also seemed like 256-bit BN curves were becoming popular, at least

in experimental systems like:

- Pond [10], using BBS signatures to prevent message spam

- SNARKs [11] as used by Zerocash [12], using pairings for

zero-knowledge proofs of correct program execution

- Apache Milagro [13,14], which proposes ID-based crypto instead of

Certificate Authorities

- "Puncturable encryption" [15,16], which proposes Attribute-Based

Encryption and Hierarchical IBE for message forward secrecy

- (maybe?) Intel SGX, which uses "EPID" group signatures for remote

attestation [17,18]

Unfortunately, "improvements in EFDLP" (as Mike called it) have

seemingly happened, in the last several months.

Kim and Barbulescu's "Extended Tower Number Field Sieve" [19] improves

the efficiency of calculating "finite field" (i.e. NOT elliptic curve)

discrete logs mod p^n, where p is large-ish and n is certain values,

like 6 or 12.

There was a great writeup by Aurore Guillevic on the ellipticnews blog

[20], and in a recent presentation [21]. I'll try to boil it down

even more:

The attack is relevant to pairing-friendly curves (like BN) that

support a "pairing" operation. A pairing maps points on the elliptic

curve to values in some "extension field". Security depends on both

the EC-DLP for the elliptic curve, and also DLP on the extension

field.

256-bit BN curves have a field prime p of 256 bits and an "embedding

degree" of 12, so the extension field is mod p^12, where p^12 has 3072

bits. The hope was that 256-bit EC-DLP and 3072-bit DLP would both

have security ~128 bits, so this would be nicely matched.

However, Kim and Barbulescu showed that DLP where the modulus is a

3072-bit (prime^12) is easier than DLP for a 3072-bit prime. How much

easier isn't clear, though by a "crude and naive estimation" they

suggest increasing the size of relevant curves by a third (Section 6).

Mehdi Tibouchi has a similar estimate [22]: "after this attack,

256-bit Barreto-Naehrig curves no longer offer 128 bits of security,

but perhaps closer to 96 or so".

Which raises questions:

* How reliable are the security estimates?

* Is this attack likely to be improved?

* Can the attacks benefit from precalculation (like Logjam [23]), or

does the work have to be repeated for each discrete log?

* What curves should new systems be based on?

I believe Voltage was using supersingular curves with embedding degree

2 (over a prime field) for Identity-Based Encryption [24]. GCHQ has

been promoting the "SAKKE" IBE scheme for various uses [25,26,27], and

I believe that uses similar curves [28]. However, IIUC, an embedding

degree of 2 means that ~128 bits of security requires a ~1536 bit

elliptic curve (to get a 3072 bit extension field). That seems pretty

slow, e.g. if a BN pairing is an order-of-magnitude slower than a

"regular" elliptic curve scalarmult, this seems like it would be

another order of magnitude slower.

Are there better options, for ~128 bits security?

[1] https://moderncrypto.org/mail-archive/curves/2015/#402

[2] https://eprint.iacr.org/2005/133

[3] https://github.com/relic-toolkit

[4] https://eprint.iacr.org/2013/722

[5] http://polycephaly.org/projects/dclxvi/

[6] https://godoc.org/golang.org/x/crypto/bn256

[7] https://github.com/miracl/MIRACL/

[8] https://github.com/herumi/ate-pairing

[9] https://moderncrypto.org/mail-archive/curves/2015/000405.html

[10] https://github.com/agl/pond

[11] https://eprint.iacr.org/2013/507

[12] http://zerocash-project.org/media/pdf/zerocash-oakland2014.pdf

[13] https://milagro.apache.org/

[14] http://docs.milagro.io/en/amcl/milagro-crypto-library-white-paper.html

[15] https://github.com/imichaelmiers/libforwardsec/

[16] https://www.computer.org/csdl/proceedings/sp/2015/6949/00/6949a305.pdf

[17] https://eprint.iacr.org/2009/095

[18] https://www.blackhat.com/docs/us-16/materials/us-16-Aumasson-SGX-Secure-Enclaves-In-Practice-Security-And-Crypto-Review-wp.pdf

[19] https://eprint.iacr.org/2015/1027

[20] https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/

[21] https://www.lorentzcenter.nl/lc/web/2016/834/presentations/Guillevic

[22] https://ellipticnews.wordpress.com/2016/09/02/crypto-and-ches-2016-santa-barbara-ca-usa/

[23] https://weakdh.org/

[24] https://tools.ietf.org/html/rfc5091

[25] https://www.benthamsgaze.org/wp-content/uploads/2016/01/SA3LI10_099.pdf

[26] https://tools.ietf.org/html/draft-barnes-mikey-sakke-mcptt-00

[27] http://www.securechorus.com/

[28] https://tools.ietf.org/html/rfc6508

Trevor