This article was revisited and updated in October 2018.
Introduction
We strive to use the best state-of-the-art cryptography for our library Themis. So when we wanted to implement an important novel feature Secure Comparator (that includes the so-called "Socialist Millionaire Protocol"), we needed to replace the prime-field modular arithmetic with something stronger.
The obvious choice for such replacement was the ed25519 signature system:
it provides even more protection from side-channel analysis than conventional (NIST-driven) ECC,
it has very good speed,
its available implementation is designed by a well-known cryptographic scientist Daniel J. Bernstein,
it is free from potential patent claims.
What is ed25519?
Note: if you’re familiar with ed25519’s properties, you can skip this, as this is just a short overview to provide a general context.
The ed25519 and its close relative curve25519 are a modern state-of-the-art ECC curve and its implementations. They are fast and extremely secure. They were originally designed to provide simple implementation and inherent protection from side-channel attacks. From the mathematical standpoint, they represent different takes on the already known curve: ed25519 is the Twisted Edwards curve and curve25519 is the Montgomery curve.
Different representations are necessary because of different implementation use cases: curve25519 was designed for key agreement — ECDH and ed25519 is a digital signature algorithm.
ECC security is mostly based on the 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 (meaning: disclose the original input using some random output). Formally speaking, inverting the function does not have algorithms with polynomial time complexity. In the ECC domain, this problem is considered to be even more secure 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, the following ECC parameters are usually set and known in advance:
the curve itself and its representation (represented by the curve coefficients depending on the representation);
the base point G — a point on the curve, which is a group generator of a cyclic group formed by a subset of points on the 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.
This multiplication is a special operation defined over the cyclic group, formed by a subset of points on the elliptic curve. These are the basics of an ECC discrete logarithm: it is easy to multiply some point on an integer (and get another point as the output), however, it is hard to compute the integer, given the 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 the 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 when such representations are used. 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 fine for ECDH, where usually only the x coordinate is used as a final shared secret (algorithm output), but not for the digital signature algorithms as they require the ability to subtract points, hence being able to negate points in the first place.
Since SMP algorithm also requires ECC point subtraction, we chose ed25519 as our base implementation.
Extending and armoring ed25519
Even though ed25519 was initially a good candidate, it was originally designed as a digital signature algorithm, but SMP requires something different. The difference comes from the differences in the overall algorithm (different combination of ECC primitive operations) and, as a consequence, different algorithm parameter handling.
The basic ed25519 also boasts constant time operations protecting users' secrets from side-channel (mostly timing) attacks.
Extending
Since the code was written with the goal of maximum optimisation 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 — the sum of two points, where one is a multiple of the 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 the 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 the digital signature case since the second operation is used only for signature verification. Only the 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 wanted to keep the security level high, so a different approach was necessary.
The reusing approach adopted in the first ed25519 operation also made little sense, since its constant time properties are based on a large pre-computed table designed specifically for G (which is constant and known in advance). We could not do the same during the 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 a 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. We'll need to do the following:
generate a random integer rnd;
compute R = rnd * G + d * Q — time variable, where an attacker can only get some information about
rnd + d, yet, since the attacker knows neither d nor rnd, it is similar to d being encrypted by rnd;
compute P = rnd * G — constant time operation, available in the 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, secret handling is involved).
Summary
This article is a shortened explanation of the original paper "Secure Comparator: a ZKP-Based Authentication System" by Ignat Korchagin and Eugene Pilyankevich.
This is the first article of the many in our blog, outlining the insides of Secure Comparator, the important cryptographic primitive, which allows checking user credentials and authenticate users via tokens without actually exposing them via the network in any form.
All the code for Secure Comparator is available in our Themis GitHub repository. It is open-source to make peer review and design evaluations easy.
2018 UPD: This article is just as valid as on the day it was published, yet Themis and Secure Comparator have significantly evolved. If you're looking for new ideas, this is the right place. If you're looking to implement security, apply for our Customer Success Program. If you're looking for ready-made solutions, consider looking into Themis, Acra, Hermes, or Toughbase.
