Three Third Generation Attacks on Format Preserving Encryption
Format Preserving Encryption (FPE) like FF3 encrypts any domain into itself, useful for databases and communication packets. Previous attacks and contributions are discussed, showcasing different generations of attacks and their complexities.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Three Third Generation Attacks on the Format Preserving Encryption FF3 Orr Dunkelman Ohad Amon Nathan Keller Eyal Ronen Adi Shamir
FF3 FF3 is Format Preserving Encryption (FPE), specified by NIST in a 2016 publication An FPE can encrypt any domain into itself E.g., a ciphertext of a credit card number can be a valid credit card number Useful for adding encryption to existing databases or communication packets that require a specific format After attacks by Durak and Vaudenay (2017), FF3-1 was specified A recent paper by Beyne (2021) presents attack on FF3-1
FF3 FF3 accepts plaintexts of a domain ? ?, along with a key ? and tweak ?, and encrypts them to ciphertexts in the domain ? ? For simplicity we assume ? = ? and use ? to express complexity The complexity of each attack is portrayed using Data, Time, and Memory requirements
Previous Attacks Attack Data ?2 Time ?2 Memory ?2 Full Codebook Recovery
Previous Attacks Attack Data ?2 Time ?2 ?(?5) Memory ?2 ?(?11/6) Full Codebook Recovery ?(?11/6) First Generation [Durak and Vaudenay, 2017]
Previous Attacks Attack Data ?2 Time ?2 ?(?5) Memory ?2 ?(?11/6) Full Codebook Recovery ?(?11/6) First Generation [Durak and Vaudenay, 2017] ?(?11/6) ?(?17/6) ?(?11/6) Second Generation [Hoang, Miller, and Trieu, 2019]
Our Contributions Attack Data ?2 Time ?2 ?(?5) Memory ?2 ?(?11/6) Full Codebook Recovery ?(?11/6) First Generation [Durak and Vaudenay, 2017] ?(?11/6) ?(?17/6) ?(?11/6) Second Generation [Hoang, Miller, and Trieu, 2019] ?(?7/4 ?) ?(?5/2+2?) ?(?7/4 ?) Symmetric Slide* * 0 ? 1/4
Our Contributions Attack Data ?2 Time ?2 ?(?5) Memory ?2 ?(?11/6) Full Codebook Recovery ?(?11/6) First Generation [Durak and Vaudenay, 2017] ?(?11/6) ?(?17/6) ?(?11/6) Second Generation [Hoang, Miller, and Trieu, 2019] ?(?7/4 ?) ?(?2 ?) ?(?5/2+2?) ?(?2+?) ?(?7/4 ?) ?(?2 ?) Symmetric Slide* Asymmetric Slide** * 0 ? 1/4 ** 0 ? 1/2
Our Contributions Attack Data ?2 Time ?2 ?(?5) Memory ?2 ?(?11/6) Full Codebook Recovery ?(?11/6) First Generation [Durak and Vaudenay, 2017] ?(?11/6) ?(?17/6) ?(?11/6) Second Generation [Hoang, Miller, and Trieu, 2019] ?(?7/4 ?) ?(?2 ?) ?(?2) ?(?5/2+2?) ?(?2+?) ?(?2) ?(?7/4 ?) ?(?2 ?) ?(?2) Symmetric Slide* Asymmetric Slide** Cycle Detection Slide * 0 ? 1/4 ** 0 ? 1/2
Our Contributions All new attacks were experimentally verified by performing them on instances of FF3 with random keys and tweaks Tests were performed domain sizes up to ? = 212 Success rates are strictly better than the second-generation attack
The FF3 Construction ??(?) ??(?) A Feistel Construction from ? ? to ? ? Contains 8 rounds Instead of XOR, addition modulo ? is used to combine the two halves ?0 ?1 ?7 ??(?) ??(?)
The Round Function ?? ??(?) ??(?) ??(?) ??(?) ?? 0 FF3 accepts two parameters: ?0 ? A 128-bit secret key ? ?? 1 A 64-bit tweak ? = ??||?? Aside from acting as an IV, the tweak is used to make the rounds distinct from one another The round function ?? is defined as: ?1 ? ?? 7 ?7 ? ??(?) = ????(?| ?? ? ?? ? ?? ???? ????(?| ?? ? ?? ? ?? ??? ??(?) ??(?) ??(?) ??(?)
Attack Outline 1. Create a reduction from 8-round FF3 to 4-round FF3 2. Break 4-round FF3 by reconstructing the codebooks of each round function (PRF Reconstruction) 3. Combine the above to reconstruct the codebooks of 8- round FF3 This presentation will focus on Step 1
The Slide Characteristic of FF3 [DV17] Assume that we can choose ? ??(?) ??(?) Then we can abuse the tweak scheme to create a slide attack ?? 0 ? Choose ? = ??||?? and ? = ?? 4||?? 4. ?? 1 ?
The Slide Characteristic of FF3 [DV17] Encryption under ? = ?? 4||?? 4: Encryption under ? = ??||??: ?0= ?? 0 ?0= ?? 4 ?1= ?? 1 ?1= ?? 5 ?2= ?? 2 ?2= ?? 6 ?3= ?? 3 ?3= ?? 7 ?4= ?? 4 ?4= ?? 0 ?5= ?? 5 ?5= ?? 1 ?6= ?? 6 ?6= ?? 2 ?7= ?? 7 ?7= ?? 3
The Slide Characteristic of FF3 [DV17] Encryption under ? = ?? 4||?? 4: Encryption under ? = ??||??: ?0= ?? 0 ?0= ?? 4 ?1= ?? 1 ?1= ?? 5 ?2= ?? 2 ?2= ?? 6 ?3= ?? 3 ?3= ?? 7 ?4= ?? 4 ?4= ?? 0 ?5= ?? 5 ?5= ?? 1 ?6= ?? 6 ?6= ?? 2 ?7= ?? 7 ?7= ?? 3
The Slide Characteristic of FF3 [DV17] ? : ?: ??3?,?= ? ? ??3?,? = ? ? ? ? ? and ? are FF3 with 4 rounds. Using this, we can perform a slide attack on FF3. Goal: find input-output pairs for ? and ? ? ?
Slid Chains [F02] We can iteratively construct an encryption chain by choosing a random ?0 and defining: ??+1= ??3?,??? = ?(? ??). ? ? ? ? ?0 ?1 ?2 Make another chain using a random ?0 and the tweak ? . ??+1= ??3?,? ?? = ?(? ??) ? ? ? ? ?0 ?1 ?2
Slid Chains [F02] What if for some ?: ? ?0 = ?? ? ? ? ? ?0 ?? ?1 ??+1 ?2 ? ? ? ? ?? ?1 ??+1 ?2 ??+2 ? ?? = ?1 ? ??+1 = ?2 ? ??+2 = ?3 ? ?0 = ?? ? ?1 = ??+1 ? ?2 = ??+2
Slid Chains [F02] What if for some ?: ? ?0 = ?? ? ? ? ? ?0 ?? ?1 ??+1 ?2 ? ? ? ? ?? ?1 ??+1 ?2 ??+2 We have plaintext-ciphertext pairs for ? and for ? Chains of such offset are called slid chains
Identifying Slid Chains Problem: difficult to identify slid chains without knowing the intermediate values Naive Solution [DV17]: try PRF Reconstruction on every offset If it succeeds, we have found a slide Very expensive PRF Reconstruction takes ?(?3/2) time ? ? ? ? ?0 ?? ?1 ??+1 ?2 ? ? ? ? ?? ?1 ??+1 ?2 ??+2
Identifying Slid Chains Solution [HMT19]: a distinguisher for 4-round FF3! If the chains are slid with offset ?, then intermediate values are plaintext- ciphertext pairs for 4-round FF3 Else, the values aren t correlated If we find a distinguisher that performs better than PRF reconstruction, then the attack is improved ? ? ? ? ?0 ?? ?1 ??+1 ?2 ? ? ? ? ?? ?1 ??+1 ?2 ??+2
A Distinguisher for 4-Round FF3 Hoang et al. used a distinguisher that requires ?(?3/2) pairs of plaintexts with a common right half Using the Chernoff bound, we show it requires ?(?) pairs We can create ?(?) pairs by accepting ?(?1/2) plaintexts with a common right half ?(?1/2) Data and Time
Slide Attacks Now we can set up our attacks Attack Data Time Memory ?(?7/4 ?) ?(?5/2+2?) ?(?7/4 ?) Symmetric Slide ?(?2 ?) ?(?2+?) ?(?2 ?) Asymmetric Slide ?(?2) ?(?2) ?(?2) Cycle Detection Slide
Slide Attacks Now we can set up our attacks Attack Data Time Memory ?(?7/4 ?) ?(?5/2+2?) ?(?7/4 ?) Symmetric Slide ?(?2 ?) ?(?2+?) ?(?2 ?) Asymmetric Slide ?(?2) ?(?2) ?(?2) Cycle Detection Slide
Cycle Structure Slide Attack FF3 is a permutation, meaning its graph is ? ? ?0 formed of cycles ? ?1 This structure can be utilized to find slid chains ? ? more easily ?3 ? Theoretical attack [BDK07] ?2 ? ?
Cycle Structure Slide Attack Consider a cyclic chain of size in the permutation graph of FF3?,? The -length cycle defined by its intermediate states exists in the permutation graph of FF3?,? ? ? ?0 ? ?0 ? ?0 ? ? ?1 ?3 ?3 ? ? ? ?1 ? ?1 ?3 ? ? ?2 ? ?2 ? ?2 ? ?
Cycle Structure Slide Attack The distinguisher needs ?(?1/2) plaintexts with a common right half Minimum cycle length ?(?3/2) With high probability such a cycle exists, and its length is unique [SL66] We need to find a cycle of the same length over ? Finding a cycle of a specific length is costly in data we need to go over most of the graph (? = ?(?2), ? = ? = ?(?2))
Cycle Structure Slide Attack ? All offsets between the two ?0 ?1 ?2 ?3 ? ?0 ? cycles are tested ?1 ?3 ?0 ?1 ?2 If an offset is accepted, it is ? used to recover ? and ? ? ?1 ?2 ?3 ?0 ?3 ? ?2 ? ?2 ?3 ?0 ?1 ?
Cycle Structure Slide Attack - Algorithm Find an input cycle of length ?(?3/2) encrypted under ?,? Find an output cycle of the same length encrypted under ?,? Preprocess the input cycle by finding the most common right-hand value and keeping all ?(?1/2) indices where it appears Test all ?(?3/2) possible slides using the distinguisher If the distinguisher accepts a slide, call PRF Reconstruction on ? and on ? ? = ? ?3/2offsets ? ?1/2distinguisher = ? ?2 D = ? = ? ?2: finding the cycles
Further Contributions Improved time complexity of PRF Reconstruction from ?(?5/3) to ?(?3/2) Two Related-Domain attacks: A generic attack on Cycle Walking FPE Schemes A distinguishing attack on FF3 and FF3-1 Additional Results
Conclusion We presented 3 new attacks on ??3: Attack Data Time Memory ?(?7/4 ?) ?(?2 ?) ?(?2) ?(?7/4 ?) ?(?2 ?) ?(?2) ?(?5/2+2?) ?(?2+?) ?(?2) Symmetric Slide Asymmetric Slide Cycle Detection Slide The Symmetric and Asymmetric attacks significantly reduce Data complexity, while also improving Time and Memory The Cycle Detection Slide is a practical application of a previously theoretical attack
