Why can't NORX produce intermediate auth tags like Keyak can? Keyak appears quite attractive because of this, but seems to be slow in the absence of hardware acceleration.

  • $\begingroup$ "[Keyak] seems to be slow in the absence of hardware acceleration." Could you provide some sources about this ? $\endgroup$ – Biv Feb 22 '16 at 12:53
  • $\begingroup$ @Biv Keyak is based on the Kekkak-F permutation, which is known to be slow in software compared to ARX primitives. However, the new version of Keyak allows full state sponge use to speed it up for associated data. The last benchmark I saw was of the original Keyak, and it was not very fast in software $\endgroup$ – Richie Frame Feb 22 '16 at 22:09
  • $\begingroup$ Well, I heard that Keyak was twice faster than Keccak due to the number of rounds divided by two and a bigger absorption rate (as you mentioned the use of the full state). So a comparison benchmark would be welcomed. ;) $\endgroup$ – Biv Feb 22 '16 at 23:30
  • $\begingroup$ @Biv Keyak does use lower rounds and a higher rate, since it is not subject to the security requirements of a hash algorithm, however the same is true with NORX, which only uses 4 rounds by default, with a very fast permutation at its core that is very friendly to vectorization on modern CPUs. $\endgroup$ – Richie Frame Feb 23 '16 at 0:50
  • $\begingroup$ @Biv NORX gets 3.37 cpb in Ivy Bridge and 2.51 cpb on Haswell: 131002.net/data/talks/norx-31c3.html#50.0 $\endgroup$ – Richie Frame Feb 23 '16 at 1:16

The NORX documentation does not specify how to use it for intermediate tags, but I agree with Richie Frame that it could easily support them. Using intermediate tags in sponge-based authenticated encryption was considered by Bertoni et al., SAC 2011, see Section 2.1. Since NORX's mode of operation is derived from the same construction, I see no obvious obstacle.

Note that, on the other hand, Keyak explicitly specifies the concept of a session with intermediate tags, its implementation readily supports them and its security analysis takes them into account.

About the second part of your question, i.e., that Keyak "seems to be slow in the absence of hardware acceleration", there is no objective reason to believe so, since Keyak with its 12 rounds and full-state absorbing should be at least twice faster than SHAKE128. For instance, our current benchmarks confirm the comment of Biv, as Ocean Keyak takes about 1.8 cycles/byte on Haswell on a single core.

Disclaimer: I am one of the co-designers of Keyak.

  • $\begingroup$ You say "our current benchmarks". Does that mean you are one of the people behind Keyak? In that case it would be good form to disclose it in your answer. $\endgroup$ – otus Feb 26 '16 at 13:52
  • $\begingroup$ Does your implementation use AVX and AVX2? $\endgroup$ – Demi Feb 26 '16 at 15:31
  • $\begingroup$ @Demetri It uses AVX2 indeed. $\endgroup$ – gvanas Feb 26 '16 at 15:58
  • $\begingroup$ How does Keyak's performance compare to chacha20-poly1305 in software on a Haswell chip (or something comparable)? $\endgroup$ – cooky451 Apr 21 '16 at 12:19
  • $\begingroup$ @cooky451 I do not know about the performance of Chacha20-Poly1305. However, you can benchmark Keyak with the KCP: do make Haswell/KeccakTests then bin/Haswell/KeccakTests --speed and look for Ocean Keyak. $\endgroup$ – gvanas Apr 23 '16 at 21:15

It can.

However the specification makes no effort to add or describe such a feature, but the mode over the permutation can do this easily with minor modification. New domain separation constants and a fixed method of generating the tags are generally all that is required on the encryption side, decryption is more complex and may require special output formatting during encryption for it to work in a seamless way.

This would however add more complexity to the description as well as to implementations. If the designers had considered intermediate tags, they probably rejected it for simplicity. It is certainly possible that intermediate tags were not considered in the design process, as many of the other candidates also do not have this feature.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.