xoofff
Farfalle with Xoodoo: Parallel Permutation-based Cryptography
Overview
Farfalle is a keyed cryptographic function with extendable input and it's able to return an output of arbitrary length --- it offers nice and flexible incremental property in both of its input and output interfaces. For example, say we have two messages X, Y and we want to compute F(X || Y), then the cost of processing it is only absorbing Y, if F(X) is already processed. Once X is absorbed, you can finalize the state to squeeze arbitrary number of bytes from it. After that one can restart absorption phase, when Y is ready to be absorbed, then state can again be finalized and arbitrary many bytes can again be squeezed. This way one can restart absorb -> finalize -> squeeze cycle again and again for processing arbitrary number of messages, while accumulator keeps the internal state intact over restarts. This idea is defined in https://ia.cr/2016/1188. And Xoofff is a farfalle contruction which is instantiated with Xoodoo permutation, which was described in https://ia.cr/2018/767. In this (later) paper, deck function name was proposed - which is a keyed function, that takes a sequence of input strings ( of arbitrary length ) and returns a pseudorandom string of arbitrary length which can be incrementally computed s.t. the acronym deck stands for Doubly-Extendable Cryptographic Keyed function.
Here I'm developing and maintaining a Rust library crate, implementing Xoofff deck function. See below for API usage examples.
Prerequisites
Rust stable toolchain, which you can obtain by following https://rustup.rs.
# When developing this library, I was using
)
[!TIP] I advise you to also use
cargo-criterionfor running benchmark executable. Read more about it @ https://crates.io/crates/cargo-criterion. You can install it system-wide by issuing$ cargo install cargo-criterion.
Testing
For ensuring that Xoofff deck function is correctly implemented and both
- oneshot message absorption into/ squeezing from deck function
- incremental message absorption into/ squeezing from deck function
reach same state, I maintain few test cases. You can run those by issuing
[!NOTE] For ensuring functional correctness of Xoofff implementation, I use known answer tests, generated using reference implementation by Xoofff authors, following instructions specified on https://gist.github.com/itzmeanjan/504113021dec30a0909e5f5b47a5bde5.
Benchmarking
Issue following command for benchmarking deck function Xoofff for various input sizes.
[!CAUTION] When benchmarking make sure you've disabled CPU frequency scaling, otherwise numbers you see can be pretty misleading. I found https://github.com/google/benchmark/blob/b40db869/docs/reducing_variance.md helpful.
RUSTFLAGS="-C opt-level=3 -C target-cpu=native"
If interested in benchmarking underlying Xoodoo permutation, consider issuing following command.
RUSTFLAGS="-C opt-level=3 -C target-cpu=native"
[!NOTE] In case you're running benchmarks on
aarch64target, consider reading https://github.com/itzmeanjan/criterion-cycles-per-byte/blob/63edc6b46/src/lib.rs#L63-L70.
[!IMPORTANT] In case you didn't install
cargo-criterion, you've to build and execute benchmark binary with$ RUSTFLAGS="-C opt-level=3 -C target-cpu=native" cargo bench ....
On 12th Gen Intel(R) Core(TM) i7-1260P
Xoofff - Deck Function
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
Xoodoo[{6, 12}] Permutation
)
)
)
)
On ARM Cortex-A72 (i.e. Raspberry Pi 4B)
Xoofff - Deck Function
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
| | | )
Xoodoo[{6, 12}] Permutation
)
)
)
)
Usage
Getting started with using Xoofff - deck function API is fairly easy.
- Add
xoofffas dependency in your project's Cargo.toml file.
[]
# either
= { = "https://github.com/itzmeanjan/xoofff" }
# or
= "=0.1.2"
- Create Xoofff deck function object.
use Xoofff;
- Absorb arbitrary (>=0) bytes message into deck function state, by issuing
absorbroutine N (>0) -many times.
// either
deck.absorb;
// or
deck.absorb;
deck.absorb;
// this does no harm, but in most cases we can avoid doing it.
deck.absorb;
- When all message bytes, of first message, are absorbed, we can finalize the state.
// (first arg) domain seperator can be at max 7 -bits wide
// (second arg) must be <= 7
// (third arg) byte offset, must be <= 48
deck.finalize;
// once finalized, calling `finalize` again should do nothing.
- Now we're ready to squeeze arbitrary number of bytes from deck function state, by invoking
squeezeroutine arbitrary number of times.
// either
deck.squeeze;
// or
deck.squeeze;
deck.squeeze;
// you can safely do it, though it's of not much help.
deck.squeeze;
- Deck functions support extending input message without paying the cost of processing historical messages in message sequence, once again. Accumulator keeps the absorbed message state intact when state is finalized and ready to be squeezed. When deck function state is restarted, once again, it's ready to go through
absorb->finalize->squeezecycle.
deck.restart;
- Now one can absorb arbitrary number of bytes, from second message in this message sequence, by invoking
absorbroutine arbitrary number of times.
deck.absorb;
- Once all bytes of second message are absorbed, you can finalize the deck function state.
deck.finalize;
- Finally squeeze arbitrary number of bytes from deck function state.
deck.squeeze;
- As you understand, this way you can again restart by
absorb->finalize->squeezecycle, when new message is ready to be processed. Deck functions offer very flexible and extendable input/ output processing interfaces.
I maintain one example, in deck_function.rs, which you may want to check out. You can also run it by issuing.