nisse@lysator.liu.se (Niels Möller) writes:
Let me first explain what I mean when I talk about a "side-channel silent" function. That means that if we call the function with operands which are of the same size, but otherwise different, the function should execute exactly the same sequence of instructions in both cases, and access memory in exactly the same pattern.
To give a flavor of what this means, here's some code (totally untested) I wrote earlier today. It's basic binary point multiplication, but intended to have running time independent of the exponent bits.
Regards, /Niels
/* nettle, low-level cryptographics library * * Copyright (C) 2013 Niels Möller * * The nettle library is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software Foundation; either version 2.1 of the License, or (at your * option) any later version. * * The nettle library is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public * License for more details. * * You should have received a copy of the GNU Lesser General Public License * along with the nettle library; see the file COPYING.LIB. If not, write to * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, * MA 02111-1301, USA. */
/* Development of Nettle's ECC support was funded by Internetfonden. */
#include <assert.h>
#include "ecc.h"
void cnd_copy (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n) { mp_limb_t mask, keep; mp_size_t i;
mask = -(mp_limb_t) (cnd !=0); keep = ~mask;
for (i = 0; i < n; i++) rp[i] = (rp[i] & keep) + (ap[i] & mask); }
void ecc_mul_binary (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *np, const mp_limb_t *p) { mp_limb_t tp[9*ecc->size]; mp_limb_t *rj = tp + 3*ecc->size; mp_limb_t *pj = tp + 6*ecc->size; int is_zero;
unsigned i;
mpn_zero (rj, 3*ecc->size);
/* Extend p to jacobian coordinates, with z = 1 */ mpn_copyi (pj, p, 2*ecc->size); pj[2*ecc->size] = 1; mpn_zero (pj + 2*ecc->size+1, ecc->size - 1);
for (i = ecc->size, is_zero = 1; i-- > 0; ) { mp_limb_t w = np[i]; mp_limb_t bit;
for (bit = (mp_limb_t) 1 << (GMP_NUMB_BITS - 1); bit > 0; bit >>= 1) { int digit; ecc_dup_jj (ecc, rj, rj); ecc_add_jja (ecc, tp, rj, p);
digit = (w & bit) > 0; /* If is_zero is set, rj is the zero point, and ecc_add_jja produced garbage. */ cnd_copy (is_zero, tp, pj, 3*ecc->size); is_zero &= ~digit; /* If we had a one-bit, use the sum. */ cnd_copy (digit, rj, tp, 3*ecc->size); } } ecc_normalize (ecc, r, rj); }