ecrdsa.c 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * Elliptic Curve (Russian) Digital Signature Algorithm for Cryptographic API
  4. *
  5. * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org>
  6. *
  7. * References:
  8. * GOST 34.10-2018, GOST R 34.10-2012, RFC 7091, ISO/IEC 14888-3:2018.
  9. *
  10. * Historical references:
  11. * GOST R 34.10-2001, RFC 4357, ISO/IEC 14888-3:2006/Amd 1:2010.
  12. *
  13. * This program is free software; you can redistribute it and/or modify it
  14. * under the terms of the GNU General Public License as published by the Free
  15. * Software Foundation; either version 2 of the License, or (at your option)
  16. * any later version.
  17. */
  18. #include <linux/module.h>
  19. #include <linux/crypto.h>
  20. #include <crypto/streebog.h>
  21. #include <crypto/internal/akcipher.h>
  22. #include <crypto/akcipher.h>
  23. #include <linux/oid_registry.h>
  24. #include <linux/scatterlist.h>
  25. #include "ecrdsa_params.asn1.h"
  26. #include "ecrdsa_pub_key.asn1.h"
  27. #include "ecc.h"
  28. #include "ecrdsa_defs.h"
  29. #define ECRDSA_MAX_SIG_SIZE (2 * 512 / 8)
  30. #define ECRDSA_MAX_DIGITS (512 / 64)
  31. struct ecrdsa_ctx {
  32. enum OID algo_oid; /* overall public key oid */
  33. enum OID curve_oid; /* parameter */
  34. enum OID digest_oid; /* parameter */
  35. const struct ecc_curve *curve; /* curve from oid */
  36. unsigned int digest_len; /* parameter (bytes) */
  37. const char *digest; /* digest name from oid */
  38. unsigned int key_len; /* @key length (bytes) */
  39. const char *key; /* raw public key */
  40. struct ecc_point pub_key;
  41. u64 _pubp[2][ECRDSA_MAX_DIGITS]; /* point storage for @pub_key */
  42. };
  43. static const struct ecc_curve *get_curve_by_oid(enum OID oid)
  44. {
  45. switch (oid) {
  46. case OID_gostCPSignA:
  47. case OID_gostTC26Sign256B:
  48. return &gost_cp256a;
  49. case OID_gostCPSignB:
  50. case OID_gostTC26Sign256C:
  51. return &gost_cp256b;
  52. case OID_gostCPSignC:
  53. case OID_gostTC26Sign256D:
  54. return &gost_cp256c;
  55. case OID_gostTC26Sign512A:
  56. return &gost_tc512a;
  57. case OID_gostTC26Sign512B:
  58. return &gost_tc512b;
  59. /* The following two aren't implemented: */
  60. case OID_gostTC26Sign256A:
  61. case OID_gostTC26Sign512C:
  62. default:
  63. return NULL;
  64. }
  65. }
  66. static int ecrdsa_verify(struct akcipher_request *req)
  67. {
  68. struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
  69. struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
  70. unsigned char sig[ECRDSA_MAX_SIG_SIZE];
  71. unsigned char digest[STREEBOG512_DIGEST_SIZE];
  72. unsigned int ndigits = req->dst_len / sizeof(u64);
  73. u64 r[ECRDSA_MAX_DIGITS]; /* witness (r) */
  74. u64 _r[ECRDSA_MAX_DIGITS]; /* -r */
  75. u64 s[ECRDSA_MAX_DIGITS]; /* second part of sig (s) */
  76. u64 e[ECRDSA_MAX_DIGITS]; /* h \mod q */
  77. u64 *v = e; /* e^{-1} \mod q */
  78. u64 z1[ECRDSA_MAX_DIGITS];
  79. u64 *z2 = _r;
  80. struct ecc_point cc = ECC_POINT_INIT(s, e, ndigits); /* reuse s, e */
  81. /*
  82. * Digest value, digest algorithm, and curve (modulus) should have the
  83. * same length (256 or 512 bits), public key and signature should be
  84. * twice bigger.
  85. */
  86. if (!ctx->curve ||
  87. !ctx->digest ||
  88. !req->src ||
  89. !ctx->pub_key.x ||
  90. req->dst_len != ctx->digest_len ||
  91. req->dst_len != ctx->curve->g.ndigits * sizeof(u64) ||
  92. ctx->pub_key.ndigits != ctx->curve->g.ndigits ||
  93. req->dst_len * 2 != req->src_len ||
  94. WARN_ON(req->src_len > sizeof(sig)) ||
  95. WARN_ON(req->dst_len > sizeof(digest)))
  96. return -EBADMSG;
  97. sg_copy_to_buffer(req->src, sg_nents_for_len(req->src, req->src_len),
  98. sig, req->src_len);
  99. sg_pcopy_to_buffer(req->src,
  100. sg_nents_for_len(req->src,
  101. req->src_len + req->dst_len),
  102. digest, req->dst_len, req->src_len);
  103. vli_from_be64(s, sig, ndigits);
  104. vli_from_be64(r, sig + ndigits * sizeof(u64), ndigits);
  105. /* Step 1: verify that 0 < r < q, 0 < s < q */
  106. if (vli_is_zero(r, ndigits) ||
  107. vli_cmp(r, ctx->curve->n, ndigits) == 1 ||
  108. vli_is_zero(s, ndigits) ||
  109. vli_cmp(s, ctx->curve->n, ndigits) == 1)
  110. return -EKEYREJECTED;
  111. /* Step 2: calculate hash (h) of the message (passed as input) */
  112. /* Step 3: calculate e = h \mod q */
  113. vli_from_le64(e, digest, ndigits);
  114. if (vli_cmp(e, ctx->curve->n, ndigits) == 1)
  115. vli_sub(e, e, ctx->curve->n, ndigits);
  116. if (vli_is_zero(e, ndigits))
  117. e[0] = 1;
  118. /* Step 4: calculate v = e^{-1} \mod q */
  119. vli_mod_inv(v, e, ctx->curve->n, ndigits);
  120. /* Step 5: calculate z_1 = sv \mod q, z_2 = -rv \mod q */
  121. vli_mod_mult_slow(z1, s, v, ctx->curve->n, ndigits);
  122. vli_sub(_r, ctx->curve->n, r, ndigits);
  123. vli_mod_mult_slow(z2, _r, v, ctx->curve->n, ndigits);
  124. /* Step 6: calculate point C = z_1P + z_2Q, and R = x_c \mod q */
  125. ecc_point_mult_shamir(&cc, z1, &ctx->curve->g, z2, &ctx->pub_key,
  126. ctx->curve);
  127. if (vli_cmp(cc.x, ctx->curve->n, ndigits) == 1)
  128. vli_sub(cc.x, cc.x, ctx->curve->n, ndigits);
  129. /* Step 7: if R == r signature is valid */
  130. if (!vli_cmp(cc.x, r, ndigits))
  131. return 0;
  132. else
  133. return -EKEYREJECTED;
  134. }
  135. int ecrdsa_param_curve(void *context, size_t hdrlen, unsigned char tag,
  136. const void *value, size_t vlen)
  137. {
  138. struct ecrdsa_ctx *ctx = context;
  139. ctx->curve_oid = look_up_OID(value, vlen);
  140. if (!ctx->curve_oid)
  141. return -EINVAL;
  142. ctx->curve = get_curve_by_oid(ctx->curve_oid);
  143. return 0;
  144. }
  145. /* Optional. If present should match expected digest algo OID. */
  146. int ecrdsa_param_digest(void *context, size_t hdrlen, unsigned char tag,
  147. const void *value, size_t vlen)
  148. {
  149. struct ecrdsa_ctx *ctx = context;
  150. int digest_oid = look_up_OID(value, vlen);
  151. if (digest_oid != ctx->digest_oid)
  152. return -EINVAL;
  153. return 0;
  154. }
  155. int ecrdsa_parse_pub_key(void *context, size_t hdrlen, unsigned char tag,
  156. const void *value, size_t vlen)
  157. {
  158. struct ecrdsa_ctx *ctx = context;
  159. ctx->key = value;
  160. ctx->key_len = vlen;
  161. return 0;
  162. }
  163. static u8 *ecrdsa_unpack_u32(u32 *dst, void *src)
  164. {
  165. memcpy(dst, src, sizeof(u32));
  166. return src + sizeof(u32);
  167. }
  168. /* Parse BER encoded subjectPublicKey. */
  169. static int ecrdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key,
  170. unsigned int keylen)
  171. {
  172. struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
  173. unsigned int ndigits;
  174. u32 algo, paramlen;
  175. u8 *params;
  176. int err;
  177. err = asn1_ber_decoder(&ecrdsa_pub_key_decoder, ctx, key, keylen);
  178. if (err < 0)
  179. return err;
  180. /* Key parameters is in the key after keylen. */
  181. params = ecrdsa_unpack_u32(&paramlen,
  182. ecrdsa_unpack_u32(&algo, (u8 *)key + keylen));
  183. if (algo == OID_gost2012PKey256) {
  184. ctx->digest = "streebog256";
  185. ctx->digest_oid = OID_gost2012Digest256;
  186. ctx->digest_len = 256 / 8;
  187. } else if (algo == OID_gost2012PKey512) {
  188. ctx->digest = "streebog512";
  189. ctx->digest_oid = OID_gost2012Digest512;
  190. ctx->digest_len = 512 / 8;
  191. } else
  192. return -ENOPKG;
  193. ctx->algo_oid = algo;
  194. /* Parse SubjectPublicKeyInfo.AlgorithmIdentifier.parameters. */
  195. err = asn1_ber_decoder(&ecrdsa_params_decoder, ctx, params, paramlen);
  196. if (err < 0)
  197. return err;
  198. /*
  199. * Sizes of algo (set in digest_len) and curve should match
  200. * each other.
  201. */
  202. if (!ctx->curve ||
  203. ctx->curve->g.ndigits * sizeof(u64) != ctx->digest_len)
  204. return -ENOPKG;
  205. /*
  206. * Key is two 256- or 512-bit coordinates which should match
  207. * curve size.
  208. */
  209. if ((ctx->key_len != (2 * 256 / 8) &&
  210. ctx->key_len != (2 * 512 / 8)) ||
  211. ctx->key_len != ctx->curve->g.ndigits * sizeof(u64) * 2)
  212. return -ENOPKG;
  213. ndigits = ctx->key_len / sizeof(u64) / 2;
  214. ctx->pub_key = ECC_POINT_INIT(ctx->_pubp[0], ctx->_pubp[1], ndigits);
  215. vli_from_le64(ctx->pub_key.x, ctx->key, ndigits);
  216. vli_from_le64(ctx->pub_key.y, ctx->key + ndigits * sizeof(u64),
  217. ndigits);
  218. if (ecc_is_pubkey_valid_partial(ctx->curve, &ctx->pub_key))
  219. return -EKEYREJECTED;
  220. return 0;
  221. }
  222. static unsigned int ecrdsa_max_size(struct crypto_akcipher *tfm)
  223. {
  224. struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
  225. /*
  226. * Verify doesn't need any output, so it's just informational
  227. * for keyctl to determine the key bit size.
  228. */
  229. return ctx->pub_key.ndigits * sizeof(u64);
  230. }
  231. static void ecrdsa_exit_tfm(struct crypto_akcipher *tfm)
  232. {
  233. }
  234. static struct akcipher_alg ecrdsa_alg = {
  235. .verify = ecrdsa_verify,
  236. .set_pub_key = ecrdsa_set_pub_key,
  237. .max_size = ecrdsa_max_size,
  238. .exit = ecrdsa_exit_tfm,
  239. .base = {
  240. .cra_name = "ecrdsa",
  241. .cra_driver_name = "ecrdsa-generic",
  242. .cra_priority = 100,
  243. .cra_module = THIS_MODULE,
  244. .cra_ctxsize = sizeof(struct ecrdsa_ctx),
  245. },
  246. };
  247. static int __init ecrdsa_mod_init(void)
  248. {
  249. return crypto_register_akcipher(&ecrdsa_alg);
  250. }
  251. static void __exit ecrdsa_mod_fini(void)
  252. {
  253. crypto_unregister_akcipher(&ecrdsa_alg);
  254. }
  255. module_init(ecrdsa_mod_init);
  256. module_exit(ecrdsa_mod_fini);
  257. MODULE_LICENSE("GPL");
  258. MODULE_AUTHOR("Vitaly Chikunov <vt@altlinux.org>");
  259. MODULE_DESCRIPTION("EC-RDSA generic algorithm");
  260. MODULE_ALIAS_CRYPTO("ecrdsa-generic");