ed25519 from Dan Bernstein et al
================================
For asymmetric cryptography, I use [ed25519](https://ed25519.cr.yp.to/) from
Dan Bernstein et al. This is a variant of his curve25519 system that is
very useful for signatures; the curve has a different shape (Edwards form), and
the algorithms are better tuned, since Edwards form has properties that
simplifies tuning (it is more regular).
Elliptic Curve Cryptography is a more complicated variant of the discrete
logarithm problem than RSA. The field used here is a curve, and an
addition operation is defined that is similar to an addition of points on a
clock (where you turn P2 by the angle of the neutral element to P1); the
difference from adding two angles in cartesian coordinates is the curve
parameter d; that's all. This operation works uniformly for neutral
element, for doubling and for negative elements; the curve is symmetric to both
x and y axis. Adding two points requires several multiplications over the
coordinate field, which is a modulo prime field. This prime is _2^255-19_,
which gives the name of the curve.
As there is an addition, there is also a scalar multiplication (repeated
addition); as the addition is a multiplication over the coordinate field, the
scalar multiplication is (from the point of complexity) an exponentiation over
the coordinate field. The inverse problem thus is a generic discrete
logarithm problem. Unlike RSA, there is no designed in shortcut, RSA is
also broken if you can factor a large number into two primes. The
factoring into primes is considerably simpler than it was originally expected,
which means that RSA security now requires long keys, and longer keys don't
result in adequately better security (3000 bits is 128 bit security, but for
256 bits security you need a 15000 bit key — that's a factor of 5). So
far, no shortcut to break ECC has been found (after 20 years!), supposed the
parameters of the curve are good.
There are weak curves which have only a small number of points on them.
Fortunately, Dan Bernstein did characterize his curve, so it's known to
be strong. The number of points on the curve _l_ is also a known
prime (this number is needed to calculate the modulus for multiplying scalars),
it is _2^252 + 27742317777372353535851937790883648493_.
I use ed25519 for both Diffie Hellman key exchange and for signatures.
Secret keys are generated by using 256 random bits, with a few of them
set to dedicated values to make it mod _l_. This means you can use
any random number as secret. For notation, I write the scalar
multiplication with the scalar on the left side in parens. The public key
is derived from the secret key
_pk=(sk)\*base_
## Diffie Hellman Key Exchange ##
For Diffie Hellman key exchange, the identity _(sk2)\*pk1 = (sk1)\*pk2_ or
_(sk1)\*(sk2)\*base = (sk2)\*(sk1)\*base_
is used (actually with -pk, as the expansion used from signature generating
also negates the public key). Each side multiplies the other's public key
with its own secret key; the resulting product is compressed (only x
coordinate), and then used as shared secret. Dan Bernstein uses a hash
function to derive two pseudo-random values out of the secret; I don't do this
for the key pair. The main reason is “nothing up my sleeve”, Dan
Bernstein doesn't explain why he's doing it, so this thing can't go in.
The ed25519 curve is isomorph to the curve25519 curve, so the cryptography
is just as strong. I prefer to have only one set of primitives for
signatures and key exchange, which also allows to use only one secret key for
both. Having only a 32 byte secret key e.g. allows you to write it on a
piece of paper, and store it somewhere safe... far away from any electronics,
on a medium that lasts for centuries.
## Signatures ##
For signatures, I compute a hash of the message or file using
[Keccak](http://keccak.noekeon.org/). The Keccak state is now
used twice, so two copies have to be made.
First, I absorb the secret key, and diffuse the state for another round.
The first 64 bytes of the Keccak state is the pseudo-random number
_k:=hash(absorb(sk,state))_, deterministic for message and secret key. For
ECDSA, this is suggested to be a random number; as Keccak is a PRF, this
deterministic pseudo-random number is just as good. It is guaranteed that
for different messages k is different (collision left aside). Now derive
a point _r_ on the curve:
_r=(k)\*base_
Compress _r_ (a point), and append (operator \|\|) the public key
to _r_, to compute another hash round on the second copy of the
Keccak state: _z=hash(absorb(r\|\|pk,state))_. Then compute the
second parameter of the signature, _(s)=(z\*sk+k)_ (this is a scalar,
i.e. mod _l_). The signature consists of _r_, _s_, and
takes a mere 64 bytes.
For verification, the receiver computes z again (same as above: hash the
message into Keccak state, and absorb _r\|\|pk_, followed by another hash round),
and then computes
_r:=(s)\*base - (z)\*pk = (z\*sk)\*base + (k)\*base - (z)\*(sk)\*base_
As _(z\*sk)\*base=(z)\*(sk)\*base_, the remainder is
_(k)\*base_. If this equals to the _r_ part of the
signature, the signature is valid.
Signing a message is considerably faster than verifying it, because
the most expensive function for signing is the _(k)\*base_ scalar
product; it's only 10% slower than generating a keypair. This is
accelerated with a precomputed table. Verifying is about as expensive
as a Diffie Hellman key exchange, because here the dominant timing is
_(z)\*pk_. There is also some precomputation, but it takes about
three times as long in total.
## Ephemeral Key Exchange ##
For key exchange, I use my own variant of ephemeral key exchange:
First, each side generates a random keypair, and exchanges the public
keys. The shared secret _(sk2)\*pk1=(sk1)\*pk2_ is now used to
encrypt and exchange the constant public keys of both sides, hiding
important metadata from evesdroppers. Another shared secret
_(skb)\*pka=(ska)\*pkb_ is generated, and concatenated to the
first shared secret; this plus a random and unique initialization
vector is the starting point to generate per-block keys. The
advantage over a signature as used in standard ECDHE is both time (no
signing needed, and verification is slightly more expensive than key
exchange), and data transmitted — only the public key needs to go to
the other side.
## Repository ##
To implement the necessary changes (add scalar multiplication with “constant”
execution time for the DHE, i.e. no secret dependent operation), I cloned
floodberry's ed25519-donna code and added autoconf stuff for build process, so
you need a
git clone [https://github.com/forthy42/ed25519-donna.git](https://github.com/forthy42/ed25519-donna.git)
and to compile&install it, just run `./autogen.sh && make && sudo make
install`. To install 32 bit libaries on a 64 bit system, run `autogen.sh`
with `CC="gcc -m32"`