The attached patch is against openssl-1.0.1-stable-SNAP-20110729 and
implements coordinate blinding. This randomizes the representative of
an elliptic curve point in its equivalence class. (For methods that
use projective coords such as curves over prime fields; for affine
coords, it does nothing.)
Coordinate blinding is a generally useful side-channel countermeasure
and is (mostly) free. The function itself takes a few field mults, but
is usually only necessary at the beginning of a scalar multiplication
(as implemented in the patch). When used this way, it makes the values
that variables take (i.e., field elements in an algorithm state)
unpredictable.
Only affine coords are implemented for curves over binary fields. If
this changes in the future, the corresponding blinding function can
easily be added.
If there are questions/concerns, please ask.
Billy
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec2_smpl.c openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec2_smpl.c
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec2_smpl.c 2011-06-06 19:00:23.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec2_smpl.c 2011-07-29 10:20:44.631809857 +0300
@@ -107,6 +107,7 @@
ec_GF2m_simple_add,
ec_GF2m_simple_dbl,
ec_GF2m_simple_invert,
+ 0 /* blind_coordinates */,
ec_GF2m_simple_is_at_infinity,
ec_GF2m_simple_is_on_curve,
ec_GF2m_simple_cmp,
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec_err.c openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec_err.c
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec_err.c 2011-06-06 15:00:18.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec_err.c 2011-07-29 10:32:56.011974902 +0300
@@ -1,6 +1,6 @@
/* crypto/ec/ec_err.c */
/* ====================================================================
- * Copyright (c) 1999-2010 The OpenSSL Project. All rights reserved.
+ * Copyright (c) 1999-2011 The OpenSSL Project. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -161,6 +161,7 @@
{ERR_FUNC(EC_F_EC_KEY_SET_PUBLIC_KEY_AFFINE_COORDINATES), "EC_KEY_set_public_key_affine_coordinates"},
{ERR_FUNC(EC_F_EC_POINTS_MAKE_AFFINE), "EC_POINTs_make_affine"},
{ERR_FUNC(EC_F_EC_POINT_ADD), "EC_POINT_add"},
+{ERR_FUNC(EC_F_EC_POINT_BLIND_COORDINATES), "EC_POINT_blind_coordinates"},
{ERR_FUNC(EC_F_EC_POINT_CMP), "EC_POINT_cmp"},
{ERR_FUNC(EC_F_EC_POINT_COPY), "EC_POINT_copy"},
{ERR_FUNC(EC_F_EC_POINT_DBL), "EC_POINT_dbl"},
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec.h openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec.h
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec.h 2011-06-06 17:00:17.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec.h 2011-07-29 10:32:56.011974902 +0300
@@ -592,6 +592,18 @@
*/
int EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx);
+/* J. S. Coron: Resistance against Differential Power Analysis for Elliptic
+ * Curve Cryptosystems. CHES 1999: 292-302.
+ * Coordinate blinding from Sec. 5.3 is generally a useful countermeasure
+ * against many types of side-channel attacks because it introduces some
+ * randomness into the algorithm state and doesn't really cost anything.
+ * \param group underlying EC_GROUP object
+ * \param a EC_POINT object to be coord-blinded (it's used for the result as well)
+ * \param ctx BN_CTX object (optional)
+ * \return 1 on success and 0 if an error occured
+ */
+int EC_POINT_blind_coordinates(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx);
+
/** Checks whether the point is the neutral element of the group
* \param group the underlying EC_GROUP object
* \param p EC_POINT object
@@ -1048,6 +1060,7 @@
#define EC_F_EC_KEY_SET_PUBLIC_KEY_AFFINE_COORDINATES 229
#define EC_F_EC_POINTS_MAKE_AFFINE 136
#define EC_F_EC_POINT_ADD 112
+#define EC_F_EC_POINT_BLIND_COORDINATES 230
#define EC_F_EC_POINT_CMP 113
#define EC_F_EC_POINT_COPY 114
#define EC_F_EC_POINT_DBL 115
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec_lcl.h openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec_lcl.h
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec_lcl.h 2011-06-06 17:00:17.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec_lcl.h 2011-07-29 10:04:26.268336600 +0300
@@ -142,10 +142,11 @@
int (*oct2point)(const EC_GROUP *, EC_POINT *,
const unsigned char *buf, size_t len, BN_CTX *);
- /* used by EC_POINT_add, EC_POINT_dbl, ECP_POINT_invert: */
+ /* used by EC_POINT_add, EC_POINT_dbl, EC_POINT_invert, EC_POINT_blind_coordinates: */
int (*add)(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *);
int (*dbl)(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, BN_CTX *);
int (*invert)(const EC_GROUP *, EC_POINT *, BN_CTX *);
+ int (*blind_coordinates)(const EC_GROUP *, EC_POINT *, BN_CTX *);
/* used by EC_POINT_is_at_infinity, EC_POINT_is_on_curve, EC_POINT_cmp: */
int (*is_at_infinity)(const EC_GROUP *, const EC_POINT *);
@@ -326,6 +327,7 @@
int ec_GFp_simple_add(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *);
int ec_GFp_simple_dbl(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, BN_CTX *);
int ec_GFp_simple_invert(const EC_GROUP *, EC_POINT *, BN_CTX *);
+int ec_GFp_simple_blind_coordinates(const EC_GROUP *, EC_POINT *, BN_CTX *);
int ec_GFp_simple_is_at_infinity(const EC_GROUP *, const EC_POINT *);
int ec_GFp_simple_is_on_curve(const EC_GROUP *, const EC_POINT *, BN_CTX *);
int ec_GFp_simple_cmp(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b, BN_CTX *);
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec_lib.c openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec_lib.c
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec_lib.c 2011-06-06 16:00:20.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec_lib.c 2011-07-29 10:00:46.804285464 +0300
@@ -956,6 +956,20 @@
}
+int EC_POINT_blind_coordinates(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx)
+ {
+ if (group->meth != a->meth)
+ {
+ ECerr(EC_F_EC_POINT_BLIND_COORDINATES, EC_R_INCOMPATIBLE_OBJECTS);
+ return 0;
+ }
+ if (group->meth->blind_coordinates != 0)
+ return group->meth->blind_coordinates(group, a, ctx);
+ else
+ return 1; /* optional: shouldn't break functionality. */
+ }
+
+
int EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
{
if (group->meth->is_at_infinity == 0)
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec_mult.c openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec_mult.c
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ec_mult.c 2010-08-26 16:04:12.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ec_mult.c 2011-07-29 10:02:07.662093914 +0300
@@ -688,6 +688,8 @@
{
if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) goto err;
r_is_at_infinity = 0;
+ /* blind coordinates to make them unpredictable. */
+ if (!EC_POINT_blind_coordinates(group, r, ctx)) goto err;
}
else
{
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ecp_mont.c openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ecp_mont.c
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ecp_mont.c 2011-06-06 19:00:23.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ecp_mont.c 2011-07-29 10:05:29.406624821 +0300
@@ -99,6 +99,7 @@
ec_GFp_simple_add,
ec_GFp_simple_dbl,
ec_GFp_simple_invert,
+ ec_GFp_simple_blind_coordinates,
ec_GFp_simple_is_at_infinity,
ec_GFp_simple_is_on_curve,
ec_GFp_simple_cmp,
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ecp_nist.c openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ecp_nist.c
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ecp_nist.c 2011-06-06 19:00:23.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ecp_nist.c 2011-07-29 10:05:39.826342343 +0300
@@ -100,6 +100,7 @@
ec_GFp_simple_add,
ec_GFp_simple_dbl,
ec_GFp_simple_invert,
+ ec_GFp_simple_blind_coordinates,
ec_GFp_simple_is_at_infinity,
ec_GFp_simple_is_on_curve,
ec_GFp_simple_cmp,
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ecp_nistp224.c openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ecp_nistp224.c
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ecp_nistp224.c 2011-05-12 17:00:15.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ecp_nistp224.c 2011-07-29 10:08:57.460983203 +0300
@@ -210,6 +210,7 @@
ec_GFp_simple_add,
ec_GFp_simple_dbl,
ec_GFp_simple_invert,
+ 0 /* blind_coordinates */,
ec_GFp_simple_is_at_infinity,
ec_GFp_simple_is_on_curve,
ec_GFp_simple_cmp,
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ecp_smpl.c openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ecp_smpl.c
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ec/ecp_smpl.c 2011-06-06 19:00:23.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ec/ecp_smpl.c 2011-07-29 10:34:57.698673564 +0300
@@ -100,6 +100,7 @@
ec_GFp_simple_add,
ec_GFp_simple_dbl,
ec_GFp_simple_invert,
+ ec_GFp_simple_blind_coordinates,
ec_GFp_simple_is_at_infinity,
ec_GFp_simple_is_on_curve,
ec_GFp_simple_cmp,
@@ -931,6 +932,64 @@
}
+/* Randomize the point's representative in the equivalence class.
+ * (X, Y, Z) = (\lambda^2 X, \lambda^3 Y, \lambda Z)
+ * is the equivalence class for this coordinate system, taken from
+ * IEEE P1363 / D13 A.9.6 "Representation of Points" p. 128.
+ */
+int ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
+ {
+ BN_CTX *new_ctx = NULL;
+ BIGNUM *t1, *t2;
+ int ret = 0;
+
+ if (EC_POINT_is_at_infinity(group, point))
+ return 1;
+
+ if (ctx == NULL)
+ {
+ ctx = new_ctx = BN_CTX_new();
+ if (ctx == NULL)
+ return 0;
+ }
+
+ BN_CTX_start(ctx);
+ t1 = BN_CTX_get(ctx);
+ t2 = BN_CTX_get(ctx);
+ if (t2 == NULL) goto err;
+
+ /* t1 = \lambda */
+ do
+ if (!BN_rand_range(t1, &group->field))
+ goto err;
+ while (BN_is_zero(t1));
+
+ /* t2 = \lambda^2 */
+ if (!group->meth->field_sqr(group, t2, t1, ctx)) goto err;
+ if (!group->meth->field_mul(group, &point->X, &point->X, t2, ctx)) goto err;
+ /* t2 = \?ambda^3 */
+ if (!group->meth->field_mul(group, t2, t2, t1, ctx)) goto err;
+ if (!group->meth->field_mul(group, &point->Y, &point->Y, t2, ctx)) goto err;
+ if (point->Z_is_one)
+ {
+ if (!BN_copy(&point->Z, t1)) goto err;
+ }
+ else
+ {
+ if (!group->meth->field_mul(group, &point->Z, &point->Z, t1, ctx)) goto err;
+ }
+ point->Z_is_one = 0;
+
+ ret = 1;
+
+ err:
+ BN_CTX_end(ctx);
+ if (new_ctx != NULL)
+ BN_CTX_free(new_ctx);
+ return ret;
+ }
+
+
int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
{
return BN_is_zero(&point->Z);
diff -ur openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ecdsa/ecdsatest.c openssl-1.0.1-stable-SNAP-20110729/crypto/ecdsa/ecdsatest.c
--- openssl-1.0.1-stable-SNAP-20110729-orig/crypto/ecdsa/ecdsatest.c 2011-06-06 15:00:18.000000000 +0300
+++ openssl-1.0.1-stable-SNAP-20110729/crypto/ecdsa/ecdsatest.c 2011-07-29 10:19:53.333200425 +0300
@@ -138,13 +138,28 @@
}
static int fbytes_counter = 0;
-static const char *numbers[8] = {
+static const char *numbers[14] = {
"651056770906015076056810763456358567190100156695615665659",
+ /* coord blinding: ECDSA keygen */
+ "111111111111111111111111111111111111111111111111111111111",
"6140507067065001063065065565667405560006161556565665656654",
+ /* coord blinding: ECDSA sign */
+ "111111111111111111111111111111111111111111111111111111111",
+ /* coord blinding: ECDSA verify */
+ "111111111111111111111111111111111111111111111111111111111",
"8763001015071075675010661307616710783570106710677817767166"
"71676178726717",
+ /* coord blinding: ECDSA keygen */
+ "1111111111111111111111111111111111111111111111111111111111"
+ "11111111111111",
"7000000175690566466555057817571571075705015757757057795755"
"55657156756655",
+ /* coord blinding: ECDSA sign */
+ "1111111111111111111111111111111111111111111111111111111111"
+ "11111111111111",
+ /* coord blinding: ECDSA verify */
+ "1111111111111111111111111111111111111111111111111111111111"
+ "11111111111111",
"1275552191113212300012030439187146164646146646466749494799",
"1542725565216523985789236956265265265235675811949404040041",
"1456427555219115346513212300075341203043918714616464614664"
@@ -157,7 +172,7 @@
int ret;
BIGNUM *tmp = NULL;
- if (fbytes_counter >= 8)
+ if (fbytes_counter >= 14)
return 0;
tmp = BN_new();
if (!tmp)
