research-article

Public Access

Message-Recovery Attacks on Feistel-Based Format Preserving Encryption

Authors:

Mihir Bellare,

Viet Tung Hoang,

Stefano TessaroAuthors Info & Claims

CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

Pages 444 - 455

https://doi.org/10.1145/2976749.2978390

Published: 24 October 2016 Publication History

PDF eReader

Abstract

We give attacks on Feistel-based format-preserving encryption (FPE) schemes that succeed in message recovery (not merely distinguishing scheme outputs from random) when the message space is small. For $4$-bit messages, the attacks fully recover the target message using $2^{21}$ examples for the FF3 NIST standard and $2^{25}$ examples for the FF1 NIST standard. The examples include only three messages per tweak, which is what makes the attacks non-trivial even though the total number of examples exceeds the size of the domain. The attacks are rigorously analyzed in a new definitional framework of message-recovery security. The attacks are easily put out of reach by increasing the number of Feistel rounds in the standards.

References

[1]

M. Bellare, T. Ristenpart, P. Rogaway, and T. Stegers. Format-preserving encryption. In M. J. Jacobson Jr., V. Rijmen, and R. Safavi-Naini, editors, SAC 2009, volume 5867 of LNCS, pages 295--312. Springer, Heidelberg, Aug. 2009.

Digital Library

Google Scholar

[2]

M. Bellare and P. Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In S. Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 409--426. Springer, Heidelberg, May / June 2006.

Digital Library

Google Scholar

[3]

M. Bellare, P. Rogaway, and T. Spies. Addendum to "the FFX mode of operation for Format-Preserving Encryption". Draft 1.0. Submission to NIST, Sept. 2010. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ffx-spec2.pdf.

Google Scholar

[4]

M. Bellare, P. Rogaway, and T. Spies. The FFX mode of operation for format-preserving encryption. Draft 1.1. Submission to NIST, Feb. 2010. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ffx-spec.pdf.

Google Scholar

[5]

J. Black and P. Rogaway. Ciphers with arbitrary finite domains. In B. Preneel, editor, CT-RSA 2002, volume 2271 of LNCS, pages 114--130. Springer, Heidelberg, Feb. 2002.

Digital Library

Google Scholar

[6]

E. Brier, T. Peyrin, and J. Stern. BPS: a format-preserving encryption proposal. Submission to NIST, 2010. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/bps/bps-spec.pdf.

Google Scholar

[7]

M. Dworkin. Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption. NIST Special Publication 800--38G, Mar. 2016. http://dx.doi.org/10.6028/NIST.SP.800--38G.

Crossref

Google Scholar

[8]

M. Liskov, R. L. Rivest, and D. Wagner. Tweakable block ciphers. Journal of Cryptology, 24(3):588--613, July 2011.

Digital Library

Google Scholar

[9]

J. Patarin. New results on pseudorandom permutation generators based on the DES scheme. In J. Feigenbaum, editor, CRYPTO'91, volume 576 of LNCS, pages 301--312. Springer, Heidelberg, Aug. 1992.

Digital Library

Google Scholar

[10]

J. Patarin. Generic attacks on Feistel schemes. In C. Boyd, editor, ASIACRYPT 2001, volume 2248 of LNCS, pages 222--238. Springer, Heidelberg, Dec. 2001.

Digital Library

Google Scholar

[11]

J. Patarin. Security of random Feistel schemes with 5 or more rounds. In M. Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 106--122. Springer, Heidelberg, Aug. 2004.

Google Scholar

Cited By

View all

Denisov O(2025)Спектральные атаки различения на схемы Луби - Ракова по независимым двублочным текстамSpectral distinguishing attacks on Luby - Rackoff schemes based on independent two-block textsМатематические вопросы криптографииMatematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography]10.4213/mvk48315:4(23-42)Online publication date: 20-Jan-2025
https://doi.org/10.4213/mvk483
Miracle SYilek S(2023)Targeted Invertible Pseudorandom Functions and Deterministic Format-Transforming EncryptionTopics in Cryptology – CT-RSA 202310.1007/978-3-031-30872-7_24(622-642)Online publication date: 19-Apr-2023
https://doi.org/10.1007/978-3-031-30872-7_24
Tsaregorodtsev K(2022)Format-preserving encryption: a surveyМатематические вопросы криптографииMatematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography]10.4213/mvk41213:2(133-153)Online publication date: 19-Jul-2022
https://doi.org/10.4213/mvk412
Show More Cited By

Index Terms

Message-Recovery Attacks on Feistel-Based Format Preserving Encryption
1. Security and privacy
  1. Cryptography
    1. Information-theoretic techniques
    2. Symmetric cryptography and hash functions

Recommendations

A format-preserving encryption FF1, FF3-1 using lightweight block ciphers LEA and, SPECK
SAC '20: Proceedings of the 35th Annual ACM Symposium on Applied Computing

Format-preserving encryption has been studied for a long time since its proposal, but the algorithm is yet to be adequately evaluated or verified. The existing standard format-preserving encryption FF1 and FF3-1 use block cipher AES in the internal ...
The Curse of Small Domains: New Attacks on Format-Preserving Encryption
Advances in Cryptology – CRYPTO 2018
Abstract
Format-preserving encryption (FPE) produces ciphertexts which have the same format as the plaintexts. Building secure FPE is very challenging, and recent attacks (Bellare, Hoang, Tessaro, CCS ’16; Durak and Vaudenay, CRYPTO ’17) have highlighted ...
Targeted Ciphers for Format-Preserving Encryption
Selected Areas in Cryptography – SAC 2018
Abstract
We introduce Targeted Ciphers, which typically encipher points on domain , but can be easily modified to instead encipher points on some subset . Ciphers that can directly support this domain targeting are useful in Format-Preserving Encryption, ...

Comments

Information & Contributors

Information

Published In

CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

October 2016

1924 pages

ISBN:9781450341394

DOI:10.1145/2976749

General Chairs:
Edgar Weippl
SBA Research, Austria
,
Stefan Katzenbeisser
TU Darmstadt, CYSEC, Germany
,
Program Chairs:
Christopher Kruegel
University of California, Santa Barbara, USA
,
Andrew Myers
Cornell University, USA
,
Shai Halevi
IBM Research, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF
European Research Council

Conference

CCS'16

Sponsor:

SIGSAC

CCS'16: 2016 ACM SIGSAC Conference on Computer and Communications Security

October 24 - 28, 2016

Vienna, Austria

Acceptance Rates

CCS '16 Paper Acceptance Rate 137 of 831 submissions, 16%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
889
Total Downloads

Downloads (Last 12 months)140
Downloads (Last 6 weeks)19

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Denisov O(2025)Спектральные атаки различения на схемы Луби - Ракова по независимым двублочным текстамSpectral distinguishing attacks on Luby - Rackoff schemes based on independent two-block textsМатематические вопросы криптографииMatematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography]10.4213/mvk48315:4(23-42)Online publication date: 20-Jan-2025
https://doi.org/10.4213/mvk483
Miracle SYilek S(2023)Targeted Invertible Pseudorandom Functions and Deterministic Format-Transforming EncryptionTopics in Cryptology – CT-RSA 202310.1007/978-3-031-30872-7_24(622-642)Online publication date: 19-Apr-2023
https://doi.org/10.1007/978-3-031-30872-7_24
Tsaregorodtsev K(2022)Format-preserving encryption: a surveyМатематические вопросы криптографииMatematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography]10.4213/mvk41213:2(133-153)Online publication date: 19-Jul-2022
https://doi.org/10.4213/mvk412
Wang DWang BPing Y(2021)Comment on ‘Targeted Ciphers for Format‐Preserving Encryption’ from Selected Areas in Cryptography 2018IET Information Security10.1049/ise2.1202815:5(395-400)Online publication date: 2-May-2021
https://doi.org/10.1049/ise2.12028
Durak FHorst HHorst MVaudenay S(2021)FAST: Secure and High Performance Format-Preserving Encryption and TokenizationAdvances in Cryptology – ASIACRYPT 202110.1007/978-3-030-92078-4_16(465-489)Online publication date: 1-Dec-2021
https://doi.org/10.1007/978-3-030-92078-4_16
Beyne T(2021)Linear Cryptanalysis of FF3-1 and FEAAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84242-0_3(41-69)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84242-0_3
Amon ODunkelman OKeller NRonen EShamir A(2021)Three Third Generation Attacks on the Format Preserving Encryption Scheme FF3Advances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77886-6_5(127-154)Online publication date: 16-Jun-2021
https://doi.org/10.1007/978-3-030-77886-6_5
Yesin VKarpinski MYesina MVilihura VWarwas K(2020)Hiding the Source Code of Stored Database ProgramsInformation10.3390/info1112057611:12(576)Online publication date: 9-Dec-2020
https://doi.org/10.3390/info11120576
Li SGao YShi T(2020)Identity-Based Hybrid Format-Preserving Encryption Scheme2020 IEEE 5th Information Technology and Mechatronics Engineering Conference (ITOEC)10.1109/ITOEC49072.2020.9141834(470-474)Online publication date: Jun-2020
https://doi.org/10.1109/ITOEC49072.2020.9141834
Sun HLuo HSun Y(2019)Data Hiding for Ensuring the Quality of the Host Image and the Security of the MessageIEEE Access10.1109/ACCESS.2019.29075307(64767-64777)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2907530
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A format-preserving encryption FF1, FF3-1 using lightweight block ciphers LEA and, SPECK

The Curse of Small Domains: New Attacks on Format-Preserving Encryption

Targeted Ciphers for Format-Preserving Encryption