lib_q_hash/
tuplehash.rs

1//! TupleHash implementation
2//!
3//! TupleHash is designed to hash tuples of input strings unambiguously.
4
5use alloc::vec;
6use alloc::vec::Vec;
7use core::fmt;
8
9use digest::block_api::{
10    AlgorithmName,
11    Block,
12    BlockSizeUser,
13    BufferKindUser,
14    Eager,
15    UpdateCore,
16};
17use digest::common::hazmat::{
18    DeserializeStateError,
19    SerializableState,
20    SerializedState,
21};
22use digest::consts::{
23    U16,
24    U32,
25    U136,
26    U168,
27    U400,
28};
29use digest::{
30    CollisionResistance,
31    ExtendableOutput,
32    HashMarker,
33    Reset,
34    Update,
35    XofReader,
36};
37
38use crate::cshake::{
39    CShake128,
40    CShake128Reader,
41    CShake256,
42    CShake256Reader,
43};
44use crate::utils::{
45    MAX_SP800185_FIXED_OUTPUT_BYTES,
46    left_encode,
47    right_encode,
48};
49
50/// TupleHash128 implementation
51#[derive(Clone)]
52pub struct TupleHash128 {
53    inner: CShake128,
54}
55
56/// TupleHash256 implementation
57#[derive(Clone)]
58pub struct TupleHash256 {
59    inner: CShake256,
60}
61
62/// TupleHash128 XOF reader
63#[derive(Clone)]
64pub struct TupleHash128Reader {
65    inner: CShake128Reader,
66}
67
68/// TupleHash256 XOF reader
69#[derive(Clone)]
70pub struct TupleHash256Reader {
71    inner: CShake256Reader,
72}
73
74macro_rules! impl_tuplehash {
75    (
76        $name:ident, $inner_type:ident, $reader_name:ident, $inner_reader_type:ident, $rate:ident, $alg_name:expr
77    ) => {
78        impl $name {
79            /// Creates a new TupleHash instance with the given customization string
80            pub fn new(custom: &[u8]) -> Self {
81                Self {
82                    inner: $inner_type::new_with_function_name(b"TupleHash", custom),
83                }
84            }
85
86            /// Update with a tuple of strings
87            pub fn update_tuple<T: AsRef<[u8]>>(&mut self, tuple: &[T]) {
88                let mut enc_buf = [0u8; 9];
89
90                for item in tuple {
91                    let item_bytes = item.as_ref();
92
93                    // encode_string(X[i])
94                    let encoded = left_encode((item_bytes.len() * 8) as u64, &mut enc_buf);
95                    Update::update(&mut self.inner, encoded);
96                    Update::update(&mut self.inner, item_bytes);
97                }
98            }
99
100            /// Update with a single string (for compatibility)
101            pub fn update(&mut self, data: &[u8]) {
102                let tuple = [data];
103                self.update_tuple(&tuple);
104            }
105
106            /// Finalize with specified output length.
107            ///
108            /// `output.len()` must not exceed [`MAX_SP800185_FIXED_OUTPUT_BYTES`]. For longer
109            /// output, use [`Self::xof`].
110            ///
111            /// Returns [`None`] if `output.len()` is greater than
112            /// [`MAX_SP800185_FIXED_OUTPUT_BYTES`].
113            pub fn finalize(mut self, output: &mut [u8]) -> Option<()> {
114                if output.len() > MAX_SP800185_FIXED_OUTPUT_BYTES {
115                    return None;
116                }
117                self.with_bitlength((output.len() * 8) as u64);
118                ExtendableOutput::finalize_xof_into(self.inner, output);
119                Some(())
120            }
121
122            /// Finalize with specified output length and return as [`Vec`].
123            ///
124            /// Returns [`None`] if `output_len` is greater than [`MAX_SP800185_FIXED_OUTPUT_BYTES`].
125            /// For longer output, use [`Self::xof`].
126            pub fn finalize_with_length(mut self, output_len: usize) -> Option<Vec<u8>> {
127                if output_len > MAX_SP800185_FIXED_OUTPUT_BYTES {
128                    return None;
129                }
130                let mut output = vec![0u8; output_len];
131                self.with_bitlength((output_len * 8) as u64);
132                ExtendableOutput::finalize_xof_into(self.inner, &mut output);
133                Some(output)
134            }
135
136            /// Returns an XOF reader for variable-length output.
137            ///
138            /// SP 800-185 encodes XOF mode with `right_encode(0)` (output bit length zero) before
139            /// squeezing.
140            ///
141            /// This consumes `self` and finalizes the sponge; you cannot call [`Self::update`] or
142            /// [`Self::update_tuple`] afterward on this value.
143            pub fn xof(mut self) -> $reader_name {
144                self.with_bitlength(0);
145                $reader_name {
146                    inner: ExtendableOutput::finalize_xof(self.inner),
147                }
148            }
149
150            fn with_bitlength(&mut self, bitlength: u64) {
151                let mut enc_buf = [0u8; 9];
152                let length_encoded = right_encode(bitlength, &mut enc_buf);
153                Update::update(&mut self.inner, length_encoded);
154            }
155        }
156
157        // Digest trait implementations
158        impl BlockSizeUser for $name {
159            type BlockSize = $rate;
160        }
161
162        impl BufferKindUser for $name {
163            type BufferKind = Eager;
164        }
165
166        impl HashMarker for $name {}
167
168        impl Update for $name {
169            #[inline]
170            fn update(&mut self, data: &[u8]) {
171                let tuple = [data];
172                self.update_tuple(&tuple);
173            }
174        }
175
176        impl UpdateCore for $name {
177            #[inline]
178            fn update_blocks(&mut self, blocks: &[Block<Self>]) {
179                for block in blocks {
180                    self.inner.update(block);
181                }
182            }
183        }
184
185        impl Reset for $name {
186            #[inline]
187            fn reset(&mut self) {
188                self.inner.reset();
189            }
190        }
191
192        impl AlgorithmName for $name {
193            fn write_alg_name(f: &mut fmt::Formatter<'_>) -> fmt::Result {
194                f.write_str($alg_name)
195            }
196        }
197
198        impl fmt::Debug for $name {
199            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
200                f.write_str(concat!(stringify!($name), " { ... }"))
201            }
202        }
203
204        #[cfg(feature = "zeroize")]
205        impl digest::zeroize::ZeroizeOnDrop for $name {}
206
207        // Implement Default trait
208        impl Default for $name {
209            fn default() -> Self {
210                Self::new(b"")
211            }
212        }
213
214        // Implement XofReader for the reader type
215        impl XofReader for $reader_name {
216            fn read(&mut self, buf: &mut [u8]) {
217                self.inner.read(buf);
218            }
219        }
220
221        impl fmt::Debug for $reader_name {
222            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
223                f.write_str(concat!(stringify!($reader_name), " { ... }"))
224            }
225        }
226    };
227}
228
229impl_tuplehash!(
230    TupleHash128,
231    CShake128,
232    TupleHash128Reader,
233    CShake128Reader,
234    U168,
235    "TupleHash128"
236);
237impl_tuplehash!(
238    TupleHash256,
239    CShake256,
240    TupleHash256Reader,
241    CShake256Reader,
242    U136,
243    "TupleHash256"
244);
245
246impl CollisionResistance for TupleHash128 {
247    type CollisionResistance = U16;
248}
249
250impl CollisionResistance for TupleHash256 {
251    type CollisionResistance = U32;
252}
253
254// Add SerializableState for TupleHash types
255impl SerializableState for TupleHash128 {
256    type SerializedStateSize = U400;
257
258    fn serialize(&self) -> SerializedState<Self> {
259        self.inner.serialize()
260    }
261
262    fn deserialize(
263        serialized_state: &SerializedState<Self>,
264    ) -> Result<Self, DeserializeStateError> {
265        let inner = CShake128::deserialize(serialized_state)?;
266        Ok(Self { inner })
267    }
268}
269
270impl SerializableState for TupleHash256 {
271    type SerializedStateSize = U400;
272
273    fn serialize(&self) -> SerializedState<Self> {
274        self.inner.serialize()
275    }
276
277    fn deserialize(
278        serialized_state: &SerializedState<Self>,
279    ) -> Result<Self, DeserializeStateError> {
280        let inner = CShake256::deserialize(serialized_state)?;
281        Ok(Self { inner })
282    }
283}
284
285#[cfg(test)]
286mod tests {
287    use super::*;
288
289    #[test]
290    fn test_tuplehash128_basic() {
291        let custom = b"custom";
292        let data = b"test";
293        let tuple = vec![data];
294
295        let mut tuplehash = TupleHash128::new(custom);
296        tuplehash.update_tuple(&tuple);
297
298        let mut output = [0u8; 32];
299        tuplehash.finalize(&mut output).unwrap();
300        assert_ne!(output, [0u8; 32]);
301    }
302
303    #[test]
304    fn test_tuplehash256_basic() {
305        let custom = b"custom";
306        let data = b"test";
307        let tuple = vec![data];
308
309        let mut tuplehash = TupleHash256::new(custom);
310        tuplehash.update_tuple(&tuple);
311
312        let mut output = [0u8; 64];
313        tuplehash.finalize(&mut output).unwrap();
314        assert_ne!(output, [0u8; 64]);
315    }
316
317    #[test]
318    fn test_tuplehash_xof() {
319        let custom = b"custom";
320        let data = b"test";
321        let tuple = vec![data];
322
323        let mut tuplehash = TupleHash128::new(custom);
324        tuplehash.update_tuple(&tuple);
325
326        let mut reader = tuplehash.xof();
327        let mut output = [0u8; 100];
328        reader.read(&mut output);
329        assert_ne!(output, [0u8; 100]);
330    }
331
332    #[test]
333    fn test_tuplehash_different_customs() {
334        let data = b"test";
335        let tuple = vec![data];
336
337        let mut tuplehash1 = TupleHash128::new(b"custom1");
338        tuplehash1.update_tuple(&tuple);
339        let mut output1 = [0u8; 32];
340        tuplehash1.finalize(&mut output1).unwrap();
341
342        let mut tuplehash2 = TupleHash128::new(b"custom2");
343        tuplehash2.update_tuple(&tuple);
344        let mut output2 = [0u8; 32];
345        tuplehash2.finalize(&mut output2).unwrap();
346
347        assert_ne!(output1, output2);
348    }
349
350    #[test]
351    fn test_tuplehash_empty_tuple() {
352        let custom = b"custom";
353        let tuple: Vec<&[u8]> = vec![];
354
355        let mut tuplehash = TupleHash128::new(custom);
356        tuplehash.update_tuple(&tuple);
357
358        let mut output = [0u8; 32];
359        tuplehash.finalize(&mut output).unwrap();
360        assert_ne!(output, [0u8; 32]);
361    }
362
363    #[test]
364    fn test_tuplehash_tuple_order_matters() {
365        // This is a key property of TupleHash - different tuple structures produce different hashes
366        let custom = b"custom";
367
368        // Tuple ("abc", "d")
369        let abc = b"abc";
370        let d = b"d";
371        let tuple1: Vec<&[u8]> = vec![abc, d];
372        let mut tuplehash1 = TupleHash128::new(custom);
373        tuplehash1.update_tuple(&tuple1);
374        let mut output1 = [0u8; 32];
375        tuplehash1.finalize(&mut output1).unwrap();
376
377        // Tuple ("ab", "cd") - same concatenated string but different tuple structure
378        let ab = b"ab";
379        let cd = b"cd";
380        let tuple2: Vec<&[u8]> = vec![ab, cd];
381        let mut tuplehash2 = TupleHash128::new(custom);
382        tuplehash2.update_tuple(&tuple2);
383        let mut output2 = [0u8; 32];
384        tuplehash2.finalize(&mut output2).unwrap();
385
386        // These should produce different hashes despite having the same concatenated content
387        assert_ne!(output1, output2);
388    }
389
390    #[test]
391    fn test_tuplehash_empty_strings() {
392        let custom = b"custom";
393
394        // Tuple with empty strings
395        let empty: &[u8] = &[];
396        let non_empty = b"non_empty";
397        let tuple = vec![empty, non_empty, empty];
398        let mut tuplehash = TupleHash128::new(custom);
399        tuplehash.update_tuple(&tuple);
400
401        let mut output = [0u8; 32];
402        tuplehash.finalize(&mut output).unwrap();
403        assert_ne!(output, [0u8; 32]);
404    }
405
406    #[test]
407    fn test_tuplehash_multiple_updates() {
408        let custom = b"custom";
409        let mut tuplehash = TupleHash128::new(custom);
410
411        // Update with multiple tuples
412        let first = b"first";
413        let tuple1 = vec![first];
414        tuplehash.update_tuple(&tuple1);
415
416        let second = b"second";
417        let tuple2 = vec![second];
418        tuplehash.update_tuple(&tuple2);
419
420        let mut output = [0u8; 32];
421        tuplehash.finalize(&mut output).unwrap();
422        assert_ne!(output, [0u8; 32]);
423    }
424
425    #[test]
426    fn test_tuplehash_large_tuples() {
427        let custom = b"custom";
428        let large_data: Vec<u8> = (0..1000).map(|i| (i % 256) as u8).collect();
429
430        let tuple = vec![&large_data[..]];
431        let mut tuplehash = TupleHash128::new(custom);
432        tuplehash.update_tuple(&tuple);
433
434        let mut output = [0u8; 64];
435        tuplehash.finalize(&mut output).unwrap();
436        assert_ne!(output, [0u8; 64]);
437    }
438
439    #[test]
440    fn test_tuplehash_256_vs_128() {
441        let custom = b"custom";
442        let tuple = vec![b"test_data"];
443
444        // TupleHash128
445        let mut tuplehash128 = TupleHash128::new(custom);
446        tuplehash128.update_tuple(&tuple);
447        let mut output128 = [0u8; 32];
448        tuplehash128.finalize(&mut output128).unwrap();
449
450        // TupleHash256
451        let mut tuplehash256 = TupleHash256::new(custom);
452        tuplehash256.update_tuple(&tuple);
453        let mut output256 = [0u8; 64];
454        tuplehash256.finalize(&mut output256).unwrap();
455
456        // Both should produce valid hashes
457        assert_ne!(output128, [0u8; 32]);
458        assert_ne!(output256, [0u8; 64]);
459    }
460
461    #[test]
462    fn test_tuplehash_reset() {
463        let custom = b"custom";
464        let data = b"test data";
465        let tuple = vec![data];
466
467        let mut tuplehash = TupleHash128::new(custom);
468        tuplehash.update_tuple(&tuple);
469
470        // Reset and test again
471        tuplehash.reset();
472        tuplehash.update_tuple(&tuple);
473
474        let mut output = [0u8; 32];
475        tuplehash.finalize(&mut output).unwrap();
476        assert_ne!(output, [0u8; 32]);
477    }
478
479    #[test]
480    fn test_tuplehash_default() {
481        let tuplehash = TupleHash128::default();
482        let data = b"test data";
483        let tuple = vec![data];
484
485        let mut hasher = tuplehash;
486        hasher.update_tuple(&tuple);
487        let result = hasher.finalize_with_length(32).unwrap();
488        assert_eq!(result.len(), 32);
489    }
490
491    #[test]
492    fn test_tuplehash_serialization() {
493        let custom = b"custom";
494        let data = b"test data";
495        let tuple = vec![data];
496
497        let mut tuplehash = TupleHash128::new(custom);
498        tuplehash.update_tuple(&tuple);
499
500        // Serialize the state
501        let serialized = tuplehash.serialize();
502
503        // Deserialize and continue
504        let mut tuplehash2 = TupleHash128::deserialize(&serialized).unwrap();
505        tuplehash2.update_tuple(&[b"more data"]);
506
507        let mut output = [0u8; 32];
508        tuplehash2.finalize(&mut output).unwrap();
509        assert_ne!(output, [0u8; 32]);
510    }
511
512    #[test]
513    fn test_tuplehash_finalize_with_length_rejects_over_cap() {
514        let mut h = TupleHash128::new(b"");
515        h.update(b"x");
516        assert!(
517            h.finalize_with_length(MAX_SP800185_FIXED_OUTPUT_BYTES + 1)
518                .is_none()
519        );
520    }
521
522    #[test]
523    fn test_tuplehash_finalize_rejects_over_cap_buffer() {
524        let mut h = TupleHash128::new(b"");
525        h.update(b"x");
526        let mut out = vec![0u8; MAX_SP800185_FIXED_OUTPUT_BYTES + 1];
527        assert!(h.finalize(&mut out).is_none());
528    }
529}
lib_q_hash/tuplehash.rs

lib_q_hash/
tuplehash.rs
