str4d/fpe

Format-preserving encryption in Rust

fpe

This crate contains pure-Rust implementations of format-preserving encryption algorithms.

The following algorithms are implemented:

• FF1 (specified in NIST Special Publication 800-38G).

This crate requires Rust version 1.56 or greater.

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

fpe's Issues

`alloc` = `std`

alloc feature imports num_bigint, which imports std.

This causes

in no_std environment.

Usage Documentation

Current documentation on https://docs.rs/fpe/0.2.0/fpe/ is extremely sparse.

The example is difficult to understand and input / outputs are not clear.

suggestions:

• use verbose variable names or include wiki links for reference.
• create a use-case example. If that is already the case, add in comments to show how the existing documented code works (what you're inputing, what key or seed you're using, the encrypted output, and then decryption tasks).

I'm not able to figure out whatever [0xab, 0xcd, 0xef] represents. And so for me, if I want to input say a string with FPE, "Super secret string", I have no clue as to where to start... Do I need to convert this into a BinaryNumeralString somehow? Is this more for FPE of binary files? Would love some detailed description as to what all is going on and how I could potentially use this module, thanks!

Example does not seem to work

Hi - this is what I'm trying

use aes::Aes256;
use fpe::ff1::{BinaryNumeralString, FF1};
fn main() {
    let key = [0; 32];
    let radix = 2;
    let pt = [0xab, 0xcd, 0xef];

    let ff = FF1::<Aes256>::new(&key, radix).unwrap();
    let ct = ff
        .encrypt(&[], &BinaryNumeralString::from_bytes_le(&pt))
        .unwrap();
    assert_eq!(ct.to_bytes_le(), [0x75, 0xfb, 0x62]);

    let p2 = ff.decrypt(&[], &ct).unwrap();
    assert_eq!(p2.to_bytes_le(), pt);
}

with a Cargo.toml that looks like this

[package]
name = "fpe-demo"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
aes = "0.8.2"
fpe = "0.5.1"

If I run cargo check I get:

    Checking fpe-demo v0.1.0 (/home/ubuntu/code/rust/fpe-demo)
error[E0599]: the function or associated item `new` exists for struct `FF1<Aes256>`, but its trait bounds were not satisfied
   --> src/main.rs:8:29
    |
8   |     let ff = FF1::<Aes256>::new(&key, radix).unwrap();
    |                             ^^^ function or associated item cannot be called on `FF1<Aes256>` due to unsatisfied trait bounds
    |
   ::: /home/ubuntu/.cargo/registry/src/github.com-1ecc6299db9ec823/aes-0.8.2/src/autodetect.rs:430:1
    |
430 | define_aes_impl!(Aes256, Aes256Enc, Aes256Dec, aes256, U32, "AES-256");
    | ----------------------------------------------------------------------
    | |
    | doesn't satisfy `Aes256: cipher::block::BlockCipher`
    | doesn't satisfy `Aes256: cipher::block::BlockDecrypt`
    | doesn't satisfy `Aes256: cipher::block::BlockEncrypt`
    | doesn't satisfy `Aes256: cipher::block::NewBlockCipher`
    |
    = note: the following trait bounds were not satisfied:
            `Aes256: cipher::block::NewBlockCipher`
            `Aes256: cipher::block::BlockEncrypt`
            `Aes256: cipher::block::BlockCipher`
            which is required by `Aes256: cipher::block::BlockEncrypt`
            `Aes256: cipher::block::BlockDecrypt`
            `Aes256: cipher::block::BlockCipher`
            which is required by `Aes256: cipher::block::BlockDecrypt`

error[E0277]: the trait bound `Aes256: cipher::block::BlockCipher` is not satisfied
   --> src/main.rs:8:14
    |
8   |     let ff = FF1::<Aes256>::new(&key, radix).unwrap();
    |              ^^^^^^^^^^^^^ the trait `cipher::block::BlockCipher` is not implemented for `Aes256`
    |
    = help: the trait `cipher::block::BlockCipher` is implemented for `&Alg`
note: required by a bound in `FF1`
   --> /home/ubuntu/.cargo/registry/src/github.com-1ecc6299db9ec823/fpe-0.5.1/src/ff1.rs:177:22
    |
177 | pub struct FF1<CIPH: BlockCipher> {
    |                      ^^^^^^^^^^^ required by this bound in `FF1`

Some errors have detailed explanations: E0277, E0599.
For more information about an error, try `rustc --explain E0277`.
error: could not compile `fpe-demo` due to 2 previous errors

I'm stumped as to why I cannot get my code to work, I can checkout this repo and run cargo bench and it works without any issues. Sorry I'm new to rust, so I may be missing something fundamental here.

Hm, Looks like the encryption process might be overtly slow.

FF1 Should be lightening fast,
However when benchmarking, I was seeing this when speed testing (note timing was restricted to the most intensive step: let cb = ff.encrypt(&[], &binarified_input); )

40 Characters: 7.4697ms

200 Characters: 59.0451ms

1000 Characters: 623.9559ms

5000 Characters: 7.009278s

As the size of input becomes larger, the amount of time it takes to encrypt starts to rapidly increase. It seems inordinately slow for the relatively small sizes in play. I would expect some > 1 second encryption times in the megabyte size of strings, but not with just a few thousand characters.

Am I missing something on the nature of the FF1 algorithm? Is there a way I can turbo charge this?

I tried to use instead but that failed with an assert_eq! error, so I'm not sure if that has been fully implemented.

Thanks!

Use const generics to remove errors from `FF1::{encrypt, decrypt}`

Currently, FF1::{encrypt, decrypt} return None if the provided numeral string has the wrong radix. Now that const generics are available, we could instead have a type parameter on FF1 specifying its radix (instead of as a constructor argument), and then restrict the encrypt and decrypt methods to numeral strings with the same radix parameter.

Encrypting binary strings of 32 bits does not work

Hi, thanks for your work on this crate! I've found it very useful, and I appreciate that the latest release improves performance and updates dependencies.

While updating fpe from v0.5.1 to v0.6.0 in one of my open-source projects, which uses it to encrypt 32-bit binary strings, I discovered thanks to unit tests that decrypting the 32-bit ciphertext with equal parameters did no longer yield the same plaintext back. In particular, I've found this code snippet to reproduce the problem, which was adapted from the docs.rs crate usage example:

use aes::Aes256;
use fpe::ff1::{BinaryNumeralString, FF1};

let key = [0; 32];
let radix = 2;
let pt = [0xab, 0xcd, 0xef, 0xaa]; // Add a extra byte

let ff = FF1::<Aes256>::new(&key, radix).unwrap();
let ct = ff.encrypt(&[], &BinaryNumeralString::from_bytes_le(&pt)).unwrap();

let p2 = ff.decrypt(&[], &ct).unwrap();
assert_eq!(p2.to_bytes_le(), pt); // The assertion fails

Running git bisect between HEAD (known "bad" commit, c4fb7b5) and the v0.5.1 release (known "good" commit, 92e5193) showed that the commit that introduced this regression was 4c3a5ab (made on PR #34). Previous commits of fpe made after v0.5.1 pass the test.

Obviously, reverting that commit is a fix for the regression, but doing that would also revert the performance improvements. Therefore, the ideal solution is to narrow down and fix what part of that rewrite is causing problems. I read the diff and tried to spot the mistake to fix it, but I couldn't do so in the time I allotted to the task, so I'm opening this issue instead.

Avoid floating-point arithmetic where possible

It should be possible to rewrite the floating-point arithmetic if the radix is a power of two. For other radix values, we should reduce its usage as much as possible.

Enforce minimum radix^minlen requirement

The original NIST SP 800-38G required for FF1 that $\mathsf{radix}^\mathsf{minlen} \geq 100$. I didn't implement this requirement check directly at the time (in 2018), in part because BinaryNumeralString enforced it indirectly (the minimum length it supports is 8 bits, which gives $2^8 = 128 \geq 100$).

In 2019, NIST released SP 800-38G revision 1, which raised the FF1 requirement for security reasons to $\mathsf{radix}^\mathsf{minlen} \geq 1,000,000$. This effectively raised the minimum binary string length to 20 bits, or 3 bytes for BinaryNumeralString.

We should implement this limit correctly for the FF1 struct, and/or the NumeralString types it supports.

Requesting single-bit precision in length

Apologies if this is already in, but it doesn't seem to be. BinaryNumeralString can only be sized at 8 bit increments.

For my application, having to operate at this level of granularity will generally induce a 50x slowdown, 100x in worst case.

Rewrite `generate_s()` to not use `BigUint`.

Given that we just need to increment a 16-byte big-endian array from 1 to 2¹²⁸ - 1, we should be able to do this more efficiently than using BigUint.

Failed to convert to BigUInt from encrypted value

I am able to encrypt and decrypt the value fine but the encrypted value is not format-preserving.

When I try to convert the encrypted value to BigUInt using the below code, it returns None.
let num_enc = BigUint::parse_bytes(&ns_encrypted.to_bytes_le(),10).unwrap();

If I use let num_enc_1 = BigUint::from_bytes_le(&ns_encrypted.to_bytes_le());, it returns 692477047269896342546 which is not length preserving.

#[test]
    fn fpe_ff1_test() {
        let bytes = b"123456789";
        let ns =  BinaryNumeralString::from_bytes_le(bytes);
        let num = BigUint::parse_bytes(&ns.to_bytes_le(),10).unwrap();
        println!("num:{:?}, ns_to_le:{:?}", num, ns.to_bytes_le());


        let fpe_ff = FF1::<Aes256>::new(&[0; 32], 2).unwrap();
        let ns_encrypted = fpe_ff.encrypt(&[], &ns).unwrap();
        println!("ns_encrypted_to_le:{:?}", ns_encrypted.to_bytes_le());

        //UNCOMMENT to reproduce the error
        //let num_enc = BigUint::parse_bytes(&ns_encrypted.to_bytes_le(),10).unwrap();
        //println!("num_enc_1:{}", num_enc);

        let ns_decrypted = fpe_ff.decrypt(&[], &ns_encrypted).unwrap();
        println!("ns_decrypted_to_le:{:?}", ns_decrypted.to_bytes_le());
        assert_eq!(bytes.to_vec(), ns_decrypted.to_bytes_le());

        let num_decrypted = BigUint::parse_bytes(&ns_decrypted.to_bytes_le(),10).unwrap();
        println!("num_decrypted:{}", num_decrypted);

        assert_eq!(num, num_decrypted);

      
        let num_enc_1 = BigUint::from_bytes_le(&ns_encrypted.to_bytes_le());
        println!("num_enc_1:{}", num_enc_1);
        let num_decrypted_1= BigUint::from_bytes_le(&ns_decrypted.to_bytes_le());
        println!("num_decrypted_1:{}", num_decrypted_1);
    }

Cannot prove correctness of `Radix::calculate_b`

I was attempting to remove the use of floating point from this crate, in order to avoid the possibility of incorrect rounding. One use of floating point, in Radix::from_u32, is relatively easy to eliminate:

    fn from_u32(radix: u32) -> Result<Self, InvalidRadix> {
        // radix must be in range [2..=2^16]
        if !(2..=(1 << 16)).contains(&radix) {
            return Err(InvalidRadix(radix));
        }

        Ok(if radix.count_ones() == 1 {
            let log_radix: u32 = 31 - radix.leading_zeros();
            Radix::PowerTwo {
                radix,
                min_len: cmp::max((MIN_RADIX_2_NS_LEN + log_radix - 1) / log_radix, MIN_NS_LEN),
                log_radix: u8::try_from(log_radix).unwrap(),
            }
        } else {
            let mut min_len = 1u32;
            let mut domain = radix;
            while domain < MIN_NS_DOMAIN_SIZE {
                domain *= radix;
                min_len += 1;
            }
            Radix::Any { radix, min_len }
        })
    }

The other, in Radix::calculate_b, is not. For input $radix$ and $v$, the intention is to find the smallest $k$ such that $2^k \geq radix^v$, then round $b$ up to the next multiple of 8. However, I was unable to either:

• prove the existing implementation using floating-point arithmetic correct, or
• find an alternative implementation of this specification, short of using bignum arithmetic.

The existing implementation:

    /// Calculates b = ceil(ceil(v * log2(radix)) / 8).
    fn calculate_b(&self, v: usize) -> usize {
        use libm::{ceil, log2};
        match *self {
            Radix::Any { radix, .. } => ceil(v as f64 * log2(f64::from(radix)) / 8f64) as usize,
            Radix::PowerTwo { log_radix, .. } => ((v * log_radix as usize) + 7) / 8,
        }
    }

is not clearly correct for the Radix::Any case because v as f64 * log2(f64::from(radix)) / 8f64 might be computed with an error such that the correct value is just below an integer and the computed value is just above, or vice versa. This is very unlikely and perhaps does not ever occur, though.

Proof by exhaustive checking of $3 \leq radix \leq 65535$ and $1 \leq v \leq 2^{16}$ is feasible; I guess we could do that.

Increase radix^minlen lower bound of FF1 to account for new distinguisher

https://eprint.iacr.org/2020/1311 published a distinguisher for FF1 against binary numeral strings, that has a data complexity of $2^{2n((r-1)-\frac{1}{2}) - n}$ and a time complexity of $2^{2n((r-1)-\frac{1}{2})}$. FF1 has 10 rounds, corresponding to $r = 5$, and its minimum binary string length corresponds to $n = 10$; this gives a data complexity of $2^{60}$ and time complexity of $2^{70}$.

While this is clearly not secure for such short inputs, it does not invalidate FF1 as a whole. For example, on the 88-bit inputs used for Zcash diversifiers ( $n = 44$ ), we get a data complexity of $2^{264}$ and time complexity of $2^{308}$, which remains sufficient.

The best fix for this is to raise the $\mathsf{radix}^\mathsf{minlen}$ requirement (once we implement #31) to be greater than what NIST SP 800-38G Rev. 1 requires. For instance, 42-bit binary strings ( $n = 21$ ) are the longest that have a data and time complexity for this distinguisher smaller than $2^{128}$.

Update `aes` version

This crate depends on aes = "^0.7" and thus doesn't work with the latest aes = "0.8.1".