aead/gcm/gcm_nohw.rs

// Copyright (c) 2019, Google Inc.
// Portions Copyright 2020 Brian Smith.
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

// This file is based on BoringSSL's gcm_nohw.c.

// This file contains a constant-time implementation of GHASH based on the notes
// in https://bearssl.org/constanttime.html#ghash-for-gcm and the reduction
// algorithm described in
// https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf.
//
// Unlike the BearSSL notes, we use u128 in the 64-bit implementation.

use super::{super::Block, Xi};
use crate::endian::BigEndian;
use core::convert::TryInto;

#[cfg(target_pointer_width = "64")]
fn gcm_mul64_nohw(a: u64, b: u64) -> (u64, u64) {
    #[inline(always)]
    fn lo(a: u128) -> u64 {
        a as u64
    }

    #[inline(always)]
    fn hi(a: u128) -> u64 {
        lo(a >> 64)
    }

    #[inline(always)]
    fn mul(a: u64, b: u64) -> u128 {
        u128::from(a) * u128::from(b)
    }

    // One term every four bits means the largest term is 64/4 = 16, which barely
    // overflows into the next term. Using one term every five bits would cost 25
    // multiplications instead of 16. It is faster to mask off the bottom four
    // bits of |a|, giving a largest term of 60/4 = 15, and apply the bottom bits
    // separately.
    let a0 = a & 0x1111111111111110;
    let a1 = a & 0x2222222222222220;
    let a2 = a & 0x4444444444444440;
    let a3 = a & 0x8888888888888880;

    let b0 = b & 0x1111111111111111;
    let b1 = b & 0x2222222222222222;
    let b2 = b & 0x4444444444444444;
    let b3 = b & 0x8888888888888888;

    let c0 = mul(a0, b0) ^ mul(a1, b3) ^ mul(a2, b2) ^ mul(a3, b1);
    let c1 = mul(a0, b1) ^ mul(a1, b0) ^ mul(a2, b3) ^ mul(a3, b2);
    let c2 = mul(a0, b2) ^ mul(a1, b1) ^ mul(a2, b0) ^ mul(a3, b3);
    let c3 = mul(a0, b3) ^ mul(a1, b2) ^ mul(a2, b1) ^ mul(a3, b0);

    // Multiply the bottom four bits of |a| with |b|.
    let a0_mask = 0u64.wrapping_sub(a & 1);
    let a1_mask = 0u64.wrapping_sub((a >> 1) & 1);
    let a2_mask = 0u64.wrapping_sub((a >> 2) & 1);
    let a3_mask = 0u64.wrapping_sub((a >> 3) & 1);
    let extra = u128::from(a0_mask & b)
        ^ (u128::from(a1_mask & b) << 1)
        ^ (u128::from(a2_mask & b) << 2)
        ^ (u128::from(a3_mask & b) << 3);

    let lo = (lo(c0) & 0x1111111111111111)
        ^ (lo(c1) & 0x2222222222222222)
        ^ (lo(c2) & 0x4444444444444444)
        ^ (lo(c3) & 0x8888888888888888)
        ^ lo(extra);
    let hi = (hi(c0) & 0x1111111111111111)
        ^ (hi(c1) & 0x2222222222222222)
        ^ (hi(c2) & 0x4444444444444444)
        ^ (hi(c3) & 0x8888888888888888)
        ^ hi(extra);
    (lo, hi)
}

#[cfg(not(target_pointer_width = "64"))]
fn gcm_mul32_nohw(a: u32, b: u32) -> u64 {
    #[inline(always)]
    fn mul(a: u32, b: u32) -> u64 {
        u64::from(a) * u64::from(b)
    }

    // One term every four bits means the largest term is 32/4 = 8, which does not
    // overflow into the next term.
    let a0 = a & 0x11111111;
    let a1 = a & 0x22222222;
    let a2 = a & 0x44444444;
    let a3 = a & 0x88888888;

    let b0 = b & 0x11111111;
    let b1 = b & 0x22222222;
    let b2 = b & 0x44444444;
    let b3 = b & 0x88888888;

    let c0 = mul(a0, b0) ^ mul(a1, b3) ^ mul(a2, b2) ^ mul(a3, b1);
    let c1 = mul(a0, b1) ^ mul(a1, b0) ^ mul(a2, b3) ^ mul(a3, b2);
    let c2 = mul(a0, b2) ^ mul(a1, b1) ^ mul(a2, b0) ^ mul(a3, b3);
    let c3 = mul(a0, b3) ^ mul(a1, b2) ^ mul(a2, b1) ^ mul(a3, b0);

    (c0 & 0x1111111111111111)
        | (c1 & 0x2222222222222222)
        | (c2 & 0x4444444444444444)
        | (c3 & 0x8888888888888888)
}

#[cfg(not(target_pointer_width = "64"))]
fn gcm_mul64_nohw(a: u64, b: u64) -> (u64, u64) {
    #[inline(always)]
    fn lo(a: u64) -> u32 {
        a as u32
    }
    #[inline(always)]
    fn hi(a: u64) -> u32 {
        lo(a >> 32)
    }

    let a0 = lo(a);
    let a1 = hi(a);
    let b0 = lo(b);
    let b1 = hi(b);
    // Karatsuba multiplication.
    let lo = gcm_mul32_nohw(a0, b0);
    let hi = gcm_mul32_nohw(a1, b1);
    let mid = gcm_mul32_nohw(a0 ^ a1, b0 ^ b1) ^ lo ^ hi;
    (lo ^ (mid << 32), hi ^ (mid >> 32))
}

pub(super) fn init(xi: [u64; 2]) -> super::u128 {
    // We implement GHASH in terms of POLYVAL, as described in RFC8452. This
    // avoids a shift by 1 in the multiplication, needed to account for bit
    // reversal losing a bit after multiplication, that is,
    // rev128(X) * rev128(Y) = rev255(X*Y).
    //
    // Per Appendix A, we run mulX_POLYVAL. Note this is the same transformation
    // applied by |gcm_init_clmul|, etc. Note |Xi| has already been byteswapped.
    //
    // See also slide 16 of
    // https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf
    let mut lo = xi[1];
    let mut hi = xi[0];

    let mut carry = hi >> 63;
    carry = 0u64.wrapping_sub(carry);

    hi <<= 1;
    hi |= lo >> 63;
    lo <<= 1;

    // The irreducible polynomial is 1 + x^121 + x^126 + x^127 + x^128, so we
    // conditionally add 0xc200...0001.
    lo ^= carry & 1;
    hi ^= carry & 0xc200000000000000;

    // This implementation does not use the rest of |Htable|.
    super::u128 { lo, hi }
}

fn gcm_polyval_nohw(xi: &mut [u64; 2], h: super::u128) {
    // Karatsuba multiplication. The product of |Xi| and |H| is stored in |r0|
    // through |r3|. Note there is no byte or bit reversal because we are
    // evaluating POLYVAL.
    let (r0, mut r1) = gcm_mul64_nohw(xi[0], h.lo);
    let (mut r2, mut r3) = gcm_mul64_nohw(xi[1], h.hi);
    let (mut mid0, mut mid1) = gcm_mul64_nohw(xi[0] ^ xi[1], h.hi ^ h.lo);
    mid0 ^= r0 ^ r2;
    mid1 ^= r1 ^ r3;
    r2 ^= mid1;
    r1 ^= mid0;

    // Now we multiply our 256-bit result by x^-128 and reduce. |r2| and
    // |r3| shifts into position and we must multiply |r0| and |r1| by x^-128. We
    // have:
    //
    //       1 = x^121 + x^126 + x^127 + x^128
    //  x^-128 = x^-7 + x^-2 + x^-1 + 1
    //
    // This is the GHASH reduction step, but with bits flowing in reverse.

    // The x^-7, x^-2, and x^-1 terms shift bits past x^0, which would require
    // another reduction steps. Instead, we gather the excess bits, incorporate
    // them into |r0| and |r1| and reduce once. See slides 17-19
    // of https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf.
    r1 ^= (r0 << 63) ^ (r0 << 62) ^ (r0 << 57);

    // 1
    r2 ^= r0;
    r3 ^= r1;

    // x^-1
    r2 ^= r0 >> 1;
    r2 ^= r1 << 63;
    r3 ^= r1 >> 1;

    // x^-2
    r2 ^= r0 >> 2;
    r2 ^= r1 << 62;
    r3 ^= r1 >> 2;

    // x^-7
    r2 ^= r0 >> 7;
    r2 ^= r1 << 57;
    r3 ^= r1 >> 7;

    *xi = [r2, r3];
}

pub(super) fn gmult(xi: &mut Xi, h: super::u128) {
    with_swapped_xi(xi, |swapped| {
        gcm_polyval_nohw(swapped, h);
    })
}

pub(super) fn ghash(xi: &mut Xi, h: super::u128, input: &[u8]) {
    with_swapped_xi(xi, |swapped| {
        input.chunks_exact(16).for_each(|inp| {
            swapped[0] ^= u64::from_be_bytes(inp[8..].try_into().unwrap());
            swapped[1] ^= u64::from_be_bytes(inp[..8].try_into().unwrap());
            gcm_polyval_nohw(swapped, h);
        });
    });
}

#[inline]
fn with_swapped_xi(Xi(xi): &mut Xi, f: impl FnOnce(&mut [u64; 2])) {
    let unswapped = xi.u64s_be_to_native();
    let mut swapped: [u64; 2] = [unswapped[1], unswapped[0]];
    f(&mut swapped);
    *xi = Block::from_u64_be(BigEndian::from(swapped[1]), BigEndian::from(swapped[0]))
}