keccak/
lib.rs

1//! Keccak [sponge function](https://en.wikipedia.org/wiki/Sponge_function).
2//!
3//! If you are looking for SHA-3 hash functions take a look at [`sha3`][1] and
4//! [`tiny-keccak`][2] crates.
5//!
6//! To disable loop unrolling (e.g. for constraint targets) use `no_unroll`
7//! feature.
8//!
9//! ```
10//! // Test vectors are from KeccakCodePackage
11//! let mut data = [0u64; 25];
12//!
13//! keccak::f1600(&mut data);
14//! assert_eq!(data, [
15//!     0xF1258F7940E1DDE7, 0x84D5CCF933C0478A, 0xD598261EA65AA9EE, 0xBD1547306F80494D,
16//!     0x8B284E056253D057, 0xFF97A42D7F8E6FD4, 0x90FEE5A0A44647C4, 0x8C5BDA0CD6192E76,
17//!     0xAD30A6F71B19059C, 0x30935AB7D08FFC64, 0xEB5AA93F2317D635, 0xA9A6E6260D712103,
18//!     0x81A57C16DBCF555F, 0x43B831CD0347C826, 0x01F22F1A11A5569F, 0x05E5635A21D9AE61,
19//!     0x64BEFEF28CC970F2, 0x613670957BC46611, 0xB87C5A554FD00ECB, 0x8C3EE88A1CCF32C8,
20//!     0x940C7922AE3A2614, 0x1841F924A2C509E4, 0x16F53526E70465C2, 0x75F644E97F30A13B,
21//!     0xEAF1FF7B5CECA249,
22//! ]);
23//!
24//! keccak::f1600(&mut data);
25//! assert_eq!(data, [
26//!     0x2D5C954DF96ECB3C, 0x6A332CD07057B56D, 0x093D8D1270D76B6C, 0x8A20D9B25569D094,
27//!     0x4F9C4F99E5E7F156, 0xF957B9A2DA65FB38, 0x85773DAE1275AF0D, 0xFAF4F247C3D810F7,
28//!     0x1F1B9EE6F79A8759, 0xE4FECC0FEE98B425, 0x68CE61B6B9CE68A1, 0xDEEA66C4BA8F974F,
29//!     0x33C43D836EAFB1F5, 0xE00654042719DBD9, 0x7CF8A9F009831265, 0xFD5449A6BF174743,
30//!     0x97DDAD33D8994B40, 0x48EAD5FC5D0BE774, 0xE3B8C8EE55B7B03C, 0x91A0226E649E42E9,
31//!     0x900E3129E7BADD7B, 0x202A9EC5FAA3CCE8, 0x5B3402464E1C3DB6, 0x609F4E62A44C1059,
32//!     0x20D06CD26A8FBF5C,
33//! ]);
34//! ```
35//!
36//! [1]: https://docs.rs/sha3
37//! [2]: https://docs.rs/tiny-keccak
38
39#![no_std]
40#![cfg_attr(docsrs, feature(doc_auto_cfg))]
41#![cfg_attr(feature = "simd", feature(portable_simd))]
42#![doc(
43    html_logo_url = "https://raw.githubusercontent.com/RustCrypto/meta/master/logo.svg",
44    html_favicon_url = "https://raw.githubusercontent.com/RustCrypto/meta/master/logo.svg"
45)]
46#![allow(non_upper_case_globals)]
47#![warn(
48    clippy::mod_module_files,
49    clippy::unwrap_used,
50    missing_docs,
51    rust_2018_idioms,
52    unused_lifetimes,
53    unused_qualifications
54)]
55
56use core::{
57    convert::TryInto,
58    fmt::Debug,
59    mem::size_of,
60    ops::{BitAnd, BitAndAssign, BitXor, BitXorAssign, Not},
61};
62
63#[rustfmt::skip]
64mod unroll;
65
66#[cfg(all(target_arch = "aarch64", feature = "asm"))]
67mod armv8;
68
69#[cfg(all(target_arch = "aarch64", feature = "asm"))]
70cpufeatures::new!(armv8_sha3_intrinsics, "sha3");
71
72const PLEN: usize = 25;
73
74const RHO: [u32; 24] = [
75    1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2, 14, 27, 41, 56, 8, 25, 43, 62, 18, 39, 61, 20, 44,
76];
77
78const PI: [usize; 24] = [
79    10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24, 4, 15, 23, 19, 13, 12, 2, 20, 14, 22, 9, 6, 1,
80];
81
82const RC: [u64; 24] = [
83    0x0000000000000001,
84    0x0000000000008082,
85    0x800000000000808a,
86    0x8000000080008000,
87    0x000000000000808b,
88    0x0000000080000001,
89    0x8000000080008081,
90    0x8000000000008009,
91    0x000000000000008a,
92    0x0000000000000088,
93    0x0000000080008009,
94    0x000000008000000a,
95    0x000000008000808b,
96    0x800000000000008b,
97    0x8000000000008089,
98    0x8000000000008003,
99    0x8000000000008002,
100    0x8000000000000080,
101    0x000000000000800a,
102    0x800000008000000a,
103    0x8000000080008081,
104    0x8000000000008080,
105    0x0000000080000001,
106    0x8000000080008008,
107];
108
109/// Keccak is a permutation over an array of lanes which comprise the sponge
110/// construction.
111pub trait LaneSize:
112    Copy
113    + Clone
114    + Debug
115    + Default
116    + PartialEq
117    + BitAndAssign
118    + BitAnd<Output = Self>
119    + BitXorAssign
120    + BitXor<Output = Self>
121    + Not<Output = Self>
122{
123    /// Number of rounds of the Keccak-f permutation.
124    const KECCAK_F_ROUND_COUNT: usize;
125
126    /// Truncate function.
127    fn truncate_rc(rc: u64) -> Self;
128
129    /// Rotate left function.
130    fn rotate_left(self, n: u32) -> Self;
131}
132
133macro_rules! impl_lanesize {
134    ($type:ty, $round:expr, $truncate:expr) => {
135        impl LaneSize for $type {
136            const KECCAK_F_ROUND_COUNT: usize = $round;
137
138            fn truncate_rc(rc: u64) -> Self {
139                $truncate(rc)
140            }
141
142            fn rotate_left(self, n: u32) -> Self {
143                self.rotate_left(n)
144            }
145        }
146    };
147}
148
149impl_lanesize!(u8, 18, |rc: u64| { rc.to_le_bytes()[0] });
150impl_lanesize!(u16, 20, |rc: u64| {
151    let tmp = rc.to_le_bytes();
152    #[allow(clippy::unwrap_used)]
153    Self::from_le_bytes(tmp[..size_of::<Self>()].try_into().unwrap())
154});
155impl_lanesize!(u32, 22, |rc: u64| {
156    let tmp = rc.to_le_bytes();
157    #[allow(clippy::unwrap_used)]
158    Self::from_le_bytes(tmp[..size_of::<Self>()].try_into().unwrap())
159});
160impl_lanesize!(u64, 24, |rc: u64| { rc });
161
162macro_rules! impl_keccak {
163    ($pname:ident, $fname:ident, $type:ty) => {
164        /// Keccak-p sponge function
165        pub fn $pname(state: &mut [$type; PLEN], round_count: usize) {
166            keccak_p(state, round_count);
167        }
168
169        /// Keccak-f sponge function
170        pub fn $fname(state: &mut [$type; PLEN]) {
171            keccak_p(state, <$type>::KECCAK_F_ROUND_COUNT);
172        }
173    };
174}
175
176impl_keccak!(p200, f200, u8);
177impl_keccak!(p400, f400, u16);
178impl_keccak!(p800, f800, u32);
179
180#[cfg(not(all(target_arch = "aarch64", feature = "asm")))]
181impl_keccak!(p1600, f1600, u64);
182
183/// Keccak-p[1600, rc] permutation.
184#[cfg(all(target_arch = "aarch64", feature = "asm"))]
185pub fn p1600(state: &mut [u64; PLEN], round_count: usize) {
186    if armv8_sha3_intrinsics::get() {
187        unsafe { armv8::p1600_armv8_sha3_asm(state, round_count) }
188    } else {
189        keccak_p(state, round_count);
190    }
191}
192
193/// Keccak-f[1600] permutation.
194#[cfg(all(target_arch = "aarch64", feature = "asm"))]
195pub fn f1600(state: &mut [u64; PLEN]) {
196    if armv8_sha3_intrinsics::get() {
197        unsafe { armv8::p1600_armv8_sha3_asm(state, 24) }
198    } else {
199        keccak_p(state, u64::KECCAK_F_ROUND_COUNT);
200    }
201}
202
203#[cfg(feature = "simd")]
204/// SIMD implementations for Keccak-f1600 sponge function
205pub mod simd {
206    use crate::{keccak_p, LaneSize, PLEN};
207    pub use core::simd::{u64x2, u64x4, u64x8};
208
209    macro_rules! impl_lanesize_simd_u64xn {
210        ($type:ty) => {
211            impl LaneSize for $type {
212                const KECCAK_F_ROUND_COUNT: usize = 24;
213
214                fn truncate_rc(rc: u64) -> Self {
215                    Self::splat(rc)
216                }
217
218                fn rotate_left(self, n: u32) -> Self {
219                    self << Self::splat(n.into()) | self >> Self::splat((64 - n).into())
220                }
221            }
222        };
223    }
224
225    impl_lanesize_simd_u64xn!(u64x2);
226    impl_lanesize_simd_u64xn!(u64x4);
227    impl_lanesize_simd_u64xn!(u64x8);
228
229    impl_keccak!(p1600x2, f1600x2, u64x2);
230    impl_keccak!(p1600x4, f1600x4, u64x4);
231    impl_keccak!(p1600x8, f1600x8, u64x8);
232}
233
234#[allow(unused_assignments)]
235/// Generic Keccak-p sponge function
236pub fn keccak_p<L: LaneSize>(state: &mut [L; PLEN], round_count: usize) {
237    if round_count > L::KECCAK_F_ROUND_COUNT {
238        panic!("A round_count greater than KECCAK_F_ROUND_COUNT is not supported!");
239    }
240
241    // https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf#page=25
242    // "the rounds of KECCAK-p[b, nr] match the last rounds of KECCAK-f[b]"
243    let round_consts = &RC[(L::KECCAK_F_ROUND_COUNT - round_count)..L::KECCAK_F_ROUND_COUNT];
244
245    // not unrolling this loop results in a much smaller function, plus
246    // it positively influences performance due to the smaller load on I-cache
247    for &rc in round_consts {
248        let mut array = [L::default(); 5];
249
250        // Theta
251        unroll5!(x, {
252            unroll5!(y, {
253                array[x] ^= state[5 * y + x];
254            });
255        });
256
257        unroll5!(x, {
258            unroll5!(y, {
259                let t1 = array[(x + 4) % 5];
260                let t2 = array[(x + 1) % 5].rotate_left(1);
261                state[5 * y + x] ^= t1 ^ t2;
262            });
263        });
264
265        // Rho and pi
266        let mut last = state[1];
267        unroll24!(x, {
268            array[0] = state[PI[x]];
269            state[PI[x]] = last.rotate_left(RHO[x]);
270            last = array[0];
271        });
272
273        // Chi
274        unroll5!(y_step, {
275            let y = 5 * y_step;
276
277            unroll5!(x, {
278                array[x] = state[y + x];
279            });
280
281            unroll5!(x, {
282                let t1 = !array[(x + 1) % 5];
283                let t2 = array[(x + 2) % 5];
284                state[y + x] = array[x] ^ (t1 & t2);
285            });
286        });
287
288        // Iota
289        state[0] ^= L::truncate_rc(rc);
290    }
291}
292
293#[cfg(test)]
294mod tests {
295    use crate::{keccak_p, LaneSize, PLEN};
296
297    fn keccak_f<L: LaneSize>(state_first: [L; PLEN], state_second: [L; PLEN]) {
298        let mut state = [L::default(); PLEN];
299
300        keccak_p(&mut state, L::KECCAK_F_ROUND_COUNT);
301        assert_eq!(state, state_first);
302
303        keccak_p(&mut state, L::KECCAK_F_ROUND_COUNT);
304        assert_eq!(state, state_second);
305    }
306
307    #[test]
308    fn keccak_f200() {
309        // Test vectors are copied from XKCP (eXtended Keccak Code Package)
310        // https://github.com/XKCP/XKCP/blob/master/tests/TestVectors/KeccakF-200-IntermediateValues.txt
311        let state_first = [
312            0x3C, 0x28, 0x26, 0x84, 0x1C, 0xB3, 0x5C, 0x17, 0x1E, 0xAA, 0xE9, 0xB8, 0x11, 0x13,
313            0x4C, 0xEA, 0xA3, 0x85, 0x2C, 0x69, 0xD2, 0xC5, 0xAB, 0xAF, 0xEA,
314        ];
315        let state_second = [
316            0x1B, 0xEF, 0x68, 0x94, 0x92, 0xA8, 0xA5, 0x43, 0xA5, 0x99, 0x9F, 0xDB, 0x83, 0x4E,
317            0x31, 0x66, 0xA1, 0x4B, 0xE8, 0x27, 0xD9, 0x50, 0x40, 0x47, 0x9E,
318        ];
319
320        keccak_f::<u8>(state_first, state_second);
321    }
322
323    #[test]
324    fn keccak_f400() {
325        // Test vectors are copied from XKCP (eXtended Keccak Code Package)
326        // https://github.com/XKCP/XKCP/blob/master/tests/TestVectors/KeccakF-400-IntermediateValues.txt
327        let state_first = [
328            0x09F5, 0x40AC, 0x0FA9, 0x14F5, 0xE89F, 0xECA0, 0x5BD1, 0x7870, 0xEFF0, 0xBF8F, 0x0337,
329            0x6052, 0xDC75, 0x0EC9, 0xE776, 0x5246, 0x59A1, 0x5D81, 0x6D95, 0x6E14, 0x633E, 0x58EE,
330            0x71FF, 0x714C, 0xB38E,
331        ];
332        let state_second = [
333            0xE537, 0xD5D6, 0xDBE7, 0xAAF3, 0x9BC7, 0xCA7D, 0x86B2, 0xFDEC, 0x692C, 0x4E5B, 0x67B1,
334            0x15AD, 0xA7F7, 0xA66F, 0x67FF, 0x3F8A, 0x2F99, 0xE2C2, 0x656B, 0x5F31, 0x5BA6, 0xCA29,
335            0xC224, 0xB85C, 0x097C,
336        ];
337
338        keccak_f::<u16>(state_first, state_second);
339    }
340
341    #[test]
342    fn keccak_f800() {
343        // Test vectors are copied from XKCP (eXtended Keccak Code Package)
344        // https://github.com/XKCP/XKCP/blob/master/tests/TestVectors/KeccakF-800-IntermediateValues.txt
345        let state_first = [
346            0xE531D45D, 0xF404C6FB, 0x23A0BF99, 0xF1F8452F, 0x51FFD042, 0xE539F578, 0xF00B80A7,
347            0xAF973664, 0xBF5AF34C, 0x227A2424, 0x88172715, 0x9F685884, 0xB15CD054, 0x1BF4FC0E,
348            0x6166FA91, 0x1A9E599A, 0xA3970A1F, 0xAB659687, 0xAFAB8D68, 0xE74B1015, 0x34001A98,
349            0x4119EFF3, 0x930A0E76, 0x87B28070, 0x11EFE996,
350        ];
351        let state_second = [
352            0x75BF2D0D, 0x9B610E89, 0xC826AF40, 0x64CD84AB, 0xF905BDD6, 0xBC832835, 0x5F8001B9,
353            0x15662CCE, 0x8E38C95E, 0x701FE543, 0x1B544380, 0x89ACDEFF, 0x51EDB5DE, 0x0E9702D9,
354            0x6C19AA16, 0xA2913EEE, 0x60754E9A, 0x9819063C, 0xF4709254, 0xD09F9084, 0x772DA259,
355            0x1DB35DF7, 0x5AA60162, 0x358825D5, 0xB3783BAB,
356        ];
357
358        keccak_f::<u32>(state_first, state_second);
359    }
360
361    #[test]
362    fn keccak_f1600() {
363        // Test vectors are copied from XKCP (eXtended Keccak Code Package)
364        // https://github.com/XKCP/XKCP/blob/master/tests/TestVectors/KeccakF-1600-IntermediateValues.txt
365        let state_first = [
366            0xF1258F7940E1DDE7,
367            0x84D5CCF933C0478A,
368            0xD598261EA65AA9EE,
369            0xBD1547306F80494D,
370            0x8B284E056253D057,
371            0xFF97A42D7F8E6FD4,
372            0x90FEE5A0A44647C4,
373            0x8C5BDA0CD6192E76,
374            0xAD30A6F71B19059C,
375            0x30935AB7D08FFC64,
376            0xEB5AA93F2317D635,
377            0xA9A6E6260D712103,
378            0x81A57C16DBCF555F,
379            0x43B831CD0347C826,
380            0x01F22F1A11A5569F,
381            0x05E5635A21D9AE61,
382            0x64BEFEF28CC970F2,
383            0x613670957BC46611,
384            0xB87C5A554FD00ECB,
385            0x8C3EE88A1CCF32C8,
386            0x940C7922AE3A2614,
387            0x1841F924A2C509E4,
388            0x16F53526E70465C2,
389            0x75F644E97F30A13B,
390            0xEAF1FF7B5CECA249,
391        ];
392        let state_second = [
393            0x2D5C954DF96ECB3C,
394            0x6A332CD07057B56D,
395            0x093D8D1270D76B6C,
396            0x8A20D9B25569D094,
397            0x4F9C4F99E5E7F156,
398            0xF957B9A2DA65FB38,
399            0x85773DAE1275AF0D,
400            0xFAF4F247C3D810F7,
401            0x1F1B9EE6F79A8759,
402            0xE4FECC0FEE98B425,
403            0x68CE61B6B9CE68A1,
404            0xDEEA66C4BA8F974F,
405            0x33C43D836EAFB1F5,
406            0xE00654042719DBD9,
407            0x7CF8A9F009831265,
408            0xFD5449A6BF174743,
409            0x97DDAD33D8994B40,
410            0x48EAD5FC5D0BE774,
411            0xE3B8C8EE55B7B03C,
412            0x91A0226E649E42E9,
413            0x900E3129E7BADD7B,
414            0x202A9EC5FAA3CCE8,
415            0x5B3402464E1C3DB6,
416            0x609F4E62A44C1059,
417            0x20D06CD26A8FBF5C,
418        ];
419
420        keccak_f::<u64>(state_first, state_second);
421    }
422
423    #[cfg(feature = "simd")]
424    mod simd {
425        use super::keccak_f;
426        use core::simd::{u64x2, u64x4, u64x8};
427
428        macro_rules! impl_keccak_f1600xn {
429            ($name:ident, $type:ty) => {
430                #[test]
431                fn $name() {
432                    // Test vectors are copied from XKCP (eXtended Keccak Code Package)
433                    // https://github.com/XKCP/XKCP/blob/master/tests/TestVectors/KeccakF-1600-IntermediateValues.txt
434                    let state_first = [
435                        <$type>::splat(0xF1258F7940E1DDE7),
436                        <$type>::splat(0x84D5CCF933C0478A),
437                        <$type>::splat(0xD598261EA65AA9EE),
438                        <$type>::splat(0xBD1547306F80494D),
439                        <$type>::splat(0x8B284E056253D057),
440                        <$type>::splat(0xFF97A42D7F8E6FD4),
441                        <$type>::splat(0x90FEE5A0A44647C4),
442                        <$type>::splat(0x8C5BDA0CD6192E76),
443                        <$type>::splat(0xAD30A6F71B19059C),
444                        <$type>::splat(0x30935AB7D08FFC64),
445                        <$type>::splat(0xEB5AA93F2317D635),
446                        <$type>::splat(0xA9A6E6260D712103),
447                        <$type>::splat(0x81A57C16DBCF555F),
448                        <$type>::splat(0x43B831CD0347C826),
449                        <$type>::splat(0x01F22F1A11A5569F),
450                        <$type>::splat(0x05E5635A21D9AE61),
451                        <$type>::splat(0x64BEFEF28CC970F2),
452                        <$type>::splat(0x613670957BC46611),
453                        <$type>::splat(0xB87C5A554FD00ECB),
454                        <$type>::splat(0x8C3EE88A1CCF32C8),
455                        <$type>::splat(0x940C7922AE3A2614),
456                        <$type>::splat(0x1841F924A2C509E4),
457                        <$type>::splat(0x16F53526E70465C2),
458                        <$type>::splat(0x75F644E97F30A13B),
459                        <$type>::splat(0xEAF1FF7B5CECA249),
460                    ];
461                    let state_second = [
462                        <$type>::splat(0x2D5C954DF96ECB3C),
463                        <$type>::splat(0x6A332CD07057B56D),
464                        <$type>::splat(0x093D8D1270D76B6C),
465                        <$type>::splat(0x8A20D9B25569D094),
466                        <$type>::splat(0x4F9C4F99E5E7F156),
467                        <$type>::splat(0xF957B9A2DA65FB38),
468                        <$type>::splat(0x85773DAE1275AF0D),
469                        <$type>::splat(0xFAF4F247C3D810F7),
470                        <$type>::splat(0x1F1B9EE6F79A8759),
471                        <$type>::splat(0xE4FECC0FEE98B425),
472                        <$type>::splat(0x68CE61B6B9CE68A1),
473                        <$type>::splat(0xDEEA66C4BA8F974F),
474                        <$type>::splat(0x33C43D836EAFB1F5),
475                        <$type>::splat(0xE00654042719DBD9),
476                        <$type>::splat(0x7CF8A9F009831265),
477                        <$type>::splat(0xFD5449A6BF174743),
478                        <$type>::splat(0x97DDAD33D8994B40),
479                        <$type>::splat(0x48EAD5FC5D0BE774),
480                        <$type>::splat(0xE3B8C8EE55B7B03C),
481                        <$type>::splat(0x91A0226E649E42E9),
482                        <$type>::splat(0x900E3129E7BADD7B),
483                        <$type>::splat(0x202A9EC5FAA3CCE8),
484                        <$type>::splat(0x5B3402464E1C3DB6),
485                        <$type>::splat(0x609F4E62A44C1059),
486                        <$type>::splat(0x20D06CD26A8FBF5C),
487                    ];
488
489                    keccak_f::<$type>(state_first, state_second);
490                }
491            };
492        }
493
494        impl_keccak_f1600xn!(keccak_f1600x2, u64x2);
495        impl_keccak_f1600xn!(keccak_f1600x4, u64x4);
496        impl_keccak_f1600xn!(keccak_f1600x8, u64x8);
497    }
498}
keccak/lib.rs

keccak/
lib.rs
