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


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
Publication date2015
ISBN (Print)978-3-662-48115-8
ISBN (Electronic)978-3-662-48116-5
Publication statusPublished - 2015
Event22nd International Workshop on Fast Software Encryption (FSE 2015) - Istanbul, Turkey
Duration: 8 Mar 201511 Mar 2015
Conference number: 22


Workshop22nd International Workshop on Fast Software Encryption (FSE 2015)
Internet address
SeriesLecture Notes in Computer Science


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


Dive into the research topics of 'Comb to Pipeline: Fast Software Encryption Revisited'. Together they form a unique fingerprint.

Cite this