Armoring ed25519 to meet extended security challenges

One tip that will help you to build even stronger security system

Introduction

In Themis we strive to use the best state-of-the art cryptography for our library. To implement important novel feature called Secure Comparator, which includes so-called Socialist Millionaire Protocol, we needed to replace prime-field modular arithmetic in it with something stronger.

The obvious choice for this was ed25519 signature system:

• it provides even more protection from side-channel analysis than conventional (NIST-driven) ECC
• has very good speed
• available implementation is designed by well-known cryptographic scientist, Daniel J. Bernstein
• is free from potential patent claims.

What is ed25519?

NOTE: if you’re familiar with ed25519’s properties, skip this, as this is just a review for general context.

Mentioned above ed25519 and it’s close relative curve25519 are modern state-of-the-art ECC curve and its implementations. They provide speed and simplicity, as well as high security. They were originally designed to provide simple implementation and inherent side-channel attack protection. From mathematical perspective, they represent the same curve in different representations: ed25519 is a Twisted Edwards curve and curve25519 is a Montgomery curve.

Different representations are driven by different use-cases in implementation: curve25519 was designed for key agreement — ECDH and ed25519 is a digital signature algorithm.

ECC security is mostly based on discrete logarithm problem. This problem represents a one-way function, where a function is easy to compute given a specific input, but hard to invert (find an input given some random output). More formally, inverting the function does not have algorithms with polynomial time complexity. In ECC domain this problem is considered even more secure. This is due to the fact that, unlike prime-field algebra, where such algorithms exist with sub-exponential time complexity, only exponential time algorithms exist for ECC.

For a specific cryptosystem and its implementation, following ECC parameters are usually fixed and known in advance:

• the curve itself and its representation (represented by curve coefficients depending on the representation);
• base point G — a point on the curve, which is a group generator of a cyclic group formed by a subset of points on elliptic curve.

Every user selects (generates) their pair of keys:

• private key d — a large integer,
• public key Q — a point on the curve, which is computed Q = d * G.

The above multiplication is a special operation defined over cyclic group, formed by a subset of points on elliptic curve. This is the basics of ECC discrete logarithm: it is easy to multiply some point on an integer (getting another point as the output), however, it is hard to compute the integer, given known Q and G.

There are other operations defined for ECC math: you can add and subtract points (always getting some other point as the output). Points can be negative with respect to each other, meaning that if you add them up, you will receive a “zero point”. ECC operations have distributive property: if you have Q = d * G you will get -Q = d * -G.

Negative points can be computed effectively: every ECC point is usually represented by a pair of coordinates on a 2D plane. Let’s say your point Q has coordinates (x, y), -Q will have (x, -y) then.

Twisted Edwards vs Montgomery

Both Twisted Edwards and Montgomery curve representations opt to provide some improvements over traditional Weierstrass form. Some ECC algorithms can be implemented in a more efficient and computer-friendly way if using such representations. The Montgomery form also allows representing points in a compressed form (saving memory and CPU cycles), however this compression comes with a price: y coordinate is discarded in Montgomery ECC calculations. This means that you can never tell the difference between Q and -Q. This is ашту for ECDH, where usually only x coordinate is used as a final shared secret (algorithm output), but not for digital signature algorithms, which require ability to subtract points, hence being able to negate points in the first place.

Since SMP algorithm also requires ECC point subtraction we naturally selected ed25519 as our base implementation.

Extending and armoring ed25519

Even though ed25519 is a good candidate, it was still designed as a digital signature algorithm, but SMP requires something different. The difference comes from differences in overall algorithm itself (different combination of ECC primitive operations) and, as a consequence, different algorithm parameter handling.

Also, basic ed25519 boasts constant time operations protecting users’ secrets from side-channel (mostly timing) attacks.

Extending

Since the code was written with high optimizations in mind, ed25519 had a limited subset of operations to start with:

• Q = d * G — basic ECC base point multiplication;
• R = s * G + r * Q — sum of two points, where one is a multiple of base point.

SMP on the other hand requires:

- T = u * P — simple point multiplication, but where P is some random (not known in advance) point.

To implement this operation based on what we already had in ed25519, the first step was to reuse the second function (sum of two points), passing n — ECC base point order- as s parameter. Therefore, since n * G = O (ECC zero point), so n * G + r * Q = O + r * Q = r * Q.

Armoring

However, the problem lies in the fact that the first ed25519 operation is constant time, while the second one is not. This is totally OK for digital signature case, since second operation is used only for signature verification. Only public key is used, with no secret information involved, so there is nothing to leak. In our case, however, ‘our adapted function may be used to multiply some secret value on an arbitrary point. We would like to keep security level high, so a different approach was needed.

Reusing approach taken in the first ed25519 operation also made little sense, since its constant time properties are based on a large pre-computed specifically for G (which is constant and known in advance) table. We could not do the same during execution for an arbitrary point, since the protocol would take ages to compute and end up eating all available memory.

Instead of trying to make the operation constant time, we decided to take blinding approach. The technique is basically mixing a random value in variable time operation to prevent the real secret parameter used from leaking through side-channel analysis.

Let’s suppose we want to compute R = d * Q. So, we do the following:

• generate random integer rnd
• compute R = rnd * G + d * Q — time variable, where attacker can only get some information about
• rnd + d, yet since he knows neither d nor rnd, it is similar if d was encrypted by rnd;
• compute P = rnd * G — constant time operation, available in original ed25519, so that attacker gets nothing;
• compute R = R — P = rnd * G + d * Q — rnd * G = d * Q — constant time operation (simple point subtraction, does not involve secret handling).

Summary

This is a first article in series, outlining the insides of Secure Comparator, important cryptographic primitive, allowing to check user credentials, authenticate users via tokens without actually exposing them via network in any form.

All code is available for anyone interested in our repository and, hopefully, will be useful for evaluating our designs.

P.S. This article was originally published on our blog.