git.samba.org - gd/nettle/blob - pkcs1-sec-decrypt.c

   1 /* pkcs1-sec-decrypt.c
   2
   3    The RSA publickey algorithm. Side channel resistant PKCS#1 decryption.
   4
   5    Copyright (C) 2001, 2012 Niels Möller
   6    Copyright (C) 2018 Red Hat, Inc.
   7
   8    This file is part of GNU Nettle.
   9
  10    GNU Nettle is free software: you can redistribute it and/or
  11    modify it under the terms of either:
  12
  13      * the GNU Lesser General Public License as published by the Free
  14        Software Foundation; either version 3 of the License, or (at your
  15        option) any later version.
  16
  17    or
  18
  19      * the GNU General Public License as published by the Free
  20        Software Foundation; either version 2 of the License, or (at your
  21        option) any later version.
  22
  23    or both in parallel, as here.
  24
  25    GNU Nettle is distributed in the hope that it will be useful,
  26    but WITHOUT ANY WARRANTY; without even the implied warranty of
  27    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  28    General Public License for more details.
  29
  30    You should have received copies of the GNU General Public License and
  31    the GNU Lesser General Public License along with this program.  If
  32    not, see http://www.gnu.org/licenses/.
  33 */
  34
  35 #if HAVE_CONFIG_H
  36 # include "config.h"
  37 #endif
  38
  39 #include <assert.h>
  40
  41 #include <string.h>
  42
  43 #include "memops.h"
  44
  45 #include "gmp-glue.h"
  46 #include "pkcs1-internal.h"
  47
  48 /* Inputs are always cast to uint32_t values. But all values used in this
  49  * function should never exceed the maximum value of a uint32_t anyway.
  50  * these macros returns 1 on success, 0 on failure */
  51 #define NOT_EQUAL(a, b) \
  52     ((0U - ((uint32_t)(a) ^ (uint32_t)(b))) >> 31)
  53 #define EQUAL(a, b) \
  54     ((((uint32_t)(a) ^ (uint32_t)(b)) - 1U) >> 31)
  55 #define GREATER_OR_EQUAL(a, b) \
  56     (1U - (((uint32_t)(a) - (uint32_t)(b)) >> 31))
  57
  58 int
  59 _pkcs1_sec_decrypt (size_t length, uint8_t *message,
  60                     size_t padded_message_length,
  61                     const volatile uint8_t *padded_message)
  62 {
  63   volatile int ok;
  64   size_t i, t;
  65
  66   assert (padded_message_length >= length);
  67
  68   t = padded_message_length - length - 1;
  69
  70   /* Check format, padding, message_size */
  71   ok = EQUAL(padded_message[0], 0);       /* ok if padded_message[0] == 0 */
  72   ok &= EQUAL(padded_message[1], 2);      /* ok if padded_message[1] == 2 */
  73   for (i = 2; i < t; i++)      /* check padding has no zeros */
  74     {
  75       ok &= NOT_EQUAL(padded_message[i], 0);
  76     }
  77   ok &= EQUAL(padded_message[t], 0);      /* ok if terminator == 0 */
  78
  79   /* fill destination buffer regardless of outcome */
  80   cnd_memcpy(ok, message, padded_message + t + 1, length);
  81
  82   return ok;
  83 }
  84
  85 int
  86 _pkcs1_sec_decrypt_variable(size_t *length, uint8_t *message,
  87                             size_t padded_message_length,
  88                             const volatile uint8_t *padded_message)
  89 {
  90   volatile int not_found = 1;
  91   volatile int ok;
  92   volatile size_t offset;
  93   size_t buflen, msglen;
  94   size_t shift, i;
  95
  96   /* Check format, padding, message_size */
  97   ok = EQUAL(padded_message[0], 0);
  98   ok &= EQUAL(padded_message[1], 2);
  99
 100   /* length is discovered in a side-channel silent way.
 101    * not_found goes to 0 when the terminator is found.
 102    * offset strts at 3 as it includes the terminator and
 103    * the fomat bytes already */
 104   offset = 3;
 105   for (i = 2; i < padded_message_length; i++)
 106     {
 107       not_found &= NOT_EQUAL(padded_message[i], 0);
 108       offset += not_found;
 109     }
 110   /* check if we ran out of buffer */
 111   ok &= NOT_EQUAL(not_found, 1);
 112   /* padding must be >= 11 (2 format bytes + 8 pad bytes min. + terminator) */
 113   ok &= GREATER_OR_EQUAL(offset, 11);
 114
 115   /* offset can vary between 3 and padded_message_length, due to the loop
 116    * above, therefore msglen can't underflow */
 117   msglen = padded_message_length - offset;
 118
 119   /* we always fill the whole buffer but only up to
 120    * padded_message_length length */
 121   buflen = *length;
 122   if (buflen > padded_message_length) { /* input independent branch */
 123     buflen = padded_message_length;
 124   }
 125
 126   /* if the message length is larger than the buffer we must fail */
 127   ok &= GREATER_OR_EQUAL(buflen, msglen);
 128
 129   /* fill destination buffer fully regardless of outcome. Copies the message
 130    * in a memory access independent way. The destination message buffer will
 131    * be clobbered past the message length. */
 132   shift = padded_message_length - buflen;
 133   cnd_memcpy(ok, message, padded_message + shift, buflen);
 134   offset -= shift;
 135   /* In this loop, the bits of the 'offset' variable are used as shifting
 136    * conditions, starting from the least significant bit. The end result is
 137    * that the buffer is shifted left exactly 'offset' bytes. */
 138   for (shift = 1; shift < buflen; shift <<= 1, offset >>= 1)
 139     {
 140       /* 'ok' is both a least significant bit mask and a condition */
 141       cnd_memcpy(offset & ok, message, message + shift, buflen - shift);
 142     }
 143
 144   /* update length only if we succeeded, otherwise leave unchanged */
 145   *length = (msglen & (-(size_t) ok)) + (*length & ((size_t) ok - 1));
 146
 147   return ok;
 148 }