Internet-Draft D. Brown
Intended status: Experimental BlackBerry
Expires: 2020-10-05 2020-04-03
Elliptic curve 2y^2=x^3+x over field size 8^91+5
<draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-05.txt>
Abstract
Multi-curve elliptic curve cryptography with 2y^2=x^3+x/GF(8^91+5)
hedges a risk of new curve-specific attacks. The curve features:
isomorphism to Miller's curve from 1985; low Kolmogorov complexity
(little room for embedded weaknesses of Gordon, Young--Yung, or
Teske); prime field; Montgomery ladder or Edwards unified arithmetic
(Hisil--Carter--Dawson--Wong); complex multiplication by i
(Gallant--Lambert--Vanstone); 34-byte keys; five 64-bit-word field
arithmetic; easy reduction, inversion, Legendre symbol, and square
root; similarity to a Bitcoin curve; and string-as-point encoding.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF). Note that
other groups may also distribute working documents as
Internet-Drafts. The list of current Internet-Drafts is at
http://datatracker.ietf.org/drafts/current.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress."
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with
respect to this document.
This document may not be modified, and derivative works of it may
not be created, except to format it for publication as an RFC or to
translate it into languages other than English.
Brown 2y^2=x^3+x over 8^91+5 [Page 1]
Internet-Draft 2020-04-03
Table of contents
1. Introduction
2. Requirements Language (RFC 2119)
3. Overview
3.1. Not for single-curve ECC
3.2. Risks of new curve-specific attacks
3.3. Multi-curve ECC
3.3.1. Multi-curve ECC is a redundancy strategy
3.3.2. Whether to use multi-ECC
3.3.2.1. Benefits of multi-curve ECC
3.3.2.2. Costs of multi-curve ECC
3.3.3. Applying multi-curve ECC
3.4. Curve features
3.4.1. Field features
3.4.3. Equation features
3.4.4. Finite curve feature
3.4.4.1. Curve size and cofactor
3.4.4.2. Pollard rho security
3.4.4.3. Pohlig--Hellman security
3.4.4.2. Menezes--Okamoto--Vanstone security
3.4.4.3. Semaev--Araki--Satoh--Smart security
3.4.4.4. Edwards and Hessian form
3.4.4.5. Bleichenbacher security
3.4.4.6. Bernstein's "twist" security
3.4.4.7. Cheon security
4. Encoding points
4.1. Point encoding process
4.1.1. Summary
4.1.2. Details
4.2. Point decoding process
4.2.1. Summary
4.2.2. Detail
5. Point validation
5.1. When to validate
5.1.1. Mandatory validation
5.1.2. Simplified validation
5.1.4. Minimal validation
5.2. Point validation process
6. OPTIONAL encodings
6.1. Encoding scalars
6.2. Encoding strings as points
7. IANA Considerations
8. Security considerations
8.1. Field choice
8.2. Curve choice
8.3. Encoding choices
8.4. General subversion concerns
8.5. Concerns about 'aegis'
9. References
Brown 2y^2=x^3+x over 8^91+5 [Page 2]
Internet-Draft 2020-04-03
9.1. Normative References
9.2. Informative References
Appendix A. Test vectors
Appendix B. Minimizing trapdoors and backdoors
Appendix C. Pseudocode
C.1. Scalar multiplication of 34-byte strings
C.1.1. Field arithmetic for GF(8^91+5)
C.1.2. Montgomery ladder scalar multiplication
C.1.3. Bernstein's 2-dimensional Montgomery ladder
C.1.4. GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong)
C.2 Pseudocode for test vectors
C.3. Pseudocode for a command-line demo of Diffie--Hellman
C.4 Pseudocode for public-key validation and twist insecurity
C.5. Elligator i
D. Primality proofs and certificates
D.1. Pratt certificate for the field size 8^91+5
D.2. Pratt certificate for subgroup order
1. Introduction
Elliptic curve cryptography (ECC) is now part of several IETF
protocols.
Multi-curve ECC mitigates the risk of new curve-specific attacks on
ECC. This document aims to contribute to multi-curve ECC by
describing how to use the curve
2y^2=x^3+x / GF(8^91+5).
2. Requirements Language (RFC 2119)
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [BCP14].
3. Overview
This sections how curve 2y^2=x^3+x/GF(8^91+5) improves ECC.
3.1. Not for single-curve ECC
Curve 2y^2=x^3+x/GF(8^91+5) SHOULD NOT be used in single-curve ECC,
because it is is riskier than other IETF-approved curves, such as
NIST P-256 and Curve25519, for at least two reasons:
Brown 2y^2=x^3+x over 8^91+5 [Page 3]
Internet-Draft 2020-04-03
- it is newer: common sense says newer is riskier, all else equal,
and
- it is special, with complex multiplication by i: consensus
continues to agree with Miller's original 1985 opinion that
using (such) special curves is not prudent.
Koblitz, Koblitz and Menezes [KKM] somewhat dissent from the latter
consensus by listing several plausible cases of special curves --
including some with complex multiplication -- that they argue might
well be safer than random curves. (Others go even further,
dismissing prudence against special curves as myth). Despite this
dissent, this report adheres to the consensus.
3.2. Risks of new curve-specific attacks
A risk for ECC is new curve-specific attacks --- "new" meaning
hypothetical and not yet published, so either future or hidden.
Prime-field curves were affected by two curve-specific attacks on
the discrete logarithm: the MOV attacks the SASS attack, both from
before 2001. For non-prime-field curves, more recent curve-specific
attacks have been discovered. The rarity of the attacks is evidence
that the probability of new curve-specific attacks is low, but is
not proof.
Sensible curves include mitigations against the nonzero risk of new
curve-specific attacks.
- NIST curve P-256 has coefficients derived from the ouptut of
SHA-1, perhaps aiming to avoid any new curve-specific weakness
that would appply rarely to random curves.
- Bernstein's Curve25519 results from a "rigid" design process,
favoring efficiency over all else, perhaps eliminating intentional
subversion towards a new curve-specifc weakness.
- Brainpool's curve are derived using hash functions to
number-up-my-sleeve numbers, perhaps aiming to mitigate both
intential subversion and accidental rare weakness.
A reasonable inference from these curves is that risk of new
curve-specific attacks warranted the mitigations used. The
risk may be less now that further time has passed, yet the
mitigations may still be warranted.
Brown 2y^2=x^3+x over 8^91+5 [Page 4]
Internet-Draft 2020-04-03
The curve 2y^2=x^3+x/GF(8^91+5) includes mitigations against the
risk of new curve-specific attacks:
- a short description (low Kolmogorov compelxity), aiming to have
little wiggle for an intentional embedded weakness, much like a
nothing-up-my-sleeve number,
- a set of special efficiencies, such as a curve endomorphism,
Montgomery form, and fast field operation, much like a "rigid"
favors efficiency to fight off intentional embedded weakness,
- a prime field, to stay clear of recent curve-specific attacks on
non-prime-field ECC.
These mitigations do not suffice to justify its use in single-curve
ECC (instead of more established non-special curves).
Multi-curve ECC aims to further mitigate the risk of curve-specific
attack, by securely combining a diverse set of curves. The aim is
that at least one of the curves used in multi-curve ECC resists the
new curve-specific attack (if a new attack ever appears). This aim
is only plausible if the set of curves used is diverse.
This curve contributes to the diversity necessary for multi-curve
ECC, with special features distinct from established curves NIST
P-256 and Curve25519:
- complex multiplication by i (low discrimiant, rather than high),
- a greater emphasis on low Kolmogorov descriptional complexity
(rather than hashed coefficient or efficiency).
3.3. Multi-curve ECC
This section further motivates the value of multi-curve ECC over
single-curve ECC, but does specify a detailed way to do multi-curve
ECC.
Multi-curve ECC is only really effective if used with a diverse set
of curves. Multi-curve ECC SHOULD use a set of curves including the
three curves:
NIST P-256, Curve25519, and 2y^2=x^3+x/GF(8^91+5).
3.3.1. Multi-curve ECC is a redundancy strategy
Brown 2y^2=x^3+x over 8^91+5 [Page 5]
Internet-Draft 2020-04-03
Multi-curve ECC is an instance of a strategy often called
redundancy, applied to ECC. Redundancy is quite general in that it
can be applied to other types of cryptography, to other types of
information security, and even to safety systems. Other names for
redundant strategies include:
strongest-link, defense-in-depth, hybrid, hedged, composite,
fail-safe, diversified, resilient, belt-and-suspenders, fault
tolerant, robust, multi-layer, robustness, compound, combination,
etc.
3.3.2. Whether to use multi-ECC
Multi-curve ECC mitigates the risk of new curve-specific attacks, so
ought to be used instead of single-curve ECC if affordable, such as
when
- the privacy of the data being protected has higher value than
the extra cost of multi-curve ECC, which may well be the case
for at least financial, medical, or personally-identifying data,
and
- ECC is only a tiny portion of the overall system costs, which
would be the case if the data is human-generated or high-volume,
or if ECC is combined with slow or large post-quantum
cryptography (PQC).
3.3.2.1. Benefits of multi-curve ECC
The benefit of multi-curve ECC over single-curve ECC, its extra
security, is difficult to quantify.
No extra security results if all the curves used are the same. The
curves must be diverse, so that a potential attack on one is somehow
unlikely to affect the other. This diversity is difficult to
assess. Intuitively, a geometric metaphor of a polygon for the
space of all choices might help. Maximally distant points in a
polygon tend to be vertices, the extremities of the polygon.
Translating this inuition suggests choosing curves at the extremes
of features.
Note: By contrast, in a single-curve ECC, the geometric
metaphor suggests a central internal point, on the grounds that
each vertex is more likely to be affected to a special attack.
Carrying this over to multi-curve suggests that a diverse set
ought to include a non-extreme curve too.
Brown 2y^2=x^3+x over 8^91+5 [Page 6]
Internet-Draft 2020-04-03
As always, the benefit of security is really the negative of the
cost of an attack, including the risk.
The contextual benefit of multi-curve ECC therefore depends very
much on the application, involving the assessing both the
probability of attack, and the impact of the attack.
Higher value private data has greater impact if attacked, and
perhaps also higher probability, if the adversary is more motivated
to attack it.
Low probability of attacks are mostly inferred through failed but
extensive cryptanalysis efforts. Normally, this is only intuited,
but approaches to quantifiably estimate these probabilities is
possible too, under sufficiently strong assumptions.
To be completed.
3.3.2.2. Costs of multi-curve ECC
The cost of multi-curve ECC can be cost compared to single-curve
ECC. The cost ratio is approximately the number of curves used.
The cost difference depends on the devices implementing the ECC.
For example, on a current personal computer, the extra cost per ECC
transaction can include up to 1 millisecond of runtime and sending
an extra 30 bytes or more. In low-end devices, the time may be
higher due to slower processors.
The contextual cost of ECC depends on the application context. In
some applications, such as personal messages between two users, the
cost (milliseconds and a few hundred bytes) is affordable relative
to the time users spent writing and reading the messages. In other
applications, such as automated inter-device communication with
frequent brief messages, single-curve ECC may already be a
bottleneck, costing most of the run-time.
3.3.3. Applying multi-curve ECC
For key establishment, NIST recently proposed in a draft amendment
to Special Publication 800-133 on key derivation a mechanism to
support derive one symmetric key from the result of multiple key
establishments. In essense, the raw ECDH shared secrets would be
concatenated and fed into a hash-based key derivation function.
An alternative would be to XOR multiple shared symmetric-key
together.
Brown 2y^2=x^3+x over 8^91+5 [Page 7]
Internet-Draft 2020-04-03
So, multi-curve elliptic curve Diffie--Hellman (ECDH) key agreement
could use one of these mechanism to derive a single key from
multi-curve ECDH. One would still need to a mechanism to support
sending more than one ECDH public key (usually ephemeral), with an
indication of the curve for each ECDH key.
For signatures, the simplest approach is to attach multiple
signatures to each message. (For signatures providing message
recovery, then an approach is to apply the results, with outer
signatures recover the inner signed message, and so on.)
3.4. Curve features
This subsection describes some general features of the curve
2y^2=x^3+x/GF(8^91+5),
presuming a familiarity with elliptic curve cryptography (ECC).
Each of a set of well-established features, such as Pollard rho
security or Mongtomgery form, for ECC in general are evaluated and
summarized for the specific curve 2y^2=x^3+x/GF(8^91+5).
Note: Interoperable ECC requires a few more details than are
deducible from mathematical description 2y^2=x^3+x/GF(8^91+5) of
the curve, such encoding points as byte strings. These details
are discussed in Section 3,4, and 5.
3.4.1. Field features
The curve's field of definition, GF(8^91+5), is a finite field, as
is always the case in ECC. (Finite fields are Galois field, and the
field of size is p is written as GF(p).)
The field size is the prime p=8^91+5. (See the appendix for a
Pratt primality certificate.)
In hexadecimal (base 16, big-endian) notation, the number 8^91+5 is
200000000000000000000000000000000000000000000000000000000000000000005
with with 67 zeros between 2 and 5.
Prime fields in ECC tend be more efficient in software than in
hardware. The most recent known curve-specific attacks on
prime-field ECC are from 2000.
Brown 2y^2=x^3+x over 8^91+5 [Page 8]
Internet-Draft 2020-04-03
The prime p is very close to a power of two. Primes very cloe to a
power of two are sometimes known as a Crandall prime. Reduction
modulo p is more efficient for Crandall primes than for most other
primes (or at least random primes). Perhaps Crandall primes more
resistant to side-channel attacks or implementation faults than than
most other primes.
The fact that p is slightly larger than a power of two -- rather
than slightly lower -- means that powering algorithms to compute
inverses, Legendre symbols, and square roots are simpler and
slightly more efficient (than would be for prime below a 2-power).
3.4.3. Equation features
The curve equation 2y^2=x^3+x has Montgomery form,
by^2=x^3+ax^2+x,
with (a,b) = (0,2). This permits the Montgomery ladder scalar point
multiplication algorithm to be used, which makes it relatively
efficient, and also easier to protect against side channels.
The curve 2y^2=x^3+x has complex multiplication by i, given an
endomorphism
(x,y) -> (-x,iy).
Note: Strictly speaking, over some fields, the curve would be
supersingular, in which the term "complex mutliplication" is not
longer used, perhaps because quaternionic multiplication is
applicable.
This permits the Gallant--Lambert--Vanstone (GLV) scalar
multiplication algorithm, which makes it relatively efficient. (The
GLV method can also be combined with Bernstein's two-dimensional
variant of the Montgomery ladder algorithm.)
The curve has j-invariant 1728 (because it has complex
multiplication by i).
Note: The j-invariants 0 and 1728 are special in that they have
more than two automorphisms. Over complex numbers, the moduli
space of elliptic curves is an orbifold, with two non-smooth
points, at j=0 and j=1728, which is yet another reason these
j-invariants are special.
3.4.4. Finite curve feature
Brown 2y^2=x^3+x over 8^91+5 [Page 9]
Internet-Draft 2020-04-03
This section describes features of 2y^2=x^3+x/GF(8^91+5) as a finite
curve consisting, the points (x,y) for x,y in GF(p), and also the
point at infinity. In other words, these features are specific to
the combination of both the finite field and the curve equation.
Note: In algebraic geometry, these points are said to rational
over k=GF(p), and the set of rational points written as E[k] =
(2y^2=x^3+)[GF(8^91+5)], to distinguish from points with
coordinates in the alebraic closure of k=GF(p).
Many security properties, and a few performance properties, of ECC
are specific to the finite curve.
3.4.4.1. Curve size and cofactor
The curve (of points rational over GF(8^91+5) has size (order) 72q
for a large prime q. (See Appendix for a Pratt primality certifcate
for q.)
In other words, the curve has cofactor 72.
Note: The curve size 72q can be found using the CM method and
Cornacchia's algorithm, instead of the more costly
Schoo--Elkies--Atkin algorithm(s). For this curve, this method
amounts to finding integers (a,b) such that a^2 + b^2 = p, and
then putting 72q = a^2 + (b-1)^2.
3.4.4.2. Pollard rho security
The prime q is 267-bit number, so the Pollard rho algorithm takes
(proportional to) sqrt(q) ~ 2^133 elliptic curve operations. So, it
seems to provide well over 2^128 security against Pollard rho
attacks, with about 5 bits to spare.
Note: Arguably, the fact ECC operations are slower than
symmetric-key operartions (such as hashing or block ciphers),
means that ECC security should be granted a few extra bits,
perhaps 5-10 bits, of security when trying to match ECC security
with symmetric-key security. In this case, one might say that
2y^2=x^3+x/GF(8^91+5) resists Pollard-rho with 2^140 security,
providing 12 bits of extra security. The extra security can be
viewed as a safety margin for error, or as an excessive to the
extent the smaller, and faster curves would more than suffice to
match 2^128 security of SHA-256 and AES-128.
Brown 2y^2=x^3+x over 8^91+5 [Page 10]
Internet-Draft 2020-04-03
Gallant, Lambert, Vanstone, show how to speed up Pollard rho
algorithms when the group has an extra endormorphism, which would
apply to 2y^2=x^3+x. The speed-up here amounts to a couple of bits
in the security,
3.4.4.3. Pohlig--Hellman security
The small cofactor means the curve effectively resists
Pohlig--Hellman attack (a generic algorithm to solve discrete
logarithms in any group in time sqrt(m) where m is the largest
prime factor of the group size).
Note: Consensus in ECC is to recommend a small factor, such as 1,
2, 4, or 8, despite the factor for random curves, the typical
cofactor is approximately p^(1/3), which is much larger. The
small cofactor helps resists Pohlig--Hellman without increasing
the field size. (A larger field size would be less efficient.)
3.4.4.2. Menezes--Okamoto--Vanstone security
The curve has a large embedding degree, so it resists the
Menezes--Okamoto--Vanstone attack. The curve 2y^2=x^3+x /
GF(8^91+5) is not supersingular.
Note: For about half of all primes q, then curve 2y^2=x^3+x is
supersingular over GF(q). Supersingular curves have q+1 points,
and are vulnerable to the MOV attack, which reduces the elliptic
curve discrete logarithm to the finite field discrete logarithm
over GF(q^2). This is one of the sense in which the curve
2y^2=x^3+x / GF(8^91+5) is close to being insecure. To be clear,
this curve was chosen after, and with full knowledge of, the MOV
attack.
Note: The non-supersingularity means that the endomorphism ring is
commutative. For this curve the endomorphism ring is isomorphic
to the ring Z[i] of Gaussian integers.
The large embedding degree also means that it has no efficient
pairing operation, so it cannot be used for pairing-based
cryptography.
3.4.4.3. Semaev--Araki--Satoh--Smart security
The fact that the curve size 72q is not p, means that the curve
resists the Semaev--Araki--Satoh--Smart attack.
3.4.4.4. Edwards and Hessian form
Brown 2y^2=x^3+x over 8^91+5 [Page 11]
Internet-Draft 2020-04-03
The cofactor 72 is divisible by 4, so the curve isomorphic to a
curve with an Edwards equation, permitting implementation even more
efficient than the Montgomery ladder.
The Edwards form makes possible the Gallant--Lambert--Vanstone
method that used the efficient endomorphism.
The cofactor 72 is also divisible by 3, so the curve is isomorphic
to a curve with a Hessian equation, which is another type of
equation permmitting efficient implementation.
Note: It is probably too optimisitic and speculative to hope that
future research will show how to take advantage by combining the
efficiencies of Edwards and Hessian curve equations.
3.4.4.5. Bleichenbacher security
The prime q is not particularly close to a power of two.
This means that for faulty implementations of digital signatures may
be more vulnerable to Bleichenbacher's attack, which would exploits
the non-uniformity in secret numbers obtained by reducing uniformly
random bit strings modulo q.
Therefore, q-uniformization of the secret numbers is critical for
signature applications of 2y^2=x^3+x/GF(8^91+5).
3.4.4.6. Bernstein's "twist" security
Unlike Curve25519, curve 2y^2=x^3+x/GF(8^91+5) is not
"twist-secure", so a Montgomery ladder implementation for static
private keys often requires public-key validation, which is
achievable by comptuation of Legendre symbol.
In particular, a Montgomery ladder x-only implementation that does
not implement public-key validation will process a value x for which
no y satsifying the equation exists in GF(p). More precsiely, a y
does exist, but it belongs to the extension field GF(p^2). In this
case, the Montgomery ladder treats x as though it were (x,y) where x
is GF(p) but y is not. Such points belong to a "twist" group, and
this group has order:
2^2 * 5 * 1526119141 * 788069478421 * 182758084524062861993 *
3452464930451677330036005252040328546941
Brown 2y^2=x^3+x over 8^91+5 [Page 12]
Internet-Draft 2020-04-03
An adversary can exploit this, by finding such invalid x that
corresond to a lower order group element, and thereby try to learn
partial information about a static private key used by a
non-validating Montgomery ladder implementation.
3.4.4.7. Cheon security
Niche applications in ECC involve revealing points [d^e]G for one
secret number d, and many different integer e, or at least one large
e. One way such points could be reveal is in protocols that employ
a static Diffie--Hellman oracle, a function to compute [d]P from any
point P, which might be applied e times, if e is reasonably small.
Typical ECDH, to be clear, would never reveal such points, for at
least two reasons:
- ECDH is ephemeral, with d not re-used across ECDH sessions, so
that d is used to compute [d]G and [d]Q, and then discarded,
- ECDH is hashed, so though P=[d]G is sent, the point [d]Q is
hashed to get k = H([d]Q), and then [d]Q is discarded, so the
fact that hash is one-way means that k should not reveal [d]Q.
The Brown--Gallant--Cheon q-1 algorithm, finds d given [d^e]G if
e|q-1, with approximately sqrt(q/e) elliptic curve operations. The
Cheon q+1 algorithm finds d given all the points [d]G, [d^2]G,
... [d^e]G if e|q+1. These algorithm rely on factors e of q-1 or
q+1, so the factorization of these numbers affects the security
against the algorithm. Cheon security refers to the ability to
render these algoirthms unusable.
It is possible seek out curves such that q-1 and q+1 have no small
factors e.
The curve 2y^2=x^3+x/GF(8^91+5) has typical Cheon security in terms
of the factorization of q-1 and q+1. Therefore, in the niche
applications that reveal the requisite points, mitigations ought to
be applied, such as limiting the rate of revealing points, or using
different value d as much as possible (one d per recipient).
For 2y^2=x^3+x/GF(8^91+5) the factorization of q-1 and q+1 are:
To be completed.
Brown 2y^2=x^3+x over 8^91+5 [Page 13]
Internet-Draft 2020-04-03
4. Encoding points
Elliptic curve cryptography uses points for public keys and raw
shared secrets.
Abstractly, points are mathematical objects. For curve 2y^2=x^3+x,
a point is either a pair (x,y), where x and y are elements of
mathematical field, or a special point O, both of whose coordinates
may be deemed as infinity.
For curve 2y^2=x^3+x/GF(8^91+5), the coordinates x and y of the
point (x,y) are integers modulo 8^91+5, which can be represented as
integers in the interval [0,8^91+4].
Note: for practicality, an implementation will often internally
represent the x-coordinate as a ratio [X:Z] of field elements.
Each field element has multiple representations, but [x:1] can
viewed as normal representation of x. (Infinity can be then
represented by [1:0], though one must be careful.)
To interoperably communicate, points must be encoded as byte
strings.
This draft specifies an encoding of finite points (x,y) as strings
of 34 bytes, as described in the following sections.
Note: The 34-byte encoding is not injective. Each point is
generally among a group of four points that share the same byte
encoding.
Note: The 34-byte encoding is not surjective. Approximately half
of 34-byte strings do not encode a point (x,y).
Note: In many typical ECC schemes, the 34-byte encoding works
well, despite being neither injective nor surjective.
4.1. Point encoding process
4.1.1. Summary
A point (x,y) is encoded by the little-endian byte representation of
x or -x, whichever fits into 34 bytes.
4.1.2. Details
A point (x,y) is encoded into 34 bytes, as follows.
Brown 2y^2=x^3+x over 8^91+5 [Page 14]
Internet-Draft 2020-04-03
First, ensure that x is fully reduced mod p=8^91+5, so that
0 <= x < 8^91+5.
Second, further reduce x by a flipping its sign, as explained next.
Let
x' =: min(x,p-x) mod 2^272.
Third, set the byte string b to be the little-endian encoding of the
reduced integer x', by finding the unique integers b[i] such that
0<=b[i]<256 and
(x' mod 2^272) = sum (0<=i<=33, b[i]*256^i).
Pseudocode can be found in Appendix C.
Note: The loss of information that happens upon replacing x by -x
corresponds to applying complex multiplication by i on the curve,
because i(x,y) = (-x,iy) is also a point on the curve. (To see
this: note 2(iy)^2 = -(2y^2) = -(x^3+x) = (-x)^3+(-x).) In many
applications, particularly Diffie--Hellman key agreement, this
loss of information is carried through the final shared secret,
which means that Alice and Bob can agree on the same secret 34
bytes.
In ECC systems where the original x-coordinate and the decoded
x-coordinate need to match exactly, then the 34-byte encoding is
probably not usable unless the following pre-encoding procedure is
practical:
Given a point x where x is larger than min(x,p-x), first replace x
by x'=p-x, on the encoder's side, using the new value x' (instead of
x) for any further step in the algorithm. In other words, replace
the point (x,y) by the point (x',y')=(-x,iy). Most algorithms will
also require a discrete logarithm d of (x,y), meaning (x,y) = [d] G
for some point G. Since (x',y') = [i](x,y), we can replace by d'
such that [d']=[i][d]. Usually, [i] can be represented by an
integer, say j, and we can compute d' = jd (mod ord(G)).
4.2. Point decoding process
4.2.1. Summary
The bytes are little-endian decoded into an integer which
becomes the x-coordinate. Public-key validation done if needed. If
needed, the y-coordinate is recovered.
Brown 2y^2=x^3+x over 8^91+5 [Page 15]
Internet-Draft 2020-04-03
4.2.2. Detail
If byte i is b[i], with an integer value between 0 and 255
inclusive, then
x = sum( 0<=i<=33, b[i]*256^i)
Note: a value of -x (mod p) will also be suitable, and results in
a point (-x,y') which might be different from the originally
encoded point. However, it will be one of the points [i](x,y) or
-[i](x,y) where [i] means complex multiplication by [i].
In many cases, such as Diffie--Hellman key agreement using the
Montgomery ladder, neither the original value of x or -x nor
coordinate y of the point is needed. In these cases, the decoding
steps can be considered completed.
+-------------------------------------------------------+
| |
| \ W / /A\ |R) |N | I |N | /G ! |
| \/ \/ / \ |^\ | \| | | \| \_7 0 |
| |
| |
| WARNING: Some byte strings b decode to an invalid |
| point (x,y) that does not belong to the curve |
| 2y^2=x^3+x. In some situations, such invalid b can |
| lead to a severe attack. In these situations, the |
| decoded point (x,y) MUST be validated, as described |
| below in Section 4. |
| |
+-------------------------------------------------------+
In cases where a value for at least one of y, -y, iy, or -iy is
needed such as Diffie--Hellman key agreement using some other
coordinate system (such as one might need when converting to Edwards
coordinates), the candidate value can be obtained by computing a
square root:
y = ((x^3+x)/2)^(1/2).
In some cases, it is important for the decoded value of x to match
the original value of x exactly. In that case, the encoder should
use the procedure that replace x by p-x, and adjusts the discrete
logarithm appropriately. These steps can be done by the encoder,
with the decoder doing nothing.
Brown 2y^2=x^3+x over 8^91+5 [Page 16]
Internet-Draft 2020-04-03
5. Point validation
In elliptic curve cryptography, scalar multiplying an invalid public
key by a private key risks leaking information about the private
key.
Note: For curve 2y^2=x^3+x over 8^91+5, the underlying attacks are
a little milder than the average a typical elliptic curve.
To avoid leaking information about the private, the public key can
be validated, which includes various checks on the public key.
5.1. When to validate
This section specifies several strategies.
5.1.1. Mandatory validation
As a precautionary defense-in-depth, an impelementation MAY opt to
apply mandatory validation, meaning every public key (and point) is
validated.
5.1.2. Simplified validation
A small, general-purpose, implementation aiming for high speed might
not be able to afford the cost of mandatory validation from Section
4.1.1, because each validation costs about 10% of a scalar
multiplication.
As a practical middle groun, an impelmentatio MAY opt to apply
simplified validation, which is the rule is that a distrusted public
key is validated before being scalar multiplied by a static secret
key.
+---------------------------------------------------------------+
| STATIC |
| SECRET |
| KEY ------\ _ ___ |
| + ) PUBLIC |\/| | | (_` | |
| UNTRUSTED ------/ KEY | | \_/ ._) | BE VALIDATED. |
| PUBLIC |
| KEY |
+---------------------------------------------------------------+
Note: Simplified validation implies that when the secret key is
ephemeral (for example, used in one Diffie--Hellman transaction),
the public key need not be validated.
Brown 2y^2=x^3+x over 8^91+5 [Page 17]
Internet-Draft 2020-04-03
Note: Simplified validation implies that when the point being
scalar multiplied, is a known valid fixed point, or a previously
validated public key (including a public key from a certificate in
which the certification authority has a policy to valid public
keys), then validation is not needed.
5.1.4. Minimal validation
An implementation MAY opt to use minimal validation, meaning doing
as little point validation as possible, just enough to resist known
attack against the implementation.
The curve 2y^2=x^3+x is not twist-secure: using the Montgomery
ladder for scalar multiplication is not enough to thwart invalid
public key attacks.
For example, consider a static hashed-ECDH implementation
implemeneted with a Montgomery ladder, such that the static secret
key is used at most ten million times hashed-ECDH transactions.
Even if exposed to invalid points on the twist, the secruity risk is
nearly negligible.
5.2. Point validation process
Upon decoding a 34-byte string into x, the next step is to compute
z=2(x^3+x). Then one checks if z has a nonzero square root (in the
field of size 8^91+5). If z has a nonzero square root, then the
represented point is valid, otherwise it is not valid.
Equivalently, one can check that x^3 + x has no square root (that
is, x^3+x is a quadratic non-residue).
To check z for a square root, one can compute the Legendre symbol
(z/p) and check that is 1. (Equivalently, one can check that
((x^3+x)/p)=-1.)
The Legendre symbol can be computed using Gauss' quadratic
reciprocity law, but this requires implementing modular integer
arithmetic for moduli smaller than 8^91+5.
More slowly, but perhaps more simply, one can compute the Legendre
symbol using powering in the field: (z/p) = z^((p-1)/2) =
z^(2^272+2). This will have value 0,1 or p-1 (which is equivalent
to -1).
Brown 2y^2=x^3+x over 8^91+5 [Page 18]
Internet-Draft 2020-04-03
More generally, in signature applications (such as [B2]), where the
y-coordinate is also needed, the computation of y, which involves
computing a square root will generally include a check that x is
valid.
OPTIONAL: In some rare situations, it is also necessary to ensure
that the point has large order, not just that it is on the curve.
For points on this curve, each point has large order, unless it has
torsion by 12. In other words, if [12]P != O, then the point P has
large order.
OPTIONAL: In even rarer situations, it may be necessary to ensure
that a point P also has a prime order n = ord(G). The costly method
to check this is checking that [n]P = O. An alternative method is
to try to solve for Q in the equation [12]Q=P, which involves
methods such a division polynomials.
To be completed.
6. OPTIONAL encodings
The following two encodings are not usually required to obtain
interoperability in the typical ECC applications, but can sometimes
be useful.
6.1. Encoding scalars
Scalar (integer point multipliers) sometimes needed to be encoding
as byte strings, at least internally to an implementation.
Basically, little-endian byte encoding of integers is recommended.
In Diffie--Hellman only implementations, the scalars s and p-s
really have not significant distinction, so all scalars can be
represented with 34 bytes.
Applications:
- Digital signature in ECC generallly require scalar encodings.
This draft does not specify signature algorithms in detail, only
providing some general suggestions.
Brown 2y^2=x^3+x over 8^91+5 [Page 19]
Internet-Draft 2020-04-03
- An implementation needs to store scalars, because scalars are
used at least twice, and must be stored between these two uses.
For example, in elliptic curve Diffie--Hellman, Alice has scalar
a, sends Bob point aG, keeps scalar a until she receives point
B from Bob, to which she then applies aB. (If a is ephemeral,
she then deletes a.) An implementation is free to use any
encoding of scalar, but implementation are often constructed in
modular pieces, and any pieces handling the same scalar need to
be able to convey the scalar.
6.2. Encoding strings as points
In niche applications, it may be desired to encode an arbtirary
string as a point on a curve. Example reasons to encode arbitrary
34-byte strings include:
- Encoding passwords (or their hashes) for use in
password-authenticated key exchange.
- Hiding the fact that ECC is being used.
To this end, this section sketches a method to reversibly encode
any 34-byte string as a point.
Note: To encode variable-length strings as points, one can first
compute a 34-byte hash of the variable-length string, and then
encode the hash. Encoding of variable-length strings is not, and
cannot be, reversible.
Note: The point decoding scheme of Section 3.2 does not suffice to
encode strings, becausse only about half of all 34-byte strings
are decodable.
Note: The string-as-point encoding has the the property that only
about half of all points are decodable as 34-bytes strings.
Encoding a uniformly distributed 34-byte string as a point yields
non-uniformly distributed points.
The encoding is called Elligator i.
Note: The Elligator i encoding is a minor variation of the
Elligator 2 construction [Elligator], introduced in [B1]. The
variation is necessary because Elligator 2 fails for curves with
j-invariant 1728, and curve 2y^2=x^3+x has j-invariant 1728.
Fix a square root i of -1 in the field in GF(8^91+5). For example,
2^(8^89+1) mod 8^91+5.
Brown 2y^2=x^3+x over 8^91+5 [Page 20]
Internet-Draft 2020-04-03
To encode a 34-byte string b,
1. Let b represent a field element r, using little-endian base
256.
2. Compute x = i-3i/(1-ir^2). Let j=1.
3. If 2y^2=x^3+x has no solution y, then replace x by x+i and j by
j+1.
4. Find two solutions y[1] and y[2] to 2y^2=x^3+x, such that
y[1]<y[2].
5. Compute y=y[j].
Now (x,y) is a point on the curve 2y^2=x^3+x.
The Elligator i encoding is reversible, because it has the decoding
sketched below.
If y>p-y, replace x by x-i. Solve for s = -i - 3/(i-x). Let r =
sqrt(s). If r > p-r, replace r by p-r. Write r in little-endian
base 256 to get a 34-byte string b.
Note: Just to illustrate a constrast between Elligator i encoding
and the normal point encoding, consider the useless example of
applying both encodings. Start with 34-byte string b. Apply
Elligator i encoding to get a point (x,y). Apply the point
encoding to (x,y) to get a 34-byte string b'. In summary,
b'=encode(encode(b)). The byte string b' has no significant
relation to b. The map b->b' from 34-byte strings to themselves
is lossy (non-injective) with ratio ~4:1, and the image set is
about one quarter of all 34-byte strings.
7. IANA Considerations
This document requires no actions by IANA, yet.
8. Security considerations
No cryptographic algorithm is without risk, but risk is difficult to
quantify.
This section lists the most plausible threats against
2y^2=x^3+x/GF(8^91+5), comparing their risk to a typical generic
curve in ECC, or in some cases, to specific well-established
curves in ECC.
Brown 2y^2=x^3+x over 8^91+5 [Page 21]
Internet-Draft 2020-04-03
8.1. Field choice
The field 8^91+5 has the following risks.
- 8^91+5 is a special prime. As such, it is perhaps vulnerable to
some kind of attack. For example, for some curve shapes, the
supersingularity depends on the prime, and the curve size is
related in a simple way to the field size, causing a potential
correlation between the field size and the effectiveness of an
attack, such as the Pohlig--Hellman attack. In summary, field
size is positively correlated to some known attacks, and perhaps a
special field size is positively correlated to a potential attack.
Nonetheless, many other standard curves, such as the NIST P-256
and Curve25519, also use special prime field sizes. In this
regard, all these special field curves have a similar risk.
Yet other standard curves, such as the Brainpool curves, use
pseudorandom field sizes, reducing their risk to potential
special-field attack.
- 8^91+5 arithmetic implementation, while implementable in five
64-bit words, has some risk of overflowing, or of not fully
reducing properly. Perhaps a smaller field, such as that used in
Curve25519, has a simpler reduction and overflow-avoidance
properties.
- 8^91+5, by virtue of being well-above 256 bits in size, risks its
user doing extra, and perhaps unnecessary, computation to protect
their 128-bit keys, whereas smaller curves might be faster (as
expected) yet still provide enough security. In other words, the
extra computational cost for exceeding 256 bits is wasteful, and
partially a form of denial of service.
- 8^91+5 is smaller than some other six-symbol primes: 8^95-9,
9^99+4 and 9^87+4. Therefore, arguably, 8^91+5 fails to
absolutely maximize field size relative to Kolmogorov complexity.
In particular, curves defined over larger field size have better
Pollard rho resistance (of the ECDLP).
Nonetheless, the primes 9^99+4 and 9^87+4 are not close to a power
of two, so probably suffer from much slower implementation than
8^91+5, which is a significant runtime cost, and perhaps also a
security risk (due to implementation bugs).
Brown 2y^2=x^3+x over 8^91+5 [Page 22]
Internet-Draft 2020-04-03
The prime 8^95-9 is, just like 8^91+5, very close to a power of
two. So should have comparable efficiency for basic field
arithmetic operations, such as addition, multiplication and
reduction. The field 8^95-9 is a little larger, but can still be
implemented using five 64-bit words. Being larger, 8^95-9, it has
a slightly greater risk than 8^91+5 of leading to an arithmetic
overflow implementation fault in field arithmetic. Field size
8^95-9 has much less simple powering algorithms for computing
field inverses, Legendre symbols, and square roots: so these
operations, often important for ECC, may require more code, more
runtime, and perhaps more risk of implementation bug.
- 8^91+5 is smaller than 2^283 (the field size for curve sect283k1
[SEC2], [Zigbee]), and many other five-symbol and four-symbol
prime powers (such as 9^97). It provides less resistance to
Pollard rho than such larger prime powers. Recent progress in the
elliptic curve discrete logarithm problem, [HPST] and [Nagao], is
the main reason to prefer prime fields instead of power of prime
fields. A second reason to prefer a prime field (including the
field of size 8^91+5) over small characteristic fields is the
generally better software speed of large characteristic field.
(Better software speed is mainly due to general-purpose hardware
often having dedicated fast multiplication circuits:
special-purpose hardware should make small characteristic field
faster.)
- The Kolmogorov complexity of 8^91+5 as six symbols is only minimal
for decimal exponential complexity: but it is not minimal if other
types of complexity measures are allowed. For example, if we
allow the exclamation mark for the factorial operation -- which is
quite standard notation! -- primes larger than 8^91+5 expressible
in fewer symbols. For example, 94!-1 is a 485-bit prime number,
expressible in five symbols. Such numbers, so far as I know, are
not close to a power of two, so would have similar inefficiency
and implementability defects to primes like 9^99+4 and 9^87+4.
Such inefficiencies could resaonably by the curve choice criteria,
ruling out such primes.
Arguably, in traditional mathematical notation, the symbol '^' is
not actually written, with operation being marked by the use of
superscripts. In this view, using an ASCII character count
arugably gives unduly low weight to the factorial operation as
compared to exponentiation.
See [B1] for further discussion about the relative merits of 8^91+5.
Brown 2y^2=x^3+x over 8^91+5 [Page 23]
Internet-Draft 2020-04-03
Note: For any form of ECC, finite field multiplication can be
achieved most quickly by using hardware integer multiplication
circuits. It is critical that those circuits have no bugs or
backdoors. Furthermore, those circuits typically can only
multiply integers smaller than the field elements. Larger inputs
to the circuits will cause overflows. It is critical to avoid
these overflows, not just to avoid interoperability failures, but
also to avoid attacks where the attackers supply inputs likely
induce overflows [bug attacks], [IT].
To be completed:
Projective coordinates are not suitable as the final representation
of an elliptic curve point, for two reasons.
- Projective coordinates for a point are generally not unique: each
point can be represented in projective coordinates in multiple
different ways. So, projective coordinates are unsuitable for
finalizing a shared secret, because the two parties computing the
shared secret point may end up with different projective
coordinates.
- Projective coordinates have been shown to leak information about
the scalar multiplier [PSM], which could be the private
key. It would be unacceptable for a public key to leak
information about the private key. In digital signatures, even a
few leaked bits can be fatal, over a few signatures
[Bleichenbacher].
Therefore, the final computation of an elliptic curve point, after
scalar multiplication, should translate the point to a unique
representation, such as the affine coordinates described in this
report.
For example, when using a Montgomery ladder, scalar multiplication
yields a representation (X:Z) of the point in projective
coordinates. Its x-coordinate is then x=X/Z, which can be computed
by computing the 1/Z and then multiplying by X.
The safest, most prudent way to compute 1/Z is to use a side-channel
resistant method, in particular at least, a constant-time method.
This reduces the risk of leaking information about Z, which might in
turn leak information about X or the scalar multiplier. Fermat
inversion, computation of Z^(p-2) mod p, is one method to compute
the inverse in constant time (if the inverse exists).
Brown 2y^2=x^3+x over 8^91+5 [Page 24]
Internet-Draft 2020-04-03
8.2. Curve choice
A first risk of using 2y^2=x^3+x is the fact that it is a special
curve. It is special in having complex multiplication leading
to an efficient endomorphism. Miller, in 1985, already suggested
exercising prudence when considering such special curves. Gallant,
Lambert and Vanstone found ways to slightly speed up Pollard rho
given such an endomorphism, but no other attacks have been found.
Menezes, Okamoto and Vanstone (MOV) found an attack on special
elliptic curves, of low embedding degree. The curve
2y^2=x^3+x/GF(8^91+5) is not vulnerable to their attack, but if one
changes the underlying to some different primes, say p', the
resulting curve 2y^2=x^3+x/GF(p') is vulnerable to their attack for
about half of all primes. Because the MOV was later than Miller's
caution from 1984, Miller's prudence seems prescient. Perhaps he
was also prescient about yet other potential attacks (still
unpublished), and these attacks might affect 2y^2=x^3+x/GF(8^91+5).
Many other standard curves, NIST P-256 [NIST-P-256], Curve25519,
Brainpool [Brainpool], do not have any efficient complex
multiplication endomorphisms. Arguably, these curves comply to
Miller's advice to be prudent about special curves.
Yet other (fairly) standard curves do, such as NIST K-283 (used in
[Zigbee]) and secp256k1 (see [SEC2] and [BitCoin]). Furthermore, it
is not implausible [KKM] that special curves, including those
efficient endomorphisms, may survive an attack on random curves.
A second risk of 2y^2=x^3+x over 8^91+5 is the fact that it is not
twist-secure. What may happen is that an implementer may use the
Montgomery ladder in Diffie--Hellman and re-use private keys. They
may think, despite the (ample?) warnings in this document, that
public key validation in unnecessary, modeling their implementation
after Curve25519 or some other twist-secure curve. This implementer
is at risk of an invalid public key attack. Moreover, the
implementer has an incentive to skip public-key validation, for
better performance. Finally, even if the implementer uses
public-key validation, then the cost of public-key validation is
non-negligible.
Brown 2y^2=x^3+x over 8^91+5 [Page 25]
Internet-Draft 2020-04-03
A third risk is a biased ephemeral private key generation in a
digital signature scheme. Most standard curves lack this risk
because the field size is close to a power of two, and the cofactor
is a power of two. Curve 2y^2=x^3+x over 8^91+5 has a base point
order which is approximately a power of two divided by nine (because
its cofactor is 72=8*9.) As such, it is more vulnerable than
typical curves to biased ephemeral keys in a signature scheme.
A fourth risk is a Cheon-type attack. Few standard curves address
this risk, and 2y^2=x^3+x over 8^91+5 is not much different.
A fifth risk is a small-subgroup confinement attack, which can also
leak a few bits of the private key. Curve 2y^2=x^3+x over 8^91+5
has 72 elements whose order divides 12.
8.3. Encoding choices
To be completed.
8.4. General subversion concerns
Although the main motivation of curve 2y^2=x^3+x over 8^91+5 is to
minimize the risk of subversion via a backdoor ([Gordon], [YY],
[Teske]), it is only fair to point out that its appearance in this
very document can be viewed with suspicion as an possible effort at
subversion (via a front-door). (See [BCCHLV] for some further
discussion.)
Any other standardized curve can be view with a similar suspicion
(except, perhaps, by the honest authors of those standards for whom
such suspicion seems absurd and unfair). A skeptic can then examine
both (a) the reputation of the (alleged) author of the standard,
making an ad hominem argument, and (b) the curve's intrinsic merits.
By the very definition of this document, the reader is encouraged to
take an especially skeptical viewpoint of curve 2y^2=x^3+x over
8^91+5. So, it is expected that skeptical users of the curve will
either
- use the curve for its other merits (other than its backdoor
mitigations), such as efficient endomorphism, field inversion,
high Pollard rho resistance within five 64-bit words, meanwhile
holding to the evidence-supported belief ECC that is now so mature
that worries about subverted curves are just far-fetched nonsense,
or
Brown 2y^2=x^3+x over 8^91+5 [Page 26]
Internet-Draft 2020-04-03
- as an additional of layer of security in addition to other
algorithms (ECC or otherwise), as an extra cost to address the
non-zero probability of other curves being subverted.
To paraphrase, consider users seriously worried about subverted
curves (or other cryptographic algorithms), either because they
estimate as high either the probability of subversion or the value
of the data needing protection. These users have good reason to
like 2y^2=x^3+x over 8^91+5 for its compact description.
Nevertheless, the best way to resist subversion of cryptographic
algorithms seems to be combine multiple dissimilar cryptographic
algorithms, in a strongest-link manner. Diversity hedges against
subversion, and should the first defense against it.
8.5. Concerns about 'aegis'
The exact curve 2y^2=x^3+x/GF(8^91+5) was (seemingly) first
described to the public in 2017 [AB]. So, it has a very low age, at
least compare to more established curves.
Furthermore, it has not been submitted for a publication with peer
review to any cryptographic forum such as the IACR conferences like
Crypto and Eurocrypt. So, it has only been reviewed by very few
eyes.
Arguably, other reviewers have little incentive to study it
critically, for several reasons. The looming threat of a quantum
computer has diverted many researchers towards studying post-quantum
cryptography, such as supersingular isogeny Diffie--Hellman. The
past disputes over NIST P-256 and Curve25519 (and several other
alternatives) have perhaps tired some reviewers, many of whom
reasonably wish to concentrate on deployment of ECC.
So, under the metric of aegis, as in age times eyes (times
incentive), 2y^2=x^3+x/GF(8^91+5) scores low. Counting myself (but
not quantifying incentive) it gets an aegis score of 0.1 (using a
rating 0.1 of my eyes factor in the aegis score: I have not
discovered any major ECC attacks of my own.) This is far smaller
than my estimates (see below) some more well-studied curves.
Nonetheless, the curve 2y^2=x^3+x over 8^91+5 at least has some
similarities to some of the better-studied curves with much higher
aegis:
Brown 2y^2=x^3+x over 8^91+5 [Page 27]
Internet-Draft 2020-04-03
- Curve25519: has field size 8^85-19, which a little similar to
8^91+5; has equation of the form by^2=x^3+ax+x, with b and a
small, which is similar to 2y^2=x^3+x. Curve25519 has been around
for over 10 years, has (presumably) many eyes looking at it, and
has been deployed thereby creating an incentive to study. An
estimated aegis for Curve25519 is 10000.
- NIST P-256: has a special field size, and maybe an estimated aegis
of 200000. (It is a high-incentive target. Also, it has received
much criticism, showing some intent of cryptanalysis. Indeed,
there has been incremental progress in finding minor weakness
(implementation security flaws), suggestive of actual
cryptanalytic effort.) The similarity to 2y^2=x^3+x over 8^91+5
is very minor, so very little of the P-256 aegis would be relevant
to this document.
- secp256k1: has a special field size, though not quite as special
as 8^91+5, and has special field equation with an efficient
endomorphism by a low-norm complex algebraic integer, quite
similar to 2y^2=x^3+x. It is about 17 years old, and though not
studied much in academic work, its deployment in Bitcoin has at
least created an incentive to attack it. An estimated aegis for
secp256k1 is 10000.
- Miller's curve: Miller's 1985 paper introducing ECC suggested,
among other choices, a curve equation y^2=x^3-ax, where a is a
quadratic non-residue. Curve 2y^2=x^3+x is isomorphic to
y^2=x^3-x, essentially one of Miller's curves, except that a=1 is
a quadratic residue. Miller's curve may not have been studied
intensely as other curves, but its age matches that ECC itself.
Miller also hinted that it was not prudent to use a special curve
y^2=x^3-ax: such a comment may have encouraged some cryptanalysts,
but discouraged cryptographers, perhaps balancing out the effect
on the eyes factor the aegis. An estimated aegis for Miller's
curves is 300.
Obvious cautions to the reader:
- Small changes in a cryptographic algorithm sometimes cause large
differences in security. So security arguments based on
similarity in cryptographic schemes should be given low priority.
Brown 2y^2=x^3+x over 8^91+5 [Page 28]
Internet-Draft 2020-04-03
- Security flaws have sometimes remained undiscovered for years,
despite both incentives and peer reviews (and lack of hard
evidence of conspiracy). So, the eyes-part of the aegis score is
very subjective, and perhaps vulnerable false positives by a herd
effect. Despite this caveat, it is not recommended to ignore the
eyes factor in the aegis score: don't just flip through old books
(of say, fiction), looking for cryptographic algorithms that might
never have been studied.
9. References
9.1. Normative References
[BCP14] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997,
<http://www.rfc-editor.org/info/bcp14>.
9.2. Informative References
To be completed.
[AB] A. Allen and D. Brown. ECC mod 8^91+5, presentation to CFRG,
2017.
<https://datatracker.ietf.org/doc/slides-99-cfrg-ecc-mod-8915/>
[AMPS] Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, and
Juraj Somorovsky. Prime and Prejudice: Primality Testing Under
Adversarial Conditions, IACR ePrint,
2018. <https://ia.cr/2018/749>
[B1] D. Brown. ECC mod 8^91+5, IACR ePrint, 2018.
<https://ia.cr/2018/121>
[B2] D. Brown. RKHD ElGamal signing and 1-way sums, IACR ePrint,
2018. <http://ia.cr/2018/186>
[KKM] A. Koblitz, N. Koblitz and A. Menezes. Elliptic Curve
Cryptography: The Serpentine Course of a Paradigm Shift, IACR
ePrint, 2008. <https://ia.cr/2008/390>
[BCCHLV] D. Bernstein, T. Chou, C. Chuengsatiansup, A. Hulsing,
T. Lange, R. Niederhagen and C. van Vredendaal. How to
manipulate curve standards: a white paper for the black hat, IACR
ePrint, 2014. <https://ia.cr/2014/571>
[Elligator] (((To do:))) fill in this reference.
Brown 2y^2=x^3+x over 8^91+5 [Page 29]
Internet-Draft 2020-04-03
[NIST-P-256] (((To do:))) NIST recommended 15 elliptic curves for
cryptography, the most popular of which is P-256.
[Zigbee] (((To do:))) Zigbee allows the use of a
small-characteristic special curve, which was also recommended by
NIST, called K-283, and also known as sect283k1. These types of
curves were introduced by Koblitz. These types of curves were
not recommended by NSA in Suite B.
[Brainpool] (((To do:))) the Brainpool consortium (???) recommended
some elliptic curves in which both the field size and the curve
equation were derived pseudorandomly from a nothing-up-my-sleeve
number.
[SEC2] Standards for Efficient Cryptography. SEC 2: Recommended
Elliptic Curve Domain Parameters, version 2.0, 2010.
<http://www.secg.org/sec2-v2.pdf>
[IT] T. Izu and T. Takagi. Exceptional procedure attack on elliptic
curve cryptosystems, Public key cryptography -- PKC 2003, Lecture
Notes in Computer Science, Springer, pp. 224--239, 2003.
[PSM] (((To do:))) Pointcheval, Smart, Malone-Lee. Projective
coordinates leak.
[BitCoin] (((To do:))) BitCoin uses curve secp256k1, which has an
efficient endomorphism.
[Bleichenbacher] To do: Bleichenbacher showed how to attack DSA
using a bias in the per-message secrets.
[Gordon] (((To do:))) Gordon showed how to embed a trapdoor in DSA
parameters.
[HPST] Y. Huang, C. Petit, N. Shinohara and T. Takagi. On
Generalized First Fall Degree Assumptions, IACR ePrint 2015.
<https://ia.cr/2015/358>
[Nagao] K. Nagao. Equations System coming from Weil descent and
subexponential attack for algebraic curve cryptosystem, IACR
ePrint, 2015. <http://ia.cr/2013/549>
[Teske] E. Teske. An Elliptic Curve Trapdoor System, IACR ePrint,
2003. <http://ia.cr/2003/058>
[YY] (((To do:))) Yung and Young, generalized Gordon's ideas into
Secretly-embedded trapdoor ... also known as a backdoor.
Brown 2y^2=x^3+x over 8^91+5 [Page 30]
Internet-Draft 2020-04-03
Appendix A. Test vectors
The following are some test vectors.
000000000000000029352b31395e382846472f782b335e783d325e79322054534554
00000000000000000000000000000000000000000000000000000000000000000117
c8c0f2f404a9fabc91c939d8ea1b9e258d82e21a427b549f05c832cf8d48296ffad7
5f336f56f86de3d52b0eab85e527f2ac7b9d77605c0d5018f5faa4243fd462b1badd
fc023b3f03b469dca32446db80d9b388d753cc77aa4c3ee7e2bb86e99e7bed38f509
8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221
8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221
The test vectors are explained as follows. (Pseudocode generating
them is supplied in Appendix C.2.)
Each line is 34 bytes, representing a non-negative 272-bit integer.
The integer encoding is hexadecimal, with most significant hex
digits on the left: which is big-endian.
Note: Public keys are encoded as 34-byte strings are little, so
one reverses the order of the bytes found in the test vectors.
The pseudocode in Appendix C.2 should make this clear.
Each integer is either a scalar (a multiplier of curve points), or
the byte representation of a point P through its x-coordinate or the
x-coordinate of iP (which is the the mod 8^91+5 negation of the
x-coordinate of P).
The first line is a scalar integer x, which would serve as a very
insecure private key. Its nonzero bytes are the ASCII
representation of the string "TEST 2y^2=x^3+x/GF(8^91+5)", with the
byte order reversed.
The second line is a representation of G, a base point on the curve.
The third line is the representation of z = xG.
The fourth and fifth lines represent updated values of x and z,
obtained after application of the following 100000 scalar
multiplications.
A loop of 50000 iterations is performed. Each iteration consists of
two re-assignments: z = xz and x = zG via scalar multiplications.
In the second assignment, the byte representation of the input point
z is used as the byte representation of an scalar. Similarly, the
output x is the byte representation of the point, which is will used
as as the byte representation of the scalar.
Brown 2y^2=x^3+x over 8^91+5 [Page 31]
Internet-Draft 2020-04-03
The purpose of the large number of iterations is to catch a bug that
has probability larger than 1/100000 of arising on pseudorandom
inputs. The iterations do nothing to find rarer bugs (that an
adversary can invoke), or silent bugs (side channel leaks).
The sixth and seventh lines are equal to each other. As explained
below, the equality of these lines represents the fact the Alice and
Bob can compute the same shared DH secret. The purpose of these
lines is not catch any more bugs, but simply a sanity check that
Diffie--Hellman is likely to work.
Alice initializes her DH private key to x, as already computed on
the fourth line of the test vectors (which was the result of 100000
iterations). She then replaces this x by x^900 mod q (where q is
the prime which is the order of the order of the base point G).
Bob sets his private key y as follows. He begins with y being the
34-byte ASCII string whose initial characters are "yet another test"
(not including the quotes, of course). He then reverses the order
of bytes, considers this to be a scalar, and reassigning y with the
equation y = yG. (So, the y on the left is new, the y on the right
is old, they are not the same.) Then another reassignment is done,
as y = yy, where the on the right side of the equation one y is
treated as a scalar, the other as a point. The left side is the new
value of y. Finally, Bob's replaces y by y^900 mod order(G), just
as Alice did.
Both lines are xyG. The first can be computed as y(xG), and the
second as x(yG). The equality of the two lines can be used to
self-test an implementation, even if the implementation being tested
disagrees with the test vectors above.
Appendix B. Minimizing trapdoors and backdoors
To main advantage of curve 2y^2=x^3+x/GF(8^91+5) over almost all
other elliptic curves is that its almost minimal Kolmogorov
complexity among curves of sufficient resistance to the Pollard rho
attack on the discrete logarithm problem.
See [AB] and [B1] for some details.
The curve can be described with 21 characters:
2 y ^ 2 = x ^ 3 + x / G F ( 8 ^ 9 1 + 5 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Brown 2y^2=x^3+x over 8^91+5 [Page 32]
Internet-Draft 2020-04-03
Those familiar with ECC will recognize that these 21 characters
suffice to specify the curve up to the level of detail needed to
describe the cost of the Pollard rho algorithm, as well as many
other security properties (especially resistance to other known
attacks on the discrete logarithm problem, such as Pohlig--Hellman
and Menezes--Okamoto--Vanstone).
Note: The letters GF mean Galois Field, and are quite traditional
mathematics, and every elliptic curve in cryptographic needs to
use some notation for the finite field.
We may therefore describe the curve's Kolmogorov complexity as 21
characters.
Note: The idea of low Kolmogorov complexity is hard to specify
exactly. Nonetheless, a claim of nearly minimal Kolmogorov
complexity is quite falsifiable. The falsifier need merely
specify several (secure) elliptic curves using 21 or fewer
characters. (But if the specification new interpretations, then
new interpretation might also be used to further compress the
specification of 2y^2=x^3+x/GF(8^91+5) to below 21 characters.)
The curve is actually isomorphic to a curve specifiable in 20
characters:
y^2=x^3-x/GF(8^91+5)
Generally, isomorphic curves have essentially equivalently hard
discrete logarithm problems, so one could argue that curve
2y^2=x^3+x/GF(8^91+5) could be rated as having Kolmogorov complexity
at most 20 characters. Isomorphic curves, however, may differ
slightly in security, due to issues of efficiency, and
implementability. The 21-character specification uses an equation
in Montgomery form, which creates an incentive to use the Montgomery
ladder algorithm, which is both safe and efficient [Bernstein?].
Allowing for non-prime fields, then the binary-field curve known
sect283k1 has a 22-character description:
y^2+xy=x^3+1/GF(2^283)
This has a longer overall specification, but the field part is
shorter field specification. Perhaps an isomorphic curve can be
found (one with three terms), so that total length is 20 or fewer
characters.
Brown 2y^2=x^3+x over 8^91+5 [Page 33]
Internet-Draft 2020-04-03
However, a non-prime field tends to be slower in software, and is
perhaps riskier due to some recent research on attacking non-prime
field discrete logarithms and elliptic curves, such as recent
asymptotic advances on discrete logarithms in low-characteristic
fields [HPST] and [Nagao]. According to [Teske], some
characteristic-two elliptic curves could be equipped with a secretly
embedded backdoor.
The units of characters as measuring Kolmogorov complexity is not
calibrated as bits of information. Doing so formally would be very
difficult, but the following approach might be reasonable.
Set the criteria for the elliptic curve. For example, e.g. prime
field, size, resistance (of say 2^128 bit operations) to known
attacks on the discrete logarithm problem (Pollard rho, MOV, etc.).
Then list all the possible ECC curve specification with Kolmogorov
complexity of 21 characters or less. Take the base two logarithm of
this number. This is then an calibrated estimate of the number of
bits needed to specify the curve. It should be viewed as a lower
bound, in case some curves were missed. To be completed.
Low Kolmogorov complexity is not directly correlated with security
of the curve.
Note: Indeed, as shown further below, the very insecure examples
exist with lower complexity, by choosing a defective curve
equation.
The benefit of low Kolmogorov complexity is an idea, which general
to cryptography, sometimes called nothing-up-my-sleeve, or
subversion-resistance, or similar. For elliptic curves, the benefit
may be stated as the two following gains.
- Low Kolmogorov complexity defends against insertion of a keyed
trapdoor, meaning the curve can broken using a secret trapdoor,
by an algorithm (eventually discovered by the public at large).
For example, the Dual EC DRBG is known to capable of having such
a trapdoor. Such a trapdoor would information-theoretically
imply an amount of information, comparable the size of the
secret, to be embedded in the curve specification. If the
calibrated estimate for the number of bits is sufficiently
accurate, then such a key cannot be large.
Brown 2y^2=x^3+x over 8^91+5 [Page 34]
Internet-Draft 2020-04-03
- Low Kolmogorov complexity defends against a secret attack
(presumably difficult to discover), which affects a subset of
curves such that (a) whether or not a specific curve is affected
is a somewhat pseudorandom function of its natural
specification, and (b) the probably of a curve being affected
(when drawn uniformly from some sensible of curve
specification), is low. For an example of real-world attacks
meeting the conditions (a) and (b) consider the MOV attack.
Exhaustively finding curve meeting these two conditions is
likely to prevent low Kolmogorov complexity, essentially by the
low probability of the attack, and the independence of attack's
success from the natural Kolmogorov complexity.
- Even more hypothetically, there may yet exist undisclosed
classes of weak curves, or attacks, for which
2y^2=x^3+x/GF(8^91+5) is lucky enough to avoid. This would be a
fluke. A real-world example is prime-order, or low cofactor
curves, which are are among all curves, but which better resist
the Pohlig--Hellman attack.
Of course, low Kolmogorov complexity is not a panacea. The worst
failure would be attacks that increase in strength as Kolmogorov
complexity gets lower. Two examples illustrate this strongly.
Singular cubics, though not formally elliptic curves, are arguably
among the same class of object, and can be described similarly,
using equations and so. For smooth singular curves (irreducible
cubics) a group can be define, using more or less the same
arithmetic as for a elliptic curve. For example y^2=x^3/GF(8^91+5)
is such a cubic. The resulting group has an easy discrete logarithm
problem, because it can be mapped to the field.
Supersingular elliptic curves can also be specified with low
Kolmogorov complexity, and these are vulnerable to MOV attack.
Worse, a low Kolmogorov complexity curve can be described that
suffers from three attacks simultaneously: y^2=x^3+1/GF(2^127-1).
To be completed.
Of course, the weak cubics are vulnerable to extremely well-known
attacks, so when estimating the bits of information in the
Kolmogorov complexity of curves that resist known attacks, we can
ignore such examples. The point of these examples, however, is to
demonstrate that there exists known attacks that affect curves of
low Kolmogorov complexity, and therefore secret attacks might have
the same property.
Brown 2y^2=x^3+x over 8^91+5 [Page 35]
Internet-Draft 2020-04-03
So, it is sensible to disclaim any resistance to secret attacks of
such a nature. For this reason, 2y^2=x^3+x/GF(8^91+5) should be
used with other elliptic curves.
Appendix C. Pseudocode
This section uses a C-like pseudocode to demonstrate both the
well-known algorithms one can use implement this curve, and some
details particular to this curve.
Note: Some implementers, such as C programmers, may prefer such
pseudocode over the wordy and formulaic specifications given
earlier in this draft. Besides the principles and algorithms are
well-known, so I have opted to put the pseudocode in a more
runnable form than traditional language-agnostic pseudocode.
Note: The pseudocode is not standard C (e.g., it uses non-standard
C type __int128), not portable, not thoroughly hardened against
side channels or any other implementation attacks.
Note: The pseudocode is highly constricted to minimize line and
character counts, with Python-like indentation and Lisp-like
clumping of closing delimiters. Tools may exist that can put
transform the pseudocode into more conventional C indentation.
The pseudocode borrows various yet further C brevities: some
idiomatic and conventional, some altogether peculiar. Anything
too indecipherable deserves explanation in a future revision of
this draft.
Note: this pseudocode has not yet received any independent review.
C.1. Scalar multiplication of 34-byte strings
The pseudocode for scalar multiplication provides an interface for
scalar multiplication. A function takes as input 3 pointer to
unsigned character strings; it also returns a Boolean value,
indicating success or failure.
The pseudocode is to be consider to form a single file, pseudo.c,
which is then include into other 3 pieces pseudocode: one to
generate test vectors, one to demo a command-line Diffie--Hellman,
one to demo public-key validation and twist insecurity of the curve.
The file pseudo.c has two sections, one for field arithmetic, and
one form scalar multiplication using Montgomery's ladder.
Brown 2y^2=x^3+x over 8^91+5 [Page 36]
Internet-Draft 2020-04-03
Note: I have been able to improve the speed of Montgomery's ladder
by ~10% using Bernstein's 2-D ladder. I have also been to improve
the speed by ~20% using Gallant--Lambert--Vanstone and Edwards
coordinates. These improvements are not likely to carry through
to a proper optimization regime, since I never used any assembly
optimizations. Also these improvements involve more complex
algorithms, which may suffer higher risk of implementation
attacks.
To be completed.
C.1.1. Field arithmetic for GF(8^91+5)
The field arithmetic pseudocode, is the first part of the file
pseudo.c, implements all the necessary field operations to implement
a Montgomery for elliptic curve 2y^2=x^3+x. This means that it does
not include a square computation: instead it has a Legendre symbol
computation.
Note: The Legendre symbol is used for public-key validation. The
pseudocode implements field inversion and the Legendre symbol
using exponentiation, with the aim of being simple and
constant-time. Alternative algorithms for these tasks are known
to experts.
Brown 2y^2=x^3+x over 8^91+5 [Page 37]
Internet-Draft 2020-04-03
<CODE BEGINS>
#define RZ return z
#define B 34
#define F4j i j=5;for(;j--;)
#define FIX(j,r,k) q=z[j]>>r, z[j]-=q<<r, z[(j+1)%5]+=q*k
#define CMP(a,b) ((a>b)-(a<b))
#define XY(j,k) x[j]*(ii)y[k]
#define R(j,k) (zz[j]>>55*k&((k<2)*M-1))
#define MUL(m,E)\
zz[0]=m(0,0)E(1,4)E(2,3)E(3,2)E(4,1),\
zz[1]=m(0,1)m(1,0)E(2,4)E(3,3)E(4,2),\
zz[2]=m(0,2)m(1,1)m(2,0)E(3,4)E(4,3),\
zz[3]=m(0,3)m(1,2)m(2,1)m(3,0)E(4,4),\
zz[4]=m(0,4)m(1,3)m(2,2)m(3,1)m(4,0);\
z[0]=R(0,0)-R(4,1)*20-R(3,2)*20,\
z[1]=R(1,0)+R(0,1)-R(4,2)*20,\
z[2]=R(2,0)+R(1,1)+R(0,2),\
z[3]=R(3,0)+R(2,1)+R(1,2),\
z[4]=R(4,0)+R(3,1)+R(2,2);\
z[1]+=z[0]>>55; z[0]&=M-1;
typedef long long i;typedef i*f,F[5];typedef __int128 ii,FF[5];
i M=((i)1)<<55;F O={0},I={1};
f fix(f z){i j=0,q;
for(;j<5*2;j++) FIX(j%5,(j%5<4?55:53),(j%5<4?1:-5));
z[0]+=(q=z[0]<0)*5; z[4]+=q<<53; RZ;}
i cmp(f x,f y){i z=(fix(x),fix(y),0); F4j z+=!z*CMP(x[j],y[j]); RZ;}
f add(f z,f x,f y){F4j z[j]=x[j]+y[j]; RZ;}
f sub(f z,f x,f y){F4j z[j]=x[j]-y[j]; RZ;}
f mal(f z,i s,f y){F4j z[j]=y[j]*s; RZ;}
f mul(f z,f x,f y){FF zz; MUL(+XY,-20*XY); {F4j zz[j]=0;} RZ;}
f squ(f z,f x){mul(z,x,x); RZ;}
i inv(f z){F t;i j=272; for(mul(z,z,squ(t,z));j--;) squ(t,t);
return mul(z,t,z), (sub(t,t,t)), cmp(O,z);}
i leg(f y){F t;i j=270; for(squ(t,squ(y,y));j--;) squ(t,t);
return j=cmp(I,mul(y,y,t)), (sub(y,y,y),sub(t,t,t)), !j;}
<CODE ENDS>
This pseudocode makes uses of some extra C-like pseudocode features:
- #define is used to create macros, which expand within the source
code (as in C pre-processing).
- type ii is 128-bit integer
- multiplying a type i by a type ii variable yields a type ii
variable. If both inputs can fit into a type i variable, then
the result has no overflow or reduction: it is exact as a product
of integers.
Brown 2y^2=x^3+x over 8^91+5 [Page 38]
Internet-Draft 2020-04-03
- type ff is array of five type ii values. It is used to represent
a field in a radix expansion, except the limbs (digits) can be
128-bits instead of 64-bits. The variable zz has type ff and is
used to intermediately store the product of two field element
variables x and y (of type f).
- function mod takes an ff variable and produce f variable
representing the same field element. A pseudocode example may be
defined further below.
TO DO: Add some notes (answer these questions):
- How small the limbs of the inputs to function mul and squ must be
to ensure no overflow occurs?
- How small are the limbs of the output of functions mul and squ?
TO DO: add notes answering these questions:
- How small must be the input limbs to avoid overflow?
- How small are the output limbs (to know how to safely use of
output in further calculations).
Note: The partial reduction technique used in the multiplication
pseudocode is sometimes known as lazy reduction. It aims to do
just enough calculation to avoid overflow errors, and thus it may be
regarded as attempt at optimization.
To be completed.
The input variable is x and the output variable is b. The declared
types and functions are as follows:
- type c: curve representative, length-34 array of non-negative
8-bit integers ("characters"),
- type f: field element, a length-5 array of 64-bit integers
(negatives allowed), representing a field element as an integer in
base 2^55,
- type i: 64-bit integers (e.g. entries of f),
- function mal: multiply a field element by a small integer (result
stored in 1st argument),
- function fix: fully reduce an integer modulo 8^91+5,
Brown 2y^2=x^3+x over 8^91+5 [Page 39]
Internet-Draft 2020-04-03
- function cmp: compare two field element (after fixing), returning
-1, 0 or 1.
Note: The two for-loops in the pseudocode are just radix
conversion, from base 2^55 to base 2^8. Because both bases are
powers of two, this amount to moving bits around. The entries of
array b are compute modulo 256. The second loop copies the bits
that the first loop misses (the bottom bits of each entry of f).
Note: Encoding is lossy, several different (x,y) may encode to the
same byte string b. Usually, if (x,y) generated as a part of
Diffie--Hellman key exchange, this lossiness has no effect.
Note: Encoding should not be confused with encryption. Encoding
is merely a conversion or representation process, whose inverse is
called decoding.
- the expression (i)b[j] means that 8-bit integer b[j] is converted
to a 64-bit integer (so is no longer treated modulo 256). (In C,
this is operation is called casting.)
Note: the decode function 'feed' only has 1 for-loop, which is the
approximate inverse of the first of the 2 for-loops in the encode
function 'bite'. The reason the 'bite' needs the 2nd for-loop is
due to the lossy conversion from integers to bytes, whereas in the
other direction the conversion is not lossy. The second loop
recovers the lost information.
C.1.2. Montgomery ladder scalar multiplication
The pseudocode below, the second part of the file pseudo.c,
implements Montgomery's well-known ladder algorithm for elliptic
curve scalar point multiplication, as it applies to the curve
2y^2=x^3+x.
Again, the pseudocode is a continuation of the pseudocode for field
arithmetic, and all previous definitions are assumed.
Brown 2y^2=x^3+x over 8^91+5 [Page 40]
Internet-Draft 2020-04-03
<CODE BEGINS>
#define X z[0]
#define Z z[1]
typedef void _;typedef volatile unsigned char *c,C[B];
typedef F*e,E[2];typedef E*v,V[2];
f feed(f x,c z){i j=((mal(x,0,x)),B);
for(;j--;) x[j/7]+=((i)z[j])<<((8*j)%55); return fix(x);}
c bite(c z,f x){F t;i j=((fix(mal(x,cmp(mal(t,-1,x),x),x))), B),k=5;
for(;j--;) z[j]=x[j/7]>>((8*j)%55); {(sub(t,t,t));}
for(;--k;) z[7*k-1]+=x[k]<<(8-k); {(sub(x,x,x));} RZ;}
i lift(e z,f x,i t){F y;return mal(X,1,x),mal(Z,1,I),t||
leg(mal(y,2,add(y,x,mul(y,x,squ(y,x)))));}
i drop(f x,e z){return
inv(Z)&&mul(x,X,Z)&&(sub(X,X,X)&&sub(Z,Z,Z));}
_ let(e z,e y){i j=2;for(;j--;)mal(z[j],1,y[j]);}
_ smv(v z,v y){i j=4;for(;j--;)add(((e)z)[j],((e)z)[j],((e)y)[j]);}
v mav(v z,i a){i j=4;for(;j--;)mal(((e)z)[j],a,((e)z)[j]);RZ;}
_ due(e z){F a,b,c,d;
mal(X,2,mul(X,squ(a,add(a,X,Z)),squ(b,sub(b,X,Z))));
mul(Z,add(c,a,b),sub(d,a,b));}
_ ade(e z,e u,f w){F a,b,c,d;f ad=a,bc=b;
mul(ad,add(a,u[0],u[1]),sub(d,X,Z)),
mul(bc,sub(b,u[0],u[1]),add(c,X,Z));
squ(X,add(X,ad,bc)),mul(Z,w,squ(Z,sub(Z,ad,bc)));}
_ duv(v a,e z){ade(a[1],a[0],z[0]);due(a[0]);}
v adv(v z,i b){V t;
let(t[0],z[1]),let(t[1],z[0]);smv(mav(z,!b),mav(t,b));mav(t,0);RZ;}
e mule(e z,c d){V a;E o={{1}};i
b=0,c,n=(let(a[0],o),let(a[1],z),8*B);
for(;n--;) c=1&d[n/8]>>n%8,duv(adv(a,c!=b),z),b=c;
let(z,*adv(a,b)); (due(*mav(a,0))); RZ;}
C G={23,1};
i mulch(c db,c d,c b){F x;E p; return
lift(p,feed(x,b),(db==d||b==G))&&drop(x,mule(p,d))&&bite(db,x);}
<CODE ENDS>
The pseudocode function mulch -- which multiplies byte string
(character) representations of point b by the byte string
representation of integer d -- omits public key validation of the
input point b if the base of scalar multiplication is the chosen
fixed base, or if the input integer d and output point db have the
same location.
The reason for the latter omission of public key validation is the
integer d is overwritten presumably the caller of mulch intended to
use d only once, so that d is likely to be an ephemeral secret,
largely obviating the need to validate b.
Brown 2y^2=x^3+x over 8^91+5 [Page 41]
Internet-Draft 2020-04-03
In other words, the caller of mulch can control whether public key
validation is done by choosing the locations of db, b, b
appropriately. (An alternative would be for mulch to include a flag
to indicate whether b needs to be validated. Instead, the
pseudocode tries to make mulch do the sensible choice for
Diffie--Hellman if the caller forgets whether public key validation
is necessary.)
The pseudocode files tv.c, dhe.c and pkv.c, define in the sections
below, demonstrate the use of mulch, and its features regarding
public key validation.
In case, mulch returns a Boolean-valued integer indicating whether b
was valid. If validation was requested by the interface, and b is
invalid, then mulch return false (0), and the memory location db
should remain unaltered.
Note: the pseudocode makes types c and C volatile, with the aim
that the C compiler will preserve attempts to zeroize values of
this type. Such zeroization steps in the pseudocode do add
clutter to the code, but have usually been delimited by
parentheses or braces to indicate their implementation-specific
purpose.
C.1.3. Bernstein's 2-dimensional Montgomery ladder
Bernstein's 2-dimensional ladder is a variant of Montgomery's ladder
that computes aP+bQ, for any two points P and Q, more quickly than
computing aP and bQ separately.
Curve 2y^2=x^3+x has an efficient endomorphism, which allows a point
Q = [i+1]P to compute efficiently. Gallant, Lambert and Vanstone
introduced a method (now called the GLV method), to compute dP more
efficiently, given such an efficient endomorphism. They write d = a
+ eb where e is the integer multiplier corresponding to the
efficient endomorphism, and a and b are integers smaller than d.
(For example, 17 bytes each instead of 34 bytes.)
The GLV method can be combined with Bernstein's 2D ladder algorithm
to be applied to compute dP = (a+be)P = aP + beP = aP + bQ, where
e=i+1.
This algorithm is not implemented by any pseudocode in the version
the draft. (Previous versions had it.)
See [B1] for further explanation and example pseudocode.
Brown 2y^2=x^3+x over 8^91+5 [Page 42]
Internet-Draft 2020-04-03
I have estimate a ~10% speedup of this method compared to the plain
Montgomery ladder. However, the code is more complicated, and
potentially more vulnerable to implementation-based attacks.
C.1.4. GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong)
To be completed.
It is also possible to convert to Edwards coordinates, and then use
the Hisil--Carter--Dawson--Wong (HCDW) elliptic curve arithmetic.
The HCDW arithmetic can be combined with the GLV techniques to
obtain a scalar multiplication potentially more efficient than
Bernstein's 2-dimensional Montgomery. The downside is that it may
require key-dependent array look-ups, which can be a security risk.
I have implemented this, finding ~20% speed-up over my
implementation of the Montgomery ladder. However, this speed-up may
disappear upon further optimization (e.g. assembly), or further
security hardening (safe table lookup code).
C.2 Pseudocode for test vectors
The following pseudocode, describing the contents of a file tv.c,
includes the previously defined file pseudo.c, and stdio.h, and then
generates some test vectors.
<CODE BEGINS>
#include <stdio.h>
#include "pseudo.c"
#define M mulch
void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");}
int main (void){i j=1e5/2,wait=/*your mileage may vary*/7000;
C x="TEST 2y^2=x^3+x/GF(8^91+5)",y="yet another test",z;
M(z,x,G); hx(x),hx(G),hx(z);
fprintf(stderr,"%30s(wait=~%ds, ymmv)","",j/wait);
for(;j--;)if(fprintf(stderr,"\r%7d\r",j),!(M(z,x,z)&&M(x,z,G)))
j=0*printf("Mulch fail rate ~%f :(\n",(2*j)/1e5);//else//debug
hx(x),hx(z);
M(y,y,G);M(y,y,y);
for(M(z,G,G),j=900;j--;)M(z,x,z);for(j=900;j--;)M(z,y,z);hx(z);
for(M(z,G,G),j=900;j--;)M(z,y,z);for(j=900;j--;)M(z,x,z);hx(z);}
<CODE ENDS>
To be completed: Explain this properly, if possible.
The test vectors should output this:
Brown 2y^2=x^3+x over 8^91+5 [Page 43]
Internet-Draft 2020-04-03
000000000000000029352b31395e382846472f782b335e783d325e79322054534554
00000000000000000000000000000000000000000000000000000000000000000117
c8c0f2f404a9fabc91c939d8ea1b9e258d82e21a427b549f05c832cf8d48296ffad7
5f336f56f86de3d52b0eab85e527f2ac7b9d77605c0d5018f5faa4243fd462b1badd
fc023b3f03b469dca32446db80d9b388d753cc77aa4c3ee7e2bb86e99e7bed38f509
8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221
8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221
C.3. Pseudocode for a command-line demo of Diffie--Hellman
The following code, representing a file dhe.c, is a bilingual: being
valid C and bash script.
As a bash script, it will compile the C code as dhe, then run it
twice, once as Alice and once as Bob, piping the ephemeral public
keys, and writing the resulting Diffie--Hellman agreed secret keys
into pipes. The agreed secret keys are fed into SHA-256 to
demonstrate their equality, but also to show the typical way to use
DH agree keys (to hash them rather than use them directly).
This pseudocode assumes a Linux-like system.
<CODE BEGINS>
#include "pseudo.c" /* dhe.c (also a bash script)
: demos ephemeral DH, also creates, clobbers files dhba dha dhb
: -- Dan Brown, BlackBerry, '19 */
#include <stdio.h>
_ get(c p,_*f){if(f)while(!fread((_*)p,B,1,f));}
_ put(c p,_*f){if(f)fwrite((_*)p,B,1,f),fflush(f); bite(p,O);}
int main (_){C s="/dev/urandom",p="EPHEMERAL s => OK if p INVALID";
get(s,fopen((_*)s,"r")), mulch(p,s,G), put(p,stdout);
get(p,stdin), mulch(s,s,p), put(s,stderr);} /*'
[ dhe.c -nt dhe ] && gcc -O3 dhe.c -o dhe && echo "$(<dhe.c)"
mkfifo dh{a,b,ba} 2>/dev/null || ([ ! -p dhba ] && :> dhba)
./dhe <dhba 2>dha | ./dhe >dhba 2>dhb &
sha256sum dha & sha256sum dhb # these should be equal
(for f in dh{a,b,ba} ; do [ -f $f ] && \rm -f $f; done)# '*/
<CODE ENDS>
C.4 Pseudocode for public-key validation and twist insecurity
The following pseudocode, describing a file pkv.c, demonstrates the
public-key validation features of mulch from pseudo.c, by
deliberately supplying invalid points to mulch. It also
demonstrates how to turn PKV on and off using the mulch interface.
Brown 2y^2=x^3+x over 8^91+5 [Page 44]
Internet-Draft 2020-04-03
It also demonstrates the need for PKV despite using the Montgomery
by finding points of low order on the twist of the curve, and
showing that such points can leak bits of the secret multiplier.
It further demonstrates the order of the curve, and complex
multiplication by i, and the fact the 34-byte representation of
points is unaffected by multiplication by i.
<CODE BEGINS>
#include <stdio.h>
#include "pseudo.c"
#define M mulch // works with +/- x, so P ~ -P ~ iP ~ -iP
void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");}
int main (void){i j;// sanity check, PKV, twist insecurity demo
C y="TEST 2y^2=x^3+x/GF(8^91+5)",z="zzzzzzzzzzzzzzzzzzzz",
q = "\xa9\x38\x04\xb8\xa7\xb8\x32\xb9\x69\x85\x41\xe9\x2a"
"\xd1\xce\x4a\x7a\x1c\xc7\x71\x1c\xc7\x71\x1c\xc7\x71\x1c"
"\xc7\x71\x1c\xc7\x71\x1c\x07", // q=order(G)
i = "\x36\x5a\xa5\x56\xd6\x4f\xb9\xc4\xd7\x48\x74\x76\xa0"
"\xc4\xcb\x4e\xa5\x18\xaf\xf6\x8f\x74\x48\x4e\xce\x1e\x64"
"\x63\xfc\x0a\x26\x0c\x1b\x04", // i^2=-1 mod q
w5= "\xb4\x69\xf6\x72\x2a\xd0\x58\xc8\x40\xe5\xb6\x7a\xfc"
"\x3b\xc4\xca\xeb\x65\x66\x66\x66\x66\x66\x66\x66\x66\x66"
"\x66\x66\x66\x66\x66\x66\x66"; // w5=(2p+2-72q)/5
for(j=0;j<=3;j++)M(z,(C){j},G),hx(z); // {0,1,2,3}G, but reject 0G
M(z,q,G),hx(z); // reject qG; but qG=O, under hood:
{F x;E p;lift(p,feed(x,G),1);mule(p,q);hx(bite(z,p[1]));}
for(j=0;j<0*25;j++){F x;E p;lift(p,feed(x,(C){j,1}),1);mule(p,q);
printf("%3d ",j),hx(bite(z,p[1]));}// see j=23 for choice of G
for(j=3;j--;)q[0]-=1,M(z,q,G),hx(z);// (q-{1,2,3})G ~ {1,2,3}G
M(z,i,G),hx(z); i[0]+=1,M(z,i,G),M(z,i,z),hx(z);// iG~G,(i+1)^2G~2G
M(w5,w5,(C){5}),hx(w5);// twist, ord(w5)=5, M(z,z,p) skipped PKV(p)
M(G,(C){1},w5),hx(G);// reject w5 (G unch.); but w5 leaks z mod 5:
for(j=10;j--;)M(z,y,G),z[0]+=j,M(z,z,w5),hx(z);}
<CODE ENDS>
C.5. Elligator i
To be deleted (or completed).
This pseudocode would show how to implement to the Elligator i map
from byte strings to points. This is INCOMPATIBLE with pseudocode
above.
Pseudocode (to be verified):
Brown 2y^2=x^3+x over 8^91+5 [Page 45]
Internet-Draft 2020-04-03
<CODE BEGINS>
typedef f xy[2] ;
#define X p[0]
#define Y p[1]
lift(xy p, f r) {
f t ; i b ;
fix(r);
squ(t,r); // r^2
mul(t,I,t); // ir^2
sub(t,(f){1},t); // 1-ir^2
inv(t,t); // 1/(1-ir^2)
mal(t,3,t); // 3/(1-ir^2)
mul(t,I,t); // 3i/(1-ir^2)
sub(X,I,t); // i-3i/(1-ir^2)
b = get_y(t,X);
mal(t,1-b,I); // (1-b)i
add(X,X,t); // EITHER x OR x + i
get_y(Y,X);
mal(Y,2*b-1,Y); // (-1)^(1-b)""
fix(X); fix(Y);
}
drop(f r, xy p)
{
f t ; i b,h ;
fix(X); fix(Y);
get_y(t,X);
b=eq(t,Y);
mal(t,1-b,I);
sub(t,X,t); // EITHER x or x-i
sub(t,I,t); // i-x
inv(t,t); // 1/(i-x)
mal(t,3,t); // 3/(i-x)
add(t,I,t); // i+ 3/(i-x)
mal(t,-1,t); // -i-3/(i-x)) = (1-3i/(i-x))/i
b = root(r,t) ;
fix(r);
h = (r[4]<(1LL<<52)) ;
mal(r,2*h-1,r);
fix(r);
}
Brown 2y^2=x^3+x over 8^91+5 [Page 46]
Internet-Draft 2020-04-03
elligator(xy p,c b) {f r; feed(r,b); lift(p,r);}
crocodile(c b,xy p) {f r; drop(r,p); bite(b,r);}
<CODE ENDS>
D. Primality proofs and certificates
Recent work of Albrecht and others [AMPS] has shown the combination
of an adversarially chosen prime, and users using improper
probabilistic primality tests can make user vulnerable to an attack.
The adversarial primes in this attack are typically the result of an
exhaustive search. They therefore contain an amount of information
corresponding to the length of their search, putting a predictable
lower bound on their Kolmogorov complexity.
The two primes involved for 2y^2=x^3+x/GF(8^91+5) should perhaps
already resist [AMPS] because of the following compact
representation of these primes:
p = 8^91+5
q = #(2y^2=x^3+x/GF(8^91+5))/72
This attack [AMPS] can also be resisted by:
- properly implementing probabilistic primality test, or
- implementing provable primality tests.
Provable primality tests can be very slow, but can be separated into
two steps:
-- a slow certificate generation, and
-- a fast certificate verification.
The certificate is a set of data, representing an intermediate step
in the provable primality test, after which the completion of the
test is quite efficient.
Pratt primality certificate generation for any prime p, involves
factorizing p-1, which can be very slow, and then recursively
generating a Pratt primality certificate for each prime factor of
p-1. Essentially, each prime has a unique Pratt primality
certificate.
Brown 2y^2=x^3+x over 8^91+5 [Page 47]
Internet-Draft 2020-04-03
Pratt primality certificate verification of (p-1), involves search
for g such that 1 = (g^(p-1) mod p) and 1 < (g^((p-1)/q) mod p) for
each q dividing p-1, and then recursively verifying each Pratt
primality certificate for each prime factor q of p-1.
In this document, we specify a Pratt primality certificate as a
sequence of (candidate) primes each being 1 plus a product of
previous primes in the list, with certificate stating this product.
Although Pratt primality certificate verification is quite
efficient, an ECC implementation can opt to trust 8^91+5 by virtue
of verifying the certificate once, perhaps before deployment or
compile time.
D.1. Pratt certificate for the field size 8^91+5
Define 52 positive integers, a,b,c,...,z,A,...,Z as follows:
a=2 b=1+a c=1+aa d=1+ab e=1+ac f=1+aab g=1+aaaa h=1+abb i=1+ae
j=1+aaac k=1+abd l=1+aaf m=1+abf n=1+aacc o=1+abg p=1+al q=1+aaag
r=1+abcc s=1+abbbb t=1+aak u=1+abbbc v=1+ack w=1+aas x=1+aabbi
y=1+aco z=1+abu A=1+at B=1+aaaadh C=1+acu D=1+aaav E=1+aeff F=1+aA
G=1+aB H=1+aD I=1+acx J=1+aaacej K=1+abqr L=1+aabJ M=1+aaaaaabdt
N=1+abdpw O=1+aaaabmC P=1+aabeK Q=1+abcfgE R=1+abP S=1+aaaaaaabcM
T=1+aIO U=1+aaaaaduGS V=1+aaaabbnuHT W=1+abffLNQR X=1+afFW
Y=1+aaaaauX Z=1+aabzUVY.
Note: variable concatenation is used to indicate multiplication.
For example, f = 1+aab = 1+2*2*(1+2) = 13.
Note: One must verify that Z=8^91+5.
Note: The Pratt primality certificate involves finding a generator
g for each the prime (after the initial prime). It is possible to
list these in the certificate, which can speed up verification by
a small factor.
(2,b), (2,c), (3,d), (2,e), (2,f), (3,g), (2,h), (5,i), (6,j),
(3,k), (2,l), (3,m), (2,n), (5,o), (2,p), (3,q), (6,r), (2,s),
(2,t), (6,u), (7,v), (2,w), (2,x), (14,y),(3,z), (5,A), (3,B),
(7,C), (3,D), (7,E), (5,F), (2,G), (2,H), (2,I), (3,J), (2,K),
(2,L),(10,M), (5,N), (10,O),(2,P), (10,Q),(6,R), (7,S), (5,T),
(3,U), (5,V), (2,W), (2,X), (3,Y), (7,Z).
Brown 2y^2=x^3+x over 8^91+5 [Page 48]
Internet-Draft 2020-04-03
Note: The decimal values for a,b,c,...,Y are given by: a=2, b=3,
c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=41, k=43, l=53, m=79,
n=101, o=103, p=107, q=137, r=151, s=163, t=173, u=271, v=431,
w=653, x=829, y=1031, z=1627, A=2063, B=2129, C=2711, D=3449,
E=3719, F=4127, G=4259, H=6899, I=8291, J=18041, K=124123,
L=216493, M=232513, N=2934583, O=10280113, P=16384237, Q=24656971,
R=98305423, S=446424961, T=170464833767, U=115417966565804897,
V=4635260015873357770993, W=1561512307516024940642967698779,
X=167553393621084508180871720014384259,
Y=1453023029482044854944519555964740294049.
D.2. Pratt certificate for subgroup order
Define 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new
values:
a=2 b=1+a c=1+a2 d=1+ab e=1+ac f=1+a2b g=1+a4 h=1+ab2 i=1+ae
j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b
r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e
z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck
G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG
O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ
V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Z=1+ab3oHOT !=1+a3SUX @=1+abNY!
#=1+a4kzF@ $=1+a3QZ#
Note: numeral after variable names represent powers. For example,
f = 1 + a2b = 1 + 2^2 * 3 = 13.
The last variable, $, is the order of the base point, and the order
of the curve is 72$.
Note: Punctuation used for variable names !,@,#,$, would not scale
for larger primes. For larger primes, a similar format might work
by using a prefix-free set of multi-letter variable names.
E.g. replace, Z,!,@,#,$ by Za,Zb,Zc,Zd,Ze:
Acknowledgments
Thanks to John Goyo and various other BlackBerry employees for past
technical review, to Gaelle Martin-Cocher for encouraging submission
of this I-D. Thanks to David Jacobson for sending Pratt primality
certificates.
Brown 2y^2=x^3+x over 8^91+5 [Page 49]
Internet-Draft 2020-04-03
Author's Address
Dan Brown
4701 Tahoe Blvd.
BlackBerry, 5th Floor
Mississauga, ON
Canada
danibrown@blackberry.com
Brown 2y^2=x^3+x over 8^91+5 [Page 50]