Sweet B is a library which implements public key elliptic curve cryptography (ECC) using the NIST P-256, SECG secp256k1, and curve25519 curves. Sweet B is:
- Safe: known attack vectors have been accounted for, design decisions have been documented, and the API has been designed to eliminate the possibility of catastrophic misuse when possible.
- Clear: the library is thoroughly commented and unit tested, and is designed to be easy to read and review.
- Compact: the library is compact in code size, uses a minimal 512-byte working context, and does not assume that keys and other intermediary products can be allocated on the stack.
Sweet B is currently available for public review and testing, and will be released under an open source license when we are confident that it is ready for widespread use. You should consider using Sweet B if you need to implement elliptic curve Diffie-Hellman shared-secret generation (ECDH) or elliptic curve digital signature generation and verification (ECDSA) in a memory-constrained environment. For instance, the P-256 curve is used in Bluetooth Low Energy Security, and is often implemented on memory-constrained devices for this purpose.
Secure system design depends on more than just the right choice of cryptographic library. Commercial support for the use and adaptation of Sweet B is available from its authors.
Sweet B is a pun on both the Short Weierstrass form of elliptic curves and on the NSA's Suite B set of cryptographic algorithms.
Sweet B was developed by Wearable Inc. We're opening Sweet B for public review in advance of the release of Nanite, our open-source operating system and developer platform for Bluetooth Low Energy.
Suite B is derived in part from work supported by DARPA under SBIR contract number D15PC00141.
Sweet B provides mitigation for several classes of known faults and attacks:
- Timing analyses reveal secret information by measuring the time that it takes to perform cryptographic operations. Sweet B prevents this by ensuring that all operations run in constant time with respect to the input data (though different curves have different performance characteristics).
- Power analyses reveal secret information by measuring the amount of power consumed during cryptographic operations. Sweet B addresses this by using randomized projective coordinates, also called Z blinding. The special case of zero value analysis has been addressed by representing reduced integers modulo 𝑝 as integers within the range [1, 𝑝], ensuring that the points (0, ±√𝐵 ∙ 𝑍³, 𝑍) on applicable curves do not cause observable multiplications by low-Hamming-weight field elements.
- Safe-error analyses reveal secret information by causing hardware faults during cryptographic operations and observing whether the fault affects the output. Sweet B mitigates these attacks through the use of a regular Montgomery ladder with no dummy computations prior to the final bit.
- Per-message secret reuse causes the private key to be revealed to anyone receiving more than one signature with the same secret. Sweet B prevents this by providing an internal implementation of a deterministic random-bit generator (DRBG) using HMAC-SHA256 for per-message secret generation in ECDSA signing. When an externally seeded instance of the DRBG is provided, the private key and message are provided as additional input to the DRBG, ensuring that even in cases of entropy source failure, per-message secrets are never re-used. When no externally seeded instance is provided, RFC6979 deterministic signing is used. The internal HMAC-DRBG is also used for projective-coordinate randomization when no external entropy source is available.
It is impossible to guarantee that side-channel mitigations in a portable C implementation will perform correctly with all compilers and with all target platforms. If power and fault-injection mitigations are important for your application, please contact Wearable for commercial support.
Sweet B is designed to be simple, safe, compact, and embeddable. In order to be as portable as possible, any word size from 8 to 64 bits may be used; you should choose the word size that corresponds to the size of your hardware multiplier. Sweet B does not assume that it's possible to store large amounts of working state on the stack; instead, a separately allocated 512-byte working context is required, which may be placed on the stack, heap allocated, or statically allocated per the user's needs.
Simple, compact implementations of SHA256, HMAC-SHA256, and HMAC-DRBG are provided both for internal use and for use in producing digests of data to be signed or verified. You are also encouraged to use the HMAC-DRBG implementation for random number generation in your system, assuming you have access to a sufficient source of hardware entropy.
Sweet B uses Montgomery multiplication, which eliminates the need for separate reduction steps. This makes it easier to produce a constant-time library supporting multiple primes, and also makes Sweet B fast compared with other embeddable implementations in C. However, there are faster implementations of ECC if you have more working memory or more code storage available.
Sweet B has been carefully designed to avoid side channel attacks, including timing and power analyses. All field operations and elliptic curve operations are designed to run in constant time, and projective coordinate randomization consistently used. All functions take an optional DRBG parameter, and you are strongly encouraged to supply a properly-seeded DRBG whenever possible to mitigate power-based side channel attacks.
sb_sw_lib.h is the main entry point for ECC operations on
short Weierstrass curves (P-256 and secp256k1);
sb_mont_lib.h is the main entry point for operations
on Montgomery curves (curve25519). For hashing and random number generation, see
sb_sha256.h and sb_hmac_drbg.h.
Each file contains a number of test cases; if you compile Sweet B with
-DSB_TEST, you can run them using the main routine in
sb_test.c.
You can set the word size used in Sweet B with the SB_MUL_SIZE preprocessor
macro. By default, this is set to 4, meaning that 32-bit multiplies producing
64-bit results will be used. On 8- or 16-bit microcontrollers, or on 32-bit
microcontrollers without full 64-bit multiply output (such as the Cortex-M0+),
you should set this to 1 or 2. On 64-bit x86 systems, you may want to set the
multiplication size to 8 to use 128-bit multiplication output.
You can disable either of the short Weierstrass curves Sweet B supports by
setting the preprocessor defines SB_SW_P256_SUPPORT or
SB_SW_SECP256K1_SUPPORT to 0. Montgomery and short Weierstrass curve support
is independent, and you may choose to link in either or both of
sb_sw_lib.c or sb_mont_lib.c. If you
have a little more program memory available, you may want to set SB_UNROLL to
a value between 1 and 3 (inclusive); on Cortex-M4, SB_UNROLL=2 provides the
best balance between size and speed. Sweet B will also attempt to detect ARM
processors which support DSP extensions and use the UMAAL instruction for
multiplication; see sb_fe.c if this autodetection does not work
for you.
CMake build support is provided; to use it, create a
directory for your build, run cmake with the path to the Sweet B sources, and
then run make to build. To run the unit tests with the clang undefined
behavior and address sanitizers, pass -DCMAKE_C_COMPILER=clang to cmake if
clang is not your default compiler.
Sweet B is not yet open source! You are encouraged to experiment, review,
analyze, and test the library, and to share your findings with others, but you
are not allowed to use it in any situation where the security of anyone's data
depends on it. For the exact details, see the LICENSE.txt file.
Once we are confident that it is ready for use, an official release will be made
under the MPL 2.0. We believe this is
the best license choice for the library as it imposes few barriers to commercial
use while requiring distributors of modified versions to share their
modifications so they can be inspected by users.
To the best of anyone's knowledge, yes. All public-key cryptography relies on unproven assumptions about the difficulty of solving certain mathematical problems; after more than three decades of research, there are no indications that prime order elliptic curves of the short Weierstrass form used in Sweet B are fundamentally weak or insecure.
There's been a fair amount of controversy about P-256 recently because of the NSA's role in the specification of both P-256 and the deliberately backdoored Dual EC DRBG algorithm. Because one of the important parameters of P-256 was specified as a hash of a supposedly-random string, some have theorized that the NSA may have tried a large number of supposedly-random hashed strings until it found one that met its criteria. However, the fact that the NSA had to resort to a clumsy and obvious backdoor mechanism in Dual EC DRBG suggests that they do not have access to any such mechanism of generating weak curves, and furthermore, it seems quite unlikely that a large class of weak curves would go unnoticed by the academic community in the almost 20 years since the NIST curve recommendations were issued. If you feel uncomfortable with P-256 and have the ability to choose a different curve for your application, the secp256k1 curve has no supposedly-random constants and is suitable as an alternative.
Recently, there's also been a fair amount of interest in curves of the Montgomery and Edwards forms; these curves have their own strengths, including performance advantages, and weaknesses of their own which must be mitigated through careful design and implementation choices. One cryptographer and promoter of such curves has declared all short Weierstrass curves to be "unsafe"; however, his analysis is at best seriously misleading, and includes only criteria of his own choosing. The claims made of unsafety are answered as follows:
- The rigidity argument has been addressed above. You might also consider that if you are choosing a curve because of the possibility that the NSA has secret knowledge of a large class of weak curves, you might accidentally pick such a curve even when following a "rigid" curve-specification procedure.
- The complex multiplication discriminant of secp256k1 permits an automorphism which can be used to improve the average running time of Pollard's ρ, but the rho method is faster yet on Montgomery and Edwards curves of equivalent prime-field size due to the smaller size of their cryptographic subgroup.
- The Montgomery ladder used in Sweet B is non-exceptional for all input scalars ∉ {-2, -1, 0, 1} mod 𝑛. These input scalars are easily checked for, and the probability of one of these scalars occurring in HMAC-DRBG output is infinitesimal.
- Complete addition formulae are not relevant to actual cryptographic software. Even implementations of twisted Edwards curves use non-unified addition and doubling formulae in practice for efficiency purposes.
- Indistinguishability of points from random strings is not a requirement for most protocols. This requirement is motivated by certain censorship-avoidance applications, but not needed for many other applications, and to the best of our knowledge, there is no proof that such a scheme can't be developed for short Weierstrass curves.
We could easily add additional criteria of our own choosing and decide that other curves are "unsafe". For instance, if avoidance of special cases is a concern, we could decide that primes ≡ 1 mod 4 are unsafe due to the extra (and irregular) step required in point decompression. Similarly, we could declare that curves with a cofactor ≠ 1 are unsafe due to the extra care required in avoiding small-subgroup attacks. Neither of these criteria make these curves unsafe in practice, but they necessitate careful attention in the implementation and use of these curves, as is the case for all cryptographic software.
Our point is not to suggest the use of P-256 or secp256k1 over other curves; rather, if you have a need to use either of these curves, you should not be concerned as long as your implementation was developed with appropriate care.
Neal Koblitz. A Course in Number Theory and Cryptography. Springer-Verlag, 1994.
This is a rather old text, and the section on elliptic curves is dated. However, it remains an outstanding reference for any discussion of finite fields.
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.
Another older text, but the chapter on efficient implementation remains a worthwhile reference for basic field arithmetic algorithms.
Jean-Sébastien Coron. Resistance Against Differential Power Analysis For Elliptic Curve Cryptosystems. In Cryptographic Hardware and Embedded Systems (CHES) 1999.
Introduces several countermeasures against power analyses, the third of which is the randomized projective coordinate technique used in Sweet B (often described as "Coron's third countermeasure").
Tetsuya Izu, Bodo Möller, and Tsuyoshi Takagi. Improved Elliptic Curve Multiplication Methods Resistant against Side Channel Attacks. In Progress in Cryptology — INDOCRYPT 2002.
Discusses the SPA and DPA-resistance of the Montgomery ladder for elliptic curves.
Raveen R. Goundar, Marc Joye, Atsuko Miyaji, Matthieu Rivain, and Alexandre Venelli. Scalar multiplication on Weierstraß elliptic curves from Co-Z arithmetic. In Journal of Cryptographic Engineering, Vol. 1, 161 (2011).
Introduces the co-Z Montgomery ladder on Weierstrass curves, and discusses its derivation.
Matthieu Rivain. Fast and Regular Algorithms for Scalar Multiplication over Elliptic Curves. IACR Cryptology ePrint Archive, Report 2011/338.
The main reference for Sweet B. Describes the co-Z addition and initial affine-to-Jacobian point doubling formulae implemented in the library.
Shay Gueron and Vlad Krasnov. Fast prime field elliptic-curve cryptography with 256-bit primes. In Journal of Cryptographic Engineering, Vol. 5, 141 (2011).
Discusses the use of Montgomery multiplication with the P-256 field prime, specifically due to its "Montgomery friendly" property.
Peter Montgomery, Speeding the Pollard and Elliptic Curve Methods of Factorization. In Mathematics of Computation, Vol. 48, 171 (1987).
Introduces Montgomery curves of the form 𝐵𝑦² = 𝑥³ + 𝐴𝑥² + 𝑥, of which curve25519 is an example, and gives formulas for their arithmetic.
Craig Costello and Benjamin Smith, Montgomery curves and their arithmetic: The case of large characteristic fields. In Journal of Cryptographic Engineering, 2017.
A survey of Montgomery curves and a description of the doubling and addition formulae used in Sweet B.
Daniel Genkin, Luke Valenta, and Yuval Yarom. May the Fourth Be With You: A Microarchitectural Side Channel Attack on Several Real-World Applications of Curve25519. ACM Conference on Computer and Communications Security (CCS) 2017. Also presented as Side channel attacks on implementations of Curve25519 at Real World Crypto 2018.
An example of what can go wrong with "safe" Montgomery curves when input points are not validated.