p256-m/p256-m/README.md

*This is the original README for the p256-m repository. Please note that as
only a subset of p256-m's files are present in Mbed TLS, this README may refer
to files that are not present/relevant here.*

p256-m is a minimalistic implementation of ECDH and ECDSA on NIST P-256,
especially suited to constrained 32-bit environments. It's written in standard
C, with optional bits of assembly for Arm Cortex-M and Cortex-A CPUs.

Its design is guided by the following goals in this order:

1. correctness & security;
2. low code size & RAM usage;
3. runtime performance.

Most cryptographic implementations care more about speed than footprint, and
some might even risk weakening security for more speed. p256-m was written
because I wanted to see what happened when reversing the usual emphasis.

The result is a full implementation of ECDH and ECDSA in **less than 3KiB of
code**, using **less than 768 bytes of RAM**, with comparable performance
to existing implementations (see below) - in less than 700 LOC.

_Contents of this Readme:_

- [Correctness](#correctness)
- [Security](#security)
- [Code size](#code-size)
- [RAM usage](#ram-usage)
- [Runtime performance](#runtime-performance)
- [Comparison with other implementations](#comparison-with-other-implementations)
- [Design overview](#design-overview)
- [Notes about other curves](#notes-about-other-curves)
- [Notes about other platforms](#notes-about-other-platforms)

## Correctness

**API design:**

- The API is minimal: only 4 public functions.
- Each public function fully validates its inputs and returns specific errors.
- The API uses arrays of octets for all input and output.

**Testing:**

- p256-m is validated against multiple test vectors from various RFCs and
  NIST.
- In addition, crafted inputs are used for negative testing and to reach
  corner cases.
- Two test suites are provided: one for closed-box testing (using only the
  public API), one for open-box testing (for unit-testing internal functions,
and reaching more error cases by exploiting knowledge of how the RNG is used).
- The resulting branch coverage is maximal: closed-box testing reaches all
  branches except four; three of them are reached by open-box testing using a
rigged RNG; the last branch could only be reached by computing a discrete log
on P-256... See `coverage.sh`.
- Testing also uses dynamic analysis: valgrind, ASan, MemSan, UBSan.

**Code quality:**

- The code is standard C99; it builds without warnings with `clang
  -Weverything` and `gcc -Wall -Wextra -pedantic`.
- The code is small and well documented, including internal APIs: with the
  header file, it's less than 700 lines of code, and more lines of comments
than of code.
- However it _has not been reviewed_ independently so far, as this is a
  personal project.

**Short Weierstrass pitfalls:**

Its has been [pointed out](https://safecurves.cr.yp.to/) that the NIST curves,
and indeed all Short Weierstrass curves, have a number of pitfalls including
risk for the implementation to:

- "produce incorrect results for some rare curve points" - this is avoided by
  carefully checking the validity domain of formulas used throughout the code;
- "leak secret data when the input isn't a curve point" - this is avoided by
  validating that points lie on the curve every time a point is deserialized.

## Security

In addition to the above correctness claims, p256-m has the following
properties:

- it has no branch depending (even indirectly) on secret data;
- it has no memory access depending (even indirectly) on secret data.

These properties are checked using valgrind and MemSan with the ideas
behind [ctgrind](https://github.com/agl/ctgrind), see `consttime.sh`.

In addition to avoiding branches and memory accesses depending on secret data,
p256-m also avoid instructions (or library functions) whose execution time
depends on the value of operands on cores of interest. Namely, it never uses
integer division, and for multiplication by default it only uses 16x16->32 bit
unsigned multiplication. On cores which have a constant-time 32x32->64 bit
unsigned multiplication instruction, the symbol `MUL64_IS_CONSTANT_TIME` can
be defined by the user at compile-time to take advantage of it in order to
improve performance and code size. (On Cortex-M and Cortex-A cores wtih GCC or
Clang this is not necessary, since inline assembly is used instead.)

As a result, p256-m should be secure against the following classes of attackers:

1. attackers who can only manipulate the input and observe the output;
2. attackers who can also measure the total computation time of the operation;
3. attackers who can also observe and manipulate micro-architectural features
   such as the cache or branch predictor with arbitrary precision.

However, p256-m makes no attempt to protect against:

4. passive physical attackers who can record traces of physical emissions
   (power, EM, sound) of the CPU while it manipulates secrets;
5. active physical attackers who can also inject faults in the computation.

(Note: p256-m should actually be secure against SPA, by virtue of being fully
constant-flow, but is not expected to resist any other physical attack.)

**Warning:** p256-m requires an externally-provided RNG function. If that
function is not cryptographically secure, then neither is p256-m's key
generation or ECDSA signature generation.

_Note:_ p256-m also follows best practices such as securely erasing secret
data on the stack before returning.

## Code size

Compiled with
[ARM-GCC 9](https://developer.arm.com/tools-and-software/open-source-software/developer-tools/gnu-toolchain/gnu-rm/downloads),
with `-mthumb -Os`, here are samples of code sizes reached on selected cores:

- Cortex-M0: 2988 bytes
- Cortex-M4: 2900 bytes
- Cortex-A7: 2924 bytes

Clang was also tried but tends to generate larger code (by about 10%). For
details, see `sizes.sh`.

**What's included:**

- Full input validation and (de)serialisation of input/outputs to/from bytes.
- Cleaning up secret values from the stack before returning from a function.
- The code has no dependency on libc functions or the toolchain's runtime
  library (such as helpers for long multiply); this can be checked for the
Arm-GCC toolchain with the `deps.sh` script.

**What's excluded:**

- A secure RNG function needs to be provided externally, see
  `p256_generate_random()` in `p256-m.h`.

## RAM usage

p256-m doesn't use any dynamic memory (on the heap), only the stack. Here's
how much stack is used by each of its 4 public functions on selected cores:

| Function                  | Cortex-M0 | Cortex-M4 | Cortex-A7 |
| ------------------------- | --------: | --------: | --------: |
| `p256_gen_keypair`        |       608 |       564 |       564 |
| `p256_ecdh_shared_secret` |       640 |       596 |       596 |
| `p256_ecdsa_sign`         |       664 |       604 |       604 |
| `p256_ecdsa_verify`       |       752 |       700 |       700 |

For details, see `stack.sh`, `wcs.py` and `libc.msu` (the above figures assume
that the externally-provided RNG function uses at most 384 bytes of stack).

## Runtime performance

Here are the timings of each public function in milliseconds measured on
platforms based on a selection of cores:

- Cortex-M0 at  48 MHz: STM32F091 board running Mbed OS 6
- Cortex-M4 at 100 MHz: STM32F411 board running Mbed OS 6
- Cortex-A7 at 900 MHz: Raspberry Pi 2B running Raspbian Buster

| Function                  | Cortex-M0 | Cortex-M4 | Cortex-A7 |
| ------------------------- | --------: | --------: | --------: |
| `p256_gen_keypair`        |       921 |       145 |        11 |
| `p256_ecdh_shared_secret` |       922 |       144 |        11 |
| `p256_ecdsa_sign`         |       990 |       155 |        12 |
| `p256_ecdsa_verify`       |      1976 |       309 |        24 |
| Sum of the above          |      4809 |       753 |        59 |

The sum of these operations corresponds to a TLS handshake using ECDHE-ECDSA
with mutual authentication based on raw public keys or directly-trusted
certificates (otherwise, add one 'verify' for each link in the peer's
certificate chain).

_Note_: the above figures where obtained by compiling with GCC, which is able
to use inline assembly. Without that inline assembly (22 lines for Cortex-M0,
1 line for Cortex-M4), the code would be roughly 2 times slower on those
platforms. (The effect is much less important on the Cortex-A7 core.)

For details, see `bench.sh`, `benchmark.c` and `on-target-benchmark/`.

## Comparison with other implementations

The most relevant/convenient implementation for comparisons is
[TinyCrypt](https://github.com/intel/tinycrypt), as it's also a standalone
implementation of ECDH and ECDSA on P-256 only, that also targets constrained
devices. Other implementations tend to implement many curves and build on a
shared bignum/MPI module (possibly also supporting RSA), which makes fair
comparisons less convenient.

The scripts used for TinyCrypt measurements are available in [this
branch](https://github.com/mpg/tinycrypt/tree/measurements), based on version
0.2.8.

**Code size**

| Core      | p256-m | TinyCrypt |
| --------- | -----: | --------: |
| Cortex-M0 |   2988 |      6134 |
| Cortex-M4 |   2900 |      5934 |
| Cortex-A7 |   2924 |      5934 |

**RAM usage**

TinyCrypto also uses no heap, only the stack. Here's the RAM used by each
operation on a Cortex-M0 core:

| operation          | p256-m | TinyCrypt |
| ------------------ | -----: | --------: |
| key generation     |    608 |       824 |
| ECDH shared secret |    640 |       728 |
| ECDSA sign         |    664 |       880 |
| ECDSA verify       |    752 |       824 |

On a Cortex-M4 or Cortex-A7 core (identical numbers):

| operation          | p256-m | TinyCrypt |
| ------------------ | -----: | --------: |
| key generation     |    564 |       796 |
| ECDH shared secret |    596 |       700 |
| ECDSA sign         |    604 |       844 |
| ECDSA verify       |    700 |       808 |

**Runtime performance**

Here are the timings of each operation in milliseconds measured on
platforms based on a selection of cores:

_Cortex-M0_ at  48 MHz: STM32F091 board running Mbed OS 6

| Operation          | p256-m | TinyCrypt |
| ------------------ | -----: | --------: |
| Key generation     |    921 |       979 |
| ECDH shared secret |    922 |       975 |
| ECDSA sign         |    990 |      1009 |
| ECDSA verify       |   1976 |      1130 |
| Sum of those 4     |   4809 |      4093 |

_Cortex-M4_ at 100 MHz: STM32F411 board running Mbed OS 6

| Operation          | p256-m | TinyCrypt |
| ------------------ | -----: | --------: |
| Key generation     |    145 |       178 |
| ECDH shared secret |    144 |       177 |
| ECDSA sign         |    155 |       188 |
| ECDSA verify       |    309 |       210 |
| Sum of those 4     |    753 |       753 |

_Cortex-A7_ at 900 MHz: Raspberry Pi 2B running Raspbian Buster

| Operation          | p256-m | TinyCrypt |
| ------------------ | -----: | --------: |
| Key generation     |     11 |        13 |
| ECDH shared secret |     11 |        13 |
| ECDSA sign         |     12 |        14 |
| ECDSA verify       |     24 |        15 |
| Sum of those 4     |     59 |        55 |

_64-bit Intel_ (i7-6500U at 2.50GHz) laptop running Ubuntu 20.04

Note: results in microseconds (previous benchmarks in milliseconds)

| Operation          | p256-m | TinyCrypt |
| ------------------ | -----: | --------: |
| Key generation     |   1060 |      1627 |
| ECDH shared secret |   1060 |      1611 |
| ECDSA sign         |   1136 |      1712 |
| ECDSA verify       |   2279 |      1888 |
| Sum of those 4     |   5535 |      6838 |

**Other differences**

- While p256-m fully validates all inputs, Tinycrypt's ECDH shared secret
  function doesn't include validation of the peer's public key, which should be
done separately by the user for static ECDH (there are attacks [when users
forget](https://link.springer.com/chapter/10.1007/978-3-319-24174-6_21)).
- The two implementations have slightly different security characteristics:
  p256-m is fully constant-time from the ground up so should be more robust
than TinyCrypt against powerful local attackers (such as an untrusted OS
attacking a secure enclave); on the other hand TinyCrypt includes coordinate
randomisation which protects against some passive physical attacks (such as
DPA, see Table 3, column C9 of [this
paper](https://www.esat.kuleuven.be/cosic/publications/article-2293.pdf#page=12)),
which p256-m completely ignores.
- TinyCrypt's code looks like it could easily be expanded to support other
  curves, while p256-m has much more hard-coded to minimize code size (see
"Notes about other curves" below).
- TinyCrypt uses a specialised routine for reduction modulo the curve prime,
  exploiting its structure as a Solinas prime, which should be faster than the
generic Montgomery reduction used by p256-m, but other factors appear to
compensate for that.
- TinyCrypt uses Co-Z Jacobian formulas for point operation, which should be
  faster (though a bit larger) than the mixed affine-Jacobian formulas
used by p256-m, but again other factors appear to compensate for that.
- p256-m uses bits of inline assembly for 64-bit multiplication on the
  platforms used for benchmarking, while TinyCrypt uses only C (and the
compiler's runtime library).
- TinyCrypt uses a specialised routine based on Shamir's trick for
  ECDSA verification, which gives much better performance than the generic
code that p256-m uses in order to minimize code size.

## Design overview

The implementation is contained in a single file to keep most functions static
and allow for more optimisations. It is organized in multiple layers:

- Fixed-width multi-precision arithmetic
- Fixed-width modular arithmetic
- Operations on curve points
- Operations with scalars
- The public API

**Multi-precision arithmetic.**

Large integers are represented as arrays of `uint32_t` limbs. When carries may
occur, casts to `uint64_t` are used to nudge the compiler towards using the
CPU's carry flag. When overflow may occur, functions return a carry flag.

This layer contains optional assembly for Cortex-M and Cortex-A cores, for the
internal `u32_muladd64()` function, as well as two pure C versions of this
function, depending on whether `MUL64_IS_CONSTANT_TIME`.

This layer's API consists of:

- addition, subtraction;
- multiply-and-add, shift by one limb (for Montgomery multiplication);
- conditional assignment, assignment of a small value;
- comparison of two values for equality, comparison to 0 for equality;
- (de)serialization as big-endian arrays of bytes.

**Modular arithmetic.**

All modular operations are done in the Montgomery domain, that is x is
represented by `x * 2^256 mod m`; integers need to be converted to that domain
before computations, and back from it afterwards. Montgomery constants
associated to the curve's p and n are pre-computed and stored in static
structures.

Modular inversion is computed using Fermat's little theorem to get
constant-time behaviour with respect to the value being inverted.

This layer's API consists of:

- the curve's constants p and n (and associated Montgomery constants);
- modular addition, subtraction, multiplication, and inversion;
- assignment of a small value;
- conversion to/from Montgomery domain;
- (de)serialization to/from bytes with integrated range checking and
  Montgomery domain conversion.

**Operations on curve points.**

Curve points are represented using either affine or Jacobian coordinates;
affine coordinates are extended to represent 0 as (0,0). Individual
coordinates are always in the Montgomery domain.

Not all formulas associated with affine or Jacobian coordinates are complete;
great care is taken to document and satisfy each function's pre-conditions.

This layer's API consists of:

- curve constants: b from the equation, the base point's coordinates;
- point validity check (on the curve and not 0);
- Jacobian to affine coordinate conversion;
- point doubling in Jacobian coordinates (complete formulas);
- point addition in mixed affine-Jacobian coordinates (P not in {0, Q, -Q});
- point addition-or-doubling in affine coordinates (leaky version, only used
  for ECDSA verify where all data is public);
- (de)serialization to/from bytes with integrated validity checking

**Scalar operations.**

The crucial function here is scalar multiplication. It uses a signed binary
ladder, which is a variant of the good old double-and-add algorithm where an
addition/subtraction is performed at each step. Again, care is taken to make
sure the pre-conditions for the addition formulas are always satisfied. The
signed binary ladder only works if the scalar is odd; this is ensured by
negating both the scalar (mod n) and the input point if necessary.

This layer's API consists of:

- scalar multiplication
- de-serialization from bytes with integrated range checking
- generation of a scalar and its associated public key

**Public API.**

This layer builds on the others, but unlike them, all inputs and outputs are
byte arrays. Key generation and ECDH shared secret computation are thin
wrappers around internal functions, just taking care of format conversions and
errors. The ECDSA functions have more non-trivial logic.

This layer's API consists of:

- key-pair generation
- ECDH shared secret computation
- ECDSA signature creation
- ECDSA signature verification

**Testing.**

A self-contained, straightforward, pure-Python implementation was first
produced as a warm-up and to help check intermediate values. Test vectors from
various sources are embedded and used to validate the implementation.

This implementation, `p256.py`, is used by a second Python script,
`gen-test-data.py`, to generate additional data for both positive and negative
testing, available from a C header file, that is then used by the closed-box
and open-box test programs.

p256-m can be compiled with extra instrumentation to mark secret data and
allow either valgrind or MemSan to check that no branch or memory access
depends on it (even indirectly). Macros are defined for this purpose near the
top of the file.

**Tested platforms.**

There are 4 versions of the internal function `u32_muladd64`: two assembly
versions, for Cortex-M/A cores with or without the DSP extension, and two
pure-C versions, depending on whether `MUL64_IS_CONSTANT_TIME`.

Tests are run on the following platforms:

- `make` on x64 tests the pure-C version without `MUL64_IS_CONSTANT_TIME`
  (with Clang).
- `./consttime.sh` on x64 tests both pure-C versions (with Clang).
- `make` on Arm v7-A (Raspberry Pi 2) tests the Arm-DSP assembly version (with
  Clang).
- `on-target-*box` on boards based on Cortex-M0 and M4 cores test both
  assembly versions (with GCC).

In addition:

- `sizes.sh` builds the code for three Arm cores with GCC and Clang.
- `deps.sh` checks for external dependencies with GCC.

## Notes about other curves

It should be clear that minimal code size can only be reached by specializing
the implementation to the curve at hand. Here's a list of things in the
implementation that are specific to the NIST P-256 curve, and how the
implementation could be changed to expand to other curves, layer by layer (see
"Design Overview" above).

**Fixed-width multi-precision arithmetic:**

- The number of limbs is hard-coded to 8. For other 256-bit curves, nothing to
  change. For a curve of another size, hard-code to another value. For multiple
curves of various sizes, add a parameter to each function specifying the
number of limbs; when declaring arrays, always use the maximum number of
limbs.

**Fixed-width modular arithmetic:**

- The values of the curve's constant p and n, and their associated Montgomery
  constants, are hard-coded. For another curve, just hard-code the new constants.
For multiple other curves, define all the constants, and from this layer's API
only keep the functions that already accept a `mod` parameter (that is, remove
convenience functions `m256_xxx_p()`).
- The number of limbs is again hard-coded to 8. See above, but it order to
  support multiple sizes there is no need to add a new parameter to functions
in this layer: the existing `mod` parameter can include the number of limbs as
well.

**Operations on curve points:**

- The values of the curve's constants b (constant term from the equation) and
  gx, gy (coordinates of the base point) are hard-coded. For another curve,
  hard-code the other values. For multiple curves, define each curve's value and
add a "curve id" parameter to all functions in this layer.
- The value of the curve's constant a is implicitly hard-coded to `-3` by using
  a standard optimisation to save one multiplication in the first step of
`point_double()`. For curves that don't have a == -3, replace that with the
normal computation.
- The fact that b != 0 in the curve equation is used indirectly, to ensure
  that (0, 0) is not a point on the curve and re-use that value to represent
the point 0. As far as I know, all Short Weierstrass curves standardized so
far have b != 0.
- The shape of the curve is assumed to be Short Weierstrass. For other curve
  shapes (Montgomery, (twisted) Edwards), this layer would probably look very
different (both implementation and API).

**Scalar operations:**

- If multiple curves are to be supported, all function in this layer need to
  gain a new "curve id" parameter.
- This layer assumes that the bit size of the curve's order n is the same as
  that of the modulus p. This is true of most curves standardized so far, the
only exception being secp224k1. If that curve were to be supported, the
representation of `n` and scalars would need adapting to allow for an extra
limb.
- The bit size of the curve's order is hard-coded in `scalar_mult()`. For
  multiple curves, this should be deduced from the "curve id" parameter.
- The `scalar_mult()` function exploits the fact that the second least
  significant bit of the curve's order n is set in order to avoid a special
case. For curve orders that don't meet this criterion, we can just handle that
special case (multiplication by +-2) separately (always compute that and
conditionally assign it to the result).
- The shape of the curve is again assumed to be Short Weierstrass. For other curve
  shapes (Montgomery, (twisted) Edwards), this layer would probably have a
very different implementation.

**Public API:**

- For multiple curves, all functions in this layer would need to gain a "curve
  id" parameter and handle variable-sized input/output.
- The shape of the curve is again assumed to be Short Weierstrass. For other curve
  shapes (Montgomery, (twisted) Edwards), the ECDH API would probably look
quite similar (with differences in the size of public keys), but the ECDSA API
wouldn't apply and an EdDSA API would look pretty different.

## Notes about other platforms

While p256-m is standard C99, it is written with constrained 32-bit platforms
in mind and makes a few assumptions about the platform:

- The types `uint8_t`, `uint16_t`, `uint32_t` and `uint64_t` exist.
- 32-bit unsigned addition and subtraction with carry are constant time.
- 16x16->32-bit unsigned multiplication is available and constant time.

Also, on platforms on which 64-bit addition and subtraction with carry, or
even 64x64->128-bit multiplication, are available, p256-m makes no use of
them, though they could significantly improve performance.

This could be improved by replacing uses of arrays of `uint32_t` with a
defined type throughout the internal APIs, and then on 64-bit platforms define
that type to be an array of `uint64_t` instead, and making the obvious
adaptations in the multi-precision arithmetic layer.

Finally, the optional assembly code (which boosts performance by a factor 2 on
tested Cortex-M CPUs, while slightly reducing code size and stack usage) is
currently only available with compilers that support GCC's extended asm
syntax (which includes GCC and Clang).