1 /*
2 * Copyright (C) 2019 Red Hat, Inc.
3 *
4 * Author: Daiki Ueno
5 *
6 * This file is part of GNUTLS.
7 *
8 * The GNUTLS library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public License
10 * as published by the Free Software Foundation; either version 2.1 of
11 * the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this program. If not, see <https://www.gnu.org/licenses/>
20 *
21 */
22
23 #if HAVE_CONFIG_H
24 # include "config.h"
25 #endif
26
27 #include "dsa-compute-k.h"
28
29 #include "gnutls_int.h"
30 #include "mem.h"
31 #include "mpn-base256.h"
32 #include <string.h>
33
34 #define BITS_TO_LIMBS(bits) (((bits) + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
35
36 /* The maximum size of q, choosen from the fact that we support
37 * 521-bit elliptic curve generator and 512-bit DSA subgroup at
38 * maximum. */
39 #define MAX_Q_BITS 521
40 #define MAX_Q_SIZE ((MAX_Q_BITS + 7) / 8)
41 #define MAX_Q_LIMBS BITS_TO_LIMBS(MAX_Q_BITS)
42
43 #define MAX_HASH_BITS (MAX_HASH_SIZE * 8)
44 #define MAX_HASH_LIMBS BITS_TO_LIMBS(MAX_HASH_BITS)
45
46 int
_gnutls_dsa_compute_k(mpz_t k,const mpz_t q,const mpz_t x,gnutls_mac_algorithm_t mac,const uint8_t * digest,size_t length)47 _gnutls_dsa_compute_k(mpz_t k,
48 const mpz_t q,
49 const mpz_t x,
50 gnutls_mac_algorithm_t mac,
51 const uint8_t *digest,
52 size_t length)
53 {
54 uint8_t V[MAX_HASH_SIZE];
55 uint8_t K[MAX_HASH_SIZE];
56 uint8_t xp[MAX_Q_SIZE];
57 uint8_t tp[MAX_Q_SIZE];
58 mp_limb_t h[MAX(MAX_Q_LIMBS, MAX_HASH_LIMBS)];
59 mp_bitcnt_t q_bits = mpz_sizeinbase (q, 2);
60 mp_size_t qn = mpz_size(q);
61 mp_bitcnt_t h_bits = length * 8;
62 mp_size_t hn = BITS_TO_LIMBS(h_bits);
63 size_t nbytes = (q_bits + 7) / 8;
64 const uint8_t c0 = 0x00;
65 const uint8_t c1 = 0x01;
66 mp_limb_t cy;
67 gnutls_hmac_hd_t hd;
68 int ret = 0;
69
70 if (unlikely(q_bits > MAX_Q_BITS))
71 return gnutls_assert_val(GNUTLS_E_INVALID_REQUEST);
72 if (unlikely(length > MAX_HASH_SIZE))
73 return gnutls_assert_val(GNUTLS_E_INVALID_REQUEST);
74
75 /* int2octets(x) */
76 mpn_get_base256(xp, nbytes, mpz_limbs_read(x), qn);
77
78 /* bits2octets(h) */
79 mpn_set_base256(h, hn, digest, length);
80
81 if (hn < qn)
82 /* qlen > blen: add zero bits to the left */
83 mpn_zero(&h[hn], qn - hn);
84 else if (h_bits > q_bits) {
85 /* qlen < blen: keep the leftmost qlen bits. We do this in 2
86 * steps because mpn_rshift only accepts shift count in the
87 * range 1 to mp_bits_per_limb-1.
88 */
89 mp_bitcnt_t shift = h_bits - q_bits;
90
91 if (shift / GMP_NUMB_BITS > 0) {
92 mpn_copyi(h, &h[shift / GMP_NUMB_BITS], qn);
93 hn -= shift / GMP_NUMB_BITS;
94 }
95
96 if (shift % GMP_NUMB_BITS > 0)
97 mpn_rshift(h, h, hn, shift % GMP_NUMB_BITS);
98 }
99
100 cy = mpn_sub_n(h, h, mpz_limbs_read(q), qn);
101 /* Fall back to addmul_1, if nettle is linked with mini-gmp. */
102 #ifdef mpn_cnd_add_n
103 mpn_cnd_add_n(cy, h, h, mpz_limbs_read(q), qn);
104 #else
105 mpn_addmul_1(h, mpz_limbs_read(q), qn, cy != 0);
106 #endif
107 mpn_get_base256(tp, nbytes, h, qn);
108
109 /* Step b */
110 memset(V, c1, length);
111
112 /* Step c */
113 memset(K, c0, length);
114
115 /* Step d */
116 ret = gnutls_hmac_init(&hd, mac, K, length);
117 if (ret < 0)
118 goto out;
119 ret = gnutls_hmac(hd, V, length);
120 if (ret < 0)
121 goto out;
122 ret = gnutls_hmac(hd, &c0, 1);
123 if (ret < 0)
124 goto out;
125 ret = gnutls_hmac(hd, xp, nbytes);
126 if (ret < 0)
127 goto out;
128 ret = gnutls_hmac(hd, tp, nbytes);
129 if (ret < 0)
130 goto out;
131 gnutls_hmac_deinit(hd, K);
132
133 /* Step e */
134 ret = gnutls_hmac_fast(mac, K, length, V, length, V);
135 if (ret < 0)
136 goto out;
137
138 /* Step f */
139 ret = gnutls_hmac_init(&hd, mac, K, length);
140 if (ret < 0)
141 goto out;
142 ret = gnutls_hmac(hd, V, length);
143 if (ret < 0)
144 goto out;
145 ret = gnutls_hmac(hd, &c1, 1);
146 if (ret < 0)
147 goto out;
148 ret = gnutls_hmac(hd, xp, nbytes);
149 if (ret < 0)
150 goto out;
151 ret = gnutls_hmac(hd, tp, nbytes);
152 if (ret < 0)
153 goto out;
154 gnutls_hmac_deinit(hd, K);
155
156 /* Step g */
157 ret = gnutls_hmac_fast(mac, K, length, V, length, V);
158 if (ret < 0)
159 goto out;
160
161 /* Step h */
162 for (;;) {
163 /* Step 1 */
164 size_t tlen = 0;
165
166 /* Step 2 */
167 while (tlen < nbytes) {
168 size_t remaining = MIN(nbytes - tlen, length);
169 ret = gnutls_hmac_fast(mac, K, length, V, length, V);
170 if (ret < 0)
171 goto out;
172 memcpy (&tp[tlen], V, remaining);
173 tlen += remaining;
174 }
175
176 /* Step 3 */
177 mpn_set_base256 (h, qn, tp, tlen);
178 if (tlen * 8 > q_bits)
179 mpn_rshift (h, h, qn, tlen * 8 - q_bits);
180 /* Check if k is in [1,q-1] */
181 if (!mpn_zero_p (h, qn) &&
182 mpn_cmp (h, mpz_limbs_read(q), qn) < 0) {
183 mpn_copyi(mpz_limbs_write(k, qn), h, qn);
184 mpz_limbs_finish(k, qn);
185 break;
186 }
187
188 ret = gnutls_hmac_init(&hd, mac, K, length);
189 if (ret < 0)
190 goto out;
191 ret = gnutls_hmac(hd, V, length);
192 if (ret < 0)
193 goto out;
194 ret = gnutls_hmac(hd, &c0, 1);
195 if (ret < 0)
196 goto out;
197 gnutls_hmac_deinit(hd, K);
198
199 ret = gnutls_hmac_fast(mac, K, length, V, length, V);
200 if (ret < 0)
201 goto out;
202 }
203
204 out:
205 zeroize_key(xp, sizeof(xp));
206 zeroize_key(tp, sizeof(tp));
207
208 return ret;
209 }
210