Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Key-Alternating Ciphers and Key-Length Extension: Exact Bounds and Multi-user Security Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Counter-in-Tweak: Authenticated Encryption Modes for Tweakable Block Ciphers

verfasst von : Thomas Peyrin, Yannick Seurin

Erschienen in: Advances in Cryptology – CRYPTO 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We propose the Synthetic Counter-in-Tweak (\(\mathsf {SCT}\)) mode, which turns a tweakable block cipher into a nonce-based authenticated encryption scheme (with associated data). The \(\mathsf {SCT}\) mode combines in a SIV-like manner a Wegman-Carter MAC inspired from \(\mathsf {PMAC}\) for the authentication part and a new counter-like mode for the encryption part, with the unusual property that the counter is applied on the tweak input of the underlying tweakable block cipher rather than on the plaintext input. Unlike many previous authenticated encryption modes, \(\mathsf {SCT}\) enjoys provable security beyond the birthday bound (and even up to roughly \(2^n\) tweakable block cipher calls, where n is the block length, when the tweak length is sufficiently large) in the nonce-respecting scenario where nonces are never repeated. In addition, \(\mathsf {SCT}\) ensures security up to the birthday bound even when nonces are reused, in the strong nonce-misuse resistance sense (MRAE) of Rogaway and Shrimpton (EUROCRYPT 2006). To the best of our knowledge, this is the first authenticated encryption mode that provides at the same time close-to-optimal security in the nonce-respecting scenario and birthday-bound security for the nonce-misuse scenario. While two passes are necessary to achieve MRAE-security, our mode enjoys a number of desirable features: it is simple, parallelizable, it requires the encryption direction only, it is particularly efficient for small messages compared to other nonce-misuse resistant schemes (no precomputation is required) and it allows incremental update of associated data.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Key-Alternating Ciphers and Key-Length Extension: Exact Bounds and Multi-user Security
Nächstes Kapitel XPX: Generalized Tweakable Even-Mansour with Improved Security Guarantees
Fußnoten
1
Similarly, the high-entropy requirement on the IV is hard to meet when no good randomness source is available.
 
2
The \(\mathsf {SCT}\) mode uses 5 tweak prefixes to separate the different usages of the TBC. The “effective” tweak length is what remains once 3 bits have been used to encode the prefix.
 
3
While \(\mathsf {SIV}\) corresponds to generic composition method A4 in the nomenclature of Namprempre et al. [46], \(\mathsf {NSIV}\) does not fit any of the NRS schemes.
 
4
This excludes for example a simple \(\mathsf {OCB}\)-like encryption mode since it is only nonce-based, not IV-based.
 
5
Similarly, the only reason why \(\mathsf {OCB}\) is secure up to the birthday bound whereas \(\mathsf {\Theta CB}\) is “perfectly” secure is because it relies on \(\mathsf {XE}\)/\(\mathsf {XEX}\) for instantiating the TBC.
 
6
The tweak prefixes used in this paper were chosen for ease of exposition and are slightly different from the ones used in \(\textsf {Deoxys}\) and \(\textsf {Joltik}\) v1.3, which were chosen mainly for efficiency reasons.
 
7
For example, for TBCs following the TWEAKEY approach [30, 31, 33], there is a large gap in the number of rounds needed to make the TBC secure as the tweak length increases.
 
8
E.g., an nPRF-secure function F might depend only on the nonce, in which case it is trivial to forge and break nMAC-security, while an nMAC-secure function F might have all its outputs starting with a 0 bit, which allows to trivially break nPRF-security.
 
9
We assume that \(\mathsf {Rand}\) returns the same output if a query is repeated.
 
10
The \(\mathsf {CTRT}\) mode does not need tweak separation per se. We use a single 1 prefix in order to conveniently combine \(\mathsf {CTRT}\) with \(\mathsf {EPWC}\) later.
 
11
Note that in that case the size of the tweak space \(\mathcal {T}\) only impacts the maximal message length \(\ell \), not the security bound.
 
12
The successor of the tweak T is \(\mathsf {Inc}(T)\).
 
13
Note that the adversary must commit to the length \(\ell _i\) of the chain before knowing the initial bin \(IV_i\) since it first makes the query \((N_i,M_i)\) and only then receives the answer \((IV_i,C_i)\).
 
14
We use a set of prefixes which is disjoint from the set used for the \(\mathsf {CTRT}\) mode in order to later combine the two modes smoothly.
 
15
When constructing an AE scheme, it is more convenient to directly define a vector-input MAC, rather than a string-input MAC that must later be transformed to handle vectors of strings, as required for an AE scheme.
 
16
Our formalization of an nAE scheme in Definition 4 assumes that the ciphertext is a binary string, whereas in our description, \(\mathsf {NSIV}[F,\varPi ].\mathsf {Enc}\) returns a pair \((C,\mathsf {tag})\). We assume some implicit encoding of this pair into a single binary string.
 
17
In more details, it is more convenient to prove Theorem 5 by first replacing \(\widetilde{E}_K\) by a uniformly random tweakable permutation, and then applying Theorems 1, 2, and 3 for a perfect TBC.
 
18
Note that this regularity condition imposes \(|\mathcal {T}|\le |\mathcal {X}|\). However, when \(\mathcal {T}|>|\mathcal {X}|\), the security bounds of \(\mathsf {CTRT}\) and \(\mathsf {EPWC}\) do not depend on the tweak length (only the maximal message length does). Hence, one can always use a subset of tweaks of size \(|\mathcal {X}|\) in case \(|\mathcal {T}|>|\mathcal {X}|\).
 
Literatur
1.
2.
Abed, F., Fluhrer, S., Forler, C., List, E., Lucks, S., McGrew, D., Wenzel, J.: Pipelineable on-line encryption. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 205–223. Springer, Heidelberg (2015)
3.
AlFardan, N.J., Paterson, K.G., Lucky thirteen: breaking the TLS and DTLS record protocols. In: Security and Privacy - SP 2013, pp. 526–540 (2013)
4.
Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B., Mouha, N., Yasuda, K.: How to securely release unverified plaintext in authenticated encryption. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 105–125. Springer, Heidelberg (2014)
5.
Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B., Tischhauser, E., Yasuda, K.: Parallelizable and authenticated online ciphers. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 424–443. Springer, Heidelberg (2013)CrossRef
6.
Asharov, G., Naor, M., Segev, G., Shahaf, I., Encryption, S.S.: Optimal locality in linear space via two-dimensional balanced allocations. IACR Cryptology ePrint Archive, Report 2016/251 (2016). To appear at STOC 2016
7.
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: FOCS 1997, pp. 394–403 (1997)
8.
Bellare, M., Impagliazzo, R.: A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. IACR Cryptology ePrint Archive, Report 1999/024 (1999)
9.
Bellare, M., Kilian, J., Rogaway, P.: The security of the cipher block chaining message authentication code. J. Comput. Syst. Sci. 61(3), 362–399 (2000)MathSciNetCrossRefMATH
10.
Bellare, M., Namprempre, C.: Authenticated encryption: relations among notions and analysis of the generic composition paradigm. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 531–545. Springer, Heidelberg (2000)CrossRef
11.
Bellare, M., Rogaway, P.: Encode-then-encipher encryption: how to exploit nonces or redundancy in plaintexts for efficient cryptography. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 317–330. Springer, Heidelberg (2000)CrossRef
12.
Bellare, M., Rogaway, P., Wagner, D.: The EAX mode of operation. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 389–407. Springer, Heidelberg (2004)CrossRef
13.
Black, J.A., Rogaway, P.: A block-cipher mode of operation for parallelizable message authentication. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 384–397. Springer, Heidelberg (2002)CrossRef
14.
Brassard, G.: On computationally secure authentication tags requiring short secret shared keys. In: CRYPTO 1982, pp. 79–86 (1982)
15.
Chen, S., Steinberger, J.: Tight security bounds for key-alternating ciphers. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 327–350. Springer, Heidelberg (2014)CrossRef
16.
Cogliati, B., Lampe, R., Patarin, J.: The indistinguishability of the XOR of \(k\) permutations. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 285–302. Springer, Heidelberg (2014)
17.
Dodis, Y., Steinberger, J.: Domain extension for MACs beyond the birthday barrier. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 323–342. Springer, Heidelberg (2011)CrossRef
18.
19.
20.
Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: The Skein hash function family. SHA3 Submission to NIST (Round 3) (2010)
21.
Fleischmann, E., Forler, C., Lucks, S.: McOE: a family of almost foolproof on-line authenticated encryption schemes. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 196–215. Springer, Heidelberg (2012)CrossRef
22.
Gligor, V.D., Donescu, P.: Fast encryption and authentication: XCBC encryption and XECB authentication modes. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, p. 92. Springer, Heidelberg (2002)CrossRef
23.
24.
Grosso, V., Leurent, G., Standaert, F.-X., Varici, K., Durvaux, F., Gaspar, L., Kerckhof, S.: SCREAM and iSCREAM. Submitted to CAESAR (2014)
25.
Gueron, S., Lindell, Y.: GCM-SIV: full nonce misuse-resistant authenticated encryption atunder one cycle per byte. In: ACM CCS 2015, pp. 109–119 (2015)
26.
Hoang, V.T., Krovetz, T., Rogaway, P.: Robust authenticated-encryption AEZ and the problem that it solves. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 15–44. Springer, Heidelberg (2015)
27.
Hoang, V.T., Reyhanitabar, R., Rogaway, P., Vizár, D.: Online authenticated-encryption and its nonce-reuse misuse-resistance. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 493–517. Springer, Heidelberg (2015)CrossRef
28.
Iwata, T.: New blockcipher modes of operation with beyond the birthday bound security. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 310–327. Springer, Heidelberg (2006)CrossRef
29.
Iwata, T.: Authenticated encryption mode for beyond the birthday bound security. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 125–142. Springer, Heidelberg (2008)CrossRef
30.
Jean, J., Nikolic, I., Peyrin, T.: Deoxys v1. Submitted to the CAESAR competition (2014)
31.
Jean, J., Nikolic, I., Peyrin, T.: Joltik v1. Submitted to the CAESAR competition (2014)
32.
Jean, J., Nikolic, I., Peyrin, T.: KIASU v1. Submitted to the CAESAR competition (2014)
33.
Jean, J., Nikolic, I., Peyrin, T.: Tweaks and keys for blockciphers: the TWEAKEY framework. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 274–288. Springer, Heidelberg (2014)
34.
Jutla, C.S.: Encryption modes with almost free message integrity. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 529–544. Springer, Heidelberg (2001)CrossRef
35.
Jutla, C.S.: Encryption modes with almost free message integrity. J. Cryptol. 21(4), 547–578 (2008). Earlier version at EUROCRYPT 2001MathSciNetCrossRefMATH
36.
Katz, J., Yung, M.: Characterization of security notions for probabilistic private-key encryption. J. Cryptol. 19(1), 67–95 (2006)MathSciNetCrossRefMATH
37.
Krawczyk, H.: The order of encryption and authentication for protecting communications (or: how secure is SSL?). In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 310–331. Springer, Heidelberg (2001)CrossRef
38.
Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 306–327. Springer, Heidelberg (2011)CrossRef
39.
Lampe, R., Seurin, Y.: Tweakable blockciphers with asymptotically optimal security. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 133–152. Springer, Heidelberg (2014)
40.
Landecker, W., Shrimpton, T., Terashima, R.S.: Tweakable blockciphers with beyond birthday-bound security. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 14–30. Springer, Heidelberg (2012)CrossRef
41.
Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 31–46. Springer, Heidelberg (2002)CrossRef
42.
Lucks, S.: The sum of PRPs is a secure PRF. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 470–484. Springer, Heidelberg (2000)CrossRef
43.
McGrew, D.A., Viega, J.: The security and performance of the Galois/counter mode (GCM) of operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 343–355. Springer, Heidelberg (2004)CrossRef
44.
Mennink, B.: Optimally secure tweakable blockciphers. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 428–448. Springer, Heidelberg (2015)CrossRef
45.
Minematsu, K.: Beyond-birthday-bound security based on tweakable block cipher. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 308–326. Springer, Heidelberg (2009)CrossRef
46.
Namprempre, C., Rogaway, P., Shrimpton, T.: Reconsidering generic composition. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 257–274. Springer, Heidelberg (2014)CrossRef
47.
Patarin, J.: A proof of security in \(O(2^n)\) for the Xor of two random permutations. In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 232–248. Springer, Heidelberg (2008)CrossRef
48.
Patarin, J.: The “Coefficients H” technique. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 328–345. Springer, Heidelberg (2009)CrossRef
49.
Patarin, J.: Security in \(O(2^n)\) for the Xor of two random permutations: proof with the standard \(H\) technique. IACR Cryptology ePrint Archive, Report 2013/368 (2013)
50.
51.
Rogaway, P.: Authenticated-encryption with associated-data. In: ACM CCS 2002, pp. 98–107 (2002)
52.
Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 16–31. Springer, Heidelberg (2004)CrossRef
53.
Rogaway, P.: Nonce-based symmetric encryption. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 348–359. Springer, Heidelberg (2004)CrossRef
54.
Rogaway, P., Bellare, M., Black, J.: OCB: a block-cipher mode of operation for efficient authenticated encryption. ACM Trans. Inf. Syst. Secur. 6(3), 365–403 (2003)CrossRef
55.
Rogaway, P., Shrimpton, T.: A provable-security treatment of the key-wrap problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 373–390. Springer, Heidelberg (2006)CrossRef
56.
Shoup, V.: On fast and provably secure message authentication based on universal hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 313–328. Springer, Heidelberg (1996)
57.
Shoup, V.: Sequences of games: a tool for taming complexity in security proofs. IACR Cryptology ePrint Archive, Report 2004/332 (2004)
58.
Shrimpton, T., Terashima, R.S.: A modular framework for building variable-input-length tweakable ciphers. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 405–423. Springer, Heidelberg (2013)CrossRef
59.
Vaudenay, S.: Security flaws induced by CBC padding - applications to SSL, IPSEC, WTLS \(..\). In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 534–546. Springer, Heidelberg (2002)CrossRef
60.
Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265–279 (1981)MathSciNetCrossRefMATH
61.
62.
Yasuda, K.: A new variant of PMAC: beyond the birthday bound. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 596–609. Springer, Heidelberg (2011)CrossRef
Metadaten
Titel
Counter-in-Tweak: Authenticated Encryption Modes for Tweakable Block Ciphers
verfasst von
Thomas Peyrin
Yannick Seurin
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – CRYPTO 2016

Print ISBN: 978-3-662-53017-7

Electronic ISBN: 978-3-662-53018-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53018-4_2