ecdsa.c 9.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * Copyright (c) 2021 IBM Corporation
  4. */
  5. #include <linux/module.h>
  6. #include <crypto/internal/akcipher.h>
  7. #include <crypto/internal/ecc.h>
  8. #include <crypto/akcipher.h>
  9. #include <crypto/ecdh.h>
  10. #include <linux/asn1_decoder.h>
  11. #include <linux/scatterlist.h>
  12. #include "ecdsasignature.asn1.h"
  13. struct ecc_ctx {
  14. unsigned int curve_id;
  15. const struct ecc_curve *curve;
  16. bool pub_key_set;
  17. u64 x[ECC_MAX_DIGITS]; /* pub key x and y coordinates */
  18. u64 y[ECC_MAX_DIGITS];
  19. struct ecc_point pub_key;
  20. };
  21. struct ecdsa_signature_ctx {
  22. const struct ecc_curve *curve;
  23. u64 r[ECC_MAX_DIGITS];
  24. u64 s[ECC_MAX_DIGITS];
  25. };
  26. /*
  27. * Get the r and s components of a signature from the X509 certificate.
  28. */
  29. static int ecdsa_get_signature_rs(u64 *dest, size_t hdrlen, unsigned char tag,
  30. const void *value, size_t vlen, unsigned int ndigits)
  31. {
  32. size_t keylen = ndigits * sizeof(u64);
  33. ssize_t diff = vlen - keylen;
  34. const char *d = value;
  35. u8 rs[ECC_MAX_BYTES];
  36. if (!value || !vlen)
  37. return -EINVAL;
  38. /* diff = 0: 'value' has exacly the right size
  39. * diff > 0: 'value' has too many bytes; one leading zero is allowed that
  40. * makes the value a positive integer; error on more
  41. * diff < 0: 'value' is missing leading zeros, which we add
  42. */
  43. if (diff > 0) {
  44. /* skip over leading zeros that make 'value' a positive int */
  45. if (*d == 0) {
  46. vlen -= 1;
  47. diff--;
  48. d++;
  49. }
  50. if (diff)
  51. return -EINVAL;
  52. }
  53. if (-diff >= keylen)
  54. return -EINVAL;
  55. if (diff) {
  56. /* leading zeros not given in 'value' */
  57. memset(rs, 0, -diff);
  58. }
  59. memcpy(&rs[-diff], d, vlen);
  60. ecc_swap_digits((u64 *)rs, dest, ndigits);
  61. return 0;
  62. }
  63. int ecdsa_get_signature_r(void *context, size_t hdrlen, unsigned char tag,
  64. const void *value, size_t vlen)
  65. {
  66. struct ecdsa_signature_ctx *sig = context;
  67. return ecdsa_get_signature_rs(sig->r, hdrlen, tag, value, vlen,
  68. sig->curve->g.ndigits);
  69. }
  70. int ecdsa_get_signature_s(void *context, size_t hdrlen, unsigned char tag,
  71. const void *value, size_t vlen)
  72. {
  73. struct ecdsa_signature_ctx *sig = context;
  74. return ecdsa_get_signature_rs(sig->s, hdrlen, tag, value, vlen,
  75. sig->curve->g.ndigits);
  76. }
  77. static int _ecdsa_verify(struct ecc_ctx *ctx, const u64 *hash, const u64 *r, const u64 *s)
  78. {
  79. const struct ecc_curve *curve = ctx->curve;
  80. unsigned int ndigits = curve->g.ndigits;
  81. u64 s1[ECC_MAX_DIGITS];
  82. u64 u1[ECC_MAX_DIGITS];
  83. u64 u2[ECC_MAX_DIGITS];
  84. u64 x1[ECC_MAX_DIGITS];
  85. u64 y1[ECC_MAX_DIGITS];
  86. struct ecc_point res = ECC_POINT_INIT(x1, y1, ndigits);
  87. /* 0 < r < n and 0 < s < n */
  88. if (vli_is_zero(r, ndigits) || vli_cmp(r, curve->n, ndigits) >= 0 ||
  89. vli_is_zero(s, ndigits) || vli_cmp(s, curve->n, ndigits) >= 0)
  90. return -EBADMSG;
  91. /* hash is given */
  92. pr_devel("hash : %016llx %016llx ... %016llx\n",
  93. hash[ndigits - 1], hash[ndigits - 2], hash[0]);
  94. /* s1 = (s^-1) mod n */
  95. vli_mod_inv(s1, s, curve->n, ndigits);
  96. /* u1 = (hash * s1) mod n */
  97. vli_mod_mult_slow(u1, hash, s1, curve->n, ndigits);
  98. /* u2 = (r * s1) mod n */
  99. vli_mod_mult_slow(u2, r, s1, curve->n, ndigits);
  100. /* res = u1*G + u2 * pub_key */
  101. ecc_point_mult_shamir(&res, u1, &curve->g, u2, &ctx->pub_key, curve);
  102. /* res.x = res.x mod n (if res.x > order) */
  103. if (unlikely(vli_cmp(res.x, curve->n, ndigits) == 1))
  104. /* faster alternative for NIST p384, p256 & p192 */
  105. vli_sub(res.x, res.x, curve->n, ndigits);
  106. if (!vli_cmp(res.x, r, ndigits))
  107. return 0;
  108. return -EKEYREJECTED;
  109. }
  110. /*
  111. * Verify an ECDSA signature.
  112. */
  113. static int ecdsa_verify(struct akcipher_request *req)
  114. {
  115. struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
  116. struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
  117. size_t keylen = ctx->curve->g.ndigits * sizeof(u64);
  118. struct ecdsa_signature_ctx sig_ctx = {
  119. .curve = ctx->curve,
  120. };
  121. u8 rawhash[ECC_MAX_BYTES];
  122. u64 hash[ECC_MAX_DIGITS];
  123. unsigned char *buffer;
  124. ssize_t diff;
  125. int ret;
  126. if (unlikely(!ctx->pub_key_set))
  127. return -EINVAL;
  128. buffer = kmalloc(req->src_len + req->dst_len, GFP_KERNEL);
  129. if (!buffer)
  130. return -ENOMEM;
  131. sg_pcopy_to_buffer(req->src,
  132. sg_nents_for_len(req->src, req->src_len + req->dst_len),
  133. buffer, req->src_len + req->dst_len, 0);
  134. ret = asn1_ber_decoder(&ecdsasignature_decoder, &sig_ctx,
  135. buffer, req->src_len);
  136. if (ret < 0)
  137. goto error;
  138. /* if the hash is shorter then we will add leading zeros to fit to ndigits */
  139. diff = keylen - req->dst_len;
  140. if (diff >= 0) {
  141. if (diff)
  142. memset(rawhash, 0, diff);
  143. memcpy(&rawhash[diff], buffer + req->src_len, req->dst_len);
  144. } else if (diff < 0) {
  145. /* given hash is longer, we take the left-most bytes */
  146. memcpy(&rawhash, buffer + req->src_len, keylen);
  147. }
  148. ecc_swap_digits((u64 *)rawhash, hash, ctx->curve->g.ndigits);
  149. ret = _ecdsa_verify(ctx, hash, sig_ctx.r, sig_ctx.s);
  150. error:
  151. kfree(buffer);
  152. return ret;
  153. }
  154. static int ecdsa_ecc_ctx_init(struct ecc_ctx *ctx, unsigned int curve_id)
  155. {
  156. ctx->curve_id = curve_id;
  157. ctx->curve = ecc_get_curve(curve_id);
  158. if (!ctx->curve)
  159. return -EINVAL;
  160. return 0;
  161. }
  162. static void ecdsa_ecc_ctx_deinit(struct ecc_ctx *ctx)
  163. {
  164. ctx->pub_key_set = false;
  165. }
  166. static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)
  167. {
  168. unsigned int curve_id = ctx->curve_id;
  169. int ret;
  170. ecdsa_ecc_ctx_deinit(ctx);
  171. ret = ecdsa_ecc_ctx_init(ctx, curve_id);
  172. if (ret == 0)
  173. ctx->pub_key = ECC_POINT_INIT(ctx->x, ctx->y,
  174. ctx->curve->g.ndigits);
  175. return ret;
  176. }
  177. /*
  178. * Set the public key given the raw uncompressed key data from an X509
  179. * certificate. The key data contain the concatenated X and Y coordinates of
  180. * the public key.
  181. */
  182. static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
  183. {
  184. struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
  185. const unsigned char *d = key;
  186. const u64 *digits = (const u64 *)&d[1];
  187. unsigned int ndigits;
  188. int ret;
  189. ret = ecdsa_ecc_ctx_reset(ctx);
  190. if (ret < 0)
  191. return ret;
  192. if (keylen < 1 || (((keylen - 1) >> 1) % sizeof(u64)) != 0)
  193. return -EINVAL;
  194. /* we only accept uncompressed format indicated by '4' */
  195. if (d[0] != 4)
  196. return -EINVAL;
  197. keylen--;
  198. ndigits = (keylen >> 1) / sizeof(u64);
  199. if (ndigits != ctx->curve->g.ndigits)
  200. return -EINVAL;
  201. ecc_swap_digits(digits, ctx->pub_key.x, ndigits);
  202. ecc_swap_digits(&digits[ndigits], ctx->pub_key.y, ndigits);
  203. ret = ecc_is_pubkey_valid_full(ctx->curve, &ctx->pub_key);
  204. ctx->pub_key_set = ret == 0;
  205. return ret;
  206. }
  207. static void ecdsa_exit_tfm(struct crypto_akcipher *tfm)
  208. {
  209. struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
  210. ecdsa_ecc_ctx_deinit(ctx);
  211. }
  212. static unsigned int ecdsa_max_size(struct crypto_akcipher *tfm)
  213. {
  214. struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
  215. return ctx->pub_key.ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
  216. }
  217. static int ecdsa_nist_p384_init_tfm(struct crypto_akcipher *tfm)
  218. {
  219. struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
  220. return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P384);
  221. }
  222. static struct akcipher_alg ecdsa_nist_p384 = {
  223. .verify = ecdsa_verify,
  224. .set_pub_key = ecdsa_set_pub_key,
  225. .max_size = ecdsa_max_size,
  226. .init = ecdsa_nist_p384_init_tfm,
  227. .exit = ecdsa_exit_tfm,
  228. .base = {
  229. .cra_name = "ecdsa-nist-p384",
  230. .cra_driver_name = "ecdsa-nist-p384-generic",
  231. .cra_priority = 100,
  232. .cra_module = THIS_MODULE,
  233. .cra_ctxsize = sizeof(struct ecc_ctx),
  234. },
  235. };
  236. static int ecdsa_nist_p256_init_tfm(struct crypto_akcipher *tfm)
  237. {
  238. struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
  239. return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P256);
  240. }
  241. static struct akcipher_alg ecdsa_nist_p256 = {
  242. .verify = ecdsa_verify,
  243. .set_pub_key = ecdsa_set_pub_key,
  244. .max_size = ecdsa_max_size,
  245. .init = ecdsa_nist_p256_init_tfm,
  246. .exit = ecdsa_exit_tfm,
  247. .base = {
  248. .cra_name = "ecdsa-nist-p256",
  249. .cra_driver_name = "ecdsa-nist-p256-generic",
  250. .cra_priority = 100,
  251. .cra_module = THIS_MODULE,
  252. .cra_ctxsize = sizeof(struct ecc_ctx),
  253. },
  254. };
  255. static int ecdsa_nist_p192_init_tfm(struct crypto_akcipher *tfm)
  256. {
  257. struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
  258. return ecdsa_ecc_ctx_init(ctx, ECC_CURVE_NIST_P192);
  259. }
  260. static struct akcipher_alg ecdsa_nist_p192 = {
  261. .verify = ecdsa_verify,
  262. .set_pub_key = ecdsa_set_pub_key,
  263. .max_size = ecdsa_max_size,
  264. .init = ecdsa_nist_p192_init_tfm,
  265. .exit = ecdsa_exit_tfm,
  266. .base = {
  267. .cra_name = "ecdsa-nist-p192",
  268. .cra_driver_name = "ecdsa-nist-p192-generic",
  269. .cra_priority = 100,
  270. .cra_module = THIS_MODULE,
  271. .cra_ctxsize = sizeof(struct ecc_ctx),
  272. },
  273. };
  274. static bool ecdsa_nist_p192_registered;
  275. static int __init ecdsa_init(void)
  276. {
  277. int ret;
  278. /* NIST p192 may not be available in FIPS mode */
  279. ret = crypto_register_akcipher(&ecdsa_nist_p192);
  280. ecdsa_nist_p192_registered = ret == 0;
  281. ret = crypto_register_akcipher(&ecdsa_nist_p256);
  282. if (ret)
  283. goto nist_p256_error;
  284. ret = crypto_register_akcipher(&ecdsa_nist_p384);
  285. if (ret)
  286. goto nist_p384_error;
  287. return 0;
  288. nist_p384_error:
  289. crypto_unregister_akcipher(&ecdsa_nist_p256);
  290. nist_p256_error:
  291. if (ecdsa_nist_p192_registered)
  292. crypto_unregister_akcipher(&ecdsa_nist_p192);
  293. return ret;
  294. }
  295. static void __exit ecdsa_exit(void)
  296. {
  297. if (ecdsa_nist_p192_registered)
  298. crypto_unregister_akcipher(&ecdsa_nist_p192);
  299. crypto_unregister_akcipher(&ecdsa_nist_p256);
  300. crypto_unregister_akcipher(&ecdsa_nist_p384);
  301. }
  302. subsys_initcall(ecdsa_init);
  303. module_exit(ecdsa_exit);
  304. MODULE_LICENSE("GPL");
  305. MODULE_AUTHOR("Stefan Berger <[email protected]>");
  306. MODULE_DESCRIPTION("ECDSA generic algorithm");
  307. MODULE_ALIAS_CRYPTO("ecdsa-generic");