soft.rs

//! Constant-time software implementation of POLYVAL

// Adapted from BearSSL's `ghash_ctmul64.c`
// <https://bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/hash/ghash_ctmul64.c;hb=4b6046412bf927d6424f20fc7ee495bb96dbd227>
//
// Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

#![allow(missing_docs)]

use super::Backend;
use crate::field::Block;
use core::{
    convert::TryInto,
    ops::{Add, Mul},
};

/// 2 x `u64` values
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub struct U64x2(u64, u64);

impl Backend for U64x2 {}

impl From<Block> for U64x2 {
    fn from(bytes: Block) -> U64x2 {
        U64x2(
            u64::from_le_bytes(bytes[..8].try_into().unwrap()),
            u64::from_le_bytes(bytes[8..].try_into().unwrap()),
        )
    }
}

impl From<U64x2> for Block {
    fn from(u64x2: U64x2) -> Block {
        let x: u128 = u64x2.into();
        x.to_le_bytes()
    }
}

impl From<u128> for U64x2 {
    fn from(x: u128) -> U64x2 {
        let lo = (x & 0xFFFF_FFFFF) as u64;
        let hi = (x >> 64) as u64;
        U64x2(lo, hi)
    }
}

impl From<U64x2> for u128 {
    fn from(u64x2: U64x2) -> u128 {
        u128::from(u64x2.0) | (u128::from(u64x2.1) << 64)
    }
}

#[allow(clippy::suspicious_arithmetic_impl)]
impl Add for U64x2 {
    type Output = Self;

    /// Adds two POLYVAL field elements.
    fn add(self, rhs: Self) -> Self::Output {
        U64x2(self.0 ^ rhs.0, self.1 ^ rhs.1)
    }
}

#[allow(clippy::suspicious_arithmetic_impl)]
impl Mul for U64x2 {
    type Output = Self;

    /// Computes POLYVAL multiplication over GF(2^128) in constant time.
    ///
    /// Method described at:
    /// <https://www.bearssl.org/constanttime.html#ghash-for-gcm>
    ///
    /// POLYVAL multiplication is effectively the little endian equivalent of
    /// GHASH multiplication, aside from one small detail described here:
    ///
    /// <https://crypto.stackexchange.com/questions/66448/how-does-bearssls-gcm-modular-reduction-work/66462#66462>
    ///
    /// > If you look at the equation above, the product of two bit-reversed
    /// > 128-bit polynomials yields the bit-reversed result over 255 bits,
    /// > not 256. The BearSSL code ends up with a 256-bit result in zw[],
    /// > and that value is shifted by one bit, because of that reversed
    /// > convention issue. Thus, the code must include a shifting step to put
    /// > it back where it should
    ///
    /// This shift is unnecessary for POLYVAL.
    fn mul(self, rhs: Self) -> Self {
        let h0 = self.0;
        let h1 = self.1;
        let h0r = rev64(h0);
        let h1r = rev64(h1);
        let h2 = h0 ^ h1;
        let h2r = h0r ^ h1r;

        let y0 = rhs.0;
        let y1 = rhs.1;
        let y0r = rev64(y0);
        let y1r = rev64(y1);
        let y2 = y0 ^ y1;
        let y2r = y0r ^ y1r;
        let z0 = bmul64(y0, h0);
        let z1 = bmul64(y1, h1);

        let mut z2 = bmul64(y2, h2);
        let mut z0h = bmul64(y0r, h0r);
        let mut z1h = bmul64(y1r, h1r);
        let mut z2h = bmul64(y2r, h2r);

        z2 ^= z0 ^ z1;
        z2h ^= z0h ^ z1h;
        z0h = rev64(z0h) >> 1;
        z1h = rev64(z1h) >> 1;
        z2h = rev64(z2h) >> 1;

        let v0 = z0;
        let mut v1 = z0h ^ z2;
        let mut v2 = z1 ^ z2h;
        let mut v3 = z1h;

        v2 ^= v0 ^ v0 >> 1 ^ v0 >> 2 ^ v0 >> 7;
        v1 ^= v0 << 63 ^ v0 << 62 ^ v0 << 57;
        v3 ^= v1 ^ v1 >> 1 ^ v1 >> 2 ^ v1 >> 7;
        v2 ^= v1 << 63 ^ v1 << 62 ^ v1 << 57;

        U64x2(v2, v3)
    }
}

fn rev64(mut x: u64) -> u64 {
    x = ((x & 0x5555_5555_5555_5555) << 1) | ((x >> 1) & 0x5555_5555_5555_5555);
    x = ((x & 0x3333_3333_3333_3333) << 2) | ((x >> 2) & 0x3333_3333_3333_3333);
    x = ((x & 0x0f0f_0f0f_0f0f_0f0f) << 4) | ((x >> 4) & 0x0f0f_0f0f_0f0f_0f0f);
    x = ((x & 0x00ff_00ff_00ff_00ff) << 8) | ((x >> 8) & 0x00ff_00ff_00ff_00ff);
    x = ((x & 0xffff_0000_ffff) << 16) | ((x >> 16) & 0xffff_0000_ffff);
    (x << 32) | (x >> 32)
}

fn bmul64(x: u64, y: u64) -> u64 {
    let x0 = x & 0x1111_1111_1111_1111;
    let x1 = x & 0x2222_2222_2222_2222;
    let x2 = x & 0x4444_4444_4444_4444;
    let x3 = x & 0x8888_8888_8888_8888;
    let y0 = y & 0x1111_1111_1111_1111;
    let y1 = y & 0x2222_2222_2222_2222;
    let y2 = y & 0x4444_4444_4444_4444;
    let y3 = y & 0x8888_8888_8888_8888;

    let mut z0 =
        x0.wrapping_mul(y0) ^ x1.wrapping_mul(y3) ^ x2.wrapping_mul(y2) ^ x3.wrapping_mul(y1);

    let mut z1 =
        x0.wrapping_mul(y1) ^ x1.wrapping_mul(y0) ^ x2.wrapping_mul(y3) ^ x3.wrapping_mul(y2);

    let mut z2 =
        x0.wrapping_mul(y2) ^ x1.wrapping_mul(y1) ^ x2.wrapping_mul(y0) ^ x3.wrapping_mul(y3);

    let mut z3 =
        x0.wrapping_mul(y3) ^ x1.wrapping_mul(y2) ^ x2.wrapping_mul(y1) ^ x3.wrapping_mul(y0);

    z0 &= 0x1111_1111_1111_1111;
    z1 &= 0x2222_2222_2222_2222;
    z2 &= 0x4444_4444_4444_4444;
    z3 &= 0x8888_8888_8888_8888;

    z0 | z1 | z2 | z3
}