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); 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 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