summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorChristian Grothoff <christian@grothoff.org>2021-04-18 12:35:06 +0200
committerChristian Grothoff <christian@grothoff.org>2021-04-18 12:35:06 +0200
commitd286d829d36d444b08c83146ca7f24a22bc10a1e (patch)
tree793c4a784d4917aaf2c384e29627bfd3f23098ab
parentafcdafc937da305c225c13527a93fe49b98940f7 (diff)
crypto: fix dlog logic with libsodium
-rw-r--r--src/util/Makefile.am1
-rw-r--r--src/util/crypto_ecc_dlog.c318
-rw-r--r--src/util/test_crypto_ecc_dlog.c92
3 files changed, 182 insertions, 229 deletions
diff --git a/src/util/Makefile.am b/src/util/Makefile.am
index e2614e5e3..063c4a71b 100644
--- a/src/util/Makefile.am
+++ b/src/util/Makefile.am
@@ -460,6 +460,7 @@ if HAVE_NOLIBGCRYPT19
test_crypto_ecc_dlog_SOURCES = \
test_crypto_ecc_dlog.c
test_crypto_ecc_dlog_LDADD = \
+ -lsodium \
libgnunetutil.la \
$(LIBGCRYPT_LIBS)
endif
diff --git a/src/util/crypto_ecc_dlog.c b/src/util/crypto_ecc_dlog.c
index 8dd0c5526..fb402d505 100644
--- a/src/util/crypto_ecc_dlog.c
+++ b/src/util/crypto_ecc_dlog.c
@@ -61,122 +61,105 @@ struct GNUNET_CRYPTO_EccDlogContext
};
-/**
- * Do pre-calculation for ECC discrete logarithm for small factors.
- *
- * @param max maximum value the factor can be
- * @param mem memory to use (should be smaller than @a max), must not be zero.
- * @return NULL on error
- */
struct GNUNET_CRYPTO_EccDlogContext *
GNUNET_CRYPTO_ecc_dlog_prepare (unsigned int max,
unsigned int mem)
{
struct GNUNET_CRYPTO_EccDlogContext *edc;
- unsigned int K = ((max + (mem - 1)) / mem);
- unsigned int Kbe = htonl (K);
- struct GNUNET_PeerIdentity key;
- unsigned int i;
+ int K = ((max + (mem - 1)) / mem);
GNUNET_assert (max < INT32_MAX);
edc = GNUNET_new (struct GNUNET_CRYPTO_EccDlogContext);
edc->max = max;
edc->mem = mem;
-
edc->map = GNUNET_CONTAINER_multipeermap_create (mem * 2,
GNUNET_NO);
-
- unsigned char fact[crypto_core_ed25519_NONREDUCEDSCALARBYTES];
- unsigned char Ki[crypto_scalarmult_ed25519_SCALARBYTES];
- unsigned char nKi[crypto_scalarmult_ed25519_SCALARBYTES];
- unsigned char Kle[crypto_core_ed25519_NONREDUCEDSCALARBYTES];
- memset (fact, 0, sizeof (fact));
- memset (Ki, 0, sizeof (Ki));
- memset (nKi, 0, sizeof (nKi));
- memset (Kle, 0, sizeof (Kle));
- for (i = 0; i < sizeof (K); i++)
- Kle[i] = ((char*) &Kbe)[sizeof (K) - 1 - i];
- for (i = 1; i <= mem; i++)
+ for (int i = -(int) mem; i <= (int) mem; i++)
{
- sodium_increment (fact, sizeof (fact));
- memset (Ki, 0, sizeof (Ki));
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
- "K*i: %u (mem=%u, i=%u)\n", K * i, mem, i);
- crypto_core_ed25519_scalar_mul (Ki, fact, Kle);
- GNUNET_assert (0 ==
- crypto_scalarmult_ed25519_base_noclamp ((unsigned
- char*) &key, Ki));
+ struct GNUNET_CRYPTO_EccScalar Ki;
+ struct GNUNET_PeerIdentity key;
+
+ GNUNET_CRYPTO_ecc_scalar_from_int (K * i,
+ &Ki);
+ if (0 == i) /* libsodium does not like to multiply with zero */
+ GNUNET_assert (
+ 0 ==
+ crypto_core_ed25519_sub ((unsigned char *) &key,
+ (unsigned char *) &key,
+ (unsigned char *) &key));
+ else
+ GNUNET_assert (
+ 0 ==
+ crypto_scalarmult_ed25519_base_noclamp ((unsigned char*) &key,
+ Ki.v));
+ GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+ "K*i: %d (mem=%u, i=%d) => %s\n",
+ K * i,
+ mem,
+ i,
+ GNUNET_i2s (&key));
GNUNET_assert (GNUNET_OK ==
GNUNET_CONTAINER_multipeermap_put (edc->map,
&key,
(void *) (long) i + max,
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
}
- /* negative values */
- memset (fact, 0, sizeof (fact));
- for (i = 1; i < mem; i++)
- {
- sodium_increment (fact, sizeof (fact));
- memset (Ki, 0, sizeof (Ki));
- memset (nKi, 0, sizeof (nKi));
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
- "K*i: -%u (mem=%u, i=%u)\n", K * i, mem, i);
-
- crypto_core_ed25519_scalar_mul (Ki, fact, Kle);
- crypto_core_ed25519_scalar_negate (nKi, Ki);
- crypto_scalarmult_ed25519_base_noclamp ((unsigned char*) &key, nKi);
- GNUNET_assert (GNUNET_OK ==
- GNUNET_CONTAINER_multipeermap_put (edc->map,
- &key,
- (void *) (long) max - i,
- GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
- }
return edc;
}
-/**
- * Calculate ECC discrete logarithm for small factors.
- *
- * @param edc precalculated values, determine range of factors
- * @param input point on the curve to factor
- * @return INT_MAX if dlog failed, otherwise the factor
- */
int
GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
const struct GNUNET_CRYPTO_EccPoint *input)
{
unsigned int K = ((edc->max + (edc->mem - 1)) / edc->mem);
- struct GNUNET_PeerIdentity key;
- struct GNUNET_PeerIdentity nkey;
- unsigned int i;
int res;
- void *retp;
-
- unsigned char g[crypto_scalarmult_BYTES];
- unsigned char q[crypto_scalarmult_BYTES];
- unsigned char nq[crypto_scalarmult_BYTES];
- unsigned char fact[crypto_scalarmult_BYTES];
- memset (g, 0, crypto_scalarmult_BYTES);
- memset (q, 0, crypto_scalarmult_BYTES);
- memset (nq, 0, crypto_scalarmult_BYTES);
- memset (fact, 0, crypto_scalarmult_BYTES);
- sodium_increment (fact, sizeof (fact));
- crypto_scalarmult_ed25519_base_noclamp (g, fact);
- memset (&key, 0, crypto_scalarmult_BYTES);
- memset (&nkey, 0, crypto_scalarmult_BYTES);
+ struct GNUNET_CRYPTO_EccPoint g;
+ struct GNUNET_CRYPTO_EccPoint q;
+ struct GNUNET_CRYPTO_EccPoint nq;
+
+ {
+ struct GNUNET_CRYPTO_EccScalar fact;
+
+ memset (&fact,
+ 0,
+ sizeof (fact));
+ sodium_increment (fact.v,
+ sizeof (fact.v));
+ GNUNET_assert (0 ==
+ crypto_scalarmult_ed25519_base_noclamp (g.v,
+ fact.v));
+ }
+ /* make compiler happy: initialize q and nq, technically not needed! */
+ memset (&q,
+ 0,
+ sizeof (q));
+ memset (&nq,
+ 0,
+ sizeof (nq));
res = INT_MAX;
- for (i = 0; i <= edc->max / edc->mem; i++)
+ for (unsigned int i = 0; i <= edc->max / edc->mem; i++)
{
+ struct GNUNET_PeerIdentity key;
+ void *retp;
+
+ GNUNET_assert (sizeof (key) == crypto_scalarmult_BYTES);
if (0 == i)
{
- memcpy (&key, input, crypto_scalarmult_BYTES);
+ memcpy (&key,
+ input,
+ sizeof (key));
}
else
{
- memcpy (&key, q, crypto_scalarmult_BYTES);
- memcpy (&nkey, nq, crypto_scalarmult_BYTES);
+ memcpy (&key,
+ &q,
+ sizeof (key));
}
+ GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+ "Trying offset i=%u): %s\n",
+ i,
+ GNUNET_i2s (&key));
retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
&key);
if (NULL != retp)
@@ -186,47 +169,35 @@ GNUNET_CRYPTO_ecc_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc,
"constant-time". If we do not care about this, we could just
'break' here and do fewer operations... */
}
- retp = GNUNET_CONTAINER_multipeermap_get (edc->map,
- &nkey);
- if (NULL != retp)
- {
- res = (((long) retp) - edc->max) * K + i;
- }
if (i == edc->max / edc->mem)
break;
/* q = q + g */
if (0 == i)
{
- crypto_core_ed25519_add (q, input->v, g);
- crypto_core_ed25519_sub (nq, input->v, g);
+ GNUNET_assert (0 ==
+ crypto_core_ed25519_add (q.v,
+ input->v,
+ g.v));
}
else
{
- crypto_core_ed25519_add (q, q, g);
- crypto_core_ed25519_sub (nq, nq, g);
+ GNUNET_assert (0 ==
+ crypto_core_ed25519_add (q.v,
+ q.v,
+ g.v));
}
}
return res;
}
-/**
- * Generate a random value mod n.
- *
- * @param[out] r random value mod n.
- */
void
-GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccScalar* r)
+GNUNET_CRYPTO_ecc_random_mod_n (struct GNUNET_CRYPTO_EccScalar *r)
{
crypto_core_ed25519_scalar_random (r->v);
}
-/**
- * Release precalculated values.
- *
- * @param edc calculation context for ECC operations
- */
void
GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
{
@@ -235,110 +206,57 @@ GNUNET_CRYPTO_ecc_dlog_release (struct GNUNET_CRYPTO_EccDlogContext *edc)
}
-/**
- * Multiply the generator g of the elliptic curve by @a val
- * to obtain the point on the curve representing @a val.
- * Afterwards, point addition will correspond to integer
- * addition. #GNUNET_CRYPTO_ecc_dlog() can be used to
- * convert a point back to an integer (as long as the
- * integer is smaller than the MAX of the @a edc context).
- *
- * @param val value to encode into a point
- * @param r where to write the point (must be allocated)
- */
void
GNUNET_CRYPTO_ecc_dexp (int val,
- struct GNUNET_CRYPTO_EccPoint*r)
+ struct GNUNET_CRYPTO_EccPoint *r)
{
+ struct GNUNET_CRYPTO_EccScalar fact;
- unsigned char fact[crypto_scalarmult_ed25519_SCALARBYTES];
- unsigned char nFact[crypto_scalarmult_ed25519_SCALARBYTES];
- unsigned int valBe;
- int i;
-
- memset (fact, 0, sizeof (fact));
- memset (nFact, 0, sizeof (fact));
- if (val < 0)
- {
- valBe = htonl (-val);
- for (i = 0; i < sizeof (val); i++)
- fact[i] = ((char*) &valBe)[sizeof (val) - 1 - i];
- crypto_core_ed25519_scalar_negate (nFact, fact);
- crypto_scalarmult_ed25519_base_noclamp (r->v, nFact);
- }
- else
- {
- valBe = htonl (val);
- for (i = 0; i < sizeof (val); i++)
- fact[i] = ((char*) &valBe)[sizeof (val) - 1 - i];
- crypto_scalarmult_ed25519_base_noclamp (r->v, fact);
- }
+ GNUNET_CRYPTO_ecc_scalar_from_int (val,
+ &fact);
+ crypto_scalarmult_ed25519_base_noclamp (r->v,
+ fact.v);
}
-/**
- * Multiply the generator g of the elliptic curve by @a val
- * to obtain the point on the curve representing @a val.
- *
- * @param val (positive) value to encode into a point
- * @param r where to write the point (must be allocated)
- * @return GNUNET_OK on success.
- */
enum GNUNET_GenericReturnValue
GNUNET_CRYPTO_ecc_dexp_mpi (const struct GNUNET_CRYPTO_EccScalar *val,
struct GNUNET_CRYPTO_EccPoint *r)
{
- if (0 == crypto_scalarmult_ed25519_base_noclamp (r->v, val->v))
+ if (0 ==
+ crypto_scalarmult_ed25519_base_noclamp (r->v,
+ val->v))
return GNUNET_OK;
return GNUNET_SYSERR;
}
-/**
- * Add two points on the elliptic curve.
- *
- * @param a some value
- * @param b some value
- * @param r where to write the point (must be allocated)
- * @return GNUNET_OK on success.
- */
enum GNUNET_GenericReturnValue
GNUNET_CRYPTO_ecc_add (const struct GNUNET_CRYPTO_EccPoint *a,
const struct GNUNET_CRYPTO_EccPoint *b,
struct GNUNET_CRYPTO_EccPoint *r)
{
- crypto_core_ed25519_add (r->v, a->v, b->v);
+ crypto_core_ed25519_add (r->v,
+ a->v,
+ b->v);
return GNUNET_OK;
}
-/**
- * Multiply the point @a p on the elliptic curve by @a val.
- *
- * @param p point to multiply
- * @param val (positive) value to encode into a point
- * @param r where to write the point (must be allocated)
- * @return GNUNET_OK on success.
- */
enum GNUNET_GenericReturnValue
GNUNET_CRYPTO_ecc_pmul_mpi (const struct GNUNET_CRYPTO_EccPoint *p,
const struct GNUNET_CRYPTO_EccScalar *val,
struct GNUNET_CRYPTO_EccPoint *r)
{
- if (0 == crypto_scalarmult_ed25519_noclamp (r->v, val->v, p->v))
+ if (0 ==
+ crypto_scalarmult_ed25519_noclamp (r->v,
+ val->v,
+ p->v))
return GNUNET_OK;
return GNUNET_SYSERR;
}
-/**
- * Obtain a random point on the curve and its
- * additive inverse.
- *
- * @param[out] r set to a random point on the curve
- * @param[out] r_inv set to the additive inverse of @a r
- * @return GNUNET_OK on success.
- */
enum GNUNET_GenericReturnValue
GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccPoint *r,
struct GNUNET_CRYPTO_EccPoint *r_inv)
@@ -347,61 +265,61 @@ GNUNET_CRYPTO_ecc_rnd (struct GNUNET_CRYPTO_EccPoint *r,
unsigned char inv_s[crypto_scalarmult_ed25519_SCALARBYTES];
GNUNET_CRYPTO_ecc_random_mod_n (&s);
- if (0 != crypto_scalarmult_ed25519_base_noclamp (r->v, s.v))
+ if (0 !=
+ crypto_scalarmult_ed25519_base_noclamp (r->v,
+ s.v))
return GNUNET_SYSERR;
- crypto_core_ed25519_scalar_negate (inv_s, s.v);
- if (0 != crypto_scalarmult_ed25519_base_noclamp (r_inv->v, inv_s))
+ crypto_core_ed25519_scalar_negate (inv_s,
+ s.v);
+ if (0 !=
+ crypto_scalarmult_ed25519_base_noclamp (r_inv->v,
+ inv_s))
return GNUNET_SYSERR;
return GNUNET_OK;
}
-/**
- * Obtain a random scalar for point multiplication on the curve and
- * its multiplicative inverse.
- *
- * @param[out] r set to a random scalar on the curve
- * @param[out] r_inv set to the multiplicative inverse of @a
- */
void
GNUNET_CRYPTO_ecc_rnd_mpi (struct GNUNET_CRYPTO_EccScalar *r,
struct GNUNET_CRYPTO_EccScalar *r_inv)
{
-
GNUNET_CRYPTO_ecc_random_mod_n (r);
- crypto_core_ed25519_scalar_invert (r_inv->v, r->v);
+ crypto_core_ed25519_scalar_invert (r_inv->v,
+ r->v);
}
-/**
- * Create a scalar from int value.
- *
- * @param val the int value
- * @param[out] r where to write the salar
- */
void
GNUNET_CRYPTO_ecc_scalar_from_int (int val,
- struct GNUNET_CRYPTO_EccScalar* r)
+ struct GNUNET_CRYPTO_EccScalar *r)
{
- unsigned int valBe;
unsigned char fact[crypto_scalarmult_ed25519_SCALARBYTES];
- int i;
-
- memset (fact, 0, sizeof (fact));
+ uint32_t valBe;
+ GNUNET_assert (sizeof (*r) == sizeof (fact));
+ if (val < 0)
+ {
+ valBe = htonl ((uint32_t) (-val));
+ }
+ else
+ {
+ valBe = htonl ((uint32_t) val);
+ }
+ memset (fact,
+ 0,
+ sizeof (fact));
+ for (unsigned int i = 0; i < sizeof (val); i++)
+ fact[i] = ((unsigned char*) &valBe)[sizeof (val) - 1 - i];
if (val < 0)
{
- valBe = htonl (-val);
- for (i = 0; i < sizeof (val); i++)
- fact[i] = ((char*) &valBe)[sizeof (val) - 1 - i];
- crypto_core_ed25519_scalar_negate (r->v, fact);
+ crypto_core_ed25519_scalar_negate (r->v,
+ fact);
}
else
{
- valBe = htonl (val);
- for (i = 0; i < sizeof (val); i++)
- fact[i] = ((char*) &valBe)[sizeof (val) - 1 - i];
- crypto_scalarmult_ed25519_base_noclamp (r->v, fact);
+ memcpy (r,
+ fact,
+ sizeof (fact));
}
}
diff --git a/src/util/test_crypto_ecc_dlog.c b/src/util/test_crypto_ecc_dlog.c
index a901bddf2..51f290d51 100644
--- a/src/util/test_crypto_ecc_dlog.c
+++ b/src/util/test_crypto_ecc_dlog.c
@@ -49,7 +49,7 @@
/**
* How many values do we test?
*/
-#define TEST_ITER 10
+#define TEST_ITER 100
/**
* Range of values to use for MATH tests.
@@ -65,46 +65,76 @@
static void
test_dlog (struct GNUNET_CRYPTO_EccDlogContext *edc)
{
- struct GNUNET_CRYPTO_EccScalar fact;
- struct GNUNET_CRYPTO_EccScalar n;
- struct GNUNET_CRYPTO_EccPoint q;
- unsigned int i;
- int x;
- int iret;
-
- for (i = 0; i < TEST_ITER; i++)
+ for (unsigned int i = 0; i < TEST_ITER; i++)
{
+ struct GNUNET_CRYPTO_EccScalar fact;
+ struct GNUNET_CRYPTO_EccScalar n;
+ struct GNUNET_CRYPTO_EccPoint q;
+ int x;
+
fprintf (stderr, ".");
x = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
MAX_FACT);
- for (i = 0; i < x; i++)
- sodium_increment (n.v, sizeof (n.v));
- //memcpy (n->v, &x, sizeof (x));
+ memset (&n,
+ 0,
+ sizeof (n));
+ for (unsigned int j = 0; j < x; j++)
+ sodium_increment (n.v,
+ sizeof (n.v));
if (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
2))
{
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
- "Trying negative %d\n", -x);
- crypto_core_ed25519_scalar_negate (fact.v, n.v);
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO,
+ "Trying negative %d\n",
+ -x);
+ crypto_core_ed25519_scalar_negate (fact.v,
+ n.v);
x = -x;
}
else
{
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO,
+ "Trying positive %d\n",
+ x);
fact = n;
}
- crypto_scalarmult_ed25519_base_noclamp (q.v, fact.v);
- if (x !=
- (iret = GNUNET_CRYPTO_ecc_dlog (edc,
- &q)))
+ if (0 == x)
{
- fprintf (stderr,
- "DLOG failed for value %d (%d)\n",
- x,
- iret);
- GNUNET_assert (0);
+ /* libsodium does not like to multiply with zero; make sure
+ 'q' is a valid point (g) first, then use q = q - q to get
+ the product with zero */
+ sodium_increment (fact.v,
+ sizeof (fact.v));
+ GNUNET_assert (0 ==
+ crypto_scalarmult_ed25519_base_noclamp (q.v,
+ fact.v));
+ GNUNET_assert (
+ 0 ==
+ crypto_core_ed25519_sub (q.v,
+ q.v,
+ q.v));
+ }
+ else
+ GNUNET_assert (0 ==
+ crypto_scalarmult_ed25519_base_noclamp (q.v,
+ fact.v));
+ {
+ int iret;
+
+ if (x !=
+ (iret = GNUNET_CRYPTO_ecc_dlog (edc,
+ &q)))
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "DLOG failed for value %d (got: %d)\n",
+ x,
+ iret);
+ GNUNET_assert (0);
+ }
}
}
- fprintf (stderr, "\n");
+ fprintf (stderr,
+ "\n");
}
@@ -132,8 +162,10 @@ test_math (struct GNUNET_CRYPTO_EccDlogContext *edc)
for (j = -MATH_MAX; j < MATH_MAX; j++)
{
fprintf (stderr, ".");
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
- "%d + %d\n", i, j);
+ GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+ "%d + %d\n",
+ i,
+ j);
GNUNET_CRYPTO_ecc_dexp (j, &jp);
GNUNET_CRYPTO_ecc_rnd (&r,
&r_inv);
@@ -144,8 +176,10 @@ test_math (struct GNUNET_CRYPTO_EccDlogContext *edc)
if (i + j != res)
{
GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
- "Got %d, expected %d\n", res, i+j);
- //GNUNET_assert (0);
+ "Got %d, expected %d\n",
+ res,
+ i + j);
+ // GNUNET_assert (0);
}
}
}