README.md 5.85 KB
Newer Older
Michael Hamburg's avatar
Michael Hamburg committed
1 2
# Decaf elliptic curve library

Michael Hamburg's avatar
Michael Hamburg committed
3
The libdecaf library is for elliptic curve research and practical application.
Michael Hamburg's avatar
Michael Hamburg committed
4 5
It currently supports Ed448-Goldilocks and Curve25519.

Michael Hamburg's avatar
Michael Hamburg committed
6 7 8 9 10 11 12 13 14 15 16
The goals of this library are:

* Implementing the X25519, X448 key exchange protocols (RFC 7748).
* Implementing the Ed25519 and EdDSA-Ed448 signature schemes (RFC 8032).
* Providing a platform for research and development of advanced cryptographic schemes using twisted Edwards curves.

This library is intended for developers who have experience with
cryptography.  It doesn't (yet?) include documentation on how to use
digital signatures or key exchange securely.  Consult your local
cryptographer for advice.

Michael Hamburg's avatar
Michael Hamburg committed
17 18 19 20 21 22
## Mailing lists

Because this is new software, please expect it to have bugs, perhaps
even critical security bugs.  If you are using it, please sign up for
updates:

Michael Hamburg's avatar
Michael Hamburg committed
23 24 25 26 27 28
* Security-critical announcements (very low volume, God willing):
    decaf-security@googlegroups.com, join at https://groups.google.com/forum/#!forum/decaf-security    
* New version announcements (low volume):
    decaf-announce@googlegroups.com, join at https://groups.google.com/forum/#!forum/decaf-annonuce
* Library discussion (potentially more volume):
    decaf-discuss@googlegroups.com, join at https://groups.google.com/forum/#!forum/decaf-discuss
Michael Hamburg's avatar
Michael Hamburg committed
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

## General elliptic curve operations.

This is a multi-purpose elliptic curve library.  There is a C library,
and a set of C++ wrapper headers.  The C++ code consists entirely of
inline calls, and has no compiled component.

The library implements a fairly complete suite of operations on the
supported curves:

* Point and scalar serialization and deserialization.
* Point addition, subtraction, doubling, and equality.
* Point multiplication by scalars.  Accelerated double- and dual-scalar multiply.
* Scalar addition, subtraction, multiplication, division, and equality.
* Construction of precomputed tables from points.  Precomputed scalarmul.
Michael Hamburg's avatar
Michael Hamburg committed
44
* Hashing to the curve with an Elligator variant.  Inverse of elligator for steganography.  These are useful for advanced protocols such as password-authenticated key exchange (PAKE) and verifiable random functions (VRFs).
Michael Hamburg's avatar
Michael Hamburg committed
45 46

Internally, the library uses twisted Edwards curves with the "decaf"
Michael Hamburg's avatar
Michael Hamburg committed
47 48 49 50 51
and "ristretto" technique to remove the curve's cofactor of 4 or 8. 
The upshot is that systems using the "decaf" interface will be using
a prime-order group, which mitigates one of the few disadvantages of
Edwards curves.  However, this means that it is not able to implement
systems which care about cofactor information.
Michael Hamburg's avatar
Michael Hamburg committed
52 53 54 55 56 57 58 59 60 61 62 63 64

The goal of this library is not only to follow best practices, but to
make it easier for clients of the library to follow best practices.
With a few well-marked exceptions, the functions in this library should
be strongly constant-time: they do not allow secret data to flow to
array indices, nor to control decisions except for a final failure
check.  Furthermore, the C++ wrapping uses RAII to automatically clear
sensitive data, and has interfaces designed to prevent certain mistakes.

## CFRG cryptosystems.

The library additionally supports two cryptosystems defined by the
Crypto Forum Research Group (CFRG): the X448/X25519 Diffie-Hellman
Michael Hamburg's avatar
Michael Hamburg committed
65 66 67
functions (RFC 7748), and the EdDSA signature scheme (RFC 8032).
Future versions might support additional operations on these curves,
such as precomputed signature verification.
Michael Hamburg's avatar
Michael Hamburg committed
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

## Symmetric crypto and hashing

The Decaf library doesn't implement much symmetric crypto, but it does
contain the hash functions required by the CFRG cryptosystems: SHA512,
SHA-3 and SHAKE.

## Internals

The "decaf" technique is described in https://eprint.iacr.org/2015/673
While the title of that paper is "removing cofactors through point
compression", it might be more accurate to say "through quotients and
isogenies".  The internal representation of points is as "even" elements
of a twisted Edwards curve with a=-1.  Using this subgroup removes a
factor of 2 from the cofactor.  The remaining factor of 2 or 4 is
removed with a quotient group: any two points which differ by an element
of the 2- or 4-torsion subgroup are considered equal to each other.

When a point is written out to wire format, it is converted (by isogeny)
to a Jacobi quartic curve, which is halfway between an Edwards curve
and a Montgomery curve.  One of the 4 or 8 equivalent points on the
Jacobi quartic is chosen (it is "distinguished" according to certain
criteria, such as having a positive x-coordinate).  The x-coordinate of
this point is written out.  The y-coordinate is not written out, but the
decoder knows which of the two possible y-coordinates is correct because
of the distinguishing rules.  See the paper for more details.

Michael Hamburg's avatar
Michael Hamburg committed
95 96 97
As of v0.9.4, libdecaf uses the "Ristretto" variant of this encoding.
See https://www.ristretto.group for details, once that site is up.

98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
## Build and Install

 cmake -DCMAKE_INSTALL_PREFIX=<Install path> <path to root directory>
 make
 make test
 make install

Most C source code is generated through a python script during the build.
Some files holding tables are generated in one more step building an
executable to generate them. They are thus stored in the source tree to help
cross-compilation. The build script update them when their dependencies
are modified, to build only these files:

 make decaf_tables

Johan Pascal's avatar
Johan Pascal committed
113 114 115 116 117
Doxygen generated documentation is located in ./doc directory in the
binary tree after running

 make doc

Michael Hamburg's avatar
Michael Hamburg committed
118 119 120
## Licensing

Most of the source files here are by Mike Hamburg.  Those files are (c)
Michael Hamburg's avatar
Michael Hamburg committed
121
2014-2017 Cryptography Research, Inc (a division of Rambus). All of these
Michael Hamburg's avatar
Michael Hamburg committed
122 123 124 125 126
files are usable under the MIT license contained in LICENSE.txt.

## Caveats

As mentioned in the license, there is absolutely NO WARRANTY on any of this
Michael Hamburg's avatar
Michael Hamburg committed
127
code.  This code might well have security-critical bugs despite my best efforts.
Michael Hamburg's avatar
Michael Hamburg committed
128 129 130 131

I've attempted to protect against timing attacks and invalid point attacks,
but as of yet I've made no attempt to protect against power analysis.