Hi
I believe I've found a bug in the EC_POINT_cmp function.
In particular, if P is a valid point on the curve (other than the point
at infinity) and Q is the point at infinity, then EC_POINT_cmp(group, P,
Q, ctx) returns zero (equal).
But revering the order of the points in the call EC_POINT_cmp(group, Q,
P, ctx) correctly returns 1 (not equal).
I think the problem is in ec_GFp_simple_cmp (ecp_smpl.c) which contains
the following check at the start of the routine:
if (EC_POINT_is_at_infinity(group, a))
{
return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
}
Note that if "a" is not at infinity, then "b" is never checked. The
program then proceeds assuming neither point are at infinity, and
returns the default condition 0.
I've verified this still exists in the latest stable snapshot
openssl-0.9.8-stable-SNAP-20071123. I also tried openssl-SNAP-20071123
but got error messages when linking my program. However the file
ecp_smpl.c is unchanged, so I expect the same behaviour.
The problem is fixed by adding the following immediately after the
previous check (note that the case when both are at infinity has already
been tested for):
if (EC_POINT_is_at_infinity(group, b))
{
return 1;
}
Attached are the following files:
testlog : "make report" output
EC_POINT_cmp_bug.c : My test case
build : A simple compile script for test case
EC_POINT_cmp_bug.patch : Patch to fix the bug
Regards
Robert
#!/bin/sh
g++ -Iopenssl-0.9.8-stable-SNAP-20071123/include EC_POINT_cmp_bug.c
openssl-0.9.8-stable-SNAP-20071123/libcrypto.a -o EC_POINT_cmp_bug
#include <openssl/engine.h>
int main()
{
BIGNUM *a, *b, *p;
BIGNUM *x, *y;
EC_GROUP *group;
EC_POINT *P, *Q;
int cmpPQ, cmpQP;
const char rnd_seed[] = "string to make the random number generator think it has entropy";
// Initialise
CRYPTO_malloc_debug_init();
CRYPTO_set_mem_debug_options(V_CRYPTO_MDEBUG_ALL);
CRYPTO_mem_ctrl(CRYPTO_MEM_CHECK_ON);
ERR_load_crypto_strings();
RAND_seed(rnd_seed, sizeof rnd_seed); // or BN_generate_prime may fail
BN_CTX *ctx = BN_CTX_new();
// Curve parameters
p = BN_new(); BN_dec2bn(&p, "2003");
a = BN_new(); BN_dec2bn(&a, "1132");
b = BN_new(); BN_dec2bn(&b, "278");
// Generate curve
group = EC_GROUP_new_curve_GFp(p, a, b, ctx);
// Point coordinates
x = BN_new(); BN_dec2bn(&x, "1120");
y = BN_new(); BN_dec2bn(&y, "1391");
// Generate point
P = EC_POINT_new(group);
EC_POINT_set_affine_coordinates_GFp(group, P, x, y, ctx);
// Generate point at infinity
Q = EC_POINT_new(group);
EC_POINT_set_to_infinity(group, Q);
// Check points are on curve
if (!EC_POINT_is_on_curve(group, P, ctx) || !EC_POINT_is_on_curve(group, Q, ctx)) {
printf("Error. Points not on curve.\n");
exit(1);
}
// Compare points
cmpPQ = EC_POINT_cmp(group, P, Q, ctx);
cmpQP = EC_POINT_cmp(group, Q, P, ctx);
// Display results (0: equal, 1: not equal)
printf("EC_POINT_cmp(group, P, Q, ctx) = %d (%s)\n", cmpPQ, cmpPQ ? "P != Q" : "P == Q");
printf("EC_POINT_cmp(group, Q, P, ctx) = %d (%s)\n", cmpQP, cmpQP ? "Q != P" : "Q == P");
// Tidy up
BN_free(p);
BN_free(a);
BN_free(b);
BN_free(x);
BN_free(y);
EC_POINT_free(P);
EC_POINT_free(Q);
EC_GROUP_free(group);
// Clean up
if (ctx) BN_CTX_free(ctx);
ENGINE_cleanup();
CRYPTO_cleanup_all_ex_data();
ERR_free_strings();
ERR_remove_state(0);
CRYPTO_mem_leaks_fp(stderr);
return 0;
}
--- openssl-0.9.8-stable-SNAP-20071123/crypto/ec/ecp_smpl.c 2006-03-14 00:04:06.000000000 +0000
+++ openssl-0.9.8-stable-SNAP-20071123-fixed/crypto/ec/ecp_smpl.c 2007-11-23 16:40:37.000000000 +0000
@@ -1406,6 +1406,11 @@
{
return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
}
+
+ if (EC_POINT_is_at_infinity(group, b))
+ {
+ return 1;
+ }
if (a->Z_is_one && b->Z_is_one)
{
OpenSSL self-test report:
OpenSSL version: 0.9.8h-dev
Last change: Implement certificate status request TLS extension defi...
Options: no-camellia no-gmp no-krb5 no-mdc2 no-rc5 no-rfc3779 no-seed
no-shared no-tlsext no-zlib no-zlib-dynamic
OS (uname): Linux ronnie 2.6.17-1.2142_FC4 #1 Tue Jul 11 22:41:06 EDT
2006 x86_64 x86_64 x86_64 GNU/Linux
OS (config): x86_64-whatever-linux2
Target (default): linux-x86_64
Target: linux-x86_64
Compiler: Using built-in specs.
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man
--infodir=/usr/share/info --enable-shared --enable-threads=posix
--enable-checking=release --with-system-zlib --enable-__cxa_atexit
--disable-libunwind-exceptions --enable-libgcj-multifile
--enable-languages=c,c++,objc,java,f95,ada --enable-java-awt=gtk
--with-java-home=/usr/lib/jvm/java-1.4.2-gcj-1.4.2.0/jre
--host=x86_64-redhat-linux
Thread model: posix
gcc version 4.0.2 20051125 (Red Hat 4.0.2-8)
Test passed.
