Attacks only get better: How to break FF3 on large domains

Viet Tung Hoang; David Miller; Ni Trieu

doi:10.1007/978-3-030-17656-3_4

Attacks only get better: How to break FF3 on large domains

Viet Tung Hoang
, David Miller
, Ni Trieu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

We improve the attack of Durak and Vaudenay (CRYPTO’17) on NIST Format-Preserving Encryption standard FF3, reducing the running time from O(N⁵) to O(N^{17 / 6}) for domain Z_N× Z_N. Concretely, DV’s attack needs about 2 ⁵⁰ operations to recover encrypted 6-digit PINs, whereas ours only spends about 2 ³⁰ operations. In realizing this goal, we provide a pedagogical example of how to use distinguishing attacks to speed up slide attacks. In addition, we improve the running time of DV’s known-plaintext attack on 4-round Feistel of domain Z_N× Z_N from O(N³) time to just O(N^{5 / 3}) time. We also generalize our attacks to a general domain Z_M× Z_N, allowing one to recover encrypted SSNs using about 2 ⁵⁰ operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.

Original language	English (US)
Title of host publication	Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Vincent Rijmen, Yuval Ishai
Publisher	Springer Verlag
Pages	85-116
Number of pages	32
ISBN (Print)	9783030176556
DOIs	https://doi.org/10.1007/978-3-030-17656-3_4
State	Published - 2019
Externally published	Yes
Event	38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 - Darmstadt, Germany Duration: May 19 2019 → May 23 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11477 LNCS

Conference

Conference	38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
Country/Territory	Germany
City	Darmstadt
Period	5/19/19 → 5/23/19

Keywords

Attacks
Format-Preserving Encryption

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-17656-3_4

Cite this

Hoang, V. T., Miller, D., & Trieu, N. (2019). Attacks only get better: How to break FF3 on large domains. In V. Rijmen, & Y. Ishai (Eds.), Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 85-116). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11477 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-17656-3_4

Attacks only get better: How to break FF3 on large domains. / Hoang, Viet Tung; Miller, David; Trieu, Ni.
Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Vincent Rijmen; Yuval Ishai. Springer Verlag, 2019. p. 85-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11477 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hoang, VT, Miller, D & Trieu, N 2019, Attacks only get better: How to break FF3 on large domains. in V Rijmen & Y Ishai (eds), Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11477 LNCS, Springer Verlag, pp. 85-116, 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019, Darmstadt, Germany, 5/19/19. https://doi.org/10.1007/978-3-030-17656-3_4

Hoang VT, Miller D, Trieu N. Attacks only get better: How to break FF3 on large domains. In Rijmen V, Ishai Y, editors, Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer Verlag. 2019. p. 85-116. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-17656-3_4

Hoang, Viet Tung ; Miller, David ; Trieu, Ni. / Attacks only get better : How to break FF3 on large domains. Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Vincent Rijmen ; Yuval Ishai. Springer Verlag, 2019. pp. 85-116 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{130683809aab45b6ae8a05453ad982f6,

title = "Attacks only get better: How to break FF3 on large domains",

abstract = "We improve the attack of Durak and Vaudenay (CRYPTO{\textquoteright}17) on NIST Format-Preserving Encryption standard FF3, reducing the running time from O(N5) to O(N17 / 6) for domain ZN× ZN. Concretely, DV{\textquoteright}s attack needs about 2 50 operations to recover encrypted 6-digit PINs, whereas ours only spends about 2 30 operations. In realizing this goal, we provide a pedagogical example of how to use distinguishing attacks to speed up slide attacks. In addition, we improve the running time of DV{\textquoteright}s known-plaintext attack on 4-round Feistel of domain ZN× ZN from O(N3) time to just O(N5 / 3) time. We also generalize our attacks to a general domain ZM× ZN, allowing one to recover encrypted SSNs using about 2 50 operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.",

keywords = "Attacks, Format-Preserving Encryption",

author = "Hoang, \{Viet Tung\} and David Miller and Ni Trieu",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2019.; 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 ; Conference date: 19-05-2019 Through 23-05-2019",

year = "2019",

doi = "10.1007/978-3-030-17656-3\_4",

language = "English (US)",

isbn = "9783030176556",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "85--116",

editor = "Vincent Rijmen and Yuval Ishai",

booktitle = "Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

}

TY - GEN

T1 - Attacks only get better

T2 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019

AU - Hoang, Viet Tung

AU - Miller, David

AU - Trieu, Ni

PY - 2019

Y1 - 2019

N2 - We improve the attack of Durak and Vaudenay (CRYPTO’17) on NIST Format-Preserving Encryption standard FF3, reducing the running time from O(N5) to O(N17 / 6) for domain ZN× ZN. Concretely, DV’s attack needs about 2 50 operations to recover encrypted 6-digit PINs, whereas ours only spends about 2 30 operations. In realizing this goal, we provide a pedagogical example of how to use distinguishing attacks to speed up slide attacks. In addition, we improve the running time of DV’s known-plaintext attack on 4-round Feistel of domain ZN× ZN from O(N3) time to just O(N5 / 3) time. We also generalize our attacks to a general domain ZM× ZN, allowing one to recover encrypted SSNs using about 2 50 operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.

AB - We improve the attack of Durak and Vaudenay (CRYPTO’17) on NIST Format-Preserving Encryption standard FF3, reducing the running time from O(N5) to O(N17 / 6) for domain ZN× ZN. Concretely, DV’s attack needs about 2 50 operations to recover encrypted 6-digit PINs, whereas ours only spends about 2 30 operations. In realizing this goal, we provide a pedagogical example of how to use distinguishing attacks to speed up slide attacks. In addition, we improve the running time of DV’s known-plaintext attack on 4-round Feistel of domain ZN× ZN from O(N3) time to just O(N5 / 3) time. We also generalize our attacks to a general domain ZM× ZN, allowing one to recover encrypted SSNs using about 2 50 operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.

KW - Attacks

KW - Format-Preserving Encryption

UR - https://www.scopus.com/pages/publications/85065887241

UR - https://www.scopus.com/pages/publications/85065887241#tab=citedBy

U2 - 10.1007/978-3-030-17656-3_4

DO - 10.1007/978-3-030-17656-3_4

M3 - Conference contribution

SN - 9783030176556

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 85

EP - 116

BT - Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Rijmen, Vincent

A2 - Ishai, Yuval

PB - Springer Verlag

Y2 - 19 May 2019 through 23 May 2019

ER -

Attacks only get better: How to break FF3 on large domains

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this