crrl 0.1.0

Library for cryptographic research
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

# crrl

This library implements some primitives for purposes of cryptographic
research. Its point is to provide efficient, optimized and constant-time
implementations that are supposed to be representative of
production-ready code, so that realistic performance benchmarks may be
performed. Thus, while meant primarily for research, the code here
*should* be fine for production use (though of course I offer no such
guarantee; use at your own risks).

So far, only some primitives related to elliptic curve cryptography
are implemented:

  - A generic type `GF255<MQ>` for finite fields of integers modulo a
    prime 2^255-`MQ` (for a value of `MQ` between 1 and 32767). The `MQ`
    value is provided as a type parameter, i.e. the exact field is known
    at compile time. This type covers the usual modulus 2^255-19 (used
    in Curve25519) as well as 2^255-18651 and 2^255-3957 (used in
    [double-odd curves do255e and do255s](https://doubleodd.group/)).

  - A generic type `ModInt256<M0, M1, M2, M3>` for arbitrary finite
    fields of integers modulo a prime between 2^192 and 2^256.
    Montgomery representation is internally used. The modulus is
    provided as type parameters, allowing the compiler to apply
    optimizations when some parts of the modulus allow them (in
    particular with the modulus used for NIST curve P-256).

  - Type `ed25519::Point` provides generic group operations in the
    twisted Edwards curve Curve25519. Ed25519 signatures (as per [RFC
    8032](https://datatracker.ietf.org/doc/html/rfc8032)) are
    implemented. Type `ed25519::Scalar` implements operations on
    integers modulo the curve subgroup order.

  - Type `ristretto255::Point` provides generic group operations in the
    [Ristretto255 group](https://ristretto.group/), whose prime order is
    exactly the size of the interesting subgroup of Curve25519.

  - Type `p256::Point` provides generic group operations in the NIST
    P-256 curve (aka "secp256r1" aka "prime256v1"). ECDSA signatures are
    supported. The `p256::Scalar` type implements the corresponding
    scalars (integers modulo the curve order).

  - Function `x25519::x25519()` implements the [X25519 function](https://datatracker.ietf.org/doc/html/rfc7748#section-5).
    An optimized `x25519::x2559_base()` function is provided when X25519
    is applied to the conventional base point.

Type `GF255` and `ModInt256` have a 32-bit and a 64-bit implementations
each. The code is portable (it was tested on 32-bit and 64-bit x86, and
64-bit aarch64). Performance is quite decent; e.g. Ed25519 signatures
are computed in about 51500 cycles, and verified in about 114000 cycles,
on an Intel "Coffee Lake" CPU; this is not too far from the best
assembly-optimized implementations. At the same time, use of operator
overloading allows to express formulas on points and scalar with about
the same syntax as their mathematical description. For instance, the
core of the X25519 implementation looks like this:

```
        let A = x2 + z2;
        let B = x2 - z2;
        let AA = A.square();
        let BB = B.square();
        let C = x3 + z3;
        let D = x3 - z3;
        let E = AA - BB;
        let DA = D * A;
        let CB = C * B;
        x3 = (DA + CB).square();
        z3 = x1 * (DA - CB).square();
        x2 = AA * BB;
        z2 = E * (AA + E.mul_small(121665));
```

which is quite close to the corresponding description in RFC 7748:

```
       A = x_2 + z_2
       AA = A^2
       B = x_2 - z_2
       BB = B^2
       E = AA - BB
       C = x_3 + z_3
       D = x_3 - z_3
       DA = D * A
       CB = C * B
       x_3 = (DA + CB)^2
       z_3 = x_1 * (DA - CB)^2
       x_2 = AA * BB
       z_2 = E * (AA + a24 * E)
```

# Security and Compliance

All the code is strict, both in terms of timing-based side-channels
(everything is constant-time, except if explicitly stated otherwise,
e.g. in a function whose name includes `vartime`) and in compliance to
relevant standards. For instance, the Ed25519 signature support applies
and enforces canonical encodings of both points and scalars.

There is no attempt at "zeroizing memory" anywhere in the code. In
general, such memory cleansing is a fool's quest. Note that since most
of the library use `no_std` rules, dynamic allocation happens only on
the stack, thereby limiting the risk of leaving secret information
lingering all over the RAM. The only functions that use heap allocation
only store public data there.

**WARNING:** I reiterate what was written above: although all of the
code aims at being representative of optimized production-ready code, it
is still fairly recent and some bugs might still lurk, however careful I
am when writing code. Any assertion of suitability to any purpose is
explcitly denied. The primary purpose is to help with "trying out stuff"
in cryptographic research, by offering an easy-to-use API backed by
performance close enough to what can be done in actual applications.

# Truncated Signatures

Support for truncated signatures is implemented for Ed25519 and
ECDSA/P-256. Standard signatures can be shortened by 8 to 32 bits (i.e.
the size may shrink from 64 down to 60 bytes), and the verifier rebuilds
the original signature during verification (at some computational cost).
This is not a ground-breaking feature, but it can be very convenient in
some situations with tight constraints on bandwidth and a requirement to
work with standard signature formats. See
`ed25519::PublicKey::verify_trunc_raw()` and
`p256::PublicKey::verify_trunc_hash()` for details.

# Benchmarks

`cargo bench` runs some benchmarks, but there are a few caveats:

  - The cycle counter is used on x86. If frequency scaling ("TurboBoost")
    is not disabled, then you'll get wrong and meaningless results.

  - On aarch64, the cycle counter is also accessed directly, which will
    in general fail with some CPU exception. Access to the counter must
    first be enabled, which requires (on Linux) a specific kernel
    module. [This
    one](https://github.com/jerinjacobk/armv8_pmu_cycle_counter_el0)
    works for me.

  - On architectures other than i386, x86-64 and aarch64, benchmark
    code will simply not compile.

# TODO

In the future, at least the following features will be added:

  - Double-odd curves do255e and do255s.
  - Schnorr signatures on Ristretto255, using the [FROST draft](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-frost-05).
  - secp256k1 curve support (possibly with an explicit type for its
    base field, though `ModInt256` should work out-of-the-box).

In general, about anything related to cryptography may show up here,
if there is a use case for it.