polyval/backend/
soft64.rs

1//! Constant-time software implementation of POLYVAL for 64-bit architectures.
2//! Adapted from BearSSL's `ghash_ctmul64.c`:
3//!
4//! <https://bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/hash/ghash_ctmul64.c;hb=4b6046412>
5//!
6//! Copyright (c) 2016 Thomas Pornin <[email protected]>
7
8use core::{
9    num::Wrapping,
10    ops::{Add, Mul},
11};
12
13use universal_hash::{
14    consts::{U1, U16},
15    crypto_common::{BlockSizeUser, KeySizeUser, ParBlocksSizeUser},
16    KeyInit, Reset, UhfBackend, UniversalHash,
17};
18
19#[cfg(feature = "zeroize")]
20use zeroize::Zeroize;
21
22use crate::{Block, Key, Tag};
23
24/// **POLYVAL**: GHASH-like universal hash over GF(2^128).
25#[derive(Clone)]
26pub struct Polyval {
27    /// GF(2^128) field element input blocks are multiplied by
28    h: U64x2,
29
30    /// Field element representing the computed universal hash
31    s: U64x2,
32}
33
34impl Polyval {
35    /// Initialize POLYVAL with the given `H` field element and initial block
36    pub fn new_with_init_block(h: &Key, init_block: u128) -> Self {
37        Self {
38            h: h.into(),
39            s: init_block.into(),
40        }
41    }
42}
43
44impl KeySizeUser for Polyval {
45    type KeySize = U16;
46}
47
48impl KeyInit for Polyval {
49    /// Initialize POLYVAL with the given `H` field element
50    fn new(h: &Key) -> Self {
51        Self::new_with_init_block(h, 0)
52    }
53}
54
55impl BlockSizeUser for Polyval {
56    type BlockSize = U16;
57}
58
59impl ParBlocksSizeUser for Polyval {
60    type ParBlocksSize = U1;
61}
62
63impl UhfBackend for Polyval {
64    fn proc_block(&mut self, x: &Block) {
65        let x = U64x2::from(x);
66        self.s = (self.s + x) * self.h;
67    }
68}
69
70impl UniversalHash for Polyval {
71    fn update_with_backend(
72        &mut self,
73        f: impl universal_hash::UhfClosure<BlockSize = Self::BlockSize>,
74    ) {
75        f.call(self);
76    }
77
78    /// Get POLYVAL result (i.e. computed `S` field element)
79    fn finalize(self) -> Tag {
80        let mut block = Block::default();
81
82        for (chunk, i) in block.chunks_mut(8).zip(&[self.s.0, self.s.1]) {
83            chunk.copy_from_slice(&i.to_le_bytes());
84        }
85
86        block
87    }
88}
89
90impl Reset for Polyval {
91    fn reset(&mut self) {
92        self.s = U64x2::default();
93    }
94}
95
96#[cfg(feature = "zeroize")]
97impl Drop for Polyval {
98    fn drop(&mut self) {
99        self.h.zeroize();
100        self.s.zeroize();
101    }
102}
103
104/// 2 x `u64` values
105#[derive(Copy, Clone, Debug, Default, Eq, PartialEq)]
106struct U64x2(u64, u64);
107
108impl From<&Block> for U64x2 {
109    fn from(bytes: &Block) -> U64x2 {
110        U64x2(
111            u64::from_le_bytes(bytes[..8].try_into().unwrap()),
112            u64::from_le_bytes(bytes[8..].try_into().unwrap()),
113        )
114    }
115}
116
117impl From<u128> for U64x2 {
118    fn from(x: u128) -> Self {
119        U64x2((x >> 64) as u64, (x) as u64)
120    }
121}
122
123#[allow(clippy::suspicious_arithmetic_impl)]
124impl Add for U64x2 {
125    type Output = Self;
126
127    /// Adds two POLYVAL field elements.
128    fn add(self, rhs: Self) -> Self::Output {
129        U64x2(self.0 ^ rhs.0, self.1 ^ rhs.1)
130    }
131}
132
133#[allow(clippy::suspicious_arithmetic_impl)]
134impl Mul for U64x2 {
135    type Output = Self;
136
137    /// Computes carryless POLYVAL multiplication over GF(2^128) in constant time.
138    ///
139    /// Method described at:
140    /// <https://www.bearssl.org/constanttime.html#ghash-for-gcm>
141    ///
142    /// POLYVAL multiplication is effectively the little endian equivalent of
143    /// GHASH multiplication, aside from one small detail described here:
144    ///
145    /// <https://crypto.stackexchange.com/questions/66448/how-does-bearssls-gcm-modular-reduction-work/66462#66462>
146    ///
147    /// > The product of two bit-reversed 128-bit polynomials yields the
148    /// > bit-reversed result over 255 bits, not 256. The BearSSL code ends up
149    /// > with a 256-bit result in zw[], and that value is shifted by one bit,
150    /// > because of that reversed convention issue. Thus, the code must
151    /// > include a shifting step to put it back where it should
152    ///
153    /// This shift is unnecessary for POLYVAL and has been removed.
154    fn mul(self, rhs: Self) -> Self {
155        let h0 = self.0;
156        let h1 = self.1;
157        let h0r = rev64(h0);
158        let h1r = rev64(h1);
159        let h2 = h0 ^ h1;
160        let h2r = h0r ^ h1r;
161
162        let y0 = rhs.0;
163        let y1 = rhs.1;
164        let y0r = rev64(y0);
165        let y1r = rev64(y1);
166        let y2 = y0 ^ y1;
167        let y2r = y0r ^ y1r;
168        let z0 = bmul64(y0, h0);
169        let z1 = bmul64(y1, h1);
170
171        let mut z2 = bmul64(y2, h2);
172        let mut z0h = bmul64(y0r, h0r);
173        let mut z1h = bmul64(y1r, h1r);
174        let mut z2h = bmul64(y2r, h2r);
175
176        z2 ^= z0 ^ z1;
177        z2h ^= z0h ^ z1h;
178        z0h = rev64(z0h) >> 1;
179        z1h = rev64(z1h) >> 1;
180        z2h = rev64(z2h) >> 1;
181
182        let v0 = z0;
183        let mut v1 = z0h ^ z2;
184        let mut v2 = z1 ^ z2h;
185        let mut v3 = z1h;
186
187        v2 ^= v0 ^ (v0 >> 1) ^ (v0 >> 2) ^ (v0 >> 7);
188        v1 ^= (v0 << 63) ^ (v0 << 62) ^ (v0 << 57);
189        v3 ^= v1 ^ (v1 >> 1) ^ (v1 >> 2) ^ (v1 >> 7);
190        v2 ^= (v1 << 63) ^ (v1 << 62) ^ (v1 << 57);
191
192        U64x2(v2, v3)
193    }
194}
195
196#[cfg(feature = "zeroize")]
197impl Zeroize for U64x2 {
198    fn zeroize(&mut self) {
199        self.0.zeroize();
200        self.1.zeroize();
201    }
202}
203
204/// Multiplication in GF(2)[X], truncated to the low 64-bits, with “holes”
205/// (sequences of zeroes) to avoid carry spilling.
206///
207/// When carries do occur, they wind up in a "hole" and are subsequently masked
208/// out of the result.
209fn bmul64(x: u64, y: u64) -> u64 {
210    let x0 = Wrapping(x & 0x1111_1111_1111_1111);
211    let x1 = Wrapping(x & 0x2222_2222_2222_2222);
212    let x2 = Wrapping(x & 0x4444_4444_4444_4444);
213    let x3 = Wrapping(x & 0x8888_8888_8888_8888);
214    let y0 = Wrapping(y & 0x1111_1111_1111_1111);
215    let y1 = Wrapping(y & 0x2222_2222_2222_2222);
216    let y2 = Wrapping(y & 0x4444_4444_4444_4444);
217    let y3 = Wrapping(y & 0x8888_8888_8888_8888);
218
219    let mut z0 = ((x0 * y0) ^ (x1 * y3) ^ (x2 * y2) ^ (x3 * y1)).0;
220    let mut z1 = ((x0 * y1) ^ (x1 * y0) ^ (x2 * y3) ^ (x3 * y2)).0;
221    let mut z2 = ((x0 * y2) ^ (x1 * y1) ^ (x2 * y0) ^ (x3 * y3)).0;
222    let mut z3 = ((x0 * y3) ^ (x1 * y2) ^ (x2 * y1) ^ (x3 * y0)).0;
223
224    z0 &= 0x1111_1111_1111_1111;
225    z1 &= 0x2222_2222_2222_2222;
226    z2 &= 0x4444_4444_4444_4444;
227    z3 &= 0x8888_8888_8888_8888;
228
229    z0 | z1 | z2 | z3
230}
231
232/// Bit-reverse a `u64` in constant time
233fn rev64(mut x: u64) -> u64 {
234    x = ((x & 0x5555_5555_5555_5555) << 1) | ((x >> 1) & 0x5555_5555_5555_5555);
235    x = ((x & 0x3333_3333_3333_3333) << 2) | ((x >> 2) & 0x3333_3333_3333_3333);
236    x = ((x & 0x0f0f_0f0f_0f0f_0f0f) << 4) | ((x >> 4) & 0x0f0f_0f0f_0f0f_0f0f);
237    x = ((x & 0x00ff_00ff_00ff_00ff) << 8) | ((x >> 8) & 0x00ff_00ff_00ff_00ff);
238    x = ((x & 0xffff_0000_ffff) << 16) | ((x >> 16) & 0xffff_0000_ffff);
239    (x << 32) | (x >> 32)
240}
polyval/backend/soft64.rs

polyval/backend/
soft64.rs
