Skip to main content

2017 | OriginalPaper | Buchkapitel

Breaking the FF3 Format-Preserving Encryption Standard over Small Domains

verfasst von : F. Betül Durak, Serge Vaudenay

Erschienen in: Advances in Cryptology – CRYPTO 2017

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The National Institute of Standards and Technology (NIST) recently published a Format-Preserving Encryption standard accepting two Feistel structure based schemes called FF1 and FF3. Particularly, FF3 is a tweakable block cipher based on an 8-round Feistel network. In CCS 2016, Bellare et al. gave an attack to break FF3 (and FF1) with time and data complexity \(O(N^5\log (N))\), which is much larger than the code book (but using many tweaks), where \(N^2\) is domain size to the Feistel network. In this work, we give a new practical total break attack to the FF3 scheme (also known as BPS scheme). Our FF3 attack requires \(O(N^{\frac{11}{6}})\) chosen plaintexts with time complexity \(O(N^{5})\). Our attack was successfully tested with \(N\leqslant 2^9\). It is a slide attack (using two tweaks) that exploits the bad domain separation of the FF3 design. Due to this weakness, we reduced the FF3 attack to an attack on 4-round Feistel network. Biryukov et al. already gave a 4-round Feistel structure attack in SAC 2015. However, it works with chosen plaintexts and ciphertexts whereas we need a known-plaintext attack. Therefore, we developed a new generic known-plaintext attack to 4-round Feistel network that reconstructs the entire tables for all round functions. It works with \(N^{\frac{3}{2}} \left( \frac{N}{2} \right) ^{\frac{1}{6}}\) known plaintexts and time complexity \(O(N^{3})\). Our 4-round attack is simple to extend to five and more rounds with complexity \(N^{(r-5)N+o(N)}\). It shows that FF1 with \(N=7\) and FF3 with \(7\leqslant N\leqslant 10\) do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our \(O(N^{5})\) attack.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
In an r-round FN, q samples give \(2q\log _2N\) bits of information but functions are defined by a table of \(rN\log _2N\) bits. Thus, \(q=\frac{r}{2}N\) queries is enough to reconstruct the round functions, in theory.
 
2
We consider here the FF3 block cipher. However, there is a mode of operation for FF3 allowing variable-length messages in the original paper [8].
 
3
Note that the cycle length notation L should not be confused with the subscript L indicating the left part of a plaintext or a ciphertext.
 
4
The probability that a given point is in a cycle of length exactly \(\mathsf {k}\) is \(\frac{(N^2-1)\cdots (N^2-k+1)}{N^2(N^2-1) \cdots (N^2-k+1)}=\frac{1}{N^2}\). Hence, the expected number of points in a cycle of length \(\mathsf {k}\) is \(1=\mathbb {E}_{\Pi }(kc_k)\).
 
5
Executions of the attack on the 4-round Feistel scheme which we used to fill our previous tables are precisely those getting the M samples in this experiment. For some rows with M too large, no experiments collected M pairwise different messages so they are not reported in the previous table. Nevertheless, our attack may still work even though we collect less than M samples. This is why they appear on Table 4.
 
6
In reaction to this attack, NIST released the following announcement:
 
Literatur
1.
Zurück zum Zitat Recommendation for Block Cipher Modes of Operation: Methods for Format Preserving Encryption. National Institute of Standards and Technology (2016) Recommendation for Block Cipher Modes of Operation: Methods for Format Preserving Encryption. National Institute of Standards and Technology (2016)
2.
Zurück zum Zitat Anderson, R., Biham, E.: Two practical and provably secure block ciphers: BEAR and LION. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 113–120. Springer, Heidelberg (1996). doi:10.1007/3-540-60865-6_48 CrossRef Anderson, R., Biham, E.: Two practical and provably secure block ciphers: BEAR and LION. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 113–120. Springer, Heidelberg (1996). doi:10.​1007/​3-540-60865-6_​48 CrossRef
3.
Zurück zum Zitat Bellare, M., Hoang, V.T., Tessaro, S.: Message-recovery attacks on Feistel-based format preserving encryption. In: 23th CCS Proceedings (2016) Bellare, M., Hoang, V.T., Tessaro, S.: Message-recovery attacks on Feistel-based format preserving encryption. In: 23th CCS Proceedings (2016)
4.
Zurück zum Zitat Bellare, M., Ristenpart, T., Rogaway, P., Stegers, T.: Format-preserving encryption. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 295–312. Springer, Heidelberg (2009). doi:10.1007/978-3-642-05445-7_19 CrossRef Bellare, M., Ristenpart, T., Rogaway, P., Stegers, T.: Format-preserving encryption. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 295–312. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-05445-7_​19 CrossRef
6.
Zurück zum Zitat Biryukov, A., Leurent, G., Perrin, L.: Cryptanalysis of Feistel networks with secret round functions. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS, vol. 9566, pp. 102–121. Springer, Cham (2016). doi:10.1007/978-3-319-31301-6_6 CrossRef Biryukov, A., Leurent, G., Perrin, L.: Cryptanalysis of Feistel networks with secret round functions. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS, vol. 9566, pp. 102–121. Springer, Cham (2016). doi:10.​1007/​978-3-319-31301-6_​6 CrossRef
10.
11.
Zurück zum Zitat Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: New attacks on Feistel structures with improved memory complexities. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 433–454. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47989-6_21 CrossRef Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: New attacks on Feistel structures with improved memory complexities. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 433–454. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47989-6_​21 CrossRef
12.
13.
Zurück zum Zitat Goldenberg, D., Hohenberger, S., Liskov, M., Schwartz, E.C., Seyalioglu, H.: On tweaking Luby-Rackoff blockciphers. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 342–356. Springer, Heidelberg (2007). doi:10.1007/978-3-540-76900-2_21 CrossRef Goldenberg, D., Hohenberger, S., Liskov, M., Schwartz, E.C., Seyalioglu, H.: On tweaking Luby-Rackoff blockciphers. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 342–356. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-76900-2_​21 CrossRef
15.
Zurück zum Zitat Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)MathSciNetCrossRefMATH Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)MathSciNetCrossRefMATH
20.
Metadaten
Titel
Breaking the FF3 Format-Preserving Encryption Standard over Small Domains
verfasst von
F. Betül Durak
Serge Vaudenay
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-63715-0_23