hashx/
siphash.rs

Help
1//! HashX-flavored SipHash implementation
2//!
3//! We need SipHash to generate parts of HashX's internal state: the initial
4//! register values for the hash program, and the stream of pseudorandom numbers
5//! used to generate the program itself. The fundamentals are as described in
6//! the SipHash paper, but much of the algorithm around the basic add-rotate-xor
7//! core has been modified:
8//!
9//!   - Seeding: vanilla SipHash uses a nothing-up-my-sleeve constant to safely
10//!     init 256 bits of internal state from 128 bits of user-supplied key data.
11//!     The HashX implementation instead uses Blake2b to pre-process an
12//!     arbitrary sized seed into a 512-bit pseudorandom value which is directly
13//!     used to init the state of two SipHash instances.
14//!
15//!   - The SipHash paper describes a compression function that includes a
16//!     length indicator and padding, and supports variable length inputs. This
17//!     is not needed, and HashX uses its own way of constructing a SipHash2,4
18//!     instance that takes a counter as input.
19//!
20//!   - HashX also needs SipHash1,3 which it uses for a lightweight pseudorandom
21//!     number stream internally. This variant isn't typically used on its own
22//!     or implemented in libraries. HashX also uses its own counter input
23//!     construction method.
24//!
25//!   - In addition to the SipHash1,3 and SipHash2,4 counter modes, HashX
26//!     makes use of raw SipRounds while digesting a RegisterFile after the
27//!     generated hash function completes.
28//!
29//! SipHash is defined by Jean-Philippe Aumasson and Daniel J.Bernstein in
30//! their paper "SipHash: a fast short-input PRF" (2012).
31
32use blake2::digest::block_buffer::LazyBuffer;
33use blake2::digest::core_api::{BlockSizeUser, UpdateCore, VariableOutputCore};
34use blake2::Blake2bVarCore;
35use std::fmt::{self, Debug};
36
37/// Internal state of one SipHash instance
38#[derive(Clone, Copy, Eq, PartialEq)]
39pub struct SipState {
40    /// State variable V0 as defined in the SipHash paper
41    pub(crate) v0: u64,
42    /// State variable V1 as defined in the SipHash paper
43    pub(crate) v1: u64,
44    /// State variable V2 as defined in the SipHash paper
45    pub(crate) v2: u64,
46    /// State variable V3 as defined in the SipHash paper
47    pub(crate) v3: u64,
48}
49
50impl Debug for SipState {
51    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
52        write!(
53            f,
54            "SipState[ {:#018x}, {:#018x}, {:#018x}, {:#018x} ]",
55            self.v0, self.v1, self.v2, self.v3
56        )
57    }
58}
59
60impl From<SipState> for [u64; 4] {
61    #[inline(always)]
62    fn from(s: SipState) -> Self {
63        [s.v0, s.v1, s.v2, s.v3]
64    }
65}
66
67impl From<[u64; 4]> for SipState {
68    #[inline(always)]
69    fn from(a: [u64; 4]) -> Self {
70        Self::new(a[0], a[1], a[2], a[3])
71    }
72}
73
74impl SipState {
75    /// Size of the internal SipHash state
76    const SIZE: usize = 32;
77
78    /// Construct a new SipHash state.
79    ///
80    /// This takes the parameters `v0..v3` as defined in the SipHash paper.
81    #[inline(always)]
82    pub fn new(v0: u64, v1: u64, v2: u64, v3: u64) -> Self {
83        Self { v0, v1, v2, v3 }
84    }
85
86    /// Construct a new SipHash state directly from bytes.
87    ///
88    /// This is not suitable for use with arbitrary user input, such
89    /// as all zeroes. HashX always generates these initialization vectors
90    /// using another pseudorandom function (Blake2b).
91    #[inline(always)]
92    pub fn new_from_bytes(bytes: &[u8; Self::SIZE]) -> Self {
93        Self::new(
94            u64::from_le_bytes(bytes[0..8].try_into().expect("slice length matches")),
95            u64::from_le_bytes(bytes[8..16].try_into().expect("slice length matches")),
96            u64::from_le_bytes(bytes[16..24].try_into().expect("slice length matches")),
97            u64::from_le_bytes(bytes[24..32].try_into().expect("slice length matches")),
98        )
99    }
100
101    /// Construct a pair of SipHash instances from a seed.
102    ///
103    /// The seed may be an arbitrary length. Takes the Blake2b hash of the seed
104    /// using the correct settings for HashX, splitting the digest into two
105    /// [`Self::new_from_bytes()`] calls.
106    pub fn pair_from_seed(seed: &[u8]) -> (SipState, SipState) {
107        /// Choice of Blake2b engine; we need to use its lower level
108        /// interface, to access new_with_params().
109        type Core = Blake2bVarCore;
110
111        /// Blake2b block size
112        type BlockSize = <Core as BlockSizeUser>::BlockSize;
113
114        let mut buffer = LazyBuffer::<BlockSize>::new(&[]);
115        let mut core = Core::new_with_params(b"HashX v1", &[], 0, 64);
116        let mut digest = Default::default();
117
118        buffer.digest_blocks(seed, |blocks| core.update_blocks(blocks));
119        core.finalize_variable_core(&mut buffer, &mut digest);
120
121        (
122            Self::new_from_bytes(digest[0..32].try_into().expect("slice length matches")),
123            Self::new_from_bytes(digest[32..64].try_into().expect("slice length matches")),
124        )
125    }
126
127    /// One `SipRound` as defined in the SipHash paper
128    ///
129    /// Modifies the `SipState` in-place.
130    #[inline(always)]
131    pub(crate) fn sip_round(&mut self) {
132        self.v0 = self.v0.wrapping_add(self.v1);
133        self.v2 = self.v2.wrapping_add(self.v3);
134        self.v1 = self.v1.rotate_left(13);
135        self.v3 = self.v3.rotate_left(16);
136        self.v1 ^= self.v0;
137        self.v3 ^= self.v2;
138        self.v0 = self.v0.rotate_left(32);
139
140        self.v2 = self.v2.wrapping_add(self.v1);
141        self.v0 = self.v0.wrapping_add(self.v3);
142        self.v1 = self.v1.rotate_left(17);
143        self.v3 = self.v3.rotate_left(21);
144        self.v1 ^= self.v2;
145        self.v3 ^= self.v0;
146        self.v2 = self.v2.rotate_left(32);
147    }
148}
149
150/// HashX's flavor of SipHash1,3 counter mode with 64-bit output
151pub(crate) fn siphash13_ctr(key: SipState, input: u64) -> u64 {
152    let mut s = key;
153    s.v3 ^= input;
154
155    s.sip_round();
156
157    s.v0 ^= input;
158    s.v2 ^= 0xff;
159
160    s.sip_round();
161    s.sip_round();
162    s.sip_round();
163
164    s.v0 ^ s.v1 ^ s.v2 ^ s.v3
165}
166
167/// HashX's flavor of SipHash2,4 counter mode with 512-bit output
168pub(crate) fn siphash24_ctr(key: SipState, input: u64) -> [u64; 8] {
169    let mut s = key;
170    s.v1 ^= 0xee;
171    s.v3 ^= input;
172
173    s.sip_round();
174    s.sip_round();
175
176    s.v0 ^= input;
177    s.v2 ^= 0xee;
178
179    s.sip_round();
180    s.sip_round();
181    s.sip_round();
182    s.sip_round();
183
184    let mut t = s;
185    t.v1 ^= 0xdd;
186
187    t.sip_round();
188    t.sip_round();
189    t.sip_round();
190    t.sip_round();
191
192    [s.v0, s.v1, s.v2, s.v3, t.v0, t.v1, t.v2, t.v3]
193}
194
195#[cfg(test)]
196mod test {
197    use super::{siphash24_ctr, SipState};
198
199    #[test]
200    fn sip_round_vectors() {
201        // Test values from Appendix A of the SipHash paper
202
203        // Includes constants, first message block, and keys
204        let mut s = SipState::new(
205            0x7469686173716475,
206            0x6b617f6d656e6665,
207            0x6b7f62616d677361,
208            0x7c6d6c6a717c6d7b,
209        );
210
211        // Rounds for first example message block
212        s.sip_round();
213        s.sip_round();
214
215        // Sample output after two rounds
216        let result: [u64; 4] = s.into();
217        assert_eq!(
218            result,
219            [
220                0x4d07749cdd0858e0,
221                0x0d52f6f62a4f59a4,
222                0x634cb3577b01fd3d,
223                0xa5224d6f55c7d9c8,
224            ]
225        );
226    }
227
228    #[test]
229    fn seed_hash_vectors() {
230        // Check against seed hash values seen during tor unit tests
231
232        let (key0, key1) = SipState::pair_from_seed(b"");
233        assert_eq!(
234            key0,
235            [
236                0xcaca7747b3c5be92,
237                0x296abd268b5f21de,
238                0x9e4c4d2f95add72a,
239                0x00ac7f27331ec1c7
240            ]
241            .into()
242        );
243        assert_eq!(
244            key1,
245            SipState::new(
246                0xc32d197f86f1c419,
247                0xbbe47abaf4e28dfe,
248                0xc174b9d5786f28d4,
249                0xa2bd4197b22a035a,
250            )
251        );
252
253        let (key0, key1) = SipState::pair_from_seed(b"abc");
254        assert_eq!(
255            key0,
256            SipState {
257                v0: 0xc538fa793ed99a50,
258                v1: 0xd2fd3e8871310ea1,
259                v2: 0xd2be7d8aff1f823a,
260                v3: 0x557b84887cfe6c0e,
261            }
262        );
263        assert_eq!(
264            key1,
265            SipState {
266                v0: 0x610218b2104c3f5a,
267                v1: 0x4222e8a58e702331,
268                v2: 0x0d53a2563a33148d,
269                v3: 0x7c24f97da4bff21f,
270            }
271        );
272    }
273
274    #[test]
275    fn siphash24_ctr_vectors() {
276        // Check against siphash24_ctr output seen during tor unit tests
277
278        let (_key0, key1) = SipState::pair_from_seed(b"abc");
279        assert_eq!(
280            siphash24_ctr(key1, 0),
281            [
282                0xe8a59a4b3ccb5e4a,
283                0xe45153f8bb93540d,
284                0x32c6accb77141596,
285                0xd5deaa56a3b1cfd7,
286                0xc5f6ff8435b80af4,
287                0xd26fd3ccfdf2a04f,
288                0x3d7fa0f14653348e,
289                0xf5a4750be0aa2ccf,
290            ]
291        );
292        assert_eq!(
293            siphash24_ctr(key1, 999),
294            [
295                0x312470a168998148,
296                0xc9624473753e8d0e,
297                0xc0879d8f0de37dbf,
298                0xfa4cc48f4f6e95d5,
299                0x9940dc39eaaceb2c,
300                0x29143feae886f221,
301                0x98f119184c4cffe5,
302                0xcf1571c6d0d18131,
303            ]
304        );
305    }
306}
hashx/siphash.rs

hashx/
siphash.rs
