1//! For LICENSE check out https://github.com/0xPARC/plonky2-crypto-gadgets/blob/main/LICENSE
  2
  3#![allow(incomplete_features)]
  4#![feature(generic_const_exprs)]
  5
  6pub mod circuit;
  7
  8use std::array;
  9
 10use plonky2::field::types::Field;
 11
 12/// Feistel-type cipher for finite fields, where XORing is replaced
 13/// with addition, cf. https://en.wikipedia.org/wiki/Feistel_cipher or
 14/// §3.5.1 of Stinson's *Cryptography* (3rd edition).
 15pub fn feistel_cipher<const STATE_HALF_LEN: usize, const KEY_LEN: usize, F: Field>(
 16    state: [F; 2 * STATE_HALF_LEN],
 17    key_schedule: &[[F; KEY_LEN]],
 18    f: &impl Fn(Vec<F>) -> [F; STATE_HALF_LEN],
 19) -> [F; 2 * STATE_HALF_LEN] {
 20    if key_schedule.is_empty() {
 21        state
 22    } else {
 23        let k = key_schedule[0];
 24        let l = &state[..STATE_HALF_LEN];
 25        let r = &state[STATE_HALF_LEN..];
 26
 27        let new_l = r;
 28        let round_offset = f([r, &k].concat());
 29        let new_r: [_; STATE_HALF_LEN] = array::from_fn(|i| l[i] + round_offset[i]);
 30
 31        feistel_cipher(
 32            array::from_fn(|i| {
 33                if i < STATE_HALF_LEN {
 34                    new_l[i]
 35                } else {
 36                    new_r[i - STATE_HALF_LEN]
 37                }
 38            }),
 39            &key_schedule[1..],
 40            f,
 41        )
 42    }
 43}
 44
 45/// Feistel-type inverse cipher for finite fields, where XORing is
 46/// replaced with subtraction.
 47pub fn feistel_inv_cipher<const STATE_HALF_LEN: usize, const KEY_LEN: usize, F: Field>(
 48    state: [F; 2 * STATE_HALF_LEN],
 49    reverse_key_schedule: &[[F; KEY_LEN]],
 50    f: &impl Fn(Vec<F>) -> [F; STATE_HALF_LEN],
 51) -> [F; 2 * STATE_HALF_LEN] {
 52    if reverse_key_schedule.is_empty() {
 53        state
 54    } else {
 55        let k = reverse_key_schedule[0];
 56        let l = &state[..STATE_HALF_LEN];
 57        let r = &state[STATE_HALF_LEN..];
 58
 59        let new_r = l;
 60        let round_offset = f([l, &k].concat());
 61        let new_l: [_; STATE_HALF_LEN] = array::from_fn(|i| r[i] - round_offset[i]);
 62
 63        feistel_inv_cipher(
 64            array::from_fn(|i| {
 65                if i < STATE_HALF_LEN {
 66                    new_l[i]
 67                } else {
 68                    new_r[i - STATE_HALF_LEN]
 69                }
 70            }),
 71            &reverse_key_schedule[1..],
 72            f,
 73        )
 74    }
 75}
 76
 77#[cfg(test)]
 78mod tests {
 79    use plonky2::{
 80        field::{
 81            goldilocks_field::GoldilocksField as F,
 82            types::{Field, Field64},
 83        },
 84        hash::{
 85            hashing::hash_n_to_hash_no_pad, keccak::KeccakPermutation,
 86            poseidon::PoseidonPermutation,
 87        },
 88    };
 89    use rand::{Rng, rngs::OsRng};
 90
 91    use crate::{feistel_cipher, feistel_inv_cipher};
 92
 93    pub(crate) fn random_fields<const N: usize>() -> [F; N] {
 94        std::array::from_fn(|_| F::from_canonical_u64(OsRng.gen_range(0..F::ORDER)))
 95    }
 96
 97    #[test]
 98    fn feistel_keccak_poseidon_roundtrip() {
 99        const NR: usize = 32;
100        const STATE_HALF_LEN: usize = 4;
101        const KEY_LEN: usize = 4;
102
103        let f_keccak =
104            |fields: Vec<_>| hash_n_to_hash_no_pad::<F, KeccakPermutation<_>>(&fields).elements;
105        let f_poseidon =
106            |fields: Vec<_>| hash_n_to_hash_no_pad::<F, PoseidonPermutation<_>>(&fields).elements;
107
108        [f_keccak, f_poseidon].into_iter().for_each(|f| {
109            (0..10).for_each(|_| {
110                let state: [_; 2 * STATE_HALF_LEN] = random_fields();
111                let key_schedule: [[_; KEY_LEN]; NR] = std::array::from_fn(|_| random_fields());
112
113                let out_state = feistel_cipher(state, &key_schedule, &f);
114                let reverse_key_schedule = key_schedule.into_iter().rev().collect::<Vec<_>>();
115                let maybe_original_state = feistel_inv_cipher(out_state, &reverse_key_schedule, &f);
116
117                assert_eq!(state, maybe_original_state);
118            })
119        })
120    }
121}