X-Git-Url: https://asedeno.scripts.mit.edu/gitweb/?a=blobdiff_plain;f=sshecc.c;h=3ce6c7fe6ae07e19e3b0b35dfdba92398e1cf999;hb=730a9fdfe3d624bb663557c67f89d2cf8b575964;hp=99321807b76c3b9cd8088e5077858704a967853d;hpb=541abf92583cd93f3952aa0e3b8f61ba9251f3fa;p=PuTTY.git diff --git a/sshecc.c b/sshecc.c index 99321807..3ce6c7fe 100644 --- a/sshecc.c +++ b/sshecc.c @@ -6,6 +6,8 @@ * in Weierstrass form using Jacobian co-ordinates. * * Montgomery form curves are supported for DH. (Curve25519) + * + * Edwards form curves are supported for DSA. (Ed25519) */ /* @@ -21,6 +23,13 @@ * Montgomery maths from: * Handbook of elliptic and hyperelliptic curve cryptography, Chapter 13 * http://cs.ucsb.edu/~koc/ccs130h/2013/EllipticHyperelliptic-CohenFrey.pdf + * + * Curve25519 spec from libssh (with reference to other things in the + * libssh code): + * https://git.libssh.org/users/aris/libssh.git/tree/doc/curve25519-sha256@libssh.org.txt + * + * Edwards DSA: + * http://ed25519.cr.yp.to/ed25519-20110926.pdf */ #include @@ -32,10 +41,11 @@ * Elliptic curve definitions */ -static int initialise_wcurve(struct ec_curve *curve, int bits, unsigned char *p, - unsigned char *a, unsigned char *b, - unsigned char *n, unsigned char *Gx, - unsigned char *Gy) +static void initialise_wcurve(struct ec_curve *curve, int bits, + const unsigned char *p, + const unsigned char *a, const unsigned char *b, + const unsigned char *n, const unsigned char *Gx, + const unsigned char *Gy) { int length = bits / 8; if (bits % 8) ++length; @@ -44,37 +54,23 @@ static int initialise_wcurve(struct ec_curve *curve, int bits, unsigned char *p, curve->fieldBits = bits; curve->p = bignum_from_bytes(p, length); - if (!curve->p) goto error; /* Curve co-efficients */ curve->w.a = bignum_from_bytes(a, length); - if (!curve->w.a) goto error; curve->w.b = bignum_from_bytes(b, length); - if (!curve->w.b) goto error; /* Group order and generator */ curve->w.n = bignum_from_bytes(n, length); - if (!curve->w.n) goto error; curve->w.G.x = bignum_from_bytes(Gx, length); - if (!curve->w.G.x) goto error; curve->w.G.y = bignum_from_bytes(Gy, length); - if (!curve->w.G.y) goto error; curve->w.G.curve = curve; curve->w.G.infinity = 0; - - return 1; - error: - if (curve->p) freebn(curve->p); - if (curve->w.a) freebn(curve->w.a); - if (curve->w.b) freebn(curve->w.b); - if (curve->w.n) freebn(curve->w.n); - if (curve->w.G.x) freebn(curve->w.G.x); - return 0; } -static int initialise_mcurve(struct ec_curve *curve, int bits, unsigned char *p, - unsigned char *a, unsigned char *b, - unsigned char *Gx) +static void initialise_mcurve(struct ec_curve *curve, int bits, + const unsigned char *p, + const unsigned char *a, const unsigned char *b, + const unsigned char *Gx) { int length = bits / 8; if (bits % 8) ++length; @@ -83,86 +79,89 @@ static int initialise_mcurve(struct ec_curve *curve, int bits, unsigned char *p, curve->fieldBits = bits; curve->p = bignum_from_bytes(p, length); - if (!curve->p) goto error; /* Curve co-efficients */ curve->m.a = bignum_from_bytes(a, length); - if (!curve->m.a) goto error; curve->m.b = bignum_from_bytes(b, length); - if (!curve->m.b) goto error; /* Generator */ curve->m.G.x = bignum_from_bytes(Gx, length); - if (!curve->m.G.x) goto error; curve->m.G.y = NULL; curve->m.G.z = NULL; curve->m.G.curve = curve; curve->m.G.infinity = 0; - - return 1; - error: - if (curve->p) freebn(curve->p); - if (curve->m.a) freebn(curve->m.a); - if (curve->m.b) freebn(curve->m.b); - return 0; } -unsigned char nistp256_oid[] = {0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07}; -int nistp256_oid_len = 8; -unsigned char nistp384_oid[] = {0x2b, 0x81, 0x04, 0x00, 0x22}; -int nistp384_oid_len = 5; -unsigned char nistp521_oid[] = {0x2b, 0x81, 0x04, 0x00, 0x23}; -int nistp521_oid_len = 5; -unsigned char curve25519_oid[] = {0x06, 0x0A, 0x2B, 0x06, 0x01, 0x04, 0x01, 0x97, 0x55, 0x01, 0x05, 0x01}; -int curve25519_oid_len = 12; +static void initialise_ecurve(struct ec_curve *curve, int bits, + const unsigned char *p, + const unsigned char *l, const unsigned char *d, + const unsigned char *Bx, const unsigned char *By) +{ + int length = bits / 8; + if (bits % 8) ++length; + + curve->type = EC_EDWARDS; + + curve->fieldBits = bits; + curve->p = bignum_from_bytes(p, length); + + /* Curve co-efficients */ + curve->e.l = bignum_from_bytes(l, length); + curve->e.d = bignum_from_bytes(d, length); + + /* Group order and generator */ + curve->e.B.x = bignum_from_bytes(Bx, length); + curve->e.B.y = bignum_from_bytes(By, length); + curve->e.B.curve = curve; + curve->e.B.infinity = 0; +} -struct ec_curve *ec_p256(void) +static struct ec_curve *ec_p256(void) { static struct ec_curve curve = { 0 }; static unsigned char initialised = 0; if (!initialised) { - unsigned char p[] = { + static const unsigned char p[] = { 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }; - unsigned char a[] = { + static const unsigned char a[] = { 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc }; - unsigned char b[] = { + static const unsigned char b[] = { 0x5a, 0xc6, 0x35, 0xd8, 0xaa, 0x3a, 0x93, 0xe7, 0xb3, 0xeb, 0xbd, 0x55, 0x76, 0x98, 0x86, 0xbc, 0x65, 0x1d, 0x06, 0xb0, 0xcc, 0x53, 0xb0, 0xf6, 0x3b, 0xce, 0x3c, 0x3e, 0x27, 0xd2, 0x60, 0x4b }; - unsigned char n[] = { + static const unsigned char n[] = { 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84, 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51 }; - unsigned char Gx[] = { + static const unsigned char Gx[] = { 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47, 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40, 0xf2, 0x77, 0x03, 0x7d, 0x81, 0x2d, 0xeb, 0x33, 0xa0, 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96 }; - unsigned char Gy[] = { + static const unsigned char Gy[] = { 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b, 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e, 0x16, 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce, 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5 }; - if (!initialise_wcurve(&curve, 256, p, a, b, n, Gx, Gy)) { - return NULL; - } + initialise_wcurve(&curve, 256, p, a, b, n, Gx, Gy); + curve.textname = curve.name = "nistp256"; /* Now initialised, no need to do it again */ initialised = 1; @@ -171,14 +170,14 @@ struct ec_curve *ec_p256(void) return &curve; } -struct ec_curve *ec_p384(void) +static struct ec_curve *ec_p384(void) { static struct ec_curve curve = { 0 }; static unsigned char initialised = 0; if (!initialised) { - unsigned char p[] = { + static const unsigned char p[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, @@ -186,7 +185,7 @@ struct ec_curve *ec_p384(void) 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff }; - unsigned char a[] = { + static const unsigned char a[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, @@ -194,7 +193,7 @@ struct ec_curve *ec_p384(void) 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xfc }; - unsigned char b[] = { + static const unsigned char b[] = { 0xb3, 0x31, 0x2f, 0xa7, 0xe2, 0x3e, 0xe7, 0xe4, 0x98, 0x8e, 0x05, 0x6b, 0xe3, 0xf8, 0x2d, 0x19, 0x18, 0x1d, 0x9c, 0x6e, 0xfe, 0x81, 0x41, 0x12, @@ -202,7 +201,7 @@ struct ec_curve *ec_p384(void) 0xc6, 0x56, 0x39, 0x8d, 0x8a, 0x2e, 0xd1, 0x9d, 0x2a, 0x85, 0xc8, 0xed, 0xd3, 0xec, 0x2a, 0xef }; - unsigned char n[] = { + static const unsigned char n[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, @@ -210,7 +209,7 @@ struct ec_curve *ec_p384(void) 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a, 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73 }; - unsigned char Gx[] = { + static const unsigned char Gx[] = { 0xaa, 0x87, 0xca, 0x22, 0xbe, 0x8b, 0x05, 0x37, 0x8e, 0xb1, 0xc7, 0x1e, 0xf3, 0x20, 0xad, 0x74, 0x6e, 0x1d, 0x3b, 0x62, 0x8b, 0xa7, 0x9b, 0x98, @@ -218,7 +217,7 @@ struct ec_curve *ec_p384(void) 0x55, 0x02, 0xf2, 0x5d, 0xbf, 0x55, 0x29, 0x6c, 0x3a, 0x54, 0x5e, 0x38, 0x72, 0x76, 0x0a, 0xb7 }; - unsigned char Gy[] = { + static const unsigned char Gy[] = { 0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f, 0x5d, 0x9e, 0x98, 0xbf, 0x92, 0x92, 0xdc, 0x29, 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c, @@ -227,9 +226,8 @@ struct ec_curve *ec_p384(void) 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0x0e, 0x5f }; - if (!initialise_wcurve(&curve, 384, p, a, b, n, Gx, Gy)) { - return NULL; - } + initialise_wcurve(&curve, 384, p, a, b, n, Gx, Gy); + curve.textname = curve.name = "nistp384"; /* Now initialised, no need to do it again */ initialised = 1; @@ -238,14 +236,14 @@ struct ec_curve *ec_p384(void) return &curve; } -struct ec_curve *ec_p521(void) +static struct ec_curve *ec_p521(void) { static struct ec_curve curve = { 0 }; static unsigned char initialised = 0; if (!initialised) { - unsigned char p[] = { + static const unsigned char p[] = { 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, @@ -256,7 +254,7 @@ struct ec_curve *ec_p521(void) 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }; - unsigned char a[] = { + static const unsigned char a[] = { 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, @@ -267,7 +265,7 @@ struct ec_curve *ec_p521(void) 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc }; - unsigned char b[] = { + static const unsigned char b[] = { 0x00, 0x51, 0x95, 0x3e, 0xb9, 0x61, 0x8e, 0x1c, 0x9a, 0x1f, 0x92, 0x9a, 0x21, 0xa0, 0xb6, 0x85, 0x40, 0xee, 0xa2, 0xda, 0x72, 0x5b, 0x99, 0xb3, @@ -278,7 +276,7 @@ struct ec_curve *ec_p521(void) 0x34, 0xf1, 0xef, 0x45, 0x1f, 0xd4, 0x6b, 0x50, 0x3f, 0x00 }; - unsigned char n[] = { + static const unsigned char n[] = { 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, @@ -289,7 +287,7 @@ struct ec_curve *ec_p521(void) 0x47, 0xae, 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38, 0x64, 0x09 }; - unsigned char Gx[] = { + static const unsigned char Gx[] = { 0x00, 0xc6, 0x85, 0x8e, 0x06, 0xb7, 0x04, 0x04, 0xe9, 0xcd, 0x9e, 0x3e, 0xcb, 0x66, 0x23, 0x95, 0xb4, 0x42, 0x9c, 0x64, 0x81, 0x39, 0x05, 0x3f, @@ -300,7 +298,7 @@ struct ec_curve *ec_p521(void) 0x42, 0x9b, 0xf9, 0x7e, 0x7e, 0x31, 0xc2, 0xe5, 0xbd, 0x66 }; - unsigned char Gy[] = { + static const unsigned char Gy[] = { 0x01, 0x18, 0x39, 0x29, 0x6a, 0x78, 0x9a, 0x3b, 0xc0, 0x04, 0x5c, 0x8a, 0x5f, 0xb4, 0x2c, 0x7d, 0x1b, 0xd9, 0x98, 0xf5, 0x44, 0x49, 0x57, 0x9b, @@ -312,9 +310,8 @@ struct ec_curve *ec_p521(void) 0x66, 0x50 }; - if (!initialise_wcurve(&curve, 521, p, a, b, n, Gx, Gy)) { - return NULL; - } + initialise_wcurve(&curve, 521, p, a, b, n, Gx, Gy); + curve.textname = curve.name = "nistp521"; /* Now initialised, no need to do it again */ initialised = 1; @@ -323,41 +320,43 @@ struct ec_curve *ec_p521(void) return &curve; } -struct ec_curve *ec_curve25519(void) +static struct ec_curve *ec_curve25519(void) { static struct ec_curve curve = { 0 }; static unsigned char initialised = 0; if (!initialised) { - unsigned char p[] = { + static const unsigned char p[] = { 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed }; - unsigned char a[] = { + static const unsigned char a[] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x6d, 0x06 }; - unsigned char b[] = { + static const unsigned char b[] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 }; - unsigned char gx[32] = { + static const unsigned char gx[32] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x09 }; - if (!initialise_mcurve(&curve, 256, p, a, b, gx)) { - return NULL; - } + initialise_mcurve(&curve, 256, p, a, b, gx); + /* This curve doesn't need a name, because it's never used in + * any format that embeds the curve name */ + curve.name = NULL; + curve.textname = "Curve25519"; /* Now initialised, no need to do it again */ initialised = 1; @@ -366,97 +365,56 @@ struct ec_curve *ec_curve25519(void) return &curve; } -static struct ec_curve *ec_name_to_curve(const char *name, int len) { - if (len > 11 && !memcmp(name, "ecdsa-sha2-", 11)) { - name += 11; - len -= 11; - } else if (len > 10 && !memcmp(name, "ecdh-sha2-", 10)) { - name += 10; - len -= 10; - } - - if (len == 8 && !memcmp(name, "nistp", 5)) { - name += 5; - if (!memcmp(name, "256", 3)) { - return ec_p256(); - } else if (!memcmp(name, "384", 3)) { - return ec_p384(); - } else if (!memcmp(name, "521", 3)) { - return ec_p521(); - } - } - - if (len == 28 && !memcmp(name, "curve25519-sha256@libssh.org", 28)) { - return ec_curve25519(); - } - - return NULL; -} - -/* Type enumeration for specifying the curve name */ -enum ec_name_type { EC_TYPE_DSA, EC_TYPE_DH, EC_TYPE_CURVE }; - -static int ec_curve_to_name(enum ec_name_type type, const struct ec_curve *curve, - unsigned char *name, int len) { - if (curve->type == EC_WEIERSTRASS) { - int length, loc; - if (type == EC_TYPE_DSA) { - length = 19; - loc = 16; - } else if (type == EC_TYPE_DH) { - length = 18; - loc = 15; - } else { - length = 8; - loc = 5; - } - - /* Return length of string */ - if (name == NULL) return length; - - /* Not enough space for the name */ - if (len < length) return 0; - - /* Put the name in the buffer */ - switch (curve->fieldBits) { - case 256: - memcpy(name+loc, "256", 3); - break; - case 384: - memcpy(name+loc, "384", 3); - break; - case 521: - memcpy(name+loc, "521", 3); - break; - default: - return 0; - } - - if (type == EC_TYPE_DSA) { - memcpy(name, "ecdsa-sha2-nistp", 16); - } else if (type == EC_TYPE_DH) { - memcpy(name, "ecdh-sha2-nistp", 15); - } else { - memcpy(name, "nistp", 5); - } - - return length; - } else { - /* No DSA for curve25519 */ - if (type == EC_TYPE_DSA || type == EC_TYPE_CURVE) return 0; +static struct ec_curve *ec_ed25519(void) +{ + static struct ec_curve curve = { 0 }; + static unsigned char initialised = 0; - /* Return length of string */ - if (name == NULL) return 28; + if (!initialised) + { + static const unsigned char q[] = { + 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed + }; + static const unsigned char l[32] = { + 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x14, 0xde, 0xf9, 0xde, 0xa2, 0xf7, 0x9c, 0xd6, + 0x58, 0x12, 0x63, 0x1a, 0x5c, 0xf5, 0xd3, 0xed + }; + static const unsigned char d[32] = { + 0x52, 0x03, 0x6c, 0xee, 0x2b, 0x6f, 0xfe, 0x73, + 0x8c, 0xc7, 0x40, 0x79, 0x77, 0x79, 0xe8, 0x98, + 0x00, 0x70, 0x0a, 0x4d, 0x41, 0x41, 0xd8, 0xab, + 0x75, 0xeb, 0x4d, 0xca, 0x13, 0x59, 0x78, 0xa3 + }; + static const unsigned char Bx[32] = { + 0x21, 0x69, 0x36, 0xd3, 0xcd, 0x6e, 0x53, 0xfe, + 0xc0, 0xa4, 0xe2, 0x31, 0xfd, 0xd6, 0xdc, 0x5c, + 0x69, 0x2c, 0xc7, 0x60, 0x95, 0x25, 0xa7, 0xb2, + 0xc9, 0x56, 0x2d, 0x60, 0x8f, 0x25, 0xd5, 0x1a + }; + static const unsigned char By[32] = { + 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, + 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, + 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, + 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x58 + }; - /* Not enough space for the name */ - if (len < 28) return 0; + /* This curve doesn't need a name, because it's never used in + * any format that embeds the curve name */ + curve.name = NULL; - /* Unknown curve field */ - if (curve->fieldBits != 256) return 0; + initialise_ecurve(&curve, 256, q, l, d, Bx, By); + curve.textname = "Ed25519"; - memcpy(name, "curve25519-sha256@libssh.org", 28); - return 28; + /* Now initialised, no need to do it again */ + initialised = 1; } + + return &curve; } /* Return 1 if a is -3 % p, otherwise return 0 @@ -471,7 +429,6 @@ static int ec_aminus3(const struct ec_curve *curve) } _p = bignum_add_long(curve->w.a, 3); - if (!_p) return 0; ret = !bignum_cmp(curve->p, _p); freebn(_p); @@ -488,18 +445,11 @@ static Bignum ecf_add(const Bignum a, const Bignum b, Bignum a1, b1, ab, ret; a1 = bigmod(a, curve->p); - if (!a1) return NULL; b1 = bigmod(b, curve->p); - if (!b1) - { - freebn(a1); - return NULL; - } ab = bigadd(a1, b1); freebn(a1); freebn(b1); - if (!ab) return NULL; ret = bigmod(ab, curve->p); freebn(ab); @@ -518,16 +468,16 @@ static Bignum ecf_treble(const Bignum a, const struct ec_curve *curve) /* Double */ tmp = bignum_lshift(a, 1); - if (!tmp) return NULL; /* Add itself (i.e. treble) */ ret = bigadd(tmp, a); freebn(tmp); /* Normalise */ - while (ret != NULL && bignum_cmp(ret, curve->p) >= 0) + while (bignum_cmp(ret, curve->p) >= 0) { tmp = bigsub(ret, curve->p); + assert(tmp); freebn(ret); ret = tmp; } @@ -538,10 +488,10 @@ static Bignum ecf_treble(const Bignum a, const struct ec_curve *curve) static Bignum ecf_double(const Bignum a, const struct ec_curve *curve) { Bignum ret = bignum_lshift(a, 1); - if (!ret) return NULL; if (bignum_cmp(ret, curve->p) >= 0) { Bignum tmp = bigsub(ret, curve->p); + assert(tmp); freebn(ret); return tmp; } @@ -593,6 +543,25 @@ static int ec_point_verify(const struct ec_point *a) { if (a->infinity) { return 1; + } else if (a->curve->type == EC_EDWARDS) { + /* Check y^2 - x^2 - 1 - d * x^2 * y^2 == 0 */ + Bignum y2, x2, tmp, tmp2, tmp3; + int ret; + + y2 = ecf_square(a->y, a->curve); + x2 = ecf_square(a->x, a->curve); + tmp = modmul(a->curve->e.d, x2, a->curve->p); + tmp2 = modmul(tmp, y2, a->curve->p); + freebn(tmp); + tmp = modsub(y2, x2, a->curve->p); + freebn(y2); + freebn(x2); + tmp3 = modsub(tmp, tmp2, a->curve->p); + freebn(tmp); + freebn(tmp2); + ret = !bignum_cmp(tmp3, One); + freebn(tmp3); + return ret; } else if (a->curve->type == EC_WEIERSTRASS) { /* Verify y^2 = x^3 + ax + b */ int ret = 0; @@ -600,29 +569,21 @@ static int ec_point_verify(const struct ec_point *a) Bignum lhs = NULL, x3 = NULL, ax = NULL, x3ax = NULL, x3axm = NULL, x3axb = NULL, rhs = NULL; Bignum Three = bignum_from_long(3); - if (!Three) return 0; lhs = modmul(a->y, a->y, a->curve->p); - if (!lhs) goto error; /* This uses montgomery multiplication to optimise */ x3 = modpow(a->x, Three, a->curve->p); freebn(Three); - if (!x3) goto error; ax = modmul(a->curve->w.a, a->x, a->curve->p); - if (!ax) goto error; x3ax = bigadd(x3, ax); - if (!x3ax) goto error; freebn(x3); x3 = NULL; freebn(ax); ax = NULL; x3axm = bigmod(x3ax, a->curve->p); - if (!x3axm) goto error; freebn(x3ax); x3ax = NULL; x3axb = bigadd(x3axm, a->curve->w.b); - if (!x3axb) goto error; freebn(x3axm); x3axm = NULL; rhs = bigmod(x3axb, a->curve->p); - if (!rhs) goto error; freebn(x3axb); ret = bignum_cmp(lhs, rhs) ? 0 : 1; @@ -630,15 +591,6 @@ static int ec_point_verify(const struct ec_point *a) freebn(rhs); return ret; - - error: - if (x3) freebn(x3); - if (ax) freebn(ax); - if (x3ax) freebn(x3ax); - if (x3axm) freebn(x3axm); - if (x3axb) freebn(x3axb); - if (lhs) freebn(lhs); - return 0; } else { return 0; } @@ -676,9 +628,6 @@ static int ecp_normalise(struct ec_point *a) } Z2 = ecf_square(a->z, a->curve); - if (!Z2) { - return 0; - } Z2inv = modinv(Z2, a->curve->p); if (!Z2inv) { freebn(Z2); @@ -686,17 +635,9 @@ static int ecp_normalise(struct ec_point *a) } tx = modmul(a->x, Z2inv, a->curve->p); freebn(Z2inv); - if (!tx) { - freebn(Z2); - return 0; - } Z3 = modmul(Z2, a->z, a->curve->p); freebn(Z2); - if (!Z3) { - freebn(tx); - return 0; - } Z3inv = modinv(Z3, a->curve->p); freebn(Z3); if (!Z3inv) { @@ -705,10 +646,6 @@ static int ecp_normalise(struct ec_point *a) } ty = modmul(a->y, Z3inv, a->curve->p); freebn(Z3inv); - if (!ty) { - freebn(tx); - return 0; - } freebn(a->x); a->x = tx; @@ -736,15 +673,15 @@ static int ecp_normalise(struct ec_point *a) } tmp2 = modmul(a->x, tmp, a->curve->p); freebn(tmp); - if (!tmp2) { - return 0; - } freebn(a->z); a->z = NULL; freebn(a->x); a->x = tmp2; return 1; + } else if (a->curve->type == EC_EDWARDS) { + /* Always normalised */ + return 1; } else { return 0; } @@ -765,25 +702,13 @@ static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3) Bignum Y2, XY2, _2XY2; Y2 = ecf_square(a->y, a->curve); - if (!Y2) { - return NULL; - } XY2 = modmul(a->x, Y2, a->curve->p); freebn(Y2); - if (!XY2) { - return NULL; - } _2XY2 = ecf_double(XY2, a->curve); freebn(XY2); - if (!_2XY2) { - return NULL; - } S = ecf_double(_2XY2, a->curve); freebn(_2XY2); - if (!S) { - return NULL; - } } /* Faster calculation if a = -3 */ @@ -796,39 +721,17 @@ static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3) } else { Z2 = ecf_square(a->z, a->curve); } - if (!Z2) { - freebn(S); - return NULL; - } XpZ2 = ecf_add(a->x, Z2, a->curve); - if (!XpZ2) { - freebn(S); - freebn(Z2); - return NULL; - } XmZ2 = modsub(a->x, Z2, a->curve->p); freebn(Z2); - if (!XmZ2) { - freebn(S); - freebn(XpZ2); - return NULL; - } second = modmul(XpZ2, XmZ2, a->curve->p); freebn(XpZ2); freebn(XmZ2); - if (!second) { - freebn(S); - return NULL; - } M = ecf_treble(second, a->curve); freebn(second); - if (!M) { - freebn(S); - return NULL; - } } else { /* M = 3*X^2 + a*Z^4 */ Bignum _3X2, X2, aZ4; @@ -839,44 +742,18 @@ static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3) Bignum Z2, Z4; Z2 = ecf_square(a->z, a->curve); - if (!Z2) { - freebn(S); - return NULL; - } Z4 = ecf_square(Z2, a->curve); freebn(Z2); - if (!Z4) { - freebn(S); - return NULL; - } aZ4 = modmul(a->curve->w.a, Z4, a->curve->p); freebn(Z4); } - if (!aZ4) { - freebn(S); - return NULL; - } X2 = modmul(a->x, a->x, a->curve->p); - if (!X2) { - freebn(S); - freebn(aZ4); - return NULL; - } _3X2 = ecf_treble(X2, a->curve); freebn(X2); - if (!_3X2) { - freebn(S); - freebn(aZ4); - return NULL; - } M = ecf_add(_3X2, aZ4, a->curve); freebn(_3X2); freebn(aZ4); - if (!M) { - freebn(S); - return NULL; - } } /* X' = M^2 - 2*S */ @@ -884,28 +761,10 @@ static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3) Bignum M2, _2S; M2 = ecf_square(M, a->curve); - if (!M2) { - freebn(S); - freebn(M); - return NULL; - } - _2S = ecf_double(S, a->curve); - if (!_2S) { - freebn(M2); - freebn(S); - freebn(M); - return NULL; - } - outx = modsub(M2, _2S, a->curve->p); freebn(M2); freebn(_2S); - if (!outx) { - freebn(S); - freebn(M); - return NULL; - } } /* Y' = M*(S - X') - 8*Y^4 */ @@ -914,53 +773,19 @@ static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3) SX = modsub(S, outx, a->curve->p); freebn(S); - if (!SX) { - freebn(M); - freebn(outx); - return NULL; - } MSX = modmul(M, SX, a->curve->p); freebn(SX); freebn(M); - if (!MSX) { - freebn(outx); - return NULL; - } Y2 = ecf_square(a->y, a->curve); - if (!Y2) { - freebn(outx); - freebn(MSX); - return NULL; - } Y4 = ecf_square(Y2, a->curve); freebn(Y2); - if (!Y4) { - freebn(outx); - freebn(MSX); - return NULL; - } Eight = bignum_from_long(8); - if (!Eight) { - freebn(outx); - freebn(MSX); - freebn(Y4); - return NULL; - } _8Y4 = modmul(Eight, Y4, a->curve->p); freebn(Eight); freebn(Y4); - if (!_8Y4) { - freebn(outx); - freebn(MSX); - return NULL; - } outy = modsub(MSX, _8Y4, a->curve->p); freebn(MSX); freebn(_8Y4); - if (!outy) { - freebn(outx); - return NULL; - } } /* Z' = 2*Y*Z */ @@ -972,19 +797,9 @@ static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3) } else { YZ = modmul(a->y, a->z, a->curve->p); } - if (!YZ) { - freebn(outx); - freebn(outy); - return NULL; - } outz = ecf_double(YZ, a->curve); freebn(YZ); - if (!outz) { - freebn(outx); - freebn(outy); - return NULL; - } } return ec_point_new(a->curve, outx, outy, outz, 0); @@ -1004,81 +819,31 @@ static struct ec_point *ecp_doublem(const struct ec_point *a) Bignum tmp; tmp = ecf_add(a->x, z, a->curve); - if (!tmp) { - return NULL; - } xpz = ecf_square(tmp, a->curve); freebn(tmp); - if (!xpz) { - return NULL; - } tmp = modsub(a->x, z, a->curve->p); - if (!tmp) { - freebn(xpz); - return NULL; - } xmz = ecf_square(tmp, a->curve); freebn(tmp); - if (!xmz) { - freebn(xpz); - return NULL; - } } /* outx = (x + z)^2 * (x - z)^2 */ outx = modmul(xpz, xmz, a->curve->p); - if (!outx) { - freebn(xpz); - freebn(xmz); - return NULL; - } /* outz = 4xz * ((x - z)^2 + ((A + 2) / 4)*4xz) */ { Bignum _4xz, tmp, tmp2, tmp3; tmp = bignum_from_long(2); - if (!tmp) { - freebn(xpz); - freebn(outx); - freebn(xmz); - return NULL; - } tmp2 = ecf_add(a->curve->m.a, tmp, a->curve); freebn(tmp); - if (!tmp2) { - freebn(xpz); - freebn(outx); - freebn(xmz); - return NULL; - } _4xz = modsub(xpz, xmz, a->curve->p); freebn(xpz); - if (!_4xz) { - freebn(tmp2); - freebn(outx); - freebn(xmz); - return NULL; - } tmp = modmul(tmp2, _4xz, a->curve->p); freebn(tmp2); - if (!tmp) { - freebn(_4xz); - freebn(outx); - freebn(xmz); - return NULL; - } tmp2 = bignum_from_long(4); - if (!tmp2) { - freebn(tmp); - freebn(_4xz); - freebn(outx); - freebn(xmz); - return NULL; - } tmp3 = modinv(tmp2, a->curve->p); freebn(tmp2); if (!tmp3) { @@ -1091,33 +856,23 @@ static struct ec_point *ecp_doublem(const struct ec_point *a) tmp2 = modmul(tmp, tmp3, a->curve->p); freebn(tmp); freebn(tmp3); - if (!tmp2) { - freebn(_4xz); - freebn(outx); - freebn(xmz); - return NULL; - } tmp = ecf_add(xmz, tmp2, a->curve); freebn(xmz); freebn(tmp2); - if (!tmp) { - freebn(_4xz); - freebn(outx); - return NULL; - } outz = modmul(_4xz, tmp, a->curve->p); freebn(_4xz); freebn(tmp); - if (!outz) { - freebn(outx); - return NULL; - } } return ec_point_new(a->curve, outx, NULL, outz, 0); } +/* Forward declaration for Edwards curve doubling */ +static struct ec_point *ecp_add(const struct ec_point *a, + const struct ec_point *b, + const int aminus3); + static struct ec_point *ecp_double(const struct ec_point *a, const int aminus3) { if (a->infinity) @@ -1126,7 +881,11 @@ static struct ec_point *ecp_double(const struct ec_point *a, const int aminus3) return ec_point_new(a->curve, NULL, NULL, NULL, 1); } - if (a->curve->type == EC_WEIERSTRASS) + if (a->curve->type == EC_EDWARDS) + { + return ecp_add(a, a, aminus3); + } + else if (a->curve->type == EC_WEIERSTRASS) { return ecp_doublew(a, aminus3); } @@ -1148,36 +907,14 @@ static struct ec_point *ecp_addw(const struct ec_point *a, Bignum Z2, Z3; Z2 = ecf_square(b->z, a->curve); - if (!Z2) { - return NULL; - } U1 = modmul(a->x, Z2, a->curve->p); - if (!U1) { - freebn(Z2); - return NULL; - } Z3 = modmul(Z2, b->z, a->curve->p); freebn(Z2); - if (!Z3) { - freebn(U1); - return NULL; - } S1 = modmul(a->y, Z3, a->curve->p); freebn(Z3); - if (!S1) { - freebn(U1); - return NULL; - } } else { U1 = copybn(a->x); - if (!U1) { - return NULL; - } S1 = copybn(a->y); - if (!S1) { - freebn(U1); - return NULL; - } } /* U2 = X2*Z1^2 */ @@ -1186,48 +923,14 @@ static struct ec_point *ecp_addw(const struct ec_point *a, Bignum Z2, Z3; Z2 = ecf_square(a->z, b->curve); - if (!Z2) { - freebn(U1); - freebn(S1); - return NULL; - } U2 = modmul(b->x, Z2, b->curve->p); - if (!U2) { - freebn(U1); - freebn(S1); - freebn(Z2); - return NULL; - } Z3 = modmul(Z2, a->z, b->curve->p); freebn(Z2); - if (!Z3) { - freebn(U1); - freebn(S1); - freebn(U2); - return NULL; - } S2 = modmul(b->y, Z3, b->curve->p); freebn(Z3); - if (!S2) { - freebn(U1); - freebn(S1); - freebn(U2); - return NULL; - } } else { U2 = copybn(b->x); - if (!U2) { - freebn(U1); - freebn(S1); - return NULL; - } S2 = copybn(b->y); - if (!S2) { - freebn(U1); - freebn(S1); - freebn(U2); - return NULL; - } } /* Check if multiplying by self */ @@ -1256,94 +959,27 @@ static struct ec_point *ecp_addw(const struct ec_point *a, /* H = U2 - U1 */ H = modsub(U2, U1, a->curve->p); freebn(U2); - if (!H) { - freebn(U1); - freebn(S1); - freebn(S2); - return NULL; - } /* R = S2 - S1 */ R = modsub(S2, S1, a->curve->p); freebn(S2); - if (!R) { - freebn(H); - freebn(S1); - freebn(U1); - return NULL; - } /* X3 = R^2 - H^3 - 2*U1*H^2 */ { Bignum R2, H2, _2UH2, first; H2 = ecf_square(H, a->curve); - if (!H2) { - freebn(U1); - freebn(S1); - freebn(H); - freebn(R); - return NULL; - } UH2 = modmul(U1, H2, a->curve->p); freebn(U1); - if (!UH2) { - freebn(H2); - freebn(S1); - freebn(H); - freebn(R); - return NULL; - } H3 = modmul(H2, H, a->curve->p); freebn(H2); - if (!H3) { - freebn(UH2); - freebn(S1); - freebn(H); - freebn(R); - return NULL; - } R2 = ecf_square(R, a->curve); - if (!R2) { - freebn(H3); - freebn(UH2); - freebn(S1); - freebn(H); - freebn(R); - return NULL; - } _2UH2 = ecf_double(UH2, a->curve); - if (!_2UH2) { - freebn(R2); - freebn(H3); - freebn(UH2); - freebn(S1); - freebn(H); - freebn(R); - return NULL; - } first = modsub(R2, H3, a->curve->p); freebn(R2); - if (!first) { - freebn(H3); - freebn(_2UH2); - freebn(UH2); - freebn(S1); - freebn(H); - freebn(R); - return NULL; - } outx = modsub(first, _2UH2, a->curve->p); freebn(first); freebn(_2UH2); - if (!outx) { - freebn(H3); - freebn(UH2); - freebn(S1); - freebn(H); - freebn(R); - return NULL; - } } /* Y3 = R*(U1*H^2 - X3) - S1*H^3 */ @@ -1352,42 +988,16 @@ static struct ec_point *ecp_addw(const struct ec_point *a, UH2mX = modsub(UH2, outx, a->curve->p); freebn(UH2); - if (!UH2mX) { - freebn(outx); - freebn(H3); - freebn(S1); - freebn(H); - freebn(R); - return NULL; - } RUH2mX = modmul(R, UH2mX, a->curve->p); freebn(UH2mX); freebn(R); - if (!RUH2mX) { - freebn(outx); - freebn(H3); - freebn(S1); - freebn(H); - return NULL; - } SH3 = modmul(S1, H3, a->curve->p); freebn(S1); freebn(H3); - if (!SH3) { - freebn(RUH2mX); - freebn(outx); - freebn(H); - return NULL; - } outy = modsub(RUH2mX, SH3, a->curve->p); freebn(RUH2mX); freebn(SH3); - if (!outy) { - freebn(outx); - freebn(H); - return NULL; - } } /* Z3 = H*Z1*Z2 */ @@ -1395,36 +1005,15 @@ static struct ec_point *ecp_addw(const struct ec_point *a, Bignum ZZ; ZZ = modmul(a->z, b->z, a->curve->p); - if (!ZZ) { - freebn(outx); - freebn(outy); - freebn(H); - return NULL; - } outz = modmul(H, ZZ, a->curve->p); freebn(H); freebn(ZZ); - if (!outz) { - freebn(outx); - freebn(outy); - return NULL; - } } else if (a->z) { outz = modmul(H, a->z, a->curve->p); freebn(H); - if (!outz) { - freebn(outx); - freebn(outy); - return NULL; - } } else if (b->z) { outz = modmul(H, b->z, a->curve->p); freebn(H); - if (!outz) { - freebn(outx); - freebn(outy); - return NULL; - } } else { outz = H; } @@ -1456,77 +1045,97 @@ static struct ec_point *ecp_addm(const struct ec_point *a, /* (Xa + Za) * (Xb - Zb) */ tmp = ecf_add(a->x, az, a->curve); - if (!tmp) { - return NULL; - } tmp2 = modsub(b->x, bz, a->curve->p); - if (!tmp2) { - freebn(tmp); - return NULL; - } tmp3 = modmul(tmp, tmp2, a->curve->p); freebn(tmp); freebn(tmp2); - if (!tmp3) { - return NULL; - } /* (Xa - Za) * (Xb + Zb) */ tmp = modsub(a->x, az, a->curve->p); - if (!tmp) { - freebn(tmp3); - return NULL; - } tmp2 = ecf_add(b->x, bz, a->curve); - if (!tmp2) { - freebn(tmp); - freebn(tmp3); - return NULL; - } tmp4 = modmul(tmp, tmp2, a->curve->p); freebn(tmp); freebn(tmp2); - if (!tmp4) { - freebn(tmp3); - return NULL; - } tmp = ecf_add(tmp3, tmp4, a->curve); - if (!tmp) { - freebn(tmp3); - freebn(tmp4); - return NULL; - } outx = ecf_square(tmp, a->curve); freebn(tmp); - if (!outx) { - freebn(tmp3); - freebn(tmp4); - return NULL; - } tmp = modsub(tmp3, tmp4, a->curve->p); freebn(tmp3); freebn(tmp4); - if (!tmp) { - freebn(outx); - return NULL; - } tmp2 = ecf_square(tmp, a->curve); freebn(tmp); - if (!tmp2) { - freebn(outx); + outz = modmul(base->x, tmp2, a->curve->p); + freebn(tmp2); + } + + return ec_point_new(a->curve, outx, NULL, outz, 0); +} + +static struct ec_point *ecp_adde(const struct ec_point *a, + const struct ec_point *b) +{ + Bignum outx, outy, dmul; + + /* outx = (a->x * b->y + b->x * a->y) / + * (1 + a->curve->e.d * a->x * b->x * a->y * b->y) */ + { + Bignum tmp, tmp2, tmp3, tmp4; + + tmp = modmul(a->x, b->y, a->curve->p); + tmp2 = modmul(b->x, a->y, a->curve->p); + tmp3 = ecf_add(tmp, tmp2, a->curve); + + tmp4 = modmul(tmp, tmp2, a->curve->p); + freebn(tmp); + freebn(tmp2); + dmul = modmul(a->curve->e.d, tmp4, a->curve->p); + freebn(tmp4); + + tmp = ecf_add(One, dmul, a->curve); + tmp2 = modinv(tmp, a->curve->p); + freebn(tmp); + if (!tmp2) + { + freebn(tmp3); + freebn(dmul); return NULL; } - outz = modmul(base->x, tmp2, a->curve->p); + + outx = modmul(tmp3, tmp2, a->curve->p); + freebn(tmp3); freebn(tmp2); - if (!outz) { + } + + /* outy = (a->y * b->y + a->x * b->x) / + * (1 - a->curve->e.d * a->x * b->x * a->y * b->y) */ + { + Bignum tmp, tmp2, tmp3, tmp4; + + tmp = modsub(One, dmul, a->curve->p); + freebn(dmul); + + tmp2 = modinv(tmp, a->curve->p); + freebn(tmp); + if (!tmp2) + { freebn(outx); return NULL; } + + tmp = modmul(a->y, b->y, a->curve->p); + tmp3 = modmul(a->x, b->x, a->curve->p); + tmp4 = ecf_add(tmp, tmp3, a->curve); + freebn(tmp); + freebn(tmp3); + + outy = modmul(tmp4, tmp2, a->curve->p); + freebn(tmp4); + freebn(tmp2); } - return ec_point_new(a->curve, outx, NULL, outz, 0); + return ec_point_new(a->curve, outx, outy, NULL, 0); } static struct ec_point *ecp_add(const struct ec_point *a, @@ -1541,6 +1150,11 @@ static struct ec_point *ecp_add(const struct ec_point *a, if (a->infinity) return ec_point_copy(b); if (b->infinity) return ec_point_copy(a); + if (a->curve->type == EC_EDWARDS) + { + return ecp_adde(a, b); + } + if (a->curve->type == EC_WEIERSTRASS) { return ecp_addw(a, b, aminus3); @@ -1558,7 +1172,7 @@ static struct ec_point *ecp_mul_(const struct ec_point *a, const Bignum b, int a ret = ec_point_new(a->curve, NULL, NULL, NULL, 1); bits = bignum_bitcount(b); - for (i = 0; ret != NULL && A != NULL && i < bits; ++i) + for (i = 0; i < bits; ++i) { if (bignum_bit(b, i)) { @@ -1574,13 +1188,7 @@ static struct ec_point *ecp_mul_(const struct ec_point *a, const Bignum b, int a } } - if (!A) { - ec_point_free(ret); - ret = NULL; - } else { - ec_point_free(A); - } - + ec_point_free(A); return ret; } @@ -1596,6 +1204,31 @@ static struct ec_point *ecp_mulw(const struct ec_point *a, const Bignum b) return ret; } +static struct ec_point *ecp_mule(const struct ec_point *a, const Bignum b) +{ + int i; + struct ec_point *ret; + + ret = ec_point_new(a->curve, NULL, NULL, NULL, 1); + + for (i = bignum_bitcount(b); i >= 0 && ret; --i) + { + { + struct ec_point *tmp = ecp_double(ret, 0); + ec_point_free(ret); + ret = tmp; + } + if (ret && bignum_bit(b, i)) + { + struct ec_point *tmp = ecp_add(ret, a, 0); + ec_point_free(ret); + ret = tmp; + } + } + + return ret; +} + static struct ec_point *ecp_mulm(const struct ec_point *p, const Bignum n) { struct ec_point *P1, *P2; @@ -1603,18 +1236,11 @@ static struct ec_point *ecp_mulm(const struct ec_point *p, const Bignum n) /* P1 <- P and P2 <- [2]P */ P2 = ecp_double(p, 0); - if (!P2) { - return NULL; - } P1 = ec_point_copy(p); - if (!P1) { - ec_point_free(P2); - return NULL; - } /* for i = bits − 2 down to 0 */ bits = bignum_bitcount(n); - for (i = bits - 2; P1 != NULL && P2 != NULL && i >= 0; --i) + for (i = bits - 2; i >= 0; --i) { if (!bignum_bit(n, i)) { @@ -1642,12 +1268,7 @@ static struct ec_point *ecp_mulm(const struct ec_point *p, const Bignum n) } } - if (!P2) { - if (P1) ec_point_free(P1); - P1 = NULL; - } else { - ec_point_free(P2); - } + ec_point_free(P2); if (!ecp_normalise(P1)) { ec_point_free(P1); @@ -1662,6 +1283,8 @@ struct ec_point *ecp_mul(const struct ec_point *a, const Bignum b) { if (a->curve->type == EC_WEIERSTRASS) { return ecp_mulw(a, b); + } else if (a->curve->type == EC_EDWARDS) { + return ecp_mule(a, b); } else { return ecp_mulm(a, b); } @@ -1699,6 +1322,83 @@ static struct ec_point *ecp_summul(const Bignum a, const Bignum b, return ret; } +static Bignum *ecp_edx(const struct ec_curve *curve, const Bignum y) +{ + /* Get the x value on the given Edwards curve for a given y */ + Bignum x, xx; + + /* xx = (y^2 - 1) / (d * y^2 + 1) */ + { + Bignum tmp, tmp2, tmp3; + + tmp = ecf_square(y, curve); + tmp2 = modmul(curve->e.d, tmp, curve->p); + tmp3 = ecf_add(tmp2, One, curve); + freebn(tmp2); + tmp2 = modinv(tmp3, curve->p); + freebn(tmp3); + if (!tmp2) { + freebn(tmp); + return NULL; + } + + tmp3 = modsub(tmp, One, curve->p); + freebn(tmp); + xx = modmul(tmp3, tmp2, curve->p); + freebn(tmp3); + freebn(tmp2); + } + + /* x = xx^((p + 3) / 8) */ + { + Bignum tmp, tmp2; + + tmp = bignum_add_long(curve->p, 3); + tmp2 = bignum_rshift(tmp, 3); + freebn(tmp); + x = modpow(xx, tmp2, curve->p); + freebn(tmp2); + } + + /* if x^2 - xx != 0 then x = x*(2^((p - 1) / 4)) */ + { + Bignum tmp, tmp2; + + tmp = ecf_square(x, curve); + tmp2 = modsub(tmp, xx, curve->p); + freebn(tmp); + freebn(xx); + if (bignum_cmp(tmp2, Zero)) { + Bignum tmp3; + + freebn(tmp2); + + tmp = modsub(curve->p, One, curve->p); + tmp2 = bignum_rshift(tmp, 2); + freebn(tmp); + tmp = bignum_from_long(2); + tmp3 = modpow(tmp, tmp2, curve->p); + freebn(tmp); + freebn(tmp2); + + tmp = modmul(x, tmp3, curve->p); + freebn(x); + freebn(tmp3); + x = tmp; + } else { + freebn(tmp2); + } + } + + /* if x % 2 != 0 then x = p - x */ + if (bignum_bit(x, 0)) { + Bignum tmp = modsub(curve->p, x, curve->p); + freebn(x); + x = tmp; + } + + return x; +} /* ---------------------------------------------------------------------- * Public point from private @@ -1708,6 +1408,37 @@ struct ec_point *ec_public(const Bignum privateKey, const struct ec_curve *curve { if (curve->type == EC_WEIERSTRASS) { return ecp_mul(&curve->w.G, privateKey); + } else if (curve->type == EC_EDWARDS) { + /* hash = H(sk) (where hash creates 2 * fieldBits) + * b = fieldBits + * a = 2^(b-2) + SUM(2^i * h_i) for i = 2 -> b-2 + * publicKey = aB */ + struct ec_point *ret; + unsigned char hash[512/8]; + Bignum a; + int i, keylen; + SHA512_State s; + SHA512_Init(&s); + + keylen = curve->fieldBits / 8; + for (i = 0; i < keylen; ++i) { + unsigned char b = bignum_byte(privateKey, i); + SHA512_Bytes(&s, &b, 1); + } + SHA512_Final(&s, hash); + + /* The second part is simply turning the hash into a Bignum, + * however the 2^(b-2) bit *must* be set, and the bottom 3 + * bits *must* not be */ + hash[0] &= 0xf8; /* Unset bottom 3 bits (if set) */ + hash[31] &= 0x7f; /* Unset above (b-2) */ + hash[31] |= 0x40; /* Set 2^(b-2) */ + /* Chop off the top part and convert to int */ + a = bignum_from_bytes_le(hash, 32); + + ret = ecp_mul(&curve->e.B, a); + freebn(a); + return ret; } else { return NULL; } @@ -1738,7 +1469,6 @@ static int _ecdsa_verify(const struct ec_point *publicKey, /* z = left most bitlen(curve->n) of data */ z = bignum_from_bytes(data, dataLen); - if (!z) return 0; n_bits = bignum_bitcount(publicKey->curve->w.n); z_bits = bignum_bitcount(z); if (z_bits > n_bits) @@ -1746,7 +1476,6 @@ static int _ecdsa_verify(const struct ec_point *publicKey, Bignum tmp = bignum_rshift(z, z_bits - n_bits); freebn(z); z = tmp; - if (!z) return 0; } /* Ensure z in range of n */ @@ -1754,7 +1483,6 @@ static int _ecdsa_verify(const struct ec_point *publicKey, Bignum tmp = bigmod(z, publicKey->curve->w.n); freebn(z); z = tmp; - if (!z) return 0; } /* Calculate signature */ @@ -1768,18 +1496,8 @@ static int _ecdsa_verify(const struct ec_point *publicKey, return 0; } u1 = modmul(z, w, publicKey->curve->w.n); - if (!u1) { - freebn(z); - freebn(w); - return 0; - } u2 = modmul(r, w, publicKey->curve->w.n); freebn(w); - if (!u2) { - freebn(z); - freebn(u1); - return 0; - } tmp = ecp_summul(u1, u2, publicKey); freebn(u1); @@ -1791,10 +1509,6 @@ static int _ecdsa_verify(const struct ec_point *publicKey, x = bigmod(tmp->x, publicKey->curve->w.n); ec_point_free(tmp); - if (!x) { - freebn(z); - return 0; - } valid = (bignum_cmp(r, x) == 0) ? 1 : 0; freebn(x); @@ -1823,7 +1537,6 @@ static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve, /* z = left most bitlen(curve->n) of data */ z = bignum_from_bytes(data, dataLen); - if (!z) return; n_bits = bignum_bitcount(curve->w.n); z_bits = bignum_bitcount(z); if (z_bits > n_bits) @@ -1832,7 +1545,6 @@ static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve, tmp = bignum_rshift(z, z_bits - n_bits); freebn(z); z = tmp; - if (!z) return; } /* Generate k between 1 and curve->n, using the same deterministic @@ -1840,7 +1552,6 @@ static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve, SHA_Simple(data, dataLen, digest); k = dss_gen_k("ECDSA deterministic k generator", curve->w.n, privateKey, digest, sizeof(digest)); - if (!k) return; kG = ecp_mul(&curve->w.G, k); if (!kG) { @@ -1852,45 +1563,18 @@ static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve, /* r = kG.x mod n */ *r = bigmod(kG->x, curve->w.n); ec_point_free(kG); - if (!*r) { - freebn(z); - freebn(k); - return; - } /* s = (z + r * priv)/k mod n */ { Bignum rPriv, zMod, first, firstMod, kInv; rPriv = modmul(*r, privateKey, curve->w.n); - if (!rPriv) { - freebn(*r); - freebn(z); - freebn(k); - return; - } zMod = bigmod(z, curve->w.n); freebn(z); - if (!zMod) { - freebn(rPriv); - freebn(*r); - freebn(k); - return; - } first = bigadd(rPriv, zMod); freebn(rPriv); freebn(zMod); - if (!first) { - freebn(*r); - freebn(k); - return; - } firstMod = bigmod(first, curve->w.n); freebn(first); - if (!firstMod) { - freebn(*r); - freebn(k); - return; - } kInv = modinv(k, curve->w.n); freebn(k); if (!kInv) { @@ -1901,10 +1585,6 @@ static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve, *s = modmul(firstMod, kInv, curve->w.n); freebn(firstMod); freebn(kInv); - if (!*s) { - freebn(*r); - return; - } } } @@ -1943,8 +1623,64 @@ static Bignum getmp(const char **data, int *datalen) return bignum_from_bytes((unsigned char *)p, length); } +static Bignum getmp_le(const char **data, int *datalen) +{ + const char *p; + int length; + + getstring(data, datalen, &p, &length); + if (!p) + return NULL; + return bignum_from_bytes_le((const unsigned char *)p, length); +} + +static int decodepoint_ed(const char *p, int length, struct ec_point *point) +{ + /* Got some conversion to do, first read in the y co-ord */ + int negative; + + point->y = bignum_from_bytes_le((const unsigned char*)p, length); + if ((unsigned)bignum_bitcount(point->y) > point->curve->fieldBits) { + freebn(point->y); + point->y = NULL; + return 0; + } + /* Read x bit and then reset it */ + negative = bignum_bit(point->y, point->curve->fieldBits - 1); + bignum_set_bit(point->y, point->curve->fieldBits - 1, 0); + bn_restore_invariant(point->y); + + /* Get the x from the y */ + point->x = ecp_edx(point->curve, point->y); + if (!point->x) { + freebn(point->y); + point->y = NULL; + return 0; + } + if (negative) { + Bignum tmp = modsub(point->curve->p, point->x, point->curve->p); + freebn(point->x); + point->x = tmp; + } + + /* Verify the point is on the curve */ + if (!ec_point_verify(point)) { + freebn(point->x); + point->x = NULL; + freebn(point->y); + point->y = NULL; + return 0; + } + + return 1; +} + static int decodepoint(const char *p, int length, struct ec_point *point) { + if (point->curve->type == EC_EDWARDS) { + return decodepoint_ed(p, length, point); + } + if (length < 1 || p[0] != 0x04) /* Only support uncompressed point */ return 0; /* Skip compression flag */ @@ -1958,15 +1694,9 @@ static int decodepoint(const char *p, int length, struct ec_point *point) return 0; } length = length / 2; - point->x = bignum_from_bytes((unsigned char *)p, length); - if (!point->x) return 0; + point->x = bignum_from_bytes((const unsigned char *)p, length); p += length; - point->y = bignum_from_bytes((unsigned char *)p, length); - if (!point->y) { - freebn(point->x); - point->x = NULL; - return 0; - } + point->y = bignum_from_bytes((const unsigned char *)p, length); point->z = NULL; /* Verify the point is on the curve */ @@ -1995,6 +1725,15 @@ static int getmppoint(const char **data, int *datalen, struct ec_point *point) * Exposed ECDSA interface */ +struct ecsign_extra { + struct ec_curve *(*curve)(void); + const struct ssh_hash *hash; + + /* These fields are used by the OpenSSH PEM format importer/exporter */ + const unsigned char *oid; + int oidlen; +}; + static void ecdsa_freekey(void *key) { struct ec_key *ec = (struct ec_key *) key; @@ -2011,8 +1750,11 @@ static void ecdsa_freekey(void *key) sfree(ec); } -static void *ecdsa_newkey(const char *data, int len) +static void *ecdsa_newkey(const struct ssh_signkey *self, + const char *data, int len) { + const struct ecsign_extra *extra = + (const struct ecsign_extra *)self->extra; const char *p; int slen; struct ec_key *ec; @@ -2023,31 +1765,29 @@ static void *ecdsa_newkey(const char *data, int len) if (!p) { return NULL; } - curve = ec_name_to_curve(p, slen); - if (!curve) return NULL; - - if (curve->type != EC_WEIERSTRASS) { - return NULL; - } + curve = extra->curve(); + assert(curve->type == EC_WEIERSTRASS || curve->type == EC_EDWARDS); /* Curve name is duplicated for Weierstrass form */ if (curve->type == EC_WEIERSTRASS) { getstring(&data, &len, &p, &slen); - if (curve != ec_name_to_curve(p, slen)) return NULL; + if (!p) return NULL; + if (!match_ssh_id(slen, p, curve->name)) return NULL; } ec = snew(struct ec_key); + ec->signalg = self; ec->publicKey.curve = curve; ec->publicKey.infinity = 0; ec->publicKey.x = NULL; ec->publicKey.y = NULL; ec->publicKey.z = NULL; + ec->privateKey = NULL; if (!getmppoint(&data, &len, &ec->publicKey)) { ecdsa_freekey(ec); return NULL; } - ec->privateKey = NULL; if (!ec->publicKey.x || !ec->publicKey.y || bignum_cmp(ec->publicKey.x, curve->p) >= 0 || @@ -2069,17 +1809,17 @@ static char *ecdsa_fmtkey(void *key) if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve) return NULL; - pos = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0); - if (pos == 0) return NULL; - len = 4 + 2 + 1; /* 2 x "0x", punctuation, \0 */ - len += pos; /* Curve name */ + if (ec->publicKey.curve->name) + len += strlen(ec->publicKey.curve->name); /* Curve name */ len += 4 * (bignum_bitcount(ec->publicKey.x) + 15) / 16; len += 4 * (bignum_bitcount(ec->publicKey.y) + 15) / 16; p = snewn(len, char); - pos = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, (unsigned char*)p, pos); - pos += sprintf(p + pos, ",0x"); + pos = 0; + if (ec->publicKey.curve->name) + pos += sprintf(p + pos, "%s,", ec->publicKey.curve->name); + pos += sprintf(p + pos, "0x"); nibbles = (3 + bignum_bitcount(ec->publicKey.x)) / 4; if (nibbles < 1) nibbles = 1; @@ -2106,11 +1846,37 @@ static unsigned char *ecdsa_public_blob(void *key, int *len) int i; unsigned char *blob, *p; - if (ec->publicKey.curve->type == EC_WEIERSTRASS) { - fullnamelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0); - if (fullnamelen == 0) return NULL; - namelen = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0); - if (namelen == 0) return NULL; + fullnamelen = strlen(ec->signalg->name); + + if (ec->publicKey.curve->type == EC_EDWARDS) { + /* Edwards compressed form "ssh-ed25519" point y[:-1] + x[0:1] */ + + pointlen = ec->publicKey.curve->fieldBits / 8; + + /* Can't handle this in our loop */ + if (pointlen < 2) return NULL; + + bloblen = 4 + fullnamelen + 4 + pointlen; + blob = snewn(bloblen, unsigned char); + + p = blob; + PUT_32BIT(p, fullnamelen); + p += 4; + memcpy(p, ec->signalg->name, fullnamelen); + p += fullnamelen; + PUT_32BIT(p, pointlen); + p += 4; + + /* Unset last bit of y and set first bit of x in its place */ + for (i = 0; i < pointlen - 1; ++i) { + *p++ = bignum_byte(ec->publicKey.y, i); + } + /* Unset last bit of y and set first bit of x in its place */ + *p = bignum_byte(ec->publicKey.y, i) & 0x7f; + *p++ |= bignum_bit(ec->publicKey.x, 0) << 7; + } else if (ec->publicKey.curve->type == EC_WEIERSTRASS) { + assert(ec->publicKey.curve->name); + namelen = strlen(ec->publicKey.curve->name); pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8; @@ -2123,10 +1889,12 @@ static unsigned char *ecdsa_public_blob(void *key, int *len) p = blob; PUT_32BIT(p, fullnamelen); p += 4; - p += ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, p, fullnamelen); + memcpy(p, ec->signalg->name, fullnamelen); + p += fullnamelen; PUT_32BIT(p, namelen); p += 4; - p += ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, p, namelen); + memcpy(p, ec->publicKey.curve->name, namelen); + p += namelen; PUT_32BIT(p, (2 * pointlen) + 1); p += 4; *p++ = 0x04; @@ -2155,7 +1923,13 @@ static unsigned char *ecdsa_private_blob(void *key, int *len) if (!ec->privateKey) return NULL; - keylen = (bignum_bitcount(ec->privateKey) + 8) / 8; + if (ec->publicKey.curve->type == EC_EDWARDS) { + /* Unsigned */ + keylen = (bignum_bitcount(ec->privateKey) + 7) / 8; + } else { + /* Signed */ + keylen = (bignum_bitcount(ec->privateKey) + 8) / 8; + } /* * mpint privateKey. Total 4 + keylen. @@ -2166,27 +1940,44 @@ static unsigned char *ecdsa_private_blob(void *key, int *len) p = blob; PUT_32BIT(p, keylen); p += 4; - for (i = keylen; i--;) - *p++ = bignum_byte(ec->privateKey, i); + if (ec->publicKey.curve->type == EC_EDWARDS) { + /* Little endian */ + for (i = 0; i < keylen; ++i) + *p++ = bignum_byte(ec->privateKey, i); + } else { + for (i = keylen; i--;) + *p++ = bignum_byte(ec->privateKey, i); + } assert(p == blob + bloblen); *len = bloblen; return blob; } -static void *ecdsa_createkey(const unsigned char *pub_blob, int pub_len, +static void *ecdsa_createkey(const struct ssh_signkey *self, + const unsigned char *pub_blob, int pub_len, const unsigned char *priv_blob, int priv_len) { struct ec_key *ec; struct ec_point *publicKey; const char *pb = (const char *) priv_blob; - ec = (struct ec_key*)ecdsa_newkey((const char *) pub_blob, pub_len); + ec = (struct ec_key*)ecdsa_newkey(self, (const char *) pub_blob, pub_len); if (!ec) { return NULL; } - ec->privateKey = getmp(&pb, &priv_len); + if (ec->publicKey.curve->type != EC_WEIERSTRASS + && ec->publicKey.curve->type != EC_EDWARDS) { + ecdsa_freekey(ec); + return NULL; + } + + if (ec->publicKey.curve->type == EC_EDWARDS) { + ec->privateKey = getmp_le(&pb, &priv_len); + } else { + ec->privateKey = getmp(&pb, &priv_len); + } if (!ec->privateKey) { ecdsa_freekey(ec); return NULL; @@ -2207,8 +1998,124 @@ static void *ecdsa_createkey(const unsigned char *pub_blob, int pub_len, return ec; } -static void *ecdsa_openssh_createkey(const unsigned char **blob, int *len) +static void *ed25519_openssh_createkey(const struct ssh_signkey *self, + const unsigned char **blob, int *len) +{ + struct ec_key *ec; + struct ec_point *publicKey; + const char *p, *q; + int plen, qlen; + + getstring((const char**)blob, len, &p, &plen); + if (!p) + { + return NULL; + } + + ec = snew(struct ec_key); + + ec->signalg = self; + ec->publicKey.curve = ec_ed25519(); + ec->publicKey.infinity = 0; + ec->privateKey = NULL; + ec->publicKey.x = NULL; + ec->publicKey.z = NULL; + ec->publicKey.y = NULL; + + if (!decodepoint_ed(p, plen, &ec->publicKey)) + { + ecdsa_freekey(ec); + return NULL; + } + + getstring((const char**)blob, len, &q, &qlen); + if (!q || qlen != 64) { + ecdsa_freekey(ec); + return NULL; + } + + ec->privateKey = bignum_from_bytes_le((const unsigned char *)q, 32); + + /* Check that private key generates public key */ + publicKey = ec_public(ec->privateKey, ec->publicKey.curve); + + if (!publicKey || + bignum_cmp(publicKey->x, ec->publicKey.x) || + bignum_cmp(publicKey->y, ec->publicKey.y)) + { + ecdsa_freekey(ec); + ec = NULL; + } + ec_point_free(publicKey); + + /* The OpenSSH format for ed25519 private keys also for some + * reason encodes an extra copy of the public key in the second + * half of the secret-key string. Check that that's present and + * correct as well, otherwise the key we think we've imported + * won't behave identically to the way OpenSSH would have treated + * it. */ + if (plen != 32 || 0 != memcmp(q + 32, p, 32)) { + ecdsa_freekey(ec); + return NULL; + } + + return ec; +} + +static int ed25519_openssh_fmtkey(void *key, unsigned char *blob, int len) +{ + struct ec_key *ec = (struct ec_key *) key; + + int pointlen; + int keylen; + int bloblen; + int i; + + if (ec->publicKey.curve->type != EC_EDWARDS) { + return 0; + } + + pointlen = (bignum_bitcount(ec->publicKey.y) + 7) / 8; + keylen = (bignum_bitcount(ec->privateKey) + 7) / 8; + bloblen = 4 + pointlen + 4 + keylen + pointlen; + + if (bloblen > len) + return bloblen; + + /* Encode the public point */ + PUT_32BIT(blob, pointlen); + blob += 4; + + for (i = 0; i < pointlen - 1; ++i) { + *blob++ = bignum_byte(ec->publicKey.y, i); + } + /* Unset last bit of y and set first bit of x in its place */ + *blob = bignum_byte(ec->publicKey.y, i) & 0x7f; + *blob++ |= bignum_bit(ec->publicKey.x, 0) << 7; + + PUT_32BIT(blob, keylen + pointlen); + blob += 4; + for (i = 0; i < keylen; ++i) { + *blob++ = bignum_byte(ec->privateKey, i); + } + /* Now encode an extra copy of the public point as the second half + * of the private key string, as the OpenSSH format for some + * reason requires */ + for (i = 0; i < pointlen - 1; ++i) { + *blob++ = bignum_byte(ec->publicKey.y, i); + } + /* Unset last bit of y and set first bit of x in its place */ + *blob = bignum_byte(ec->publicKey.y, i) & 0x7f; + *blob++ |= bignum_bit(ec->publicKey.x, 0) << 7; + + return bloblen; +} + +static void *ecdsa_openssh_createkey(const struct ssh_signkey *self, + const unsigned char **blob, int *len) { + const struct ecsign_extra *extra = + (const struct ecsign_extra *)self->extra; const char **b = (const char **) blob; const char *p; int slen; @@ -2221,11 +2128,12 @@ static void *ecdsa_openssh_createkey(const unsigned char **blob, int *len) if (!p) { return NULL; } - curve = ec_name_to_curve(p, slen); - if (!curve) return NULL; + curve = extra->curve(); + assert(curve->type == EC_WEIERSTRASS); ec = snew(struct ec_key); + ec->signalg = self; ec->publicKey.curve = curve; ec->publicKey.infinity = 0; ec->publicKey.x = NULL; @@ -2283,13 +2191,12 @@ static int ecdsa_openssh_fmtkey(void *key, unsigned char *blob, int len) int bloblen; int i; - if (ec->publicKey.curve->type != EC_WEIERSTRASS) { return 0; } pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8; - namelen = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0); + namelen = strlen(ec->publicKey.curve->name); bloblen = 4 + namelen /* nistpXXX */ + 4 + 1 + (pointlen * 2) /* 0x04 pX pY */ @@ -2302,8 +2209,8 @@ static int ecdsa_openssh_fmtkey(void *key, unsigned char *blob, int len) PUT_32BIT(blob+bloblen, namelen); bloblen += 4; - - bloblen += ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, blob+bloblen, namelen); + memcpy(blob+bloblen, ec->publicKey.curve->name, namelen); + bloblen += namelen; PUT_32BIT(blob+bloblen, 1 + (pointlen * 2)); bloblen += 4; @@ -2322,12 +2229,13 @@ static int ecdsa_openssh_fmtkey(void *key, unsigned char *blob, int len) return bloblen; } -static int ecdsa_pubkey_bits(const void *blob, int len) +static int ecdsa_pubkey_bits(const struct ssh_signkey *self, + const void *blob, int len) { struct ec_key *ec; int ret; - ec = (struct ec_key*)ecdsa_newkey((const char *) blob, len); + ec = (struct ec_key*)ecdsa_newkey(self, (const char *) blob, len); if (!ec) return -1; ret = ec->publicKey.curve->fieldBits; @@ -2336,119 +2244,154 @@ static int ecdsa_pubkey_bits(const void *blob, int len) return ret; } -static char *ecdsa_fingerprint(void *key) -{ - struct ec_key *ec = (struct ec_key *) key; - struct MD5Context md5c; - unsigned char digest[16], lenbuf[4]; - char *ret; - unsigned char *name, *fullname; - int pointlen, namelen, fullnamelen, i, j; - - MD5Init(&md5c); - - namelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0); - name = snewn(namelen, unsigned char); - ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, name, namelen); - - if (ec->publicKey.curve->type == EC_WEIERSTRASS) { - fullnamelen = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0); - fullname = snewn(namelen, unsigned char); - ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, fullname, fullnamelen); - - PUT_32BIT(lenbuf, fullnamelen); - MD5Update(&md5c, lenbuf, 4); - MD5Update(&md5c, fullname, fullnamelen); - sfree(fullname); - - PUT_32BIT(lenbuf, namelen); - MD5Update(&md5c, lenbuf, 4); - MD5Update(&md5c, name, namelen); - - pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8; - PUT_32BIT(lenbuf, 1 + (pointlen * 2)); - MD5Update(&md5c, lenbuf, 4); - MD5Update(&md5c, (const unsigned char *)"\x04", 1); - for (i = pointlen; i--; ) { - unsigned char c = bignum_byte(ec->publicKey.x, i); - MD5Update(&md5c, &c, 1); - } - for (i = pointlen; i--; ) { - unsigned char c = bignum_byte(ec->publicKey.y, i); - MD5Update(&md5c, &c, 1); - } - } else { - sfree(name); - return NULL; - } - - MD5Final(digest, &md5c); - - ret = snewn(namelen + 1 + (16 * 3), char); - - i = 0; - memcpy(ret, name, namelen); - i += namelen; - sfree(name); - ret[i++] = ' '; - for (j = 0; j < 16; j++) { - i += sprintf(ret + i, "%s%02x", j ? ":" : "", digest[j]); - } - - return ret; -} - static int ecdsa_verifysig(void *key, const char *sig, int siglen, const char *data, int datalen) { struct ec_key *ec = (struct ec_key *) key; + const struct ecsign_extra *extra = + (const struct ecsign_extra *)ec->signalg->extra; const char *p; int slen; - unsigned char digest[512 / 8]; int digestLen; int ret; - Bignum r, s; if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve) return 0; - /* Check the signature curve matches the key curve */ + /* Check the signature starts with the algorithm name */ getstring(&sig, &siglen, &p, &slen); if (!p) { return 0; } - if (ec->publicKey.curve != ec_name_to_curve(p, slen)) { + if (!match_ssh_id(slen, p, ec->signalg->name)) { return 0; } getstring(&sig, &siglen, &p, &slen); + if (!p) return 0; + if (ec->publicKey.curve->type == EC_EDWARDS) { + struct ec_point *r; + Bignum s, h; + /* Check that the signature is two times the length of a point */ + if (slen != (ec->publicKey.curve->fieldBits / 8) * 2) { + return 0; + } - r = getmp(&p, &slen); - if (!r) return 0; - s = getmp(&p, &slen); - if (!s) { - freebn(r); - return 0; - } + /* Check it's the 256 bit field so that SHA512 is the correct hash */ + if (ec->publicKey.curve->fieldBits != 256) { + return 0; + } + + /* Get the signature */ + r = ec_point_new(ec->publicKey.curve, NULL, NULL, NULL, 0); + if (!r) { + return 0; + } + if (!decodepoint(p, ec->publicKey.curve->fieldBits / 8, r)) { + ec_point_free(r); + return 0; + } + s = bignum_from_bytes_le((unsigned char*)p + (ec->publicKey.curve->fieldBits / 8), + ec->publicKey.curve->fieldBits / 8); + + /* Get the hash of the encoded value of R + encoded value of pk + message */ + { + int i, pointlen; + unsigned char b; + unsigned char digest[512 / 8]; + SHA512_State hs; + SHA512_Init(&hs); + + /* Add encoded r (no need to encode it again, it was in the signature) */ + SHA512_Bytes(&hs, p, ec->publicKey.curve->fieldBits / 8); + + /* Encode pk and add it */ + pointlen = ec->publicKey.curve->fieldBits / 8; + for (i = 0; i < pointlen - 1; ++i) { + b = bignum_byte(ec->publicKey.y, i); + SHA512_Bytes(&hs, &b, 1); + } + /* Unset last bit of y and set first bit of x in its place */ + b = bignum_byte(ec->publicKey.y, i) & 0x7f; + b |= bignum_bit(ec->publicKey.x, 0) << 7; + SHA512_Bytes(&hs, &b, 1); + + /* Add the message itself */ + SHA512_Bytes(&hs, data, datalen); + + /* Get the hash */ + SHA512_Final(&hs, digest); + + /* Convert to Bignum */ + h = bignum_from_bytes_le(digest, sizeof(digest)); + } + + /* Verify sB == r + h*publicKey */ + { + struct ec_point *lhs, *rhs, *tmp; + + /* lhs = sB */ + lhs = ecp_mul(&ec->publicKey.curve->e.B, s); + freebn(s); + if (!lhs) { + ec_point_free(r); + freebn(h); + return 0; + } - /* Perform correct hash function depending on curve size */ - if (ec->publicKey.curve->fieldBits <= 256) { - SHA256_Simple(data, datalen, digest); - digestLen = 256 / 8; - } else if (ec->publicKey.curve->fieldBits <= 384) { - SHA384_Simple(data, datalen, digest); - digestLen = 384 / 8; + /* rhs = r + h*publicKey */ + tmp = ecp_mul(&ec->publicKey, h); + freebn(h); + if (!tmp) { + ec_point_free(lhs); + ec_point_free(r); + return 0; + } + rhs = ecp_add(r, tmp, 0); + ec_point_free(r); + ec_point_free(tmp); + if (!rhs) { + ec_point_free(lhs); + return 0; + } + + /* Check the point is the same */ + ret = !bignum_cmp(lhs->x, rhs->x); + if (ret) { + ret = !bignum_cmp(lhs->y, rhs->y); + if (ret) { + ret = 1; + } + } + ec_point_free(lhs); + ec_point_free(rhs); + } } else { - SHA512_Simple(data, datalen, digest); - digestLen = 512 / 8; - } + Bignum r, s; + unsigned char digest[512 / 8]; + void *hashctx; + + r = getmp(&p, &slen); + if (!r) return 0; + s = getmp(&p, &slen); + if (!s) { + freebn(r); + return 0; + } - /* Verify the signature */ - ret = _ecdsa_verify(&ec->publicKey, digest, digestLen, r, s); + digestLen = extra->hash->hlen; + assert(digestLen <= sizeof(digest)); + hashctx = extra->hash->init(); + extra->hash->bytes(hashctx, data, datalen); + extra->hash->final(hashctx, digest); - freebn(r); - freebn(s); + /* Verify the signature */ + ret = _ecdsa_verify(&ec->publicKey, digest, digestLen, r, s); + + freebn(r); + freebn(s); + } return ret; } @@ -2457,6 +2400,8 @@ static unsigned char *ecdsa_sign(void *key, const char *data, int datalen, int *siglen) { struct ec_key *ec = (struct ec_key *) key; + const struct ecsign_extra *extra = + (const struct ecsign_extra *)ec->signalg->extra; unsigned char digest[512 / 8]; int digestLen; Bignum r = NULL, s = NULL; @@ -2468,55 +2413,201 @@ static unsigned char *ecdsa_sign(void *key, const char *data, int datalen, return NULL; } - /* Perform correct hash function depending on curve size */ - if (ec->publicKey.curve->fieldBits <= 256) { - SHA256_Simple(data, datalen, digest); - digestLen = 256 / 8; - } else if (ec->publicKey.curve->fieldBits <= 384) { - SHA384_Simple(data, datalen, digest); - digestLen = 384 / 8; + if (ec->publicKey.curve->type == EC_EDWARDS) { + struct ec_point *rp; + int pointlen = ec->publicKey.curve->fieldBits / 8; + + /* hash = H(sk) (where hash creates 2 * fieldBits) + * b = fieldBits + * a = 2^(b-2) + SUM(2^i * h_i) for i = 2 -> b-2 + * r = H(h[b/8:b/4] + m) + * R = rB + * S = (r + H(encodepoint(R) + encodepoint(pk) + m) * a) % l */ + { + unsigned char hash[512/8]; + unsigned char b; + Bignum a; + SHA512_State hs; + SHA512_Init(&hs); + + for (i = 0; i < pointlen; ++i) { + unsigned char b = (unsigned char)bignum_byte(ec->privateKey, i); + SHA512_Bytes(&hs, &b, 1); + } + + SHA512_Final(&hs, hash); + + /* The second part is simply turning the hash into a + * Bignum, however the 2^(b-2) bit *must* be set, and the + * bottom 3 bits *must* not be */ + hash[0] &= 0xf8; /* Unset bottom 3 bits (if set) */ + hash[31] &= 0x7f; /* Unset above (b-2) */ + hash[31] |= 0x40; /* Set 2^(b-2) */ + /* Chop off the top part and convert to int */ + a = bignum_from_bytes_le(hash, 32); + + SHA512_Init(&hs); + SHA512_Bytes(&hs, + hash+(ec->publicKey.curve->fieldBits / 8), + (ec->publicKey.curve->fieldBits / 4) + - (ec->publicKey.curve->fieldBits / 8)); + SHA512_Bytes(&hs, data, datalen); + SHA512_Final(&hs, hash); + + r = bignum_from_bytes_le(hash, 512/8); + rp = ecp_mul(&ec->publicKey.curve->e.B, r); + if (!rp) { + freebn(r); + freebn(a); + return NULL; + } + + /* Now calculate s */ + SHA512_Init(&hs); + /* Encode the point R */ + for (i = 0; i < pointlen - 1; ++i) { + b = bignum_byte(rp->y, i); + SHA512_Bytes(&hs, &b, 1); + } + /* Unset last bit of y and set first bit of x in its place */ + b = bignum_byte(rp->y, i) & 0x7f; + b |= bignum_bit(rp->x, 0) << 7; + SHA512_Bytes(&hs, &b, 1); + + /* Encode the point pk */ + for (i = 0; i < pointlen - 1; ++i) { + b = bignum_byte(ec->publicKey.y, i); + SHA512_Bytes(&hs, &b, 1); + } + /* Unset last bit of y and set first bit of x in its place */ + b = bignum_byte(ec->publicKey.y, i) & 0x7f; + b |= bignum_bit(ec->publicKey.x, 0) << 7; + SHA512_Bytes(&hs, &b, 1); + + /* Add the message */ + SHA512_Bytes(&hs, data, datalen); + SHA512_Final(&hs, hash); + + { + Bignum tmp, tmp2; + + tmp = bignum_from_bytes_le(hash, 512/8); + tmp2 = modmul(tmp, a, ec->publicKey.curve->e.l); + freebn(a); + freebn(tmp); + tmp = bigadd(r, tmp2); + freebn(r); + freebn(tmp2); + s = bigmod(tmp, ec->publicKey.curve->e.l); + freebn(tmp); + } + } + + /* Format the output */ + namelen = strlen(ec->signalg->name); + *siglen = 4+namelen+4+((ec->publicKey.curve->fieldBits / 8)*2); + buf = snewn(*siglen, unsigned char); + p = buf; + PUT_32BIT(p, namelen); + p += 4; + memcpy(p, ec->signalg->name, namelen); + p += namelen; + PUT_32BIT(p, ((ec->publicKey.curve->fieldBits / 8)*2)); + p += 4; + + /* Encode the point */ + pointlen = ec->publicKey.curve->fieldBits / 8; + for (i = 0; i < pointlen - 1; ++i) { + *p++ = bignum_byte(rp->y, i); + } + /* Unset last bit of y and set first bit of x in its place */ + *p = bignum_byte(rp->y, i) & 0x7f; + *p++ |= bignum_bit(rp->x, 0) << 7; + ec_point_free(rp); + + /* Encode the int */ + for (i = 0; i < pointlen; ++i) { + *p++ = bignum_byte(s, i); + } + freebn(s); } else { - SHA512_Simple(data, datalen, digest); - digestLen = 512 / 8; - } + void *hashctx; - /* Do the signature */ - _ecdsa_sign(ec->privateKey, ec->publicKey.curve, digest, digestLen, &r, &s); - if (!r || !s) { - if (r) freebn(r); - if (s) freebn(s); - return NULL; - } + digestLen = extra->hash->hlen; + assert(digestLen <= sizeof(digest)); + hashctx = extra->hash->init(); + extra->hash->bytes(hashctx, data, datalen); + extra->hash->final(hashctx, digest); - rlen = (bignum_bitcount(r) + 8) / 8; - slen = (bignum_bitcount(s) + 8) / 8; + /* Do the signature */ + _ecdsa_sign(ec->privateKey, ec->publicKey.curve, digest, digestLen, &r, &s); + if (!r || !s) { + if (r) freebn(r); + if (s) freebn(s); + return NULL; + } - namelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0); + rlen = (bignum_bitcount(r) + 8) / 8; + slen = (bignum_bitcount(s) + 8) / 8; - /* Format the output */ - *siglen = 8+namelen+rlen+slen+8; - buf = snewn(*siglen, unsigned char); - p = buf; - PUT_32BIT(p, namelen); - p += 4; - p += ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, p, namelen); - PUT_32BIT(p, rlen + slen + 8); - p += 4; - PUT_32BIT(p, rlen); - p += 4; - for (i = rlen; i--;) - *p++ = bignum_byte(r, i); - PUT_32BIT(p, slen); - p += 4; - for (i = slen; i--;) - *p++ = bignum_byte(s, i); + namelen = strlen(ec->signalg->name); - freebn(r); - freebn(s); + /* Format the output */ + *siglen = 8+namelen+rlen+slen+8; + buf = snewn(*siglen, unsigned char); + p = buf; + PUT_32BIT(p, namelen); + p += 4; + memcpy(p, ec->signalg->name, namelen); + p += namelen; + PUT_32BIT(p, rlen + slen + 8); + p += 4; + PUT_32BIT(p, rlen); + p += 4; + for (i = rlen; i--;) + *p++ = bignum_byte(r, i); + PUT_32BIT(p, slen); + p += 4; + for (i = slen; i--;) + *p++ = bignum_byte(s, i); + + freebn(r); + freebn(s); + } return buf; } +const struct ecsign_extra sign_extra_ed25519 = { + ec_ed25519, NULL, + NULL, 0, +}; +const struct ssh_signkey ssh_ecdsa_ed25519 = { + ecdsa_newkey, + ecdsa_freekey, + ecdsa_fmtkey, + ecdsa_public_blob, + ecdsa_private_blob, + ecdsa_createkey, + ed25519_openssh_createkey, + ed25519_openssh_fmtkey, + 2 /* point, private exponent */, + ecdsa_pubkey_bits, + ecdsa_verifysig, + ecdsa_sign, + "ssh-ed25519", + "ssh-ed25519", + &sign_extra_ed25519, +}; + +/* OID: 1.2.840.10045.3.1.7 (ansiX9p256r1) */ +static const unsigned char nistp256_oid[] = { + 0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07 +}; +const struct ecsign_extra sign_extra_nistp256 = { + ec_p256, &ssh_sha256, + nistp256_oid, lenof(nistp256_oid), +}; const struct ssh_signkey ssh_ecdsa_nistp256 = { ecdsa_newkey, ecdsa_freekey, @@ -2528,13 +2619,21 @@ const struct ssh_signkey ssh_ecdsa_nistp256 = { ecdsa_openssh_fmtkey, 3 /* curve name, point, private exponent */, ecdsa_pubkey_bits, - ecdsa_fingerprint, ecdsa_verifysig, ecdsa_sign, "ecdsa-sha2-nistp256", "ecdsa-sha2-nistp256", + &sign_extra_nistp256, }; +/* OID: 1.3.132.0.34 (secp384r1) */ +static const unsigned char nistp384_oid[] = { + 0x2b, 0x81, 0x04, 0x00, 0x22 +}; +const struct ecsign_extra sign_extra_nistp384 = { + ec_p384, &ssh_sha384, + nistp384_oid, lenof(nistp384_oid), +}; const struct ssh_signkey ssh_ecdsa_nistp384 = { ecdsa_newkey, ecdsa_freekey, @@ -2546,13 +2645,21 @@ const struct ssh_signkey ssh_ecdsa_nistp384 = { ecdsa_openssh_fmtkey, 3 /* curve name, point, private exponent */, ecdsa_pubkey_bits, - ecdsa_fingerprint, ecdsa_verifysig, ecdsa_sign, "ecdsa-sha2-nistp384", "ecdsa-sha2-nistp384", + &sign_extra_nistp384, }; +/* OID: 1.3.132.0.35 (secp521r1) */ +static const unsigned char nistp521_oid[] = { + 0x2b, 0x81, 0x04, 0x00, 0x23 +}; +const struct ecsign_extra sign_extra_nistp521 = { + ec_p521, &ssh_sha512, + nistp521_oid, lenof(nistp521_oid), +}; const struct ssh_signkey ssh_ecdsa_nistp521 = { ecdsa_newkey, ecdsa_freekey, @@ -2564,17 +2671,21 @@ const struct ssh_signkey ssh_ecdsa_nistp521 = { ecdsa_openssh_fmtkey, 3 /* curve name, point, private exponent */, ecdsa_pubkey_bits, - ecdsa_fingerprint, ecdsa_verifysig, ecdsa_sign, "ecdsa-sha2-nistp521", "ecdsa-sha2-nistp521", + &sign_extra_nistp521, }; /* ---------------------------------------------------------------------- * Exposed ECDH interface */ +struct eckex_extra { + struct ec_curve *(*curve)(void); +}; + static Bignum ecdh_calculate(const Bignum private, const struct ec_point *public) { @@ -2586,20 +2697,30 @@ static Bignum ecdh_calculate(const Bignum private, p->x = NULL; if (p->curve->type == EC_MONTGOMERY) { - /* Do conversion in network byte order */ + /* + * Endianness-swap. The Curve25519 algorithm definition + * assumes you were doing your computation in arrays of 32 + * little-endian bytes, and now specifies that you take your + * final one of those and convert it into a bignum in + * _network_ byte order, i.e. big-endian. + * + * In particular, the spec says, you convert the _whole_ 32 + * bytes into a bignum. That is, on the rare occasions that + * p->x has come out with the most significant 8 bits zero, we + * have to imagine that being represented by a 32-byte string + * with the last byte being zero, so that has to be converted + * into an SSH-2 bignum with the _low_ byte zero, i.e. a + * multiple of 256. + */ int i; - int bytes = (bignum_bitcount(ret)+7) / 8; + int bytes = (p->curve->fieldBits+7) / 8; unsigned char *byteorder = snewn(bytes, unsigned char); - if (!byteorder) { - ec_point_free(p); - freebn(ret); - return NULL; - } for (i = 0; i < bytes; ++i) { byteorder[i] = bignum_byte(ret, i); } freebn(ret); ret = bignum_from_bytes(byteorder, bytes); + smemclr(byteorder, bytes); sfree(byteorder); } @@ -2607,19 +2728,25 @@ static Bignum ecdh_calculate(const Bignum private, return ret; } -void *ssh_ecdhkex_newkey(const char *name) +const char *ssh_ecdhkex_curve_textname(const struct ssh_kex *kex) { + const struct eckex_extra *extra = (const struct eckex_extra *)kex->extra; + struct ec_curve *curve = extra->curve(); + return curve->textname; +} + +void *ssh_ecdhkex_newkey(const struct ssh_kex *kex) +{ + const struct eckex_extra *extra = (const struct eckex_extra *)kex->extra; struct ec_curve *curve; struct ec_key *key; struct ec_point *publicKey; - curve = ec_name_to_curve(name, strlen(name)); + curve = extra->curve(); key = snew(struct ec_key); - if (!key) { - return NULL; - } + key->signalg = NULL; key->publicKey.curve = curve; if (curve->type == EC_MONTGOMERY) { @@ -2633,11 +2760,8 @@ void *ssh_ecdhkex_newkey(const char *name) bytes[0] &= 248; bytes[31] &= 127; bytes[31] |= 64; - key->privateKey = bignum_from_bytes(bytes, sizeof(bytes)); - for (i = 0; i < sizeof(bytes); ++i) - { - ((volatile char*)bytes)[i] = 0; - } + key->privateKey = bignum_from_bytes_le(bytes, sizeof(bytes)); + smemclr(bytes, sizeof(bytes)); if (!key->privateKey) { sfree(key); return NULL; @@ -2687,9 +2811,6 @@ char *ssh_ecdhkex_getpublic(void *key, int *len) *len = pointlen; } point = (char*)snewn(*len, char); - if (!point) { - return NULL; - } p = point; if (ec->publicKey.curve->type == EC_WEIERSTRASS) { @@ -2745,30 +2866,102 @@ void ssh_ecdhkex_freekey(void *key) ecdsa_freekey(key); } +static const struct eckex_extra kex_extra_curve25519 = { ec_curve25519 }; static const struct ssh_kex ssh_ec_kex_curve25519 = { - "curve25519-sha256@libssh.org", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha256 + "curve25519-sha256@libssh.org", NULL, KEXTYPE_ECDH, + &ssh_sha256, &kex_extra_curve25519, }; +const struct eckex_extra kex_extra_nistp256 = { ec_p256 }; static const struct ssh_kex ssh_ec_kex_nistp256 = { - "ecdh-sha2-nistp256", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha256 + "ecdh-sha2-nistp256", NULL, KEXTYPE_ECDH, + &ssh_sha256, &kex_extra_nistp256, }; +const struct eckex_extra kex_extra_nistp384 = { ec_p384 }; static const struct ssh_kex ssh_ec_kex_nistp384 = { - "ecdh-sha2-nistp384", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha384 + "ecdh-sha2-nistp384", NULL, KEXTYPE_ECDH, + &ssh_sha384, &kex_extra_nistp384, }; +const struct eckex_extra kex_extra_nistp521 = { ec_p521 }; static const struct ssh_kex ssh_ec_kex_nistp521 = { - "ecdh-sha2-nistp521", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha512 + "ecdh-sha2-nistp521", NULL, KEXTYPE_ECDH, + &ssh_sha512, &kex_extra_nistp521, }; static const struct ssh_kex *const ec_kex_list[] = { &ssh_ec_kex_curve25519, &ssh_ec_kex_nistp256, &ssh_ec_kex_nistp384, - &ssh_ec_kex_nistp521 + &ssh_ec_kex_nistp521, }; const struct ssh_kexes ssh_ecdh_kex = { sizeof(ec_kex_list) / sizeof(*ec_kex_list), ec_kex_list }; + +/* ---------------------------------------------------------------------- + * Helper functions for finding key algorithms and returning auxiliary + * data. + */ + +const struct ssh_signkey *ec_alg_by_oid(int len, const void *oid, + const struct ec_curve **curve) +{ + static const struct ssh_signkey *algs_with_oid[] = { + &ssh_ecdsa_nistp256, + &ssh_ecdsa_nistp384, + &ssh_ecdsa_nistp521, + }; + int i; + + for (i = 0; i < lenof(algs_with_oid); i++) { + const struct ssh_signkey *alg = algs_with_oid[i]; + const struct ecsign_extra *extra = + (const struct ecsign_extra *)alg->extra; + if (len == extra->oidlen && !memcmp(oid, extra->oid, len)) { + *curve = extra->curve(); + return alg; + } + } + return NULL; +} + +const unsigned char *ec_alg_oid(const struct ssh_signkey *alg, + int *oidlen) +{ + const struct ecsign_extra *extra = (const struct ecsign_extra *)alg->extra; + *oidlen = extra->oidlen; + return extra->oid; +} + +const int ec_nist_curve_lengths[] = { 256, 384, 521 }; +const int n_ec_nist_curve_lengths = lenof(ec_nist_curve_lengths); + +const int ec_nist_alg_and_curve_by_bits(int bits, + const struct ec_curve **curve, + const struct ssh_signkey **alg) +{ + switch (bits) { + case 256: *alg = &ssh_ecdsa_nistp256; break; + case 384: *alg = &ssh_ecdsa_nistp384; break; + case 521: *alg = &ssh_ecdsa_nistp521; break; + default: return FALSE; + } + *curve = ((struct ecsign_extra *)(*alg)->extra)->curve(); + return TRUE; +} + +const int ec_ed_alg_and_curve_by_bits(int bits, + const struct ec_curve **curve, + const struct ssh_signkey **alg) +{ + switch (bits) { + case 256: *alg = &ssh_ecdsa_ed25519; break; + default: return FALSE; + } + *curve = ((struct ecsign_extra *)(*alg)->extra)->curve(); + return TRUE; +}