ed25519.md 6.78 KB
 bernd committed Sep 15, 2015 1 2 3 ``````ed25519 from Dan Bernstein et al ================================ `````` Bernd Paysan committed Apr 29, 2018 4 ``````For asymmetric cryptography, I use [ed25519](https://ed25519.cr.yp.to/) from `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 18 ``````coordinate field, which is a modulo prime field. This prime is _2^255-19_, `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 30 ``````256 bits security you need a 15000 bit key — that's a factor of 5). So `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 36 ``````be strong. The number of points on the curve _l_ is also a known `````` bernd committed Sep 15, 2015 37 ``````prime (this number is needed to calculate the modulus for multiplying scalars), `````` Bernd Paysan committed Apr 29, 2018 38 ``````it is _2^252 + 27742317777372353535851937790883648493_. `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 42 ``````set to dedicated values to make it mod _l_. This means you can use `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 47 ``````_pk=(sk)\*base_ `````` bernd committed Sep 15, 2015 48 49 50 `````` ## Diffie Hellman Key Exchange ## `````` Bernd Paysan committed Apr 29, 2018 51 ``````For Diffie Hellman key exchange, the identity _(sk2)\*pk1 = (sk1)\*pk2_ or `````` bernd committed Sep 15, 2015 52 `````` `````` Bernd Paysan committed Apr 29, 2018 53 ``````_(sk1)\*(sk2)\*base = (sk2)\*(sk1)\*base_ `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 60 ``````for the key pair. The main reason is “nothing up my sleeve”, Dan `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 78 ``````_k:=hash(absorb(sk,state))_, deterministic for message and secret key. For `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 82 ``````a point _r_ on the curve: `````` bernd committed Sep 15, 2015 83 `````` `````` Bernd Paysan committed Apr 29, 2018 84 ``````_r=(k)\*base_ `````` bernd committed Sep 15, 2015 85 `````` `````` Bernd Paysan committed Apr 29, 2018 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 committed Sep 15, 2015 91 ``````takes a mere 64 bytes. `````` bernd committed Sep 15, 2015 92 93 `````` For verification, the receiver computes z again (same as above: hash the `````` Bernd Paysan committed Apr 29, 2018 94 ``````message into Keccak state, and absorb _r\|\|pk_, followed by another hash round), `````` bernd committed Sep 15, 2015 95 96 ``````and then computes `````` Bernd Paysan committed Apr 29, 2018 97 ``````_r:=(s)\*base - (z)\*pk = (z\*sk)\*base + (k)\*base - (z)\*(sk)\*base_ `````` bernd committed Sep 15, 2015 98 `````` `````` Bernd Paysan committed Apr 29, 2018 99 100 ``````As _(z\*sk)\*base=(z)\*(sk)\*base_, the remainder is _(k)\*base_. If this equals to the _r_ part of the `````` bernd committed Sep 15, 2015 101 ``````signature, the signature is valid. `````` bernd committed Sep 15, 2015 102 `````` `````` bernd committed Sep 15, 2015 103 ``````Signing a message is considerably faster than verifying it, because `````` Bernd Paysan committed Apr 29, 2018 104 ``````the most expensive function for signing is the _(k)\*base_ scalar `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 108 ``````_(z)\*pk_. There is also some precomputation, but it takes about `````` bernd committed Sep 15, 2015 109 ``````three times as long in total. `````` bernd committed Sep 15, 2015 110 111 112 `````` ## Ephemeral Key Exchange ## `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 115 ``````keys. The shared secret _(sk2)\*pk1=(sk1)\*pk2_ is now used to `````` bernd committed Sep 15, 2015 116 117 ``````encrypt and exchange the constant public keys of both sides, hiding important metadata from evesdroppers. Another shared secret `````` Bernd Paysan committed Apr 29, 2018 118 ``````_(skb)\*pka=(ska)\*pkb_ is generated, and concatenated to the `````` bernd committed Sep 15, 2015 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 committed Apr 29, 2018 123 ``````exchange), and data transmitted — only the public key needs to go to `````` bernd committed Sep 15, 2015 124 ``````the other side. `````` bernd committed Sep 15, 2015 125 126 127 `````` ## Repository ## `````` Bernd Paysan committed Apr 29, 2018 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 committed Sep 15, 2015 132 `````` `````` Bernd Paysan committed Apr 29, 2018 133 ``````git clone [https://github.com/forthy42/ed25519-donna.git](https://github.com/forthy42/ed25519-donna.git) `````` bernd committed Sep 15, 2015 134 `````` `````` Bernd Paysan committed Mar 09, 2019 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"```````