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)
Sign data using symmetric-key algorithm encryption.

Sign data using symmetric-key algorithm encryption. Validate signed data and identify possible validation errors. Uses sha-(1, 224, 256, 385 and 512)/hmac for signature encryption. Custom hash algorithms are allowed. Useful shortcut functions for signing (and validating) dictionaries and URLs.

Artur Barseghyan 39 Jun 10, 2022
A raw implementation of the nearest insertion algorithm to resolve TSP problems in a TXT format.

TSP-Nearest-Insertion A raw implementation of the nearest insertion algorithm to resolve TSP problems in a TXT format. Instructions Load a txt file wi

sjas_Phantom 1 Dec 2, 2021
Algorithms-in-Python - Programs related to DSA in Python for placement practice

Algorithms-in-Python Programs related to DSA in Python for placement practice CO

MAINAK CHAUDHURI 2 Feb 2, 2022
Minimal examples of data structures and algorithms in Python

Pythonic Data Structures and Algorithms Minimal and clean example implementations of data structures and algorithms in Python 3. Contributing Thanks f

Keon 22k Jan 9, 2023
Repository for data structure and algorithms in Python for coding interviews

Python Data Structures and Algorithms This repository contains questions requiring implementation of data structures and algorithms concepts. It is us

Prabhu Pant 1.9k Jan 1, 2023
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 4, 2023
All Algorithms implemented in Python

The Algorithms - Python All algorithms implemented in Python (for education) These implementations are for learning purposes only. Therefore they may

The Algorithms 150.6k Jan 3, 2023
A collection of design patterns/idioms in Python

python-patterns A collection of design patterns and idioms in Python. Current Patterns Creational Patterns: Pattern Description abstract_factory use a

Sakis Kasampalis 36.2k Jan 5, 2023
A lightweight, object-oriented finite state machine implementation in Python with many extensions

transitions A lightweight, object-oriented state machine implementation in Python with many extensions. Compatible with Python 2.7+ and 3.0+. Installa

null 4.7k Jan 1, 2023
: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 1, 2023
Algorithms implemented in Python

Python Algorithms Library Laurent Luce Description The purpose of this library is to help you with common algorithms like: A* path finding. String Mat

Laurent Luce 264 Dec 6, 2022
A fast python implementation of the SimHash algorithm.

This Python package provides hashing algorithms for computing cohort ids of users based on their browsing history. As such, it may be used to compute cohort ids of users following Google's Federated Learning of Cohorts (FLoC) proposal.

Hybrid Theory 19 Dec 15, 2022
A command line tool for memorizing algorithms in Python by typing them.

Algo Drills A command line tool for memorizing algorithms in Python by typing them. In alpha and things will change. How it works Type out an algorith

Travis Jungroth 43 Dec 2, 2022
A genetic algorithm written in Python for educational purposes.

Genea: A Genetic Algorithm in Python Genea is a Genetic Algorithm written in Python, for educational purposes. I started writing it for fun, while lea

Dom De Felice 20 Jul 6, 2022
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 1, 2023
An implementation of ordered dithering algorithm in python as multimedia course project

One way of minimizing the size of an image is to simply reduce the number of bits you use to represent each pixel.

null 7 Dec 2, 2022
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 easy to use , flexible and powerful tool to reduce your feature size.

Jaswinder Singh 168 Dec 30, 2022
A Python Package for Portfolio Optimization using the Critical Line Algorithm

A Python Package for Portfolio Optimization using the Critical Line Algorithm

null 19 Oct 11, 2022
The DarkRift2 networking framework written in Python 3

DarkRiftPy is Darkrift2 written in Python 3. The implementation is fully compatible with the original version. So you can write a client side on Python that connects to a Darkrift2 server written in C# using the original Darkrift2 library, and vice versa.

Anton Dobryakov 6 May 23, 2022