An implementation of Keccak derived functions specified in FIPS-202, SP800-185 and KangarooTwelve

Marek Kotewicz

Last update: Oct 21, 2022

Related tags

Cryptography rust cryptography shake keccak sha3 kangarootwelve kmac tuplehash cshake parallelhash fips-202

Overview

tiny-keccak

An implementation of Keccak derived functions specified in FIPS-202, SP800-185 and KangarooTwelve.

Documentation

The Keccak-f[1600] permutation is fully unrolled; it's nearly as fast as the Keccak team's optimized permutation.

Usage

In your Cargo.toml specify what features (hash functions, you are intending to use). Available options are: cshake, fips202, k12, keccak, kmac, parallel_hash, sha3, shake, sp800, tuple_hash.

[dependencies]
tiny-keccak = { version = "2.0", features = ["sha3"] }

Example

use tiny_keccak::Sha3;

fn main() {
    let mut sha3 = Sha3::v256();
    let mut output = [0u8; 32];
    let expected = b"\
        \x64\x4b\xcc\x7e\x56\x43\x73\x04\x09\x99\xaa\xc8\x9e\x76\x22\xf3\
        \xca\x71\xfb\xa1\xd9\x72\xfd\x94\xa3\x1c\x3b\xfb\xf2\x4e\x39\x38\
    ";

    sha3.update(b"hello");
    sha3.update(b" ");
    sha3.update(b"world");
    sha3.finalize(&mut output);

    assert_eq!(expected, &output);
}

Benchmarks

Benchmarked with rust-crypto sha3 on:

MacBook Pro (Retina, 15-inch, Mid 2015)
2,5 GHz Intel Core i7
16 GB 1600 MHz DDR3
Intel Iris Pro 1536 MB

Benchmark code is available here

running 4 tests
test rust_crypto_sha3_256_input_32_bytes   ... bench:         677 ns/iter (+/- 113) = 47 MB/s
test rust_crypto_sha3_256_input_4096_bytes ... bench:      17,619 ns/iter (+/- 4,174) = 232 MB/s
test tiny_keccak_sha3_256_input_32_bytes   ... bench:         569 ns/iter (+/- 204) = 56 MB/s
test tiny_keccak_sha3_256_input_4096_bytes ... bench:      17,185 ns/iter (+/- 4,575) = 238 MB/s

Comments

Bounds checking

I believe there is a trick to avoid the bounds checking without unsafe code by consolodating the bound checks to the beginning and end of the loop. I forget exactly how it works though, maybe using a slice [..] or something.

opened by burdges 7
Fix borrows

Incidentally this improve performance slightly because the compiler avoids some check caused by the extra unsafe code:

Old : test bench_sha3_256_input_4096_bytes ... bench: 19,252 ns/iter (+/- 2,023) = 212 MB/s test keccakf_u64 ... bench: 591 ns/iter (+/- 234) = 42 MB/s

New: test bench_sha3_256_input_4096_bytes ... bench: 18,195 ns/iter (+/- 851) = 225 MB/s test keccakf_u64 ... bench: 574 ns/iter (+/- 19) = 43 MB/s

opened by burdges 5

Replace some unsafe with safe Rust without performance regression

There seems to be no performance regression. I actually noticed a small improvement.

With unsafe:

test bench_sha3_256_input_4096_bytes ... bench:      13,141 ns/iter (+/- 890) = 311 MB/s
test keccakf_u64                     ... bench:         413 ns/iter (+/- 31) = 60 MB/s

Without unsafe:

test bench_sha3_256_input_4096_bytes ... bench:      12,986 ns/iter (+/- 1,054) = 315 MB/s
test keccakf_u64                     ... bench:         409 ns/iter (+/- 27) = 61 MB/s

opened by brycx 3

Add a test for overlapping buffers (WAS: Don't unroll outer loop for speed™)

Not unrolling the outer loop seems to speed up hashing quite significally:

Original (unrolled):

running 3 tests
test bench_keccak_256_with_empty_input   ... bench:         557 ns/iter (+/- 46)
test bench_keccak_256_with_large_input   ... bench:      17,288 ns/iter (+/- 1,871) = 236 MB/s
test bench_keccak_256_with_typical_input ... bench:         577 ns/iter (+/- 28) = 88 MB/s

This branch (not unrolled):

running 3 tests
test bench_keccak_256_with_empty_input   ... bench:         487 ns/iter (+/- 25)
test bench_keccak_256_with_large_input   ... bench:      14,645 ns/iter (+/- 675) = 279 MB/s
test bench_keccak_256_with_typical_input ... bench:         495 ns/iter (+/- 32) = 103 MB/s

"Inspired" by https://github.com/RustCrypto/sponges/blob/master/keccak/src/lib.rs#L138

Running benchmarks from the keccak-hash crate so we can compare to the numbers here.

opened by dvdplm 3

Add support for half-duplex use

This patch improves the API by allowing squeezing output any number of times, and switching between absorbing and squeezing any number of times.

Methods absorb and squeeze automatically keep track of the current offset in the Keccak state and apply necessary padding and/or permutation when transitioning from one mode to another.

As a result, XofReader is changed to a simple type alias and can be removed in the long term. Note that XofReader does not allow switching back to absorbing.

The rationale for half-duplex API is to enable use of Keccak in cryptographic protocol that employ "random oracle" via a Fiat-Shamir transform. Such protocols have to switch between committing some data (absorbing into a sponge) and generating challenges (squeezing the sponge).

opened by oleganza 3
Optimisations and convert to use crunchy
Basically I just converted a bunch of mutable variables to be constants and made the array zeroing simpler/faster, mostly by using the macros in crunchy. Unrolling for i in 0..24 outer loop leads to a noticeable increase in compilation time but also massively increases the speed (probably because it allows more optimisations to be done on the array[i][...] accesses). I was looking at this repo because I wanted to convert it to use simd but it turns out there was some low-hanging optimisation fruit that doesn't require nightly.

Benchcmp results (I ran the benches 3 times each before and after this PR so there are 3 copies of each benching function):

name pre.bench ns/iter post.bench ns/iter diff ns/iter diff % speedup bench_sha3_256_input_4096_bytes 26,662 (153 MB/s) 20,100 (203 MB/s) -6,562 -24.61% x 1.33 bench_sha3_256_input_4096_bytes 26,203 (156 MB/s) 19,995 (204 MB/s) -6,208 -23.69% x 1.31 bench_sha3_256_input_4096_bytes 26,322 (155 MB/s) 20,157 (203 MB/s) -6,165 -23.42% x 1.31 keccakf_u64 663 (37 MB/s) 496 (50 MB/s) -167 -25.19% x 1.34 keccakf_u64 650 (38 MB/s) 491 (50 MB/s) -159 -24.46% x 1.32 keccakf_u64 699 (35 MB/s) 486 (51 MB/s) -213 -30.47% x 1.44

One unresolved question is whether the loop at line 75 should be replaced with something like:

for x in 0..5 { let mut out = 0; unroll! { for y_count in 0..5 { let y = y_count * 5; out ^= a[x + y]; } } arrays[i][x] = out; }

with mem::uninitialized for the initialisation of arrays. This should be more consistently optimised since it says what we actually want to happen, but on my computer it's slower, about 5%. If someone could test this against the version that's committed here on a different computer that'd be really useful.
opened by Vurich 3
Allow custom rate/delim
I try to implement cSHAKE. According to the specification, ~~it needs to use a different rate~~.

If N = "" and S = "": return SHAKE128(X, L); Else: return KECCAK[256](bytepad(encode_string(N) || encode_string(S), 168) || X || 00, L).

Note that the numbers 168 and 136 are rates (in bytes) of the KECCAK[256] and KECCAK[512] sponge functions, respectively; the characters 00 in the Courier New font in these definitions specify two zero bits.
opened by quininer 3
Compile error for tiny-keccak

error: Could not compile tiny-keccak.

Caused by: process didn't exit successfully: rustc --crate-name tiny_keccak /home/james/.cargo/registry/src/github.com-1ecc6299db9ec823/tiny-keccak-1.4.1/src/lib.rs --crate-type lib --emit=dep-info,link -C debuginfo=2 -C metadata=b5e8e3638fbc1be2 -C extra-filename=-b5e8e3638fbc1be2 --out-dir /home/james/dod/target/debug/deps -L dependency=/home/james/dod/target/debug/deps --extern crunchy=/home/james/dod/target/debug/deps/libcrunchy-88d10eef0a5335a1.rlib --cap-lints allow (signal: 9, SIGKILL: kill)

To reproduce:

Clone https://github.com/jamesray1/diamond_drops

and checkout to fix-errors-in-lib-rs

then run cargo make test-all.

opened by jamesray1 2

Build Error on Ubuntu 16

When building a Rust crate with tiny-keccak as a dependency, I received the following build error.

   Compiling tiny-keccak v1.4.1
     Running `rustc --crate-name tiny_keccak /home/ubuntu/.cargo/registry/src/github.com-1ecc6299db9ec823/tiny-keccak-1.4.1/src/lib.rs --crate-type lib --emit=dep-info,link -C debuginfo=2 -C metadata=49d6f213a92cfbc2 -C extra-filename=-49d6f213a92cfbc2 --out-dir /home/ubuntu/whatever/target/debug/deps -L dependency=/home/ubuntu/whatever/target/debug/deps --extern crunchy=/home/ubuntu/whatever/target/debug/deps/libcrunchy-c57bfed60427bcc4.rlib --cap-lints allow`
error: Could not compile `tiny-keccak`.

Caused by:
  process didn't exit successfully: `rustc --crate-name tiny_keccak /home/ubuntu/.cargo/registry/src/github.com-1ecc6299db9ec823/tiny-keccak-1.4.1/src/lib.rs --crate-type lib --emit=dep-info,link -C debuginfo=2 -C metadata=49d6f213a92cfbc2 -C extra-filename=-49d6f213a92cfbc2 --out-dir /home/ubuntu/whatever/target/debug/deps -L dependency=/home/ubuntu/whatever/target/debug/deps --extern crunchy=/home/ubuntu/whatever/target/debug/deps/libcrunchy-c57bfed60427bcc4.rlib --cap-lints allow` (signal: 9, SIGKILL: kill)

This error occurred when building tiny-keccak on a fresh Ubuntu 16 EC2 instance.

Cargo.toml:

[dependencies]
tiny-keccak = "1.4.1"

Rust Version: rustc 1.27.0-nightly

opened by DrPeterVanNostrand 2

Use f1600 from keccak crate

I've implemented a stand-alone crate keccak which currently contains only f1600 function. (in future I plan to expand it with other keccak-f variants and keccak-p) The crate is licensed under CC0 terms and it's based on @Vurich's contribution. The main changes are use of custom unrolling macros (i.e. no dependency on crunchy) and disabled unrolling of rounds loop. The latter results in a better performance (~15-20% on my machine) and in a significantly smaller function size (~24 times), which proportionally improves compilation times, especially after recent regression in the compiler.

opened by newpavlov 2
Comparison with sha3
rust-crypto is abandoned and RustCrypto organization aims to succeed it. sha3 is part of it.

I've taken your f implementation and applied some other modifications to code inherited from the rust-crypto. (I've attributed you in the license file if you are interested) I think it's worth to do comparison with the sha3 crate not with the rust-crypto.

On my laptop I am getting the following results:

test rustcrypto_sha3_256_input_32_bytes ... bench: 835 ns/iter (+/- 65) = 38 MB/s test rustcrypto_sha3_256_input_4096_bytes ... bench: 22,927 ns/iter (+/- 1,799) = 178 MB/s test tiny_keccak_sha3_256_input_32_bytes ... bench: 800 ns/iter (+/- 175) = 40 MB/s test tiny_keccak_sha3_256_input_4096_bytes ... bench: 23,229 ns/iter (+/- 2,176) = 176 MB/s
opened by newpavlov 2

`const fn` hashing

Hi!

I'm using Shake in a setting where all input data is known at compile-time, a case where the hash value could be computed at compile-time too.

I feel that Rust has everything needed for it, so I've been toying with const fn for all the things.

Main hurdles:

The "rounds" for loop. Solved by a macro that transforms the for loop into a while loop. We could just manually make it a while loop too, probably simpler. The other for loops are unrolled, so nothing more needed. keccakf is now const fn.
The Permutation trait. A trait function cannot be const. Not sure how to solve; we could get rid of the trait entirely (since there's only one permutation).

Would a const implementation be welcome? If so, do you have an idea to get around the trait problem?

My WIP const implementation

diff --git a/src/lib.rs b/src/lib.rs                                                                    
index 9329fd3..a46aa79 100644                                                                           
--- a/src/lib.rs                                                                                        
+++ b/src/lib.rs                                                                                        
@@ -38,6 +38,7 @@                                                                                       
 //! [`@oleganza`]: https://github.com/oleganza                                                         
 //! [`CC0`]: https://github.com/debris/tiny-keccak/blob/master/LICENSE                                 
                                                                                                        
+#![feature(const_mut_refs)]                                                                            
 #![no_std]                                                                                             
 #![deny(missing_docs)]                                                                                 
                                                                                                        
@@ -51,71 +52,83 @@ const PI: [usize; 24] = [                                                           
                                                                                                        
 const WORDS: usize = 25;                                                                               
                                                                                                        
+macro_rules! const_for {                                                                               
+    (for $i:ident in $begin:tt..$end:tt { $($body:tt)* }) => {                                         
+        let mut $i = $begin;                                                                           
+        while $i < $end {                                                                              
+            $($body)*                                                                                  
+            $i += 1;                                                                                   
+        }                                                                                              
+    };                                                                                                 
+}                                                                                                      
+                                                                                                       
 macro_rules! keccak_function {                                                                         
     ($doc: expr, $name: ident, $rounds: expr, $rc: expr) => {                                          
         #[doc = $doc]                                                                                  
         #[allow(unused_assignments)]                                                                   
         #[allow(non_upper_case_globals)]                                                               
-        pub fn $name(a: &mut [u64; $crate::WORDS]) {                                                   
+        pub const fn $name(a: &mut [u64; $crate::WORDS]) {                                             
             use crunchy::unroll;                                                                       
                                                                                                        
-            for i in 0..$rounds {                                                                      
-                let mut array: [u64; 5] = [0; 5];                                                      
-                                                                                                       
-                // Theta                                                                               
-                unroll! {                                                                              
-                    for x in 0..5 {                                                                    
-                        unroll! {                                                                      
-                            for y_count in 0..5 {                                                      
-                                let y = y_count * 5;                                                   
-                                array[x] ^= a[x + y];                                                  
+            const_for! {                                                                               
+                for i in 0..$rounds {                                                                  
+                    let mut array: [u64; 5] = [0; 5];                                                  
+                                                                                                       
+                    // Theta                                                                           
+                    unroll! {                                                                          
+                        for x in 0..5 {                                                                
+                            unroll! {                                                                  
+                                for y_count in 0..5 {                                                  
+                                    let y = y_count * 5;                                               
+                                    array[x] ^= a[x + y];                                              
+                                }                                                                      
                             }                                                                          
                         }                                                                              
                     }                                                                                  
-                }                                                                                      
                                                                                                        
-                unroll! {                                                                              
-                    for x in 0..5 {                                                                    
-                        unroll! {                                                                      
-                            for y_count in 0..5 {                                                      
-                                let y = y_count * 5;                                                   
-                                a[y + x] ^= array[(x + 4) % 5] ^ array[(x + 1) % 5].rotate_left(1);    
+                    unroll! {                                                                          
+                        for x in 0..5 {                                                                
+                            unroll! {                                                                  
+                                for y_count in 0..5 {                                                  
+                                    let y = y_count * 5;                                               
+                                    a[y + x] ^= array[(x + 4) % 5] ^ array[(x + 1) % 5].rotate_left(1);
+                                }                                                                                    
                             }                                                                                        
                         }                                                                                            
                     }                                                                                                
-                }                                                                                                    
                                                                                                                      
-                // Rho and pi                                                                                        
-                let mut last = a[1];                                                                                 
-                unroll! {                                                                                            
-                    for x in 0..24 {                                                                                 
-                        array[0] = a[$crate::PI[x]];                                                                 
-                        a[$crate::PI[x]] = last.rotate_left($crate::RHO[x]);                                         
-                        last = array[0];                                                                             
+                    // Rho and pi                                                                                    
+                    let mut last = a[1];                                                                             
+                    unroll! {                                                                                        
+                        for x in 0..24 {                                                                             
+                            array[0] = a[$crate::PI[x]];                                                             
+                            a[$crate::PI[x]] = last.rotate_left($crate::RHO[x]);                                     
+                            last = array[0];                                                                         
+                        }                                                                                            
                     }                                                                                                
-                }                                                                                                    
                                                                                                                      
-                // Chi                                                                                               
-                unroll! {                                                                                            
-                    for y_step in 0..5 {                                                                             
-                        let y = y_step * 5;                                                                          
+                    // Chi                                                                                           
+                    unroll! {                                                                                        
+                        for y_step in 0..5 {                                                                         
+                            let y = y_step * 5;                                                                      
                                                                                                                      
-                        unroll! {                                                                                    
-                            for x in 0..5 {                                                                          
-                                array[x] = a[y + x];                                                                 
+                            unroll! {                                                                                
+                                for x in 0..5 {                                                                      
+                                    array[x] = a[y + x];                                                             
+                                }                                                                                    
                             }                                                                                        
-                        }                                                                                            
                                                                                                                      
-                        unroll! {                                                                                    
-                            for x in 0..5 {                                                                          
-                                a[y + x] = array[x] ^ ((!array[(x + 1) % 5]) & (array[(x + 2) % 5]));                
+                            unroll! {                                                                                
+                                for x in 0..5 {                                                                      
+                                    a[y + x] = array[x] ^ ((!array[(x + 1) % 5]) & (array[(x + 2) % 5]));            
+                                }                                                                                    
                             }                                                                                        
                         }                                                                                            
-                    }                                                                                                
-                };                                                                                                   
+                    };                                                                                               
                                                                                                                      
-                // Iota                                                                                              
-                a[0] ^= $rc[i];                                                                                      
+                    // Iota                                                                                          
+                    a[0] ^= $rc[i];                                                                                  
+                }                                                                                                    
             }                                                                                                        
         }                                                                                                            
     }                                                                                                                
@@ -301,7 +314,7 @@ fn right_encode(len: usize) -> EncodedLen {                                                       
 struct Buffer([u64; WORDS]);                                                                                         
                                                                                                                      
 impl Buffer {                                                                                                        
-    fn words(&mut self) -> &mut [u64; WORDS] {                                                                       
+    const fn words(&mut self) -> &mut [u64; WORDS] {                                                                 
         &mut self.0                                                                                                  
     }

Best regards,

Ruben

opened by rubdos 0

Allow resetting Keccak internal buffer by zeroing out

I would like to be able to reset the internal KeccakState of a Keccak instance so that its buffer and offset are zeroed out. I can see that there is a method reset on KeccakState, which however is only ever called from KangarooTwelve.

It is possible to provide a reset method on Keccak calling KeccakState:reset? Is there maybe a reason why there is no such method? I can otherwise provide a PR, but I wanted to ask first.

opened by SuperFluffy 1

Owner

Marek Kotewicz

rust

GitHub

Dexios-Core is a library used for managing cryptographic functions and headers that adhere to the Dexios format.

What is it? Dexios-Core is a library used for managing cryptographic functions and headers that adhere to the Dexios format. Security Dexios-Core uses

3 Jul 4, 2022

Helpful functions and macros for developing smart contracts on NEAR Protocol.

near-contract-tools Helpful functions and macros for developing smart contracts on NEAR Protocol. This package is a collection of common tools and pat

27 Dec 17, 2022

Helpful functions and macros for developing smart contracts on NEAR Protocol.

near-contract-tools Helpful functions and macros for developing smart contracts on NEAR Protocol. This package is a collection of common tools and pat

9 Aug 3, 2022

Collection of cryptographic hash functions written in pure Rust

RustCrypto: hashes Collection of cryptographic hash functions written in pure Rust. All algorithms reside in the separate crates and implemented using

1.2k Jan 8, 2023

Password hashing functions / KDFs

RustCrypto: Password Hashes Collection of password hashing algorithms, otherwise known as password-based key derivation functions, written in pure Rus

387 Dec 28, 2022

The project brings the IC ecosystem to Unity, allowing Unity developers to call the functions of canisters on IC,

Agent of Internet Computer for Unity The Intro The project brings the IC ecosystem to Unity, allowing Unity developers to call the functions of canist

9 Nov 18, 2022

Expose various non-cryptographic hashing functions with Digest traits

noncrypto-digests Expose various non-cryptographic hashing functions with Digest traits. This allows users to use any hashing function with the same t

3 Dec 9, 2023

IBC modules and relayer - Formal specifications and Rust implementation

ibc-rs Rust implementation of the Inter-Blockchain Communication (IBC) protocol. This project comprises primarily four crates: The ibc crate defines t

296 Dec 31, 2022

A safe implementation of the secure remote password authentication and key-exchange protocol (SRP), SRP6a and legacy are as features available.

Secure Remote Password (SRP 6 / 6a) A safe implementation of the secure remote password authentication and key-exchange protocol (SRP version 6a). Ver