ed25519.md 6.78 KB
Newer Older
bernd's avatar
bernd committed
1 2 3
ed25519 from Dan Bernstein et al
================================

Bernd Paysan's avatar
Bernd Paysan committed
4
For asymmetric cryptography, I use [ed25519](https://ed25519.cr.yp.to/) from
bernd's avatar
bernd committed
5 6 7 8 9 10 11 12 13 14 15 16 17
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
Bernd Paysan's avatar
Bernd Paysan committed
18
coordinate field, which is a modulo prime field.  This prime is _2^255-19_,
bernd's avatar
bernd committed
19 20 21 22 23 24 25 26 27 28 29
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
Bernd Paysan's avatar
Bernd Paysan committed
30
256 bits security you need a 15000 bit key — that's a factor of 5).  So
bernd's avatar
bernd committed
31 32 33 34 35
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
Bernd Paysan's avatar
Bernd Paysan committed
36
be strong.  The number of points on the curve _l_ is also a known
bernd's avatar
bernd committed
37
prime (this number is needed to calculate the modulus for multiplying scalars),
Bernd Paysan's avatar
Bernd Paysan committed
38
it is _2^252 + 27742317777372353535851937790883648493_.
bernd's avatar
bernd committed
39 40 41

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
Bernd Paysan's avatar
Bernd Paysan committed
42
set to dedicated values to make it mod _l_.  This means you can use
bernd's avatar
bernd committed
43 44 45 46
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

Bernd Paysan's avatar
Bernd Paysan committed
47
_pk=(sk)\*base_
bernd's avatar
bernd committed
48 49 50

## Diffie Hellman Key Exchange ##

Bernd Paysan's avatar
Bernd Paysan committed
51
For Diffie Hellman key exchange, the identity _(sk2)\*pk1 = (sk1)\*pk2_ or
bernd's avatar
bernd committed
52

Bernd Paysan's avatar
Bernd Paysan committed
53
_(sk1)\*(sk2)\*base = (sk2)\*(sk1)\*base_
bernd's avatar
bernd committed
54 55 56 57 58 59

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
Bernd Paysan's avatar
Bernd Paysan committed
60
for the key pair.  The main reason is “nothing up my sleeve”, Dan
bernd's avatar
bernd committed
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
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
Bernd Paysan's avatar
Bernd Paysan committed
78
_k:=hash(absorb(sk,state))_, deterministic for message and secret key.  For
bernd's avatar
bernd committed
79 80 81
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
Bernd Paysan's avatar
Bernd Paysan committed
82
a point _r_ on the curve:
bernd's avatar
bernd committed
83

Bernd Paysan's avatar
Bernd Paysan committed
84
_r=(k)\*base_
bernd's avatar
bernd committed
85

Bernd Paysan's avatar
Bernd Paysan committed
86 87 88 89 90
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
bernd's avatar
bernd committed
91
takes a mere 64 bytes.
bernd's avatar
bernd committed
92 93

For verification, the receiver computes z again (same as above: hash the
Bernd Paysan's avatar
Bernd Paysan committed
94
message into Keccak state, and absorb _r\|\|pk_, followed by another hash round),
bernd's avatar
bernd committed
95 96
and then computes

Bernd Paysan's avatar
Bernd Paysan committed
97
_r:=(s)\*base - (z)\*pk = (z\*sk)\*base + (k)\*base - (z)\*(sk)\*base_
bernd's avatar
bernd committed
98

Bernd Paysan's avatar
Bernd Paysan committed
99 100
As _(z\*sk)\*base=(z)\*(sk)\*base_, the remainder is
_(k)\*base_.  If this equals to the _r_ part of the
bernd's avatar
Typos  
bernd committed
101
signature, the signature is valid.
bernd's avatar
bernd committed
102

bernd's avatar
bernd committed
103
Signing a message is considerably faster than verifying it, because
Bernd Paysan's avatar
Bernd Paysan committed
104
the most expensive function for signing is the _(k)\*base_ scalar
bernd's avatar
bernd committed
105 106 107
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
Bernd Paysan's avatar
Bernd Paysan committed
108
_(z)\*pk_.  There is also some precomputation, but it takes about
bernd's avatar
bernd committed
109
three times as long in total.
bernd's avatar
bernd committed
110 111 112

## Ephemeral Key Exchange ##

bernd's avatar
bernd committed
113 114
For key exchange, I use my own variant of ephemeral key exchange:
First, each side generates a random keypair, and exchanges the public
Bernd Paysan's avatar
Bernd Paysan committed
115
keys.  The shared secret _(sk2)\*pk1=(sk1)\*pk2_ is now used to
bernd's avatar
bernd committed
116 117
encrypt and exchange the constant public keys of both sides, hiding
important metadata from evesdroppers.  Another shared secret
Bernd Paysan's avatar
Bernd Paysan committed
118
_(skb)\*pka=(ska)\*pkb_ is generated, and concatenated to the
bernd's avatar
bernd committed
119 120 121 122
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
Bernd Paysan's avatar
Bernd Paysan committed
123
exchange), and data transmitted — only the public key needs to go to
bernd's avatar
bernd committed
124
the other side.
bernd's avatar
bernd committed
125 126 127

## Repository ##

Bernd Paysan's avatar
Bernd Paysan committed
128 129 130 131
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
bernd's avatar
bernd committed
132

Bernd Paysan's avatar
Bernd Paysan committed
133
git clone [https://github.com/forthy42/ed25519-donna.git](https://github.com/forthy42/ed25519-donna.git)
bernd's avatar
bernd committed
134

Bernd Paysan's avatar
Bernd Paysan committed
135 136 137
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"`