1 /*
2 * Copyright (C) 2021 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "crypto_hash_to_point.h"
17 #include <openssl/bn.h>
18 #include <openssl/evp.h>
19 #include <openssl/rand.h>
20 #include "hal_error.h"
21 #include "hc_log.h"
22 #include "hc_types.h"
23 #include "hks_type.h"
24
25 #define KEY_BYTES_CURVE25519 32
26
27 struct CurveConstPara {
28 BIGNUM *p;
29 BIGNUM *one;
30 BIGNUM *d;
31 BIGNUM *k;
32 BIGNUM *capitalA;
33 BIGNUM *minusA;
34 BIGNUM *u;
35 BIGNUM *q;
36 };
37
38 /* RFC 8032, the prime of Curve25519, p = 2^255-19 */
39 static const uint8_t g_curveParamP[KEY_BYTES_CURVE25519] = {
40 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
41 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
42 };
43
44 /* RFC 8032, one = 1 */
45 static const uint8_t g_curveParamOne[KEY_BYTES_CURVE25519] = {
46 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
47 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01
48 };
49
50 /* RFC 8032, A non-zero element in the finite field GF(p), not equal to 1 */
51 static const uint8_t g_curveParamD[KEY_BYTES_CURVE25519] = {
52 0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75, 0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
53 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c, 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52
54 };
55
56 /* RFC 8032, k = (p - 1) / 2 */
57 static const uint8_t g_curveParamK[KEY_BYTES_CURVE25519] = {
58 0xf6, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
59 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f
60 };
61
62 /* RFC 8032, A = 486662 */
63 static const uint8_t g_curveParamCapitalA[KEY_BYTES_CURVE25519] = {
64 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
65 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x6d, 0x06
66 };
67
68 /* RFC 8032, -A = -486662 */
69 static const uint8_t g_curveParamMinusA[KEY_BYTES_CURVE25519] = {
70 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
71 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x92, 0xe7
72 };
73
74 /* RFC 8032, u = 2 */
75 static const uint8_t g_curveParamU[KEY_BYTES_CURVE25519] = {
76 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
77 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02
78 };
79
80 /* RFC 8032, q = endian_swap(k) */
81 static const uint8_t g_curveParamQ[KEY_BYTES_CURVE25519] = {
82 0x3f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
83 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf6
84 };
85
CurveInitConstPara(struct CurveConstPara * para)86 static void CurveInitConstPara(struct CurveConstPara *para)
87 {
88 para->p = BN_new();
89 para->one = BN_new();
90 para->d = BN_new();
91 para->k = BN_new();
92 para->capitalA = BN_new();
93 para->minusA = BN_new();
94 para->u = BN_new();
95 para->q = BN_new();
96 }
97
CurveFreeConstPara(struct CurveConstPara * para)98 static void CurveFreeConstPara(struct CurveConstPara *para)
99 {
100 BN_free(para->p);
101 BN_free(para->one);
102 BN_free(para->d);
103 BN_free(para->k);
104 BN_free(para->capitalA);
105 BN_free(para->minusA);
106 BN_free(para->u);
107 BN_free(para->q);
108 }
109
110 /* b := -A / (1 + u * a ^ 2) */
CurveHashToPointCalcB(const struct HksBlob * hash,const struct CurveConstPara * curvePara,BIGNUM * b,BN_CTX * ctx)111 static int32_t CurveHashToPointCalcB(const struct HksBlob *hash,
112 const struct CurveConstPara *curvePara, BIGNUM *b, BN_CTX *ctx)
113 {
114 BIGNUM *swap = BN_new();
115 int32_t ret = HAL_FAILED;
116 do {
117 if (BN_bin2bn(hash->data, hash->size, swap) == NULL) {
118 break;
119 }
120 if (BN_mul(b, swap, swap, ctx) <= 0) {
121 break;
122 }
123 if (BN_mod(b, b, curvePara->p, ctx) <= 0) {
124 break;
125 }
126 if (BN_mul(swap, b, curvePara->u, ctx) <= 0) {
127 break;
128 }
129 if (BN_mod(swap, swap, curvePara->p, ctx) <= 0) {
130 break;
131 }
132 if (BN_add(b, swap, curvePara->one) <= 0) {
133 break;
134 }
135 if (BN_mod(b, b, curvePara->p, ctx) <= 0) {
136 break;
137 }
138 if (BN_mod_inverse(swap, b, curvePara->p, ctx) <= 0) {
139 break;
140 }
141 if (BN_mul(b, swap, curvePara->minusA, ctx) <= 0) {
142 break;
143 }
144 if (BN_mod(b, b, curvePara->p, ctx) <= 0) {
145 break;
146 }
147 ret = HAL_SUCCESS;
148 } while (0);
149 BN_free(swap);
150 return ret;
151 }
152
CurveHashToPointCalcA(const BIGNUM * b,const struct CurveConstPara * curvePara,BIGNUM * a,BN_CTX * ctx)153 static int32_t CurveHashToPointCalcA(const BIGNUM *b,
154 const struct CurveConstPara *curvePara, BIGNUM *a, BN_CTX *ctx)
155 {
156 BIGNUM *swap = BN_new();
157 BIGNUM *result = BN_new();
158 int32_t ret = HAL_FAILED;
159
160 do {
161 if (BN_mul(result, b, b, ctx) <= 0) {
162 break;
163 }
164 if (BN_mod(result, result, curvePara->p, ctx) <= 0) {
165 break;
166 }
167 if (BN_mul(swap, result, b, ctx) <= 0) {
168 break;
169 }
170 if (BN_mod(swap, swap, curvePara->p, ctx) <= 0) {
171 break;
172 }
173 if (BN_mul(a, result, curvePara->capitalA, ctx) <= 0) {
174 break;
175 }
176 if (BN_mod(a, a, curvePara->p, ctx) <= 0) {
177 break;
178 }
179 if (BN_add(result, swap, a) <= 0) {
180 break;
181 }
182 if (BN_mod(result, result, curvePara->p, ctx) <= 0) {
183 break;
184 }
185 if (BN_add(a, result, b) <= 0) {
186 break;
187 }
188 if (BN_mod(a, a, curvePara->p, ctx) <= 0) {
189 break;
190 }
191 ret = HAL_SUCCESS;
192 } while (0);
193
194 BN_free(swap);
195 BN_free(result);
196 return ret;
197 }
198
CurveHashToPointCalcC(const BIGNUM * a,BIGNUM * b,const struct CurveConstPara * curvePara,BIGNUM * c,BN_CTX * ctx)199 static int32_t CurveHashToPointCalcC(const BIGNUM *a, BIGNUM *b,
200 const struct CurveConstPara *curvePara, BIGNUM *c, BN_CTX *ctx)
201 {
202 BIGNUM *result = BN_new();
203 int32_t ret = HAL_FAILED;
204
205 do {
206 /* If a is a quadratic residue modulo p, c := b and high_y := 1 Otherwise c := -b - A and high_y := 0 */
207 if (BN_sub(c, curvePara->p, b) <= 0) {
208 break;
209 }
210 if (BN_mod(c, c, curvePara->p, ctx) <= 0) {
211 break;
212 }
213 if (BN_add(c, c, curvePara->minusA) <= 0) {
214 break;
215 }
216 if (BN_mod(c, c, curvePara->p, ctx) <= 0) {
217 break;
218 }
219 /* Sliding-window exponentiation: result = a^q mod p */
220 if (BN_mod_exp(result, a, curvePara->q, curvePara->p, ctx) <= 0) {
221 break;
222 }
223 if (BN_cmp(curvePara->q, result) > 0) {
224 BN_swap(b, c);
225 }
226 ret = HAL_SUCCESS;
227 } while (0);
228
229 BN_free(result);
230 return ret;
231 }
232
CurveSetConstPara(struct CurveConstPara * para)233 static int32_t CurveSetConstPara(struct CurveConstPara *para)
234 {
235 int32_t ret = HAL_FAILED;
236 do {
237 if (BN_bin2bn(g_curveParamP, KEY_BYTES_CURVE25519, para->p) == NULL) {
238 break;
239 }
240 if (BN_bin2bn(g_curveParamOne, KEY_BYTES_CURVE25519, para->one) == NULL) {
241 break;
242 }
243 if (BN_bin2bn(g_curveParamD, KEY_BYTES_CURVE25519, para->d) == NULL) {
244 break;
245 }
246 if (BN_bin2bn(g_curveParamK, KEY_BYTES_CURVE25519, para->k) == NULL) {
247 break;
248 }
249 if (BN_bin2bn(g_curveParamCapitalA, KEY_BYTES_CURVE25519, para->capitalA) == NULL) {
250 break;
251 }
252 if (BN_bin2bn(g_curveParamMinusA, KEY_BYTES_CURVE25519, para->minusA) == NULL) {
253 break;
254 }
255 if (BN_bin2bn(g_curveParamU, KEY_BYTES_CURVE25519, para->u) == NULL) {
256 break;
257 }
258 if (BN_bin2bn(g_curveParamQ, KEY_BYTES_CURVE25519, para->q) == NULL) {
259 break;
260 }
261 ret = HAL_SUCCESS;
262 } while (0);
263
264 return ret;
265 }
266
CurveHashToPoint(const struct HksBlob * hash,struct HksBlob * point)267 static int32_t CurveHashToPoint(const struct HksBlob *hash, struct HksBlob *point)
268 {
269 if ((hash == NULL) || (hash->data == NULL) ||
270 (hash->size != KEY_BYTES_CURVE25519)) {
271 return HAL_ERR_NULL_PTR;
272 }
273 if ((point == NULL) || (point->data == NULL) ||
274 (point->size != KEY_BYTES_CURVE25519)) {
275 return HAL_ERR_NULL_PTR;
276 }
277
278 BIGNUM *a = BN_new();
279 BIGNUM *b = BN_new();
280 BIGNUM *c = BN_new();
281 struct CurveConstPara curvePara;
282 (void)memset_s(&curvePara, sizeof(curvePara), 0, sizeof(curvePara));
283 CurveInitConstPara(&curvePara);
284 int32_t ret;
285 BN_CTX *ctx = BN_CTX_new();
286 if (ctx == NULL) {
287 ret = HAL_ERR_BAD_ALLOC;
288 goto ERR;
289 }
290 do {
291 ret = CurveSetConstPara(&curvePara);
292 if (ret != HAL_SUCCESS) {
293 break;
294 }
295 ret = CurveHashToPointCalcB(hash, &curvePara, b, ctx);
296 if (ret != HAL_SUCCESS) {
297 break;
298 }
299
300 ret = CurveHashToPointCalcA(b, &curvePara, a, ctx);
301 if (ret != HAL_SUCCESS) {
302 break;
303 }
304
305 ret = CurveHashToPointCalcC(a, b, &curvePara, c, ctx);
306 if (ret != HAL_SUCCESS) {
307 break;
308 }
309
310 if (BN_bn2bin(c, point->data) <= 0) {
311 ret = HAL_FAILED;
312 }
313 } while (0);
314 ERR:
315 CurveFreeConstPara(&curvePara);
316 BN_free(a);
317 BN_free(b);
318 BN_free(c);
319 BN_CTX_free(ctx);
320 return ret;
321 }
322
EndianSwap(struct HksBlob * data)323 static int32_t EndianSwap(struct HksBlob *data)
324 {
325 if (data->data == NULL) {
326 return HAL_ERR_NULL_PTR;
327 }
328
329 if (data->size == 0) {
330 return HAL_ERR_NULL_PTR;
331 }
332
333 int32_t end = data->size - 1;
334 const int32_t start = 0;
335
336 /* count the middle index of array */
337 int32_t cnt = data->size / 2; // 2 used to calculate half of the data size
338
339 for (int32_t i = 0; i < cnt; i++) {
340 uint8_t tmp;
341 tmp = data->data[start + i];
342 data->data[start + i] = data->data[end - i];
343 data->data[end - i] = tmp;
344 }
345 return HAL_SUCCESS;
346 }
347
OpensslHashToPoint(const struct HksBlob * hash,struct HksBlob * point)348 int32_t OpensslHashToPoint(const struct HksBlob *hash, struct HksBlob *point)
349 {
350 int32_t ret = HAL_FAILED;
351 uint8_t *copyData = HcMalloc(hash->size, 0);
352 if (copyData == NULL) {
353 LOGE("malloc size %u failed", hash->size);
354 return HKS_ERROR_MALLOC_FAIL;
355 }
356 struct HksBlob hashCopy = { hash->size, copyData};
357
358 do {
359 if (memcpy_s(hashCopy.data, hashCopy.size, hash->data, hash->size) != EOK) {
360 break;
361 }
362
363 hashCopy.data[hashCopy.size - 1] &= 0x3f; /* RFC 8032 */
364 ret = EndianSwap(&hashCopy);
365 if (ret != HAL_SUCCESS) {
366 LOGE("swap endian before convert failed");
367 break;
368 }
369
370 ret = CurveHashToPoint(&hashCopy, point);
371 if (ret != HAL_SUCCESS) {
372 LOGE("curve hash to point failed");
373 break;
374 }
375
376 ret = EndianSwap(point);
377 if (ret != HAL_SUCCESS) {
378 LOGE("swap endian after convert failed");
379 break;
380 }
381 } while (0);
382 HcFree(hashCopy.data);
383 return ret;
384 }