FPE - Format Preserving Encryption with FF3 in Python

Overview

Build Status Coverage Status License Downloads

ff3 - Format Preserving Encryption in Python

An implementation of the NIST approved FF3 and FF3-1 Format Preserving Encryption (FPE) algorithms in Python.

This package implements the FF3 algorithm for Format Preserving Encryption as described in the March 2016 NIST publication 800-38G Methods for Format-Preserving Encryption, and revised on February 28th, 2019 with a draft update for FF3-1.

Changes to minimum domain size and revised tweak length have been implemented in this package with both 64-bit and 56-bit tweaks are supported. NIST has only published official test vectors for 64-bit tweaks, but draft ACVP test vectors have been used for testing FF3-1. It is expected the final NIST standard will provide updated test vectors with 56-bit tweak lengths.

Requires

This project was built and tested with Python 3.6 and later versions. The only dependency is PyCryptodome.

Installation

For a normal install of the latest PyPI release with pip:

pip3 install ff3

To instead install the development version:

git clone https://github.com/mysto/python-fpe.git
cd python-fpe
pip3 install --editable .

Before contributing any pull requests, you will need to first fork this repository and change the remote origin to reflect your fork:

git remote set-url origin [email protected]:YOUR-GITHUB-USERNAME/python-fpe.git

To uninstall:

pip3 uninstall ff3

Usage

FF3 is a Feistel cipher, and Feistel ciphers are initialized with a radix representing an alphabet. The number of characters in an alphabet is called the radix. The following radix values are typical:

  • radix 10: digits 0..9
  • radix 36: alphanumeric 0..9, a-z
  • radix 62: alphanumeric 0..9, a-z, A-Z

Special characters and international character sets, such as those found in UTF-8, are supported by specifying a custom alphabet. Also, all elements in a plaintext string share the same radix. Thus, an identification number that consists of an initial letter followed by 6 digits (e.g. A123456) cannot be correctly encrypted by FPE while preserving this convention.

Input plaintext has maximum length restrictions based upon the chosen radix (2 * floor(96/log2(radix))):

  • radix 10: 56
  • radix 36: 36
  • radix 62: 32

To work around string length, its possible to encode longer text in chunks.

As with any cryptographic package, managing and protecting the key(s) is crucial. The tweak is generally not kept secret. This package does not store the key in memory after initializing the cipher.

Code Example

The example code below uses the default domain [0-9] and can help you get started.

{ciphertext} -> {decrypted}") # format encrypted value ccn = f"{ciphertext[:4]} {ciphertext[4:8]} {ciphertext[8:12]} {ciphertext[12:]}" print(f"Encrypted CCN value with formatting: {ccn}") ">
from ff3 import FF3Cipher

key = "EF4359D8D580AA4F7F036D6F04FC6A94"
tweak = "D8E7920AFA330A73"
c = FF3Cipher(key, tweak)

plaintext = "4000001234567899"
ciphertext = c.encrypt(plaintext)
decrypted = c.decrypt(ciphertext)

print(f"{plaintext} -> {ciphertext} -> {decrypted}")

# format encrypted value
ccn = f"{ciphertext[:4]} {ciphertext[4:8]} {ciphertext[8:12]} {ciphertext[12:]}"
print(f"Encrypted CCN value with formatting: {ccn}")

Custom alphabets

Custom alphabets up to 256 characters are supported. To use an alphabet consisting of the uppercase letters A-F (radix=6), we can continue from the above code example with:

{ciphertext} -> {decrypted}") ">
c6 = FF3Cipher.withCustomAlphabet(key, tweak, "ABCDEF")
plaintext = "DEADBEEF"
ciphertext = c6.encrypt(plaintext)
decrypted = c6.decrypt(ciphertext)

print(f"{plaintext} -> {ciphertext} -> {decrypted}")

Testing

Official test vectors for FF3 provided by NIST, are used for testing in this package. Also included are draft ACVP test vectors with 56-bit tweaks.

To run unit tests on this implementation, including all test vectors from the NIST specification, run the command:

python3 -m ff3.ff3_test

Performance Benchmarks

The Mysto FF3 was benchmarked on a MacBook Air (1.1 GHz Quad-Core Intel Core i5) performing 70,000 tokenization per second with random 8 character data input.

To run the performance tests:

python3 ff3_perf.py

The FF3 Algorithm

The FF3 algorithm is a tweakable block cipher based on an eight round Feistel cipher. A block cipher operates on fixed-length groups of bits, called blocks. A Feistel Cipher is not a specific cipher, but a design model. This FF3 Feistel encryption consisting of eight rounds of processing the plaintext. Each round applies an internal function or round function, followed by transformation steps.

The FF3 round function uses AES encryption in ECB mode, which is performed each iteration on alternating halves of the text being encrypted. The key value is used only to initialize the AES cipher. Thereafter the tweak is used together with the intermediate encrypted text as input to the round function.

Other FPE Algorithms

Only FF1 and FF3 have been approved by NIST for format preserving encryption. There are patent claims on FF1 which allegedly include open source implementations. Given the issues raised in "The Curse of Small Domains: New Attacks on Format-Preserving Encryption" by Hoang, Tessaro and Trieu in 2018, it is prudent to be very cautious about using any FPE that isn't a standard and hasn't stood up to public scrutiny.

Implementation Notes

This implementation was originally based upon the Capital One Go implementation. It follows the algorithm as outlined in the NIST specification as closely as possible, including naming.

FPE can be used for data tokenization of sensitive data which is cryptographically reversible. This implementation does not provide any guarantees regarding PCI DSS or other validation.

While all NIST and ACVP test vectors pass, this package has not otherwise been extensively tested.

The cryptographic library used is PyCryptodome for AES encryption. FF3 uses a single-block with an IV of 0, which is effectively ECB mode. AES ECB is the only block cipher function which matches the requirement of the FF3 spec.

The domain size was revised in FF3-1 to radixminLen >= 1,000,000 and is represented by the constant DOMAIN_MIN in ff3.py. FF3-1 is in draft status.

The tweak is required in the initial FF3Cipher constructor, but can optionally be overridden in each encrypt and decrypt call. This is similar to passing an IV or nonce when creating an encrypter object.

Author

Brad Schoening

License

This project is licensed under the terms of the Apache 2.0 license.

Comments
  • Ff3-1 aes256 key and tweak Generation

    Ff3-1 aes256 key and tweak Generation

    Thanks for this! I'm using your library atm to protect some testing data and it works great. But how can I generate an ff3-1 key and tweak for usage with aes256 block cipher please?

    opened by Kkeller83 6
  • Address outstanding issues with alphabets

    Address outstanding issues with alphabets

    As I explained in #17, the approach with withCustomAlphabet seems flawed to me. It prevents implementation of the full specification with radix up to 65536.

    Please see test_why_withCustomAlphabet_is_broken() in comparison with test_german(). Do you see how to get this test to pass?

    opened by maresb 4
  • Include broad .gitignore

    Include broad .gitignore

    Having a broad range of environment-specific stuff is good in my experience. That allows contributors to use whatever tools they want without going through the mess we saw with the .idea/ files. If the Python package is set up properly, the .gitignore won't be included in the PyPI distribution.

    In the end, it won't prevent you from git adding files. It just prevents git from suggesting irrelevant files to add.

    I read over @PuspenduBanerjee's .gitignore and it looks perfectly good to me. I'd recommend restoring it. Or at the very least find a standard Python-oriented .gitignore from somewhere.

    opened by maresb 4
  • Properly install as package, restore test_whole_domain, allow general radix.

    Properly install as package, restore test_whole_domain, allow general radix.

    Hi @bschoening, I've been slammed the past few weeks so I didn't get a chance to respond to https://github.com/mysto/python-fpe/pull/11#issuecomment-926608199 until now.

    That issue was caused by not having python-fpe properly installed as a Python package. (The way Python handles packages is a total mess...) In short, Python imports work for both files and modules with the same syntax. The command from ff3 import ff3 has two possible meanings:

    1. From the ff3 package import the ff3 module.
    2. From the ff3 subdirectory of the current directory, import ff3.py.

    Option 2 is bad because it depends on the path where the command is being executed. Thus it's better to install everything as a package with pip so that 1. makes sense and your commands work regardless of the path.

    I updated the README accordingly. An added benefit is that setuptools will automatically install pycryptodome as needed. There's no need for a separate pip install command.

    I then restored my test. My test was however broken due to radixMap. I removed radixMap because it behaves differently from what I expect. I would expect radix=26 to correspond to the character set [0-9a-p]. If you want [a-z] I think it would make more sense to implement an alphabet string parameter. You could then:

    1. Check that there are no duplicates (len(set(alphabet)) == len(alphabet))
    2. Check that all the characters in the input message occur in the alphabet
    3. Convert the input message to and from an integer based on the alphabet instead of base_conv_r() and Python's int(n, radix) function

    As a bonus, base-62 would be trivial. (alphabet=string.digits + string.ascii_lowercase + string.ascii_uppercase)

    opened by maresb 3
  • FF1

    FF1

    I started using the FF3-1 implementation recently and its super cool. However I was approached if FF1 would also be an option. I was told its "better" as in "more secure" than FF3-1.

    I dont know if that is true, but I certainly know that I can not implement FF1 in Python now.

    Would it be something to consider to also add FF1 support please?

    opened by sfc-gh-kkeller 2
  • Not an issue, actually

    Not an issue, actually

    I just wanted to let you know that I have used some of your test vectors to verify my C-implementation of the FPE algorithms. Of course I have mentioned the source and credit. Please feel free to check out the testvectors folder of this repository and inform me of any issues.

    Cheers

    opened by polfosol 1
  • Add failing tests for FF3Cipher constructors

    Add failing tests for FF3Cipher constructors

    In my branch, all of these cases worked correctly with my validate_radix_and_alphabet() function:

    def validate_radix_and_alphabet(radix, alphabet):
        """Validate and compute radix and alphabet given one or the other.
    
        If only radix is given, use the default alphabet up to that many characters.
        If only alphabet is given, compute the radix as the length of the alphabet.
        If both are given, verify consistency.
    
        Arguments:
        - `radix`: The length of the alphabet
        - `alphabet`: A string containing successive characters to be used as digits
    
        Returns:
        - `radix`, `alphabet`: A validated tuple containing both the radix and alphabet
        """
    
        if not isinstance(radix, (NoneType, int)):
            raise ValueError(f"radix must be an integer.")
    
        if radix is not None and radix < 2:
            raise ValueError("radix must be at least 2.")
    
        if not isinstance(alphabet, (NoneType, str)):
            raise ValueError(f"alphabet must be an string.")
    
        if alphabet is not None and len(alphabet) < 2:
            raise ValueError(f"alphabet must contain at least two characters.")
    
        if radix is not None and alphabet is not None:
            # Verify consistency
            if len(alphabet) != radix:
                raise ValueError(
                    f"The alphabet has length {len(alphabet)} which conflicts with "
                    f"the given value of {radix} for radix."
                )
    
        if alphabet is None:
            if radix is None:
                radix = 10
            # Use characters from the default alphabet.
            if radix > len(STANDARD_ALPHABET):
                raise ValueError(
                    f"For radix >{len(STANDARD_ALPHABET)} "
                    f"please specify a custom alphabet."
                )
            alphabet = STANDARD_ALPHABET[:radix]
        # alphabet is now defined. The radix might not be.
    
        if len(alphabet) != len(set(alphabet)):
            raise ValueError("The specified alphabet has duplicate characters.")
    
        if radix is None:
            radix = len(alphabet)
        # radix is now defined.
    
        if radix > RADIX_MAX:
            raise ValueError(
                f"The current radix {radix} exceeds the maximum allowed radix of "
                f"{RADIX_MAX} in the FF3-1 specification."
            )
    
        return radix, alphabet
    
    opened by maresb 1
  • Update PyPI package

    Update PyPI package

    The current release on PyPI is from Mar 17. It may be worth considering a workflow for automatically publishing tagged releases to PyPI, for example:

    https://packaging.python.org/guides/publishing-package-distribution-releases-using-github-actions-ci-cd-workflows/

    opened by maresb 1
  • Missing setup.py

    Missing setup.py

    The setup.py file which appears on PyPI does not appear in this repository.

    You may want to set up a CI workflow which publishes tagged commits to PyPI automatically, and for that you'd need to include the setup.py.

    opened by maresb 1
  • module 'Crypto.Cipher.AES' has no attribute 'AESCipher'

    module 'Crypto.Cipher.AES' has no attribute 'AESCipher'

    Hi There,

    I'm running this on Python 3.9.2 and I'm getting the package ff-3.py

    \lib\site-packages\ff3\ff3.py", line 90, in init self.aesBlock = AES.AESCipher(reverse_string(self.key))

    Code from ff-3.py line 90

    aes.NewCipher automatically returns the correct block based on the length of the key

        # Always use the reversed key since Encrypt and Decrypt call ciph expecting that
    
        self.aesBlock = AES.AESCipher(reverse_string(self.key))
    

    I've imported the package crypto. cipher but I couldn't find the AESCipher but it seems to be under crypto, let me know what do you think?

    opened by 1luvc0d3 1
  • Improve variable names in test_whole_domain

    Improve variable names in test_whole_domain

    Good point with https://github.com/mysto/python-fpe/pull/21#pullrequestreview-781518568

    Does this make it more understandable? I renamed working_digitsplaintext_len and eliminated n in favor of len(plaintexts_as_ints).

    opened by maresb 0
Releases(v1.0.1)
  • v1.0.1(Dec 31, 2021)

    This is a minor update of the Mysto FF3 format-preserving encryption library. This release has made no changes to encryption or decryption but offers some additional features for ease of use.

    What's Changed

    • Added ff3_encrypt and ff3_decrypt scripts for command line usage
    • Converted build to use setup.cfg and removed requirements.txt
    • Improved README.md

    Full Changelog: https://github.com/mysto/python-fpe/compare/v1.0.0...v1.0.1

    Source code(tar.gz)
    Source code(zip)
  • v1.0.0(Oct 27, 2021)

    This is the initial production stable release of the Mysto FF3 format-preserving encryption library. This release includes NIST and ACVP test vector for both FF3 with 64-bit tweaks and FF3-1 with 56-bit tweaks.

    What's Changed

    • ACVP FF3-1 test vectors
    • Added custom alphabet support with static factory method withCustomAlphabet()
    • Updated README.md by @PuspenduBanerjee and @maresb
    • Added regular python related gitignores, added setup.py by @PuspenduBanerjee in https://github.com/mysto/python-fpe/pull/8
    • Add misc. test by @maresb in https://github.com/mysto/python-fpe/pull/11
    • Properly install as a package with dependency (1/3) by @maresb in https://github.com/mysto/python-fpe/pull/14

    New Contributors

    • Puspendu Banerjee
    • Ben Mares @maresb

    Full Changelog: https://github.com/mysto/python-fpe/compare/v0.9.0...v1.0.0

    Source code(tar.gz)
    Source code(zip)
ROS Basics and TurtleSim

Homework 1: Turtle Control Package Anna Garverick This package draws given waypoints, then waits for a service call with a start position to send the

Anna Garverick 1 Nov 22, 2021
zoofs is a Python library for performing feature selection using an variety of nature inspired wrapper algorithms. The algorithms range from swarm-intelligence to physics based to Evolutionary. It's easy to use ,flexible and powerful tool to reduce your feature size.

zoofs is a Python library for performing feature selection using a variety of nature-inspired wrapper algorithms. The algorithms range from swarm-intelligence to physics-based to Evolutionary. It's e

Jaswinder Singh 168 Dec 30, 2022
Programming Foundations Algorithms With Python

Programming-Foundations-Algorithms Algorithms purpose to solve a specific proplem with a sequential sets of steps for instance : if you need to add di

omar nafea 1 Nov 01, 2021
A calculator to test numbers against the collatz conjecture

The Collatz Calculator This is an algorithm custom built by Kyle Dickey, used to test numbers against the simple rules of the Collatz Conjecture. Get

Kyle Dickey 2 Jun 14, 2022
Provide player's names and mmr and generate mathematically balanced teams

Lollo's matchmaking algorithm Provide player's names and mmr and generate mathematically balanced teams How to use Fill the input.json file with your

4 Aug 04, 2022
:computer: Data Structures and Algorithms in Python

Algorithms in Python Implementations of a few algorithms and datastructures for fun and profit! Completed Karatsuba Multiplication Basic Sorting Rabin

Prakhar Srivastav 2.9k Jan 01, 2023
Sorting-Algorithms - All information about sorting algorithm you need and you can visualize the code tracer

Sorting-Algorithms - All information about sorting algorithm you need and you can visualize the code tracer

Ahmed Hossam 15 Oct 16, 2022
With this algorithm you can see all best positions for a Team.

Best Positions Imagine that you have a favorite team, and you want to know until wich position your team can reach With this algorithm you can see all

darlyn 4 Jan 28, 2022
Python Sorted Container Types: Sorted List, Sorted Dict, and Sorted Set

Python Sorted Containers Sorted Containers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions. Python

Grant Jenks 2.8k Jan 04, 2023
Using Bayesian, KNN, Logistic Regression to classify spam and non-spam.

Make Sure the dataset file "spamData.mat" is in the folder spam\src Environment: Python --version = 3.7 Third Party: numpy, matplotlib, math, scipy

0 Dec 26, 2021
Visualisation for sorting algorithms. Version 2.0

Visualisation for sorting algorithms v2. Upped a notch from version 1. This program provides animates simple, common and popular sorting algorithms, t

Ben Woo 7 Nov 08, 2022
🌟 Python algorithm team note for programming competition or coding test

🌟 Python algorithm team note for programming competition or coding test

Seung Hoon Lee 3 Feb 25, 2022
BCI datasets and algorithms

Brainda Welcome! First and foremost, Welcome! Thank you for visiting the Brainda repository which was initially released at this repo and reorganized

52 Jan 04, 2023
frePPLe - open source supply chain planning

frePPLe Open source supply chain planning FrePPLe is an easy-to-use and easy-to-implement open source advanced planning and scheduling tool for manufa

frePPLe 385 Jan 06, 2023
A simple library for implementing common design patterns.

PyPattyrn from pypattyrn.creational.singleton import Singleton class DummyClass(object, metaclass=Singleton): # DummyClass is now a Singleton!

1.7k Jan 01, 2023
This repository is an individual project made at BME with the topic of self-driving car simulator and control algorithm.

BME individual project - NEAT based self-driving car This repository is an individual project made at BME with the topic of self-driving car simulator

NGO ANH TUAN 1 Dec 13, 2021
Python sample codes for robotics algorithms.

PythonRobotics Python codes for robotics algorithm. Table of Contents What is this? Requirements Documentation How to use Localization Extended Kalman

Atsushi Sakai 17.2k Jan 01, 2023
Multiple Imputation with Random Forests in Python

miceforest: Fast, Memory Efficient Imputation with lightgbm Fast, memory efficient Multiple Imputation by Chained Equations (MICE) with lightgbm. The

Samuel Wilson 202 Dec 31, 2022
Official implementation of "Path Planning using Neural A* Search" (ICML-21)

Path Planning using Neural A* Search (ICML 2021) This is a repository for the following paper: Ryo Yonetani*, Tatsunori Taniai*, Mohammadamin Barekata

OMRON SINIC X 82 Jan 07, 2023
A* (with 2 heuristic functions), BFS , DFS and DFS iterativeA* (with 2 heuristic functions), BFS , DFS and DFS iterative

Descpritpion This project solves the Taquin game (jeu de taquin) problem using different algorithms : A* (with 2 heuristic functions), BFS , DFS and D

Ayari Ahmed 3 May 09, 2022