capsules_extra/
sip_hash.rs

Help
1// Licensed under the Apache License, Version 2.0 or the MIT License.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Copyright Tock Contributors 2022.
4
5//! Tock SipHash capsule.
6//!
7//! This is a async implementation of the SipHash.
8//!
9//! This capsule was originally written to be used as part of Tock's
10//! key/value store. SipHash was used as it is generally fast, while also
11//! being resilient against DOS attacks from userspace
12//! (unlike <https://github.com/servo/rust-fnv>).
13//!
14//! Read <https://github.com/veorq/SipHash/blob/master/README.md> for more
15//! details on SipHash.
16//!
17//! The implementation is based on the Rust implementation from
18//! rust-core, available here: <https://github.com/jedisct1/rust-siphash>
19//!
20//! Copyright 2012-2016 The Rust Project Developers.
21//! Copyright 2016-2021 Frank Denis.
22//! Copyright 2021 Western Digital
23//!
24//! Licensed under the Apache License, Version 2.0 LICENSE-APACHE or
25//! <http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
26//! LICENSE-MIT or <http://opensource.org/licenses/MIT>, at your
27//! option.
28
29use core::cell::Cell;
30use core::{cmp, mem};
31use kernel::deferred_call::{DeferredCall, DeferredCallClient};
32use kernel::hil::hasher::{Client, Hasher, SipHash};
33use kernel::utilities::cells::{OptionalCell, TakeCell};
34use kernel::utilities::leasable_buffer::SubSlice;
35use kernel::utilities::leasable_buffer::SubSliceMut;
36use kernel::utilities::leasable_buffer::SubSliceMutImmut;
37use kernel::ErrorCode;
38
39pub struct SipHasher24<'a> {
40    client: OptionalCell<&'a dyn Client<8>>,
41
42    hasher: Cell<SipHasher>,
43
44    add_data_deferred_call: Cell<bool>,
45    complete_deferred_call: Cell<bool>,
46    deferred_call: DeferredCall,
47
48    data_buffer: Cell<Option<SubSliceMutImmut<'static, u8>>>,
49    out_buffer: TakeCell<'static, [u8; 8]>,
50}
51
52#[derive(Debug, Clone, Copy)]
53struct SipHasher {
54    k0: u64,
55    k1: u64,
56    length: usize, // how many bytes we've processed
57    state: State,  // hash State
58    tail: u64,     // unprocessed bytes le
59    ntail: usize,  // how many bytes in tail are valid
60}
61
62#[derive(Debug, Clone, Copy)]
63struct State {
64    // v0, v2 and v1, v3 show up in pairs in the algorithm,
65    // and simd implementations of SipHash will use vectors
66    // of v02 and v13. By placing them in this order in the struct,
67    // the compiler can pick up on just a few simd optimizations by itself.
68    v0: u64,
69    v2: u64,
70    v1: u64,
71    v3: u64,
72}
73
74impl SipHasher24<'_> {
75    pub fn new() -> Self {
76        let hasher = SipHasher {
77            k0: 0,
78            k1: 0,
79            length: 0,
80            state: State {
81                v0: 0x736f6d6570736575,
82                v1: 0x646f72616e646f6d,
83                v2: 0x6c7967656e657261,
84                v3: 0x7465646279746573,
85            },
86            ntail: 0,
87            tail: 0,
88        };
89
90        Self {
91            client: OptionalCell::empty(),
92            hasher: Cell::new(hasher),
93            add_data_deferred_call: Cell::new(false),
94            complete_deferred_call: Cell::new(false),
95            deferred_call: DeferredCall::new(),
96            data_buffer: Cell::new(None),
97            out_buffer: TakeCell::empty(),
98        }
99    }
100
101    pub fn new_with_keys(k0: u64, k1: u64) -> Self {
102        let hasher = SipHasher {
103            k0,
104            k1,
105            length: 0,
106            state: State {
107                v0: 0x736f6d6570736575,
108                v1: 0x646f72616e646f6d,
109                v2: 0x6c7967656e657261,
110                v3: 0x7465646279746573,
111            },
112            ntail: 0,
113            tail: 0,
114        };
115
116        Self {
117            client: OptionalCell::empty(),
118            hasher: Cell::new(hasher),
119            add_data_deferred_call: Cell::new(false),
120            complete_deferred_call: Cell::new(false),
121            deferred_call: DeferredCall::new(),
122            data_buffer: Cell::new(None),
123            out_buffer: TakeCell::empty(),
124        }
125    }
126}
127
128macro_rules! compress {
129    ($state:expr) => {{
130        compress!($state.v0, $state.v1, $state.v2, $state.v3)
131    }};
132    ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => {{
133        $v0 = $v0.wrapping_add($v1);
134        $v1 = $v1.rotate_left(13);
135        $v1 ^= $v0;
136        $v0 = $v0.rotate_left(32);
137        $v2 = $v2.wrapping_add($v3);
138        $v3 = $v3.rotate_left(16);
139        $v3 ^= $v2;
140        $v0 = $v0.wrapping_add($v3);
141        $v3 = $v3.rotate_left(21);
142        $v3 ^= $v0;
143        $v2 = $v2.wrapping_add($v1);
144        $v1 = $v1.rotate_left(17);
145        $v1 ^= $v2;
146        $v2 = $v2.rotate_left(32);
147    }};
148}
149
150fn read_le_u64(input: &[u8]) -> u64 {
151    let mut eight_buf: [u8; 8] = [0; 8];
152    for i in 0..8 {
153        eight_buf[i] = *input.get(i).unwrap_or(&0);
154    }
155    u64::from_le_bytes(eight_buf)
156}
157
158fn read_le_u16(input: &[u8]) -> u16 {
159    let (int_bytes, _rest) = input.split_at(mem::size_of::<u16>());
160    u16::from_le_bytes(int_bytes.try_into().unwrap())
161}
162
163#[inline]
164fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 {
165    debug_assert!(len < 8);
166    let mut i = 0; // current byte index (from LSB) in the output u64
167    let mut out = 0;
168    if i + 3 < len {
169        out = read_le_u64(&buf[start + i..]);
170        i += 4;
171    }
172    if i + 1 < len {
173        out |= (read_le_u16(&buf[start + i..]) as u64) << (i * 8);
174        i += 2
175    }
176    if i < len {
177        out |= (buf[start + i] as u64) << (i * 8);
178        i += 1;
179    }
180    debug_assert_eq!(i, len);
181    out
182}
183
184impl<'a> Hasher<'a, 8> for SipHasher24<'a> {
185    fn set_client(&'a self, client: &'a dyn Client<8>) {
186        self.client.set(client);
187    }
188
189    fn add_data(
190        &self,
191        data: SubSlice<'static, u8>,
192    ) -> Result<usize, (ErrorCode, SubSlice<'static, u8>)> {
193        let length = data.len();
194        let mut hasher = self.hasher.get();
195
196        hasher.length += length;
197
198        let mut needed = 0;
199
200        if hasher.ntail != 0 {
201            needed = 8 - hasher.ntail;
202            hasher.tail |=
203                u8to64_le(data.as_slice(), 0, cmp::min(length, needed)) << (8 * hasher.ntail);
204            if length < needed {
205                hasher.ntail += length;
206                return Ok(length);
207            } else {
208                hasher.state.v3 ^= hasher.tail;
209                compress!(&mut hasher.state);
210                compress!(&mut hasher.state);
211                hasher.state.v0 ^= hasher.tail;
212                hasher.ntail = 0;
213            }
214        }
215
216        // Buffered tail is now flushed, process new input.
217        let len = length - needed;
218        let left = len & 0x7;
219
220        let mut i = needed;
221        while i < len - left {
222            let mi = read_le_u64(&data[i..]);
223
224            hasher.state.v3 ^= mi;
225            compress!(&mut hasher.state);
226            compress!(&mut hasher.state);
227            hasher.state.v0 ^= mi;
228
229            i += 8;
230        }
231
232        hasher.tail = u8to64_le(data.as_slice(), i, left);
233        hasher.ntail = left;
234
235        self.hasher.set(hasher);
236        self.data_buffer
237            .set(Some(SubSliceMutImmut::Immutable(data)));
238
239        self.add_data_deferred_call.set(true);
240        self.deferred_call.set();
241
242        Ok(length)
243    }
244
245    fn add_mut_data(
246        &self,
247        mut data: SubSliceMut<'static, u8>,
248    ) -> Result<usize, (ErrorCode, SubSliceMut<'static, u8>)> {
249        let length = data.len();
250        let mut hasher = self.hasher.get();
251
252        hasher.length += length;
253
254        let mut needed = 0;
255
256        if hasher.ntail != 0 {
257            needed = 8 - hasher.ntail;
258            hasher.tail |=
259                u8to64_le(data.as_slice(), 0, cmp::min(length, needed)) << (8 * hasher.ntail);
260            if length < needed {
261                hasher.ntail += length;
262                return Ok(length);
263            } else {
264                hasher.state.v3 ^= hasher.tail;
265                compress!(&mut hasher.state);
266                compress!(&mut hasher.state);
267                hasher.state.v0 ^= hasher.tail;
268                hasher.ntail = 0;
269            }
270        }
271
272        // Buffered tail is now flushed, process new input.
273        let len = length - needed;
274        let left = len & 0x7;
275
276        let mut i = needed;
277        while i < len - left {
278            let mi = read_le_u64(&data[i..]);
279
280            hasher.state.v3 ^= mi;
281            compress!(&mut hasher.state);
282            compress!(&mut hasher.state);
283            hasher.state.v0 ^= mi;
284
285            i += 8;
286        }
287
288        hasher.tail = u8to64_le(data.as_slice(), i, left);
289        hasher.ntail = left;
290
291        self.hasher.set(hasher);
292        self.data_buffer.set(Some(SubSliceMutImmut::Mutable(data)));
293
294        self.add_data_deferred_call.set(true);
295        self.deferred_call.set();
296
297        Ok(length)
298    }
299
300    fn run(
301        &'a self,
302        digest: &'static mut [u8; 8],
303    ) -> Result<(), (ErrorCode, &'static mut [u8; 8])> {
304        let mut hasher = self.hasher.get();
305
306        let b: u64 = ((hasher.length as u64 & 0xff) << 56) | hasher.tail;
307
308        hasher.state.v3 ^= b;
309        compress!(&mut hasher.state);
310        compress!(&mut hasher.state);
311        hasher.state.v0 ^= b;
312
313        hasher.state.v2 ^= 0xff;
314        compress!(&mut hasher.state);
315        compress!(&mut hasher.state);
316        compress!(&mut hasher.state);
317        compress!(&mut hasher.state);
318
319        self.hasher.set(hasher);
320        self.out_buffer.replace(digest);
321
322        self.complete_deferred_call.set(true);
323        self.deferred_call.set();
324
325        Ok(())
326    }
327
328    fn clear_data(&self) {
329        let mut hasher = self.hasher.get();
330
331        hasher.length = 0;
332        hasher.state.v0 = hasher.k0 ^ 0x736f6d6570736575;
333        hasher.state.v1 = hasher.k1 ^ 0x646f72616e646f6d;
334        hasher.state.v2 = hasher.k0 ^ 0x6c7967656e657261;
335        hasher.state.v3 = hasher.k1 ^ 0x7465646279746573;
336        hasher.ntail = 0;
337
338        self.hasher.set(hasher);
339    }
340}
341
342impl SipHash for SipHasher24<'_> {
343    fn set_keys(&self, k0: u64, k1: u64) -> Result<(), ErrorCode> {
344        let mut hasher = self.hasher.get();
345
346        hasher.k0 = k0;
347        hasher.k1 = k1;
348
349        self.hasher.set(hasher);
350        self.clear_data();
351
352        Ok(())
353    }
354}
355
356impl DeferredCallClient for SipHasher24<'_> {
357    fn handle_deferred_call(&self) {
358        if self.add_data_deferred_call.get() {
359            self.add_data_deferred_call.set(false);
360
361            self.client.map(|client| {
362                self.data_buffer.take().map(|buffer| match buffer {
363                    SubSliceMutImmut::Immutable(b) => client.add_data_done(Ok(()), b),
364                    SubSliceMutImmut::Mutable(b) => client.add_mut_data_done(Ok(()), b),
365                });
366            });
367        }
368
369        if self.complete_deferred_call.get() {
370            self.complete_deferred_call.set(false);
371
372            self.client.map(|client| {
373                self.out_buffer.take().map(|buffer| {
374                    let state = self.hasher.get().state;
375
376                    let result = state.v0 ^ state.v1 ^ state.v2 ^ state.v3;
377                    buffer.copy_from_slice(&result.to_le_bytes());
378
379                    client.hash_done(Ok(()), buffer);
380                });
381            });
382        }
383    }
384
385    fn register(&'static self) {
386        self.deferred_call.register(self);
387    }
388}
capsules_extra/sip_hash.rs

capsules_extra/
sip_hash.rs
