crypto/property/property.c

   1 /*
   2  * Copyright 2019-2021 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
   4  *
   5  * Licensed under the Apache License 2.0 (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  */
  10
  11 #include <string.h>
  12 #include <stdio.h>
  13 #include <stdarg.h>
  14 #include <openssl/crypto.h>
  15 #include "internal/core.h"
  16 #include "internal/property.h"
  17 #include "internal/provider.h"
  18 #include "crypto/ctype.h"
  19 #include <openssl/lhash.h>
  20 #include <openssl/rand.h>
  21 #include "internal/thread_once.h"
  22 #include "crypto/lhash.h"
  23 #include "crypto/sparse_array.h"
  24 #include "property_local.h"
  25
  26 /*
  27  * The number of elements in the query cache before we initiate a flush.
  28  * If reducing this, also ensure the stochastic test in test/property_test.c
  29  * isn't likely to fail.
  30  */
  31 #define IMPL_CACHE_FLUSH_THRESHOLD  500
  32
  33 typedef struct {
  34     void *method;
  35     int (*up_ref)(void *);
  36     void (*free)(void *);
  37 } METHOD;
  38
  39 typedef struct {
  40     const OSSL_PROVIDER *provider;
  41     OSSL_PROPERTY_LIST *properties;
  42     METHOD method;
  43 } IMPLEMENTATION;
  44
  45 DEFINE_STACK_OF(IMPLEMENTATION)
  46
  47 typedef struct {
  48     const char *query;
  49     METHOD method;
  50     char body[1];
  51 } QUERY;
  52
  53 DEFINE_LHASH_OF(QUERY);
  54
  55 typedef struct {
  56     int nid;
  57     STACK_OF(IMPLEMENTATION) *impls;
  58     LHASH_OF(QUERY) *cache;
  59 } ALGORITHM;
  60
  61 struct ossl_method_store_st {
  62     OSSL_LIB_CTX *ctx;
  63     size_t nelem;
  64     SPARSE_ARRAY_OF(ALGORITHM) *algs;
  65     int need_flush;
  66     CRYPTO_RWLOCK *lock;
  67 };
  68
  69 typedef struct {
  70     LHASH_OF(QUERY) *cache;
  71     size_t nelem;
  72     uint32_t seed;
  73 } IMPL_CACHE_FLUSH;
  74
  75 DEFINE_SPARSE_ARRAY_OF(ALGORITHM);
  76
  77 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid);
  78
  79 /* Global properties are stored per library context */
  80 static void ossl_ctx_global_properties_free(void *vstore)
  81 {
  82     OSSL_PROPERTY_LIST **plp = vstore;
  83
  84     if (plp != NULL) {
  85         ossl_property_free(*plp);
  86         OPENSSL_free(plp);
  87     }
  88 }
  89
  90 static void *ossl_ctx_global_properties_new(OSSL_LIB_CTX *ctx)
  91 {
  92     return OPENSSL_zalloc(sizeof(OSSL_PROPERTY_LIST **));
  93 }
  94
  95
  96 static const OSSL_LIB_CTX_METHOD ossl_ctx_global_properties_method = {
  97     OSSL_LIB_CTX_METHOD_DEFAULT_PRIORITY,
  98     ossl_ctx_global_properties_new,
  99     ossl_ctx_global_properties_free,
 100 };
 101
 102 OSSL_PROPERTY_LIST **ossl_ctx_global_properties(OSSL_LIB_CTX *libctx,
 103                                                 int loadconfig)
 104 {
 105 #ifndef FIPS_MODULE
 106     if (loadconfig && !OPENSSL_init_crypto(OPENSSL_INIT_LOAD_CONFIG, NULL))
 107         return NULL;
 108 #endif
 109     return ossl_lib_ctx_get_data(libctx, OSSL_LIB_CTX_GLOBAL_PROPERTIES,
 110                                  &ossl_ctx_global_properties_method);
 111 }
 112
 113 static int ossl_method_up_ref(METHOD *method)
 114 {
 115     return (*method->up_ref)(method->method);
 116 }
 117
 118 static void ossl_method_free(METHOD *method)
 119 {
 120     (*method->free)(method->method);
 121 }
 122
 123 static __owur int ossl_property_read_lock(OSSL_METHOD_STORE *p)
 124 {
 125     return p != NULL ? CRYPTO_THREAD_read_lock(p->lock) : 0;
 126 }
 127
 128 static __owur int ossl_property_write_lock(OSSL_METHOD_STORE *p)
 129 {
 130     return p != NULL ? CRYPTO_THREAD_write_lock(p->lock) : 0;
 131 }
 132
 133 static int ossl_property_unlock(OSSL_METHOD_STORE *p)
 134 {
 135     return p != 0 ? CRYPTO_THREAD_unlock(p->lock) : 0;
 136 }
 137
 138 static unsigned long query_hash(const QUERY *a)
 139 {
 140     return OPENSSL_LH_strhash(a->query);
 141 }
 142
 143 static int query_cmp(const QUERY *a, const QUERY *b)
 144 {
 145     return strcmp(a->query, b->query);
 146 }
 147
 148 static void impl_free(IMPLEMENTATION *impl)
 149 {
 150     if (impl != NULL) {
 151         ossl_method_free(&impl->method);
 152         OPENSSL_free(impl);
 153     }
 154 }
 155
 156 static void impl_cache_free(QUERY *elem)
 157 {
 158     if (elem != NULL) {
 159         ossl_method_free(&elem->method);
 160         OPENSSL_free(elem);
 161     }
 162 }
 163
 164 static void alg_cleanup(ossl_uintmax_t idx, ALGORITHM *a)
 165 {
 166     if (a != NULL) {
 167         sk_IMPLEMENTATION_pop_free(a->impls, &impl_free);
 168         lh_QUERY_doall(a->cache, &impl_cache_free);
 169         lh_QUERY_free(a->cache);
 170         OPENSSL_free(a);
 171     }
 172 }
 173
 174 /*
 175  * The OSSL_LIB_CTX param here allows access to underlying property data needed
 176  * for computation
 177  */
 178 OSSL_METHOD_STORE *ossl_method_store_new(OSSL_LIB_CTX *ctx)
 179 {
 180     OSSL_METHOD_STORE *res;
 181
 182     res = OPENSSL_zalloc(sizeof(*res));
 183     if (res != NULL) {
 184         res->ctx = ctx;
 185         if ((res->algs = ossl_sa_ALGORITHM_new()) == NULL) {
 186             OPENSSL_free(res);
 187             return NULL;
 188         }
 189         if ((res->lock = CRYPTO_THREAD_lock_new()) == NULL) {
 190             ossl_sa_ALGORITHM_free(res->algs);
 191             OPENSSL_free(res);
 192             return NULL;
 193         }
 194     }
 195     return res;
 196 }
 197
 198 void ossl_method_store_free(OSSL_METHOD_STORE *store)
 199 {
 200     if (store != NULL) {
 201         ossl_sa_ALGORITHM_doall(store->algs, &alg_cleanup);
 202         ossl_sa_ALGORITHM_free(store->algs);
 203         CRYPTO_THREAD_lock_free(store->lock);
 204         OPENSSL_free(store);
 205     }
 206 }
 207
 208 static ALGORITHM *ossl_method_store_retrieve(OSSL_METHOD_STORE *store, int nid)
 209 {
 210     return ossl_sa_ALGORITHM_get(store->algs, nid);
 211 }
 212
 213 static int ossl_method_store_insert(OSSL_METHOD_STORE *store, ALGORITHM *alg)
 214 {
 215         return ossl_sa_ALGORITHM_set(store->algs, alg->nid, alg);
 216 }
 217
 218 int ossl_method_store_add(OSSL_METHOD_STORE *store, const OSSL_PROVIDER *prov,
 219                           int nid, const char *properties, void *method,
 220                           int (*method_up_ref)(void *),
 221                           void (*method_destruct)(void *))
 222 {
 223     ALGORITHM *alg = NULL;
 224     IMPLEMENTATION *impl;
 225     int ret = 0;
 226     int i;
 227
 228     if (nid <= 0 || method == NULL || store == NULL)
 229         return 0;
 230     if (properties == NULL)
 231         properties = "";
 232
 233     /* Create new entry */
 234     impl = OPENSSL_malloc(sizeof(*impl));
 235     if (impl == NULL)
 236         return 0;
 237     impl->method.method = method;
 238     impl->method.up_ref = method_up_ref;
 239     impl->method.free = method_destruct;
 240     if (!ossl_method_up_ref(&impl->method)) {
 241         OPENSSL_free(impl);
 242         return 0;
 243     }
 244     impl->provider = prov;
 245
 246     /*
 247      * Insert into the hash table if required.
 248      *
 249      * A write lock is used unconditionally because we wend our way down to the
 250      * property string code which isn't locking friendly.
 251      */
 252     if (!ossl_property_write_lock(store)) {
 253         OPENSSL_free(impl);
 254         return 0;
 255     }
 256     ossl_method_cache_flush(store, nid);
 257     if ((impl->properties = ossl_prop_defn_get(store->ctx, properties)) == NULL) {
 258         impl->properties = ossl_parse_property(store->ctx, properties);
 259         if (impl->properties == NULL)
 260             goto err;
 261         ossl_prop_defn_set(store->ctx, properties, impl->properties);
 262     }
 263
 264     alg = ossl_method_store_retrieve(store, nid);
 265     if (alg == NULL) {
 266         if ((alg = OPENSSL_zalloc(sizeof(*alg))) == NULL
 267                 || (alg->impls = sk_IMPLEMENTATION_new_null()) == NULL
 268                 || (alg->cache = lh_QUERY_new(&query_hash, &query_cmp)) == NULL)
 269             goto err;
 270         alg->nid = nid;
 271         if (!ossl_method_store_insert(store, alg))
 272             goto err;
 273     }
 274
 275     /* Push onto stack if there isn't one there already */
 276     for (i = 0; i < sk_IMPLEMENTATION_num(alg->impls); i++) {
 277         const IMPLEMENTATION *tmpimpl = sk_IMPLEMENTATION_value(alg->impls, i);
 278
 279         if (tmpimpl->provider == impl->provider
 280             && tmpimpl->properties == impl->properties)
 281             break;
 282     }
 283     if (i == sk_IMPLEMENTATION_num(alg->impls)
 284         && sk_IMPLEMENTATION_push(alg->impls, impl))
 285         ret = 1;
 286     ossl_property_unlock(store);
 287     if (ret == 0)
 288         impl_free(impl);
 289     return ret;
 290
 291 err:
 292     ossl_property_unlock(store);
 293     alg_cleanup(0, alg);
 294     impl_free(impl);
 295     return 0;
 296 }
 297
 298 int ossl_method_store_remove(OSSL_METHOD_STORE *store, int nid,
 299                              const void *method)
 300 {
 301     ALGORITHM *alg = NULL;
 302     int i;
 303
 304     if (nid <= 0 || method == NULL || store == NULL)
 305         return 0;
 306
 307     if (!ossl_property_write_lock(store))
 308         return 0;
 309     ossl_method_cache_flush(store, nid);
 310     alg = ossl_method_store_retrieve(store, nid);
 311     if (alg == NULL) {
 312         ossl_property_unlock(store);
 313         return 0;
 314     }
 315
 316     /*
 317      * A sorting find then a delete could be faster but these stacks should be
 318      * relatively small, so we avoid the overhead.  Sorting could also surprise
 319      * users when result orderings change (even though they are not guaranteed).
 320      */
 321     for (i = 0; i < sk_IMPLEMENTATION_num(alg->impls); i++) {
 322         IMPLEMENTATION *impl = sk_IMPLEMENTATION_value(alg->impls, i);
 323
 324         if (impl->method.method == method) {
 325             impl_free(impl);
 326             (void)sk_IMPLEMENTATION_delete(alg->impls, i);
 327             ossl_property_unlock(store);
 328             return 1;
 329         }
 330     }
 331     ossl_property_unlock(store);
 332     return 0;
 333 }
 334
 335 int ossl_method_store_fetch(OSSL_METHOD_STORE *store, int nid,
 336                             const char *prop_query,
 337                             void **method)
 338 {
 339     OSSL_PROPERTY_LIST **plp;
 340     ALGORITHM *alg;
 341     IMPLEMENTATION *impl;
 342     OSSL_PROPERTY_LIST *pq = NULL, *p2 = NULL;
 343     METHOD *best_method = NULL;
 344     int ret = 0;
 345     int j, best = -1, score, optional;
 346
 347 #ifndef FIPS_MODULE
 348     if (!OPENSSL_init_crypto(OPENSSL_INIT_LOAD_CONFIG, NULL))
 349         return 0;
 350 #endif
 351
 352     if (nid <= 0 || method == NULL || store == NULL)
 353         return 0;
 354
 355     /*
 356      * This only needs to be a read lock, because queries never create property
 357      * names or value and thus don't modify any of the property string layer.
 358      */
 359     if (!ossl_property_read_lock(store))
 360         return 0;
 361     alg = ossl_method_store_retrieve(store, nid);
 362     if (alg == NULL) {
 363         ossl_property_unlock(store);
 364         return 0;
 365     }
 366
 367     if (prop_query != NULL)
 368         p2 = pq = ossl_parse_query(store->ctx, prop_query, 0);
 369     plp = ossl_ctx_global_properties(store->ctx, 0);
 370     if (plp != NULL && *plp != NULL) {
 371         if (pq == NULL) {
 372             pq = *plp;
 373         } else {
 374             p2 = ossl_property_merge(pq, *plp);
 375             ossl_property_free(pq);
 376             if (p2 == NULL)
 377                 goto fin;
 378             pq = p2;
 379         }
 380     }
 381
 382     if (pq == NULL) {
 383         if ((impl = sk_IMPLEMENTATION_value(alg->impls, 0)) != NULL) {
 384             best_method = &impl->method;
 385             ret = 1;
 386         }
 387         goto fin;
 388     }
 389     optional = ossl_property_has_optional(pq);
 390     for (j = 0; j < sk_IMPLEMENTATION_num(alg->impls); j++) {
 391         impl = sk_IMPLEMENTATION_value(alg->impls, j);
 392         score = ossl_property_match_count(pq, impl->properties);
 393         if (score > best) {
 394             best_method = &impl->method;
 395             best = score;
 396             ret = 1;
 397             if (!optional)
 398                 goto fin;
 399         }
 400     }
 401 fin:
 402     if (ret && ossl_method_up_ref(best_method))
 403         *method = best_method->method;
 404     else
 405         ret = 0;
 406     ossl_property_unlock(store);
 407     ossl_property_free(p2);
 408     return ret;
 409 }
 410
 411 static void impl_cache_flush_alg(ossl_uintmax_t idx, ALGORITHM *alg, void *arg)
 412 {
 413     SPARSE_ARRAY_OF(ALGORITHM) *algs = arg;
 414
 415     lh_QUERY_doall(alg->cache, &impl_cache_free);
 416     if (algs != NULL) {
 417         sk_IMPLEMENTATION_pop_free(alg->impls, &impl_free);
 418         lh_QUERY_free(alg->cache);
 419         OPENSSL_free(alg);
 420         ossl_sa_ALGORITHM_set(algs, idx, NULL);
 421     } else {
 422         lh_QUERY_flush(alg->cache);
 423     }
 424 }
 425
 426 static void ossl_method_cache_flush(OSSL_METHOD_STORE *store, int nid)
 427 {
 428     ALGORITHM *alg = ossl_method_store_retrieve(store, nid);
 429
 430     if (alg != NULL) {
 431         ossl_provider_clear_all_operation_bits(store->ctx);
 432         store->nelem -= lh_QUERY_num_items(alg->cache);
 433         impl_cache_flush_alg(0, alg, NULL);
 434     }
 435 }
 436
 437 int ossl_method_store_flush_cache(OSSL_METHOD_STORE *store, int all)
 438 {
 439     void *arg = (all != 0 ? store->algs : NULL);
 440
 441     if (!ossl_property_write_lock(store))
 442         return 0;
 443     ossl_provider_clear_all_operation_bits(store->ctx);
 444     ossl_sa_ALGORITHM_doall_arg(store->algs, &impl_cache_flush_alg, arg);
 445     store->nelem = 0;
 446     ossl_property_unlock(store);
 447     return 1;
 448 }
 449
 450 IMPLEMENT_LHASH_DOALL_ARG(QUERY, IMPL_CACHE_FLUSH);
 451
 452 /*
 453  * Flush an element from the query cache (perhaps).
 454  *
 455  * In order to avoid taking a write lock or using atomic operations
 456  * to keep accurate least recently used (LRU) or least frequently used
 457  * (LFU) information, the procedure used here is to stochastically
 458  * flush approximately half the cache.
 459  *
 460  * This procedure isn't ideal, LRU or LFU would be better.  However,
 461  * in normal operation, reaching a full cache would be unexpected.
 462  * It means that no steady state of algorithm queries has been reached.
 463  * That is, it is most likely an attack of some form.  A suboptimal clearance
 464  * strategy that doesn't degrade performance of the normal case is
 465  * preferable to a more refined approach that imposes a performance
 466  * impact.
 467  */
 468 static void impl_cache_flush_cache(QUERY *c, IMPL_CACHE_FLUSH *state)
 469 {
 470     uint32_t n;
 471
 472     /*
 473      * Implement the 32 bit xorshift as suggested by George Marsaglia in:
 474      *      https://doi.org/10.18637/jss.v008.i14
 475      *
 476      * This is a very fast PRNG so there is no need to extract bits one at a
 477      * time and use the entire value each time.
 478      */
 479     n = state->seed;
 480     n ^= n << 13;
 481     n ^= n >> 17;
 482     n ^= n << 5;
 483     state->seed = n;
 484
 485     if ((n & 1) != 0)
 486         impl_cache_free(lh_QUERY_delete(state->cache, c));
 487     else
 488         state->nelem++;
 489 }
 490
 491 static void impl_cache_flush_one_alg(ossl_uintmax_t idx, ALGORITHM *alg,
 492                                      void *v)
 493 {
 494     IMPL_CACHE_FLUSH *state = (IMPL_CACHE_FLUSH *)v;
 495
 496     state->cache = alg->cache;
 497     lh_QUERY_doall_IMPL_CACHE_FLUSH(state->cache, &impl_cache_flush_cache,
 498                                     state);
 499 }
 500
 501 static void ossl_method_cache_flush_some(OSSL_METHOD_STORE *store)
 502 {
 503     IMPL_CACHE_FLUSH state;
 504
 505     state.nelem = 0;
 506     if ((state.seed = OPENSSL_rdtsc()) == 0)
 507         state.seed = 1;
 508     ossl_provider_clear_all_operation_bits(store->ctx);
 509     store->need_flush = 0;
 510     ossl_sa_ALGORITHM_doall_arg(store->algs, &impl_cache_flush_one_alg, &state);
 511     store->nelem = state.nelem;
 512 }
 513
 514 int ossl_method_store_cache_get(OSSL_METHOD_STORE *store, int nid,
 515                                 const char *prop_query, void **method)
 516 {
 517     ALGORITHM *alg;
 518     QUERY elem, *r;
 519     int res = 0;
 520
 521     if (nid <= 0 || store == NULL)
 522         return 0;
 523
 524     if (!ossl_property_read_lock(store))
 525         return 0;
 526     alg = ossl_method_store_retrieve(store, nid);
 527     if (alg == NULL)
 528         goto err;
 529
 530     elem.query = prop_query != NULL ? prop_query : "";
 531     r = lh_QUERY_retrieve(alg->cache, &elem);
 532     if (r == NULL)
 533         goto err;
 534     if (ossl_method_up_ref(&r->method)) {
 535         *method = r->method.method;
 536         res = 1;
 537     }
 538 err:
 539     ossl_property_unlock(store);
 540     return res;
 541 }
 542
 543 int ossl_method_store_cache_set(OSSL_METHOD_STORE *store, int nid,
 544                                 const char *prop_query, void *method,
 545                                 int (*method_up_ref)(void *),
 546                                 void (*method_destruct)(void *))
 547 {
 548     QUERY elem, *old, *p = NULL;
 549     ALGORITHM *alg;
 550     size_t len;
 551     int res = 1;
 552
 553     if (nid <= 0 || store == NULL)
 554         return 0;
 555     if (prop_query == NULL)
 556         return 1;
 557
 558     if (!ossl_property_write_lock(store))
 559         return 0;
 560     if (store->need_flush)
 561         ossl_method_cache_flush_some(store);
 562     alg = ossl_method_store_retrieve(store, nid);
 563     if (alg == NULL)
 564         goto err;
 565
 566     if (method == NULL) {
 567         elem.query = prop_query;
 568         if ((old = lh_QUERY_delete(alg->cache, &elem)) != NULL) {
 569             impl_cache_free(old);
 570             store->nelem--;
 571         }
 572         goto end;
 573     }
 574     p = OPENSSL_malloc(sizeof(*p) + (len = strlen(prop_query)));
 575     if (p != NULL) {
 576         p->query = p->body;
 577         p->method.method = method;
 578         p->method.up_ref = method_up_ref;
 579         p->method.free = method_destruct;
 580         if (!ossl_method_up_ref(&p->method))
 581             goto err;
 582         memcpy((char *)p->query, prop_query, len + 1);
 583         if ((old = lh_QUERY_insert(alg->cache, p)) != NULL) {
 584             impl_cache_free(old);
 585             goto end;
 586         }
 587         if (!lh_QUERY_error(alg->cache)) {
 588             if (++store->nelem >= IMPL_CACHE_FLUSH_THRESHOLD)
 589                 store->need_flush = 1;
 590             goto end;
 591         }
 592         ossl_method_free(&p->method);
 593     }
 594 err:
 595     res = 0;
 596     OPENSSL_free(p);
 597 end:
 598     ossl_property_unlock(store);
 599     return res;
 600 }