aboutsummaryrefslogtreecommitdiff
path: root/rsa.c
AgeCommit message (Expand)Author
2016-07-05Attempt to add resource management, for multiple cores of the same type.Paul Selkirk
2016-06-14Add support for ModExpA7Paul Selkirk
2016-06-13Allow NULL der_len parameter in hal-rsa_private_key_to_der().Rob Austein
2016-05-14Trailing whitespace cleanup.Rob Austein
2016-03-29Client-side rsa and ecdsa need to call remote get_random.Paul Selkirk
2015-12-23RPC interface to TRNG and (incomplete) PIN code.Rob Austein
2015-12-23Software modexp() implementation didn't compile due to missing proRob Austein
2015-12-22Add ASN.1 support for public keys (X.509 SubjectPublicKeyInfo format).Rob Austein
2015-12-21Fix names of private key DER functions.Rob Austein
2015-12-20RPC server stuff mostly written. Compiles, not yet tested. RPCRob Austein
2015-12-13whack copyrightsPaul Selkirk
2015-10-04Whack libhal API to use current configure_core_selector mechanism.Rob Austein
2015-10-03Use initializers for automatic variables of type fp_int because it's aRob Austein
2015-09-08Merge branch 'master' into ecdsaRob Austein
2015-09-06Add ECPoint I/O functions. ASN.1 cleanup.Rob Austein
2015-09-02Still more const-ification.Rob Austein
2015-09-02Clean up excessively complicated handling of opaque types in hash andRob Austein
2015-07-14Changes to support Pavel's ModExpS6 core.Rob Austein
2015-07-01Change default to use software modexp until we sort out performanceRob Austein
2015-06-24Rework API for loading keys from components. Relax key sizeRob Austein
2015-06-21libcryptech -> libhal, doh.Rob Austein
2015-06-21Add digest algorithm IDs.Rob Austein
2015-06-19Add methods to extract public components from an RSA key. Other minorRob Austein
2015-06-19Add temporary workaround to let us use software ModExp when we'reRob Austein
2015-06-19Add replacement for fp_exptmod() using our ModExp core, so we don'tRob Austein
2015-06-18Supply public exponent as bigendian byte string rather than unsignedRob Austein
2015-06-18Helps to set the return value when reading a key, doh.Rob Austein
2015-06-18Add RSA blinding.Rob Austein
2015-06-18Refactor CRT code into public API.Rob Austein
2015-06-17Debug RSA key generation.Rob Austein
2015-06-17RSA key generation and DER support.Rob Austein
2015-06-17RSA key generation. Compiles, not (yet) tested otherwise.Rob Austein
2015-06-16Refactor key loading code.Rob Austein
2015-06-11Debug modexp_fp() buffer handling. Add basic timing report.Rob Austein
2015-06-11First cut at RSA decryption/signature using the Chinese RemainderRob Austein
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-05 22:10:13 +0000
a id='n275' href='#n275'>275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 
/*
 * ks_index.c
 * ----------
 * Keystore index API.  This is internal within libhal.
 *
 * Copyright (c) 2016, NORDUnet A/S All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * - Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 *
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *
 * - Neither the name of the NORDUnet nor the names of its contributors may
 *   be used to endorse or promote products derived from this software
 *   without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <string.h>
#include <assert.h>

#include "hal.h"
#include "hal_internal.h"

/*
 * Compare two hal_ks_name_t objects.
 */

static inline int ks_name_cmp(const hal_ks_name_t * const name1, const hal_ks_name_t * const name2)
{
  assert(name1 != NULL && name2 != NULL);

  int cmp = hal_uuid_cmp(&name1->name, &name2->name);

  if (cmp == 0)
    cmp = ((int) name1->chunk) - ((int) name2->chunk);

  return cmp;
}

/*
 * Find a block in the index, return true (found) or false (not found).
 * "where" indicates the name's position, or the position of the first free block.
 *
 * NB: This does NOT return a block number, it returns an index into
 * ksi->index[].
 */

static int ks_find(const hal_ks_index_t * const ksi,
		   const hal_uuid_t * const uuid,
                   const uint8_t chunk,
                   const int * const hint,
		   int *where)
{
  assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL && uuid != NULL && where != NULL);

  const hal_ks_name_t name = { *uuid, chunk };

  if (hint != NULL && *hint >= 0 && *hint < ksi->used &&
      ks_name_cmp(&name, &ksi->names[ksi->index[*hint]]) == 0) {
    *where = *hint;
    return 1;
  }

  int lo = -1;
  int hi = ksi->used;

  for (;;) {
    int m = (lo + hi) / 2;
    if (hi == 0 || m == lo) {
      *where = hi;
      return 0;
    }
    const int cmp = ks_name_cmp(&name, &ksi->names[ksi->index[m]]);
    if (cmp < 0)
      hi = m;
    else if (cmp > 0)
      lo = m;
    else {
      *where = m;
      return 1;
    }
  }
}

/*
 * Heapsort the index.  We only need to do this on setup, for other
 * operations we're just inserting or deleting a single entry in an
 * already-ordered array, which is just a search problem.  If we were
 * really crunched for space, we could use an insertion sort here, but
 * heapsort is easy and works well with data already in place.
 */

static inline void ks_heapsift(hal_ks_index_t *ksi, int parent, const int end)
{
  assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL &&
	 parent >= 0 && end >= parent);
  for (;;) {
    const int left_child  = parent * 2 + 1;
    const int right_child = parent * 2 + 2;
    int biggest = parent;
    if (left_child  <= end && ks_name_cmp(&ksi->names[ksi->index[biggest]],
                                          &ksi->names[ksi->index[left_child]])  < 0)
      biggest = left_child;
    if (right_child <= end && ks_name_cmp(&ksi->names[ksi->index[biggest]],
                                          &ksi->names[ksi->index[right_child]]) < 0)
      biggest = right_child;
    if (biggest == parent)
      return;
    const uint16_t tmp  = ksi->index[biggest];
    ksi->index[biggest] = ksi->index[parent];
    ksi->index[parent] = tmp;
    parent = biggest;
  }
}

static inline void ks_heapsort(hal_ks_index_t *ksi)
{
  assert(ksi != NULL && ksi->index != NULL && ksi->names != NULL);
  if (ksi->used < 2)
    return;
  for (int i = (ksi->used - 2) / 2; i >= 0; i--)
    ks_heapsift(ksi, i, ksi->used - 1);
  for (int i = ksi->used - 1; i > 0; i--) {
    const uint16_t tmp = ksi->index[i];
    ksi->index[i]      = ksi->index[0];
    ksi->index[0]      = tmp;
    ks_heapsift(ksi, 0, i - 1);
  }
}

/*
 * Perform a consistency check on the index.
 */

#define fsck(_ksi) \
  do { hal_error_t _err = hal_ks_index_fsck(_ksi); if (_err != HAL_OK) return _err; } while (0)


hal_error_t hal_ks_index_fsck(hal_ks_index_t *ksi)
{
  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
      ksi->size == 0 || ksi->used > ksi->size)
    return HAL_ERROR_BAD_ARGUMENTS;

  for (int i = 0; i < ksi->used; i++) {

    const int cmp = i == 0 ? -1 : hal_uuid_cmp(&ksi->names[ksi->index[i - 1]].name,
                                               &ksi->names[ksi->index[i    ]].name);

    const uint8_t prev_chunk = i == 0 ? 0 : ksi->names[ksi->index[i - 1]].chunk;
    const uint8_t cur_chunk  =              ksi->names[ksi->index[i    ]].chunk;

    if (cmp > 0)
      return HAL_ERROR_KSI_INDEX_UUID_MISORDERED;

    if (cur_chunk > 0 && cmp != 0)
      return HAL_ERROR_KSI_INDEX_CHUNK_ORPHANED;

    if (cur_chunk > 0 && prev_chunk + 1 < cur_chunk)
      return HAL_ERROR_KSI_INDEX_CHUNK_MISSING;

    if (cur_chunk > 0 && prev_chunk + 1 > cur_chunk)
      return HAL_ERROR_KSI_INDEX_CHUNK_OVERLAPS;
  }

  return HAL_OK;
}

/*
 * Set up the index. Only setup task we have at the moment is sorting the index.
 */

hal_error_t hal_ks_index_setup(hal_ks_index_t *ksi)
{
  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
      ksi->size == 0 || ksi->used > ksi->size)
    return HAL_ERROR_BAD_ARGUMENTS;

  ks_heapsort(ksi);

  /*
   * One might think we should fsck here, but errors in the index
   * at this point probably relate to errors in the supplied data,
   * which only the driver knows how to clean up.
   */

  return HAL_OK;
}

/*
 * Find a single block by name and chunk number.
 */

hal_error_t hal_ks_index_find(hal_ks_index_t *ksi,
			      const hal_uuid_t * const name,
                              const unsigned chunk,
			      unsigned *blockno,
                              int *hint)
{
  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  int where;

  fsck(ksi);

  int ok = ks_find(ksi, name, chunk, hint, &where);

  if (blockno != NULL)
    *blockno = ksi->index[where];

  if (hint != NULL)
    *hint = where;

  return ok ? HAL_OK : HAL_ERROR_KEY_NOT_FOUND;
}

/*
 * Find all blocks with the given name.
 * If 'strict' is set, expect it to be a well-ordered set of chunks.
 */

hal_error_t hal_ks_index_find_range(hal_ks_index_t *ksi,
                                    const hal_uuid_t * const name,
                                    const unsigned max_blocks,
                                    unsigned *n_blocks,
                                    unsigned *blocknos,
                                    int *hint,
                                    const int strict)
{
  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  int where;

  fsck(ksi);

  if (!ks_find(ksi, name, 0, hint, &where))
    return HAL_ERROR_KEY_NOT_FOUND;

  int n = 0;

  for (int i = where; i < ksi->used && !hal_uuid_cmp(name, &ksi->names[ksi->index[i]].name); i++) {
    if (strict && n != ksi->names[ksi->index[i]].chunk)
      return HAL_ERROR_IMPOSSIBLE;
    if (blocknos != NULL && n < max_blocks)
      blocknos[n] = ksi->index[i];
    n++;
  }

  if (n_blocks != NULL)
    *n_blocks = n;

  if (hint != NULL)
    *hint = where;

  if (blocknos != NULL && n > max_blocks)
    return HAL_ERROR_RESULT_TOO_LONG;

  return HAL_OK;
}

/*
 * Add a single block to the index.
 */

hal_error_t hal_ks_index_add(hal_ks_index_t *ksi,
			     const hal_uuid_t * const name,
                             const unsigned chunk,
			     unsigned *blockno,
                             int *hint)
{
  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  if (ksi->used == ksi->size)
    return HAL_ERROR_NO_KEY_INDEX_SLOTS;

  int where;

  fsck(ksi);

  if (ks_find(ksi, name, chunk, hint, &where))
    return HAL_ERROR_KEY_NAME_IN_USE;

  /*
   * Grab first block on free list, which makes room to slide the
   * index up by one slot so we can insert the new block number.
   */

  const size_t len = (ksi->used - where) * sizeof(*ksi->index);
  const uint16_t b = ksi->index[ksi->used++];
  memmove(&ksi->index[where + 1], &ksi->index[where], len);
  ksi->index[where] = b;
  ksi->names[b].name = *name;
  ksi->names[b].chunk = chunk;

  if (blockno != NULL)
    *blockno = b;

  if (hint != NULL)
    *hint = where;

  fsck(ksi);

  return HAL_OK;
}

/*
 * Delete a single block from the index.
 */

hal_error_t hal_ks_index_delete(hal_ks_index_t *ksi,
				const hal_uuid_t * const name,
                                const unsigned chunk,
				unsigned *blockno,
                                int *hint)
{
  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  int where;

  fsck(ksi);

  if (ksi->used == 0 || !ks_find(ksi, name, chunk, hint, &where))
    return HAL_ERROR_KEY_NOT_FOUND;

  /*
   * Free the block and stuff it at the end of the free list.
   */

  const size_t len = (ksi->size - where - 1) * sizeof(*ksi->index);
  const uint16_t b = ksi->index[where];
  memmove(&ksi->index[where], &ksi->index[where + 1], len);
  ksi->index[ksi->size - 1] = b;
  ksi->used--;
  memset(&ksi->names[b], 0, sizeof(ksi->names[b]));

  if (blockno != NULL)
    *blockno = b;

  if (hint != NULL)
    *hint = where;

  fsck(ksi);

  return HAL_OK;
}

/*
 * Delete all blocks with the given name. If blocknos is NULL, return a
 * count of the matching blocks without deleting anything.
 */

hal_error_t hal_ks_index_delete_range(hal_ks_index_t *ksi,
                                      const hal_uuid_t * const name,
                                      const unsigned max_blocks,
                                      unsigned *n_blocks,
                                      unsigned *blocknos,
                                      int *hint)
{
  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  int where;

  fsck(ksi);

  if (ksi->used == 0 || !ks_find(ksi, name, 0, hint, &where))
    return HAL_ERROR_KEY_NOT_FOUND;

  int n = 0;

  for (int i = where; i < ksi->used && !hal_uuid_cmp(name, &ksi->names[ksi->index[i]].name); i++) {
    if (n != ksi->names[ksi->index[i]].chunk)
      return HAL_ERROR_IMPOSSIBLE;
    if (blocknos != NULL && n < max_blocks)
      blocknos[n] = ksi->index[i];
    n++;
  }

  if (n_blocks != NULL)
    *n_blocks = n;

  /*
   * Free the blocks and stuff them at the end of the free list.
   */

  if (blocknos != NULL) {
    if (n > max_blocks)
      return HAL_ERROR_RESULT_TOO_LONG;
    const size_t len = (ksi->size - where - n) * sizeof(*ksi->index);
    memmove(&ksi->index[where], &ksi->index[where + n], len);
    ksi->used -= n;
    for (int i = 0; i < n; i++) {
      ksi->index[ksi->size - n + i] = blocknos[i];
      memset(&ksi->names[blocknos[i]], 0, sizeof(ksi->names[blocknos[i]]));
    }
    where = -1;
  }

  if (hint != NULL)
    *hint = where;

  fsck(ksi);

  return HAL_OK;
}

/*
 * Replace a single block in the index.
 */

hal_error_t hal_ks_index_replace(hal_ks_index_t *ksi,
                                 const hal_uuid_t * const name,
                                 const unsigned chunk,
                                 unsigned *blockno,
                                 int *hint)
{
  if (ksi == NULL || ksi->index == NULL || ksi->names == NULL ||
      ksi->size == 0 || ksi->used > ksi->size || name == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  if (ksi->used == ksi->size)
    return HAL_ERROR_NO_KEY_INDEX_SLOTS;

  int where;

  fsck(ksi);

  if (ksi->used == 0 || !ks_find(ksi, name, chunk, hint, &where))
    return HAL_ERROR_KEY_NOT_FOUND;

  /*
   * Grab first block from free list, slide free list down, put old
   * block at end of free list and replace old block with new block.
   */

  const size_t len = (ksi->size - ksi->used - 1) * sizeof(*ksi->index);
  const uint16_t b1 = ksi->index[where];
  const uint16_t b2 = ksi->index[ksi->used];
  memmove(&ksi->index[ksi->used], &ksi->index[ksi->used + 1], len);
  ksi->index[ksi->size - 1] = b1;
  ksi->index[where] = b2;
  ksi->names[b2].name = *name;
  ksi->names[b2].chunk = chunk;
  memset(&ksi->names[b1], 0, sizeof(ksi->names[b1]));

  if (blockno != NULL)
    *blockno = b2;

  if (hint != NULL)
    *hint = where;

  fsck(ksi);

  return HAL_OK;
}

/*
 * Local variables:
 * indent-tabs-mode: nil
 * End:
 */