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