universal_hash/
lib.rs

1//! Traits for [Universal Hash Functions].
2//!
3//! # About universal hashes
4//!
5//! Universal hash functions provide a "universal family" of possible
6//! hash functions where a given member of a family is selected by a key.
7//!
8//! They are well suited to the purpose of "one time authenticators" for a
9//! sequence of bytestring inputs, as their construction has a number of
10//! desirable properties such as pairwise independence as well as amenability
11//! to efficient implementations, particularly when implemented using SIMD
12//! instructions.
13//!
14//! When combined with a cipher, such as in Galois/Counter Mode (GCM) or the
15//! Salsa20 family AEAD constructions, they can provide the core functionality
16//! for a Message Authentication Code (MAC).
17//!
18//! [Universal Hash Functions]: https://en.wikipedia.org/wiki/Universal_hashing
19
20#![no_std]
21#![doc(
22    html_logo_url = "https://raw.githubusercontent.com/RustCrypto/media/8f1a9894/logo.svg",
23    html_favicon_url = "https://raw.githubusercontent.com/RustCrypto/media/8f1a9894/logo.svg"
24)]
25#![cfg_attr(docsrs, feature(doc_cfg))]
26#![deny(unsafe_code)]
27#![warn(missing_docs, rust_2018_idioms)]
28
29#[cfg(feature = "std")]
30extern crate std;
31
32pub use crypto_common::{
33    self, generic_array,
34    typenum::{self, consts},
35    Block, Key, KeyInit, ParBlocks, Reset,
36};
37
38use core::slice;
39use crypto_common::{BlockSizeUser, ParBlocksSizeUser};
40use generic_array::{ArrayLength, GenericArray};
41use subtle::ConstantTimeEq;
42use typenum::Unsigned;
43
44/// Trait implemented by UHF backends.
45pub trait UhfBackend: ParBlocksSizeUser {
46    /// Process single block.
47    fn proc_block(&mut self, block: &Block<Self>);
48
49    /// Process several blocks in parallel.
50    #[inline(always)]
51    fn proc_par_blocks(&mut self, blocks: &ParBlocks<Self>) {
52        for block in blocks {
53            self.proc_block(block);
54        }
55    }
56
57    /// Returns the number of blocks that should be passed to `Self::proc_block` before
58    /// `Self::proc_par_blocks` can be used efficiently. This is always less than
59    /// `Self::ParBlocksSize`.
60    fn blocks_needed_to_align(&self) -> usize {
61        0
62    }
63}
64
65/// Trait for [`UhfBackend`] users.
66///
67/// This trait is used to define rank-2 closures.
68pub trait UhfClosure: BlockSizeUser {
69    /// Execute closure with the provided UHF backend.
70    fn call<B: UhfBackend<BlockSize = Self::BlockSize>>(self, backend: &mut B);
71}
72
73/// The [`UniversalHash`] trait defines a generic interface for universal hash
74/// functions.
75pub trait UniversalHash: BlockSizeUser + Sized {
76    /// Update hash function state using the provided rank-2 closure.
77    fn update_with_backend(&mut self, f: impl UhfClosure<BlockSize = Self::BlockSize>);
78
79    /// Update hash function state with the provided block.
80    #[inline]
81    fn update(&mut self, blocks: &[Block<Self>]) {
82        struct Ctx<'a, BS: ArrayLength<u8>> {
83            blocks: &'a [Block<Self>],
84        }
85
86        impl<'a, BS: ArrayLength<u8>> BlockSizeUser for Ctx<'a, BS> {
87            type BlockSize = BS;
88        }
89
90        impl<'a, BS: ArrayLength<u8>> UhfClosure for Ctx<'a, BS> {
91            #[inline(always)]
92            fn call<B: UhfBackend<BlockSize = BS>>(self, backend: &mut B) {
93                let pb = B::ParBlocksSize::USIZE;
94                if pb > 1 {
95                    let (par_blocks, tail) = to_blocks(self.blocks);
96                    for par_block in par_blocks {
97                        backend.proc_par_blocks(par_block);
98                    }
99                    for block in tail {
100                        backend.proc_block(block);
101                    }
102                } else {
103                    for block in self.blocks {
104                        backend.proc_block(block);
105                    }
106                }
107            }
108        }
109
110        self.update_with_backend(Ctx { blocks });
111    }
112
113    /// Input data into the universal hash function. If the length of the
114    /// data is not a multiple of the block size, the remaining data is
115    /// padded with zeroes up to the `BlockSize`.
116    ///
117    /// This approach is frequently used by AEAD modes which use
118    /// Message Authentication Codes (MACs) based on universal hashing.
119    #[inline]
120    fn update_padded(&mut self, data: &[u8]) {
121        let (blocks, tail) = to_blocks(data);
122
123        self.update(blocks);
124
125        if !tail.is_empty() {
126            let mut padded_block = GenericArray::default();
127            padded_block[..tail.len()].copy_from_slice(tail);
128            self.update(slice::from_ref(&padded_block));
129        }
130    }
131
132    /// Retrieve result and consume hasher instance.
133    fn finalize(self) -> Block<Self>;
134
135    /// Obtain the [`Output`] of a [`UniversalHash`] computation and reset it back
136    /// to its initial state.
137    #[inline]
138    fn finalize_reset(&mut self) -> Block<Self>
139    where
140        Self: Clone + Reset,
141    {
142        let ret = self.clone().finalize();
143        self.reset();
144        ret
145    }
146
147    /// Verify the [`UniversalHash`] of the processed input matches
148    /// a given `expected` value.
149    ///
150    /// This is useful when constructing Message Authentication Codes (MACs)
151    /// from universal hash functions.
152    #[inline]
153    fn verify(self, expected: &Block<Self>) -> Result<(), Error> {
154        if self.finalize().ct_eq(expected).into() {
155            Ok(())
156        } else {
157            Err(Error)
158        }
159    }
160}
161
162/// Error type used by the [`UniversalHash::verify`] method
163/// to indicate that UHF output is not equal the expected value.
164#[derive(Default, Debug, Copy, Clone, Eq, PartialEq)]
165pub struct Error;
166
167impl core::fmt::Display for Error {
168    #[inline]
169    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
170        f.write_str("UHF output mismatch")
171    }
172}
173
174#[cfg(feature = "std")]
175#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
176impl std::error::Error for Error {}
177
178/// Split message into slice of blocks and leftover tail.
179// TODO: replace with `slice::as_chunks` on migration to const generics
180#[inline(always)]
181fn to_blocks<T, N: ArrayLength<T>>(data: &[T]) -> (&[GenericArray<T, N>], &[T]) {
182    let nb = data.len() / N::USIZE;
183    let (left, right) = data.split_at(nb * N::USIZE);
184    let p = left.as_ptr() as *const GenericArray<T, N>;
185    // SAFETY: we guarantee that `blocks` does not point outside of `data`
186    // and `p` is valid for reads
187    #[allow(unsafe_code)]
188    let blocks = unsafe { slice::from_raw_parts(p, nb) };
189    (blocks, right)
190}
universal_hash/lib.rs

universal_hash/
lib.rs
