In most encryption methods we deal with block sizes, such as 64 bit for DES and 128 bits for AES. The output will then be a multiple of 64 bits or 128 bits, as we cipher one block at a time. In FPE (Format Preserving Encryption), we want to have something which will match to the length of the input data. One solution is Format-preserving, Feistel-based encryption (FFX) and which produces an output which matches the length of the input.
Format-preserving, Feistel-based encryption (FFX) in Rust |
Outline
Within tokenization we can apply format preserving encryption (FPE) methods, which will convert our data into a format which still looks valid, but which cannot be mapped to the original value. For example, we could hide Bob's credit card detail into another valid credit card number, and which would not reveal his real number. A tokenization server could then convert the real credit card number into a format which still looked valid. For this we have a key which takes the data, and then converts it into a form which the same length as the original.
The method we use is based on a Feistel structure, and where we have a number of rounds, and then apply the key through a Feistel function for each round:
We thus split the data into blocks (typically 64-bits), and then split into two parts. We then take these splits into the left part and the right part, and feed through each round, and then swap them over. The ⊕ symbol is an exclusive-OR operator.
So, we have a problem here. In most encryption methods we deal with block sizes, such as 64 bit for DES and 128 bits for AES. The output will then be a multiple of 64 bits or 128 bits, as we cipher one block at a time. In FPE we want to have something which will match to the length of the input data. The solution is Format-preserving, Feistel-based encryption (FFX) and which produces an output which matches the length of the input.
NIST have thus defined a standard known as SP 800–38G, and which defines two FF schemes: FF1 an FF3. While these work on 128-bit block sizes, they can also work on blocks which have fewer bits than this. For this we have a key (K) and which creates a permutation of the bits to create an invertible version of the output.
For FF1 we have 10 rounds and for FF3 we have eight rounds. First, we split an input value of n characters into a number of characters (u and v - and where n = u + v):
For the encrypting process we use a modular addition (EX-OR) and for decryption, we use a modular subtraction. For each round, we split into \(a\) and \(b\). For the F function in each round, we generate an HMAC output (using SHA-1) from the key (K), the bᵢ, and the counter value (i):
h = hmac.new(self.key, key + struct.pack('I', i), self.digestmod)
and where self.key (\(K\)) is the key (normally a passphrase) that we will use to make the conversion, key is the \(b_i\) input, and self.digestmod is defined as hashlib.sha1. This output will then either be added (encryption) or subtracted (decryption) to the \(a_i\) input.
An important parameter is the radix value, and which defines the total number of characters that we will use for the character set. If it is binary, we will have a value of 2, if it is hexadecimal characters the value will 16, and for lower case characters it will be 26.
For encryption we just modular add our current value of \(a\) to the output of the key round (\(h\)) and swap values:
c = self.add(radix, a, self.round(radix, i, b)) a, b = b, c
For decryption we just modular subtract our current value of \(a\) from the output of the key round (\(h\)) and swap values:
c = self.sub(radix, a, self.round(radix, i, b)) a, b = b, c
An outline of the Rust code is:
extern crate aes; extern crate fpe; extern crate hex; extern crate rand; use std::env; use rand::{Rng}; fn main() { use aes::Aes128; use fpe::ff1::{BinaryNumeralString,FF1}; let key = rand::thread_rng().gen::<[u8; 16]>(); let radix = 2; let mut instr="hello 123"; let args: Vec= env::args().collect(); if args.len() >1 { instr = args[1].as_str();} let pt = instr.as_bytes(); let ff = FF1:: ::new(&key, radix).unwrap(); let ct = ff.encrypt(&[], &BinaryNumeralString::from_bytes_le(&pt)).unwrap(); let p2 = ff.decrypt(&[], &ct).unwrap(); println!("Input: {0}\n", instr); let p2_str=String::from_utf8(p2.to_bytes_le()); println!("Key: {}\n",hex::encode(key)); println!("Cipher: {}\n",hex::encode(ct.to_bytes_le())); println!("Decrypted: {0}", p2_str.unwrap()); }
Finally we simply build with:
cargo build
A sample run is:
Input: This is a secret message! Yes Key: 4a6ef1de1bfe359f23f20efd52eb6ac5 Cipher: b615433eeefd70f68bfb86e860bb13e1d36d20546ccdaea8ca18c15dbc Decrypted: This is a secret message! Yes