1 /*
2 * Copyright (C) 2017 - This file is part of libecc project
3 *
4 * Authors:
5 * Ryad BENADJILA <ryadbenadjila@gmail.com>
6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
7 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
8 *
9 * Contributors:
10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
12 *
13 * This software is licensed under a dual BSD and GPL v2 license.
14 * See LICENSE file at the root folder of the project.
15 */
16 #include <libecc/lib_ecc_config.h>
17 #include <libecc/libec.h>
18
19 /* We include the printf external dependency for printf output */
20 #include <libecc/external_deps/print.h>
21
22 /*
23 * The purpose of this example is to implement a 'toy'
24 * ECDH (Elliptic curve Diffie-Hellman) protocol. Alice
25 * and Bob want to derive a secret 'x' without sharing the
26 * same secret key (using asymmetric cryptography). In order
27 * to do this, they agree upon a public Elliptic Curve with
28 * a generator G. Alice (resp. Bob) generates a private value
29 * d_Alice (resp. d_Bob) < q, where q is the order of G.
30 * Alice (resp. Bob) computes and shares Q_Alice = d_Alice x G
31 * (resp. Q_Bob = d_Bob x G) over a public channel. Alice
32 * and Bob now both can compute the same point Q such that
33 * Q = d_Alice x Q_Bob = d_Bob x Q_Alice, and the shared
34 * secret 'x' is the first coordinate of the curve point Q.
35 * External passive observers cannot compute 'x'.
36 *
37 * NOTE: We don't seek for communication bandwidth
38 * optimization here, this is why we use arrays to
39 * exchange affine coordinates points (and not
40 * the compressed x coordinate since the
41 * curve equation can be used).
42 *
43 * XXX NOTE: for a robust implementation of the ECDH
44 * primitives, please use the APIs provided in src/ecdh
45 * of libecc as they are suitable for "production". The
46 * purpose of the current toy example is only to show how
47 * one can manipulate the curve level APIs.
48 *
49 */
50
51 /* Zero buffer to detect empty buffers */
52 static u8 zero[2 * NN_MAX_BYTE_LEN] = { 0 };
53
54 /*
55 * The following global variables simulate our shared "data bus"
56 * where Alice and Bob exchange data.
57 */
58
59 /* Global array holding Alice to Bob public value
60 * Q_Alice = d_Alice x G.
61 * This is a serialized affine EC point, holding
62 * 2 coordinates, meaning that its maximum size is
63 * 2 * NN_MAX_BYTE_LEN (i.e. this will work for
64 * all our curves).
65 */
66 static u8 Alice_to_Bob[2 * NN_MAX_BYTE_LEN] = { 0 };
67
68 /* Global array holding Bob to Alice public value
69 * Q_Bob = d_Bob x G.
70 * This is a serialized affine EC point, holding
71 * 2 coordinates, meaning that its maximum size is
72 * 2 * NN_MAX_BYTE_LEN. (i.e. this will work for
73 * all our curves).
74 */
75 static u8 Bob_to_Alice[2 * NN_MAX_BYTE_LEN] = { 0 };
76
77 static const u8 Alice[] = "Alice";
78 static const u8 Bob[] = "Bob";
79 #define CHECK_SIZE LOCAL_MIN(sizeof(Alice), sizeof(Bob))
80
81 ATTRIBUTE_WARN_UNUSED_RET int ECDH_helper(const u8 *curve_name, const u8 *role);
ECDH_helper(const u8 * curve_name,const u8 * role)82 int ECDH_helper(const u8 *curve_name, const u8 *role)
83 {
84 int ret, check1, check2;
85 /* The projective point we will use */
86 prj_pt Q;
87 /* The private scalar value for Alice and Bob, as well as their
88 * respective shared secrets.
89 * These are 'static' in order to keep them across multiple calls
90 * of the function.
91 */
92 static nn d_Alice, d_Bob;
93 nn_t d = NULL;
94 static fp x_Alice, x_Bob;
95 fp_t x = NULL;
96 const char *x_str;
97 /* Pointers to the communication buffers */
98 u8 *our_public_buffer, *other_public_buffer;
99 u32 len;
100
101 const ec_str_params *the_curve_const_parameters;
102 /* libecc internal structure holding the curve parameters */
103 ec_params curve_params;
104
105 Q.magic = WORD(0);
106
107 MUST_HAVE((curve_name != NULL) && (role != NULL), ret, err);
108
109 /****** Alice => Bob *********************************************************/
110 ret = are_equal(role, Alice, CHECK_SIZE, &check1); EG(ret, err);
111 ret = are_equal(role, Bob, CHECK_SIZE, &check2); EG(ret, err);
112 if (check1) {
113 our_public_buffer = Alice_to_Bob;
114 other_public_buffer = Bob_to_Alice;
115 d = &d_Alice;
116 x = &x_Alice;
117 x_str = " x_Alice";
118 }
119 /****** Bob => Alice *********************************************************/
120 else if (check2) {
121 our_public_buffer = Bob_to_Alice;
122 other_public_buffer = Alice_to_Bob;
123 d = &d_Bob;
124 x = &x_Bob;
125 x_str = " x_Bob ";
126 }
127 else {
128 /* Unknown role, get out */
129 ext_printf(" Error: unknown role %s for ECDH\n", role);
130 ret = -1;
131 goto err;
132 }
133
134 /* Importing specific curve parameters from the constant static
135 * buffers describing it:
136 * It is possible to import a curve set of parameters by its name.
137 */
138 ret = local_strnlen((const char *)curve_name, MAX_CURVE_NAME_LEN, &len); EG(ret, err);
139 len += 1;
140 MUST_HAVE((len < 256), ret, err);
141 ret = ec_get_curve_params_by_name(curve_name,
142 (u8)len, &the_curve_const_parameters); EG(ret, err);
143 /* Get out if getting the parameters went wrong */
144 if (the_curve_const_parameters == NULL) {
145 ext_printf(" Error: error when importing curve %s "
146 "parameters ...\n", curve_name);
147 ret = -1;
148 goto err;
149 }
150 /* Now map the curve parameters to our libecc internal representation */
151 ret = import_params(&curve_params, the_curve_const_parameters); EG(ret, err);
152
153 /* Initialize our projective point with the curve parameters */
154 ret = prj_pt_init(&Q, &(curve_params.ec_curve)); EG(ret, err);
155 ret = are_equal(our_public_buffer, zero, sizeof(zero), &check1); EG(ret, err);
156 if (!check1) {
157 /* We have already generated and sent our parameters, skip to
158 * the state where we wait for the other party to generate and
159 * send us data.
160 */
161 goto generate_shared_secret;
162 }
163
164 /* Generate our ECDH parameters: a private scalar d and a public value Q = dG where G is the
165 * curve generator.
166 * d = random mod (q) where q is the order of the generator G.
167 */
168 ret = nn_init(d, 0); EG(ret, err);
169 ret = nn_get_random_mod(d, &(curve_params.ec_gen_order)); EG(ret, err);
170
171 /* Q = dG */
172 ret = prj_pt_mul(&Q, d, &(curve_params.ec_gen)); EG(ret, err);
173
174 /* Now send the public value Q to the other party, get the other party
175 * public value and compute the shared secret.
176 * Our export size is exactly 2 coordinates in Fp (affine point representation),
177 * so this should be 2 times the size of an element in Fp.
178 */
179 ret = prj_pt_export_to_aff_buf(&Q, our_public_buffer,
180 (u32)(2 * BYTECEIL(curve_params.ec_fp.p_bitlen))); EG(ret, err);
181
182 generate_shared_secret:
183 /* Now (non blocking) wait for the other party to send us its public value */
184 ret = are_equal(other_public_buffer, zero, sizeof(zero), &check1); EG(ret, err);
185 if (check1) {
186 /* Other party has not sent its public value yet! */
187 ret = 0;
188 goto err;
189 }
190 /* If our private value d is not initialized, this means that we have already
191 * done the job of computing the shared secret!
192 */
193 if (nn_check_initialized(d)) {
194 ret = 1;
195 goto err;
196 }
197 /* Import the shared value as a projective point from an affine point buffer
198 */
199 ret = prj_pt_import_from_aff_buf(&Q, other_public_buffer,
200 (u16)(2 * BYTECEIL(curve_params.ec_fp.p_bitlen)),
201 &(curve_params.ec_curve)); EG(ret, err);
202 /* Compute the shared value = first coordinate of dQ */
203 ret = prj_pt_mul(&Q, d, &Q); EG(ret, err);
204 /* Move to the unique representation */
205 /* Compute the affine coordinates to get the unique (x, y) representation
206 * (projective points are equivalent by a z scalar)
207 */
208 ret = prj_pt_unique(&Q, &Q); EG(ret, err);
209 ext_printf(" ECDH shared secret computed by %s:\n", role);
210 /* The shared secret 'x' is the first coordinate of Q */
211 ret = fp_init(x, &(curve_params.ec_fp)); EG(ret, err);
212 ret = fp_copy(x, &(Q.X)); EG(ret, err);
213 fp_print(x_str, x);
214
215 ret = 1;
216
217 /* Uninit local variables */
218 prj_pt_uninit(&Q);
219 if(x != NULL){
220 fp_uninit(x);
221 }
222 if(d != NULL){
223 nn_uninit(d);
224 }
225
226 err:
227 return ret;
228 }
229
230 #ifdef CURVE_ECDH
main(int argc,char * argv[])231 int main(int argc, char *argv[])
232 {
233 unsigned int i;
234 u8 curve_name[MAX_CURVE_NAME_LEN] = { 0 };
235 int ret;
236 FORCE_USED_VAR(argc);
237 FORCE_USED_VAR(argv);
238
239 /* Traverse all the possible curves we have at our disposal (known curves and
240 * user defined curves).
241 */
242 for (i = 0; i < EC_CURVES_NUM; i++) {
243 ret = local_memset(Alice_to_Bob, 0, sizeof(Alice_to_Bob)); EG(ret, err);
244 ret = local_memset(Bob_to_Alice, 0, sizeof(Bob_to_Alice)); EG(ret, err);
245 /* All our possible curves are in ../curves/curves_list.h
246 * We can get the curve name from its internal type.
247 */
248 if(ec_get_curve_name_by_type(ec_maps[i].type, curve_name,
249 sizeof(curve_name))){
250 ret = -1;
251 ext_printf("Error: error when treating %s\n", curve_name);
252 goto err;
253 }
254 /* Perform ECDH between Alice and Bob! */
255 ext_printf("[+] ECDH on curve %s\n", curve_name);
256 if(ECDH_helper(curve_name, Alice) != 0){
257 ret = -1;
258 ext_printf("Error: error in ECDH_helper\n");
259 goto err;
260 }
261 if(ECDH_helper(curve_name, Bob) != 1){
262 ret = -1;
263 ext_printf("Error: error in ECDH_helper\n");
264 goto err;
265 }
266 /* We have to call our ECDH helper again for Alice
267 * since she was waiting for Bob to send his public data.
268 * This is our loose way of dealing with 'concurrency'
269 * without threads ...
270 */
271 if(ECDH_helper(curve_name, Alice) != 1){
272 ret = -1;
273 ext_printf("Error: error in ECDH_helper\n");
274 goto err;
275 }
276 ext_printf("==================================\n");
277 }
278
279 ret = 0;
280
281 err:
282 return ret;
283 }
284 #endif /* CURVE_ECDH */
285