Comb to Pipeline: Fast Software Encryption Revisited

Andrey Bogdanov, Martin Mehl Lauridsen, Elmar Wolfgang Tischhauser

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

AES-NI, or Advanced Encryption Standard New Instructions, is an extension of the x86 architecture proposed by Intel in 2008. With a pipelined implementation utilizing AES-NI, parallelizable modes such as AES-CTR become extremely efficient. However, out of the four non-trivial NIST-recommended encryption modes, three are inherently sequential: CBC, CFB, and OFB. This inhibits the advantage of using AES-NI significantly. Similar observations apply to CMAC, CCM and a great deal of other modes. We address this issue by proposing the comb scheduler – a fast scheduling algorithm based on an efficient look-ahead strategy, featuring a low overhead – with which sequential modes profit from the AES-NI pipeline in real-world settings by filling it with multiple, independent messages.

We apply the comb scheduler to implementations on Haswell, Intel’s latest microarchitecture, for a wide range of modes. We observe a drastic speed-up of factor 5 for NIST’s CBC, CFB, OFB and CMAC performing around 0.88 cpb. Surprisingly, contrary to the entire body of previous performance analysis, the throughput of the authenticated encryption (AE) mode CCM gets very close to that of GCM and OCB3, with about 1.64 cpb (vs. 1.63 cpb and 1.51 cpb, resp.), despite Haswell’s heavily improved binary field multiplication. This suggests CCM as an AE mode of choice as it is NIST-recommended, does not have any weak-key issues like GCM, and is royalty-free as opposed to OCB3. Among the CAESAR contestants, the comb scheduler significantly speeds up CLOC/SILC, JAMBU, and POET, with the mostly sequential nonce-misuse resistant design of POET, performing at 2.14 cpb, becoming faster than the well-parallelizable COPA.

Finally, this paper provides the first optimized AES-NI implementations for the novel AE modes OTR, CLOC/SILC, COBRA, POET, McOE-G, and Julius.
Original languageEnglish
Title of host publicationRevised Selected Papers of the 22nd International Workshop on Fast Software Encryption (FSE 2015)
EditorsGregor Leander
PublisherSpringer
Publication date2015
Pages150-171
ISBN (Print)978-3-662-48115-8
ISBN (Electronic)978-3-662-48116-5
DOIs
Publication statusPublished - 2015
Event22nd International Workshop on Fast Software Encryption (FSE 2015) - Istanbul, Turkey
Duration: 8 Mar 201511 Mar 2015
Conference number: 22
http://www.lightsec.org/fse2015/

Workshop

Workshop22nd International Workshop on Fast Software Encryption (FSE 2015)
Number22
CountryTurkey
CityIstanbul
Period08/03/201511/03/2015
Internet address
SeriesLecture Notes in Computer Science
Volume9054
ISSN0302-9743

Keywords

  • AES-NI
  • pclmulqdq
  • Haswell
  • Authenticated encryption
  • CAESAR
  • CBC
  • OFB
  • CFB
  • CMAC
  • CCM
  • GCM
  • OCB3
  • OTR
  • CLOC
  • COBRA
  • JAMBU
  • SILC
  • McOE-G
  • COPA
  • POET
  • Julius

Cite this

Bogdanov, A., Lauridsen, M. M., & Tischhauser, E. W. (2015). Comb to Pipeline: Fast Software Encryption Revisited. In G. Leander (Ed.), Revised Selected Papers of the 22nd International Workshop on Fast Software Encryption (FSE 2015) (pp. 150-171). Springer. Lecture Notes in Computer Science, Vol.. 9054 https://doi.org/10.1007/978-3-662-48116-5_8
Bogdanov, Andrey ; Lauridsen, Martin Mehl ; Tischhauser, Elmar Wolfgang. / Comb to Pipeline: Fast Software Encryption Revisited. Revised Selected Papers of the 22nd International Workshop on Fast Software Encryption (FSE 2015). editor / Gregor Leander. Springer, 2015. pp. 150-171 (Lecture Notes in Computer Science, Vol. 9054).
@inproceedings{bc503231eca24f4b8747059b6a3c62f8,
title = "Comb to Pipeline: Fast Software Encryption Revisited",
abstract = "AES-NI, or Advanced Encryption Standard New Instructions, is an extension of the x86 architecture proposed by Intel in 2008. With a pipelined implementation utilizing AES-NI, parallelizable modes such as AES-CTR become extremely efficient. However, out of the four non-trivial NIST-recommended encryption modes, three are inherently sequential: CBC, CFB, and OFB. This inhibits the advantage of using AES-NI significantly. Similar observations apply to CMAC, CCM and a great deal of other modes. We address this issue by proposing the comb scheduler – a fast scheduling algorithm based on an efficient look-ahead strategy, featuring a low overhead – with which sequential modes profit from the AES-NI pipeline in real-world settings by filling it with multiple, independent messages.We apply the comb scheduler to implementations on Haswell, Intel’s latest microarchitecture, for a wide range of modes. We observe a drastic speed-up of factor 5 for NIST’s CBC, CFB, OFB and CMAC performing around 0.88 cpb. Surprisingly, contrary to the entire body of previous performance analysis, the throughput of the authenticated encryption (AE) mode CCM gets very close to that of GCM and OCB3, with about 1.64 cpb (vs. 1.63 cpb and 1.51 cpb, resp.), despite Haswell’s heavily improved binary field multiplication. This suggests CCM as an AE mode of choice as it is NIST-recommended, does not have any weak-key issues like GCM, and is royalty-free as opposed to OCB3. Among the CAESAR contestants, the comb scheduler significantly speeds up CLOC/SILC, JAMBU, and POET, with the mostly sequential nonce-misuse resistant design of POET, performing at 2.14 cpb, becoming faster than the well-parallelizable COPA.Finally, this paper provides the first optimized AES-NI implementations for the novel AE modes OTR, CLOC/SILC, COBRA, POET, McOE-G, and Julius.",
keywords = "AES-NI, pclmulqdq, Haswell, Authenticated encryption, CAESAR, CBC, OFB, CFB, CMAC, CCM, GCM, OCB3, OTR, CLOC, COBRA, JAMBU, SILC, McOE-G, COPA, POET, Julius",
author = "Andrey Bogdanov and Lauridsen, {Martin Mehl} and Tischhauser, {Elmar Wolfgang}",
year = "2015",
doi = "10.1007/978-3-662-48116-5_8",
language = "English",
isbn = "978-3-662-48115-8",
pages = "150--171",
editor = "Gregor Leander",
booktitle = "Revised Selected Papers of the 22nd International Workshop on Fast Software Encryption (FSE 2015)",
publisher = "Springer",

}

Bogdanov, A, Lauridsen, MM & Tischhauser, EW 2015, Comb to Pipeline: Fast Software Encryption Revisited. in G Leander (ed.), Revised Selected Papers of the 22nd International Workshop on Fast Software Encryption (FSE 2015). Springer, Lecture Notes in Computer Science, vol. 9054, pp. 150-171, 22nd International Workshop on Fast Software Encryption (FSE 2015), Istanbul, Turkey, 08/03/2015. https://doi.org/10.1007/978-3-662-48116-5_8

Comb to Pipeline: Fast Software Encryption Revisited. / Bogdanov, Andrey; Lauridsen, Martin Mehl; Tischhauser, Elmar Wolfgang.

Revised Selected Papers of the 22nd International Workshop on Fast Software Encryption (FSE 2015). ed. / Gregor Leander. Springer, 2015. p. 150-171 (Lecture Notes in Computer Science, Vol. 9054).

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - Comb to Pipeline: Fast Software Encryption Revisited

AU - Bogdanov, Andrey

AU - Lauridsen, Martin Mehl

AU - Tischhauser, Elmar Wolfgang

PY - 2015

Y1 - 2015

N2 - AES-NI, or Advanced Encryption Standard New Instructions, is an extension of the x86 architecture proposed by Intel in 2008. With a pipelined implementation utilizing AES-NI, parallelizable modes such as AES-CTR become extremely efficient. However, out of the four non-trivial NIST-recommended encryption modes, three are inherently sequential: CBC, CFB, and OFB. This inhibits the advantage of using AES-NI significantly. Similar observations apply to CMAC, CCM and a great deal of other modes. We address this issue by proposing the comb scheduler – a fast scheduling algorithm based on an efficient look-ahead strategy, featuring a low overhead – with which sequential modes profit from the AES-NI pipeline in real-world settings by filling it with multiple, independent messages.We apply the comb scheduler to implementations on Haswell, Intel’s latest microarchitecture, for a wide range of modes. We observe a drastic speed-up of factor 5 for NIST’s CBC, CFB, OFB and CMAC performing around 0.88 cpb. Surprisingly, contrary to the entire body of previous performance analysis, the throughput of the authenticated encryption (AE) mode CCM gets very close to that of GCM and OCB3, with about 1.64 cpb (vs. 1.63 cpb and 1.51 cpb, resp.), despite Haswell’s heavily improved binary field multiplication. This suggests CCM as an AE mode of choice as it is NIST-recommended, does not have any weak-key issues like GCM, and is royalty-free as opposed to OCB3. Among the CAESAR contestants, the comb scheduler significantly speeds up CLOC/SILC, JAMBU, and POET, with the mostly sequential nonce-misuse resistant design of POET, performing at 2.14 cpb, becoming faster than the well-parallelizable COPA.Finally, this paper provides the first optimized AES-NI implementations for the novel AE modes OTR, CLOC/SILC, COBRA, POET, McOE-G, and Julius.

AB - AES-NI, or Advanced Encryption Standard New Instructions, is an extension of the x86 architecture proposed by Intel in 2008. With a pipelined implementation utilizing AES-NI, parallelizable modes such as AES-CTR become extremely efficient. However, out of the four non-trivial NIST-recommended encryption modes, three are inherently sequential: CBC, CFB, and OFB. This inhibits the advantage of using AES-NI significantly. Similar observations apply to CMAC, CCM and a great deal of other modes. We address this issue by proposing the comb scheduler – a fast scheduling algorithm based on an efficient look-ahead strategy, featuring a low overhead – with which sequential modes profit from the AES-NI pipeline in real-world settings by filling it with multiple, independent messages.We apply the comb scheduler to implementations on Haswell, Intel’s latest microarchitecture, for a wide range of modes. We observe a drastic speed-up of factor 5 for NIST’s CBC, CFB, OFB and CMAC performing around 0.88 cpb. Surprisingly, contrary to the entire body of previous performance analysis, the throughput of the authenticated encryption (AE) mode CCM gets very close to that of GCM and OCB3, with about 1.64 cpb (vs. 1.63 cpb and 1.51 cpb, resp.), despite Haswell’s heavily improved binary field multiplication. This suggests CCM as an AE mode of choice as it is NIST-recommended, does not have any weak-key issues like GCM, and is royalty-free as opposed to OCB3. Among the CAESAR contestants, the comb scheduler significantly speeds up CLOC/SILC, JAMBU, and POET, with the mostly sequential nonce-misuse resistant design of POET, performing at 2.14 cpb, becoming faster than the well-parallelizable COPA.Finally, this paper provides the first optimized AES-NI implementations for the novel AE modes OTR, CLOC/SILC, COBRA, POET, McOE-G, and Julius.

KW - AES-NI

KW - pclmulqdq

KW - Haswell

KW - Authenticated encryption

KW - CAESAR

KW - CBC

KW - OFB

KW - CFB

KW - CMAC

KW - CCM

KW - GCM

KW - OCB3

KW - OTR

KW - CLOC

KW - COBRA

KW - JAMBU

KW - SILC

KW - McOE-G

KW - COPA

KW - POET

KW - Julius

U2 - 10.1007/978-3-662-48116-5_8

DO - 10.1007/978-3-662-48116-5_8

M3 - Article in proceedings

SN - 978-3-662-48115-8

SP - 150

EP - 171

BT - Revised Selected Papers of the 22nd International Workshop on Fast Software Encryption (FSE 2015)

A2 - Leander, Gregor

PB - Springer

ER -

Bogdanov A, Lauridsen MM, Tischhauser EW. Comb to Pipeline: Fast Software Encryption Revisited. In Leander G, editor, Revised Selected Papers of the 22nd International Workshop on Fast Software Encryption (FSE 2015). Springer. 2015. p. 150-171. (Lecture Notes in Computer Science, Vol. 9054). https://doi.org/10.1007/978-3-662-48116-5_8