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