1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ "[Keyak] seems to be slow in the absence of hardware acceleration." Could you provide some sources about this ? $\endgroup$
    – Biv
    Feb 22, 2016 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$ Feb 22, 2016 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, 2016 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$ Feb 23, 2016 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$ Feb 23, 2016 at 1:16

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
5
  • $\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, 2016 at 13:52
  • $\begingroup$ Does your implementation use AVX and AVX2? $\endgroup$
    – Demi
    Feb 26, 2016 at 15:31
  • $\begingroup$ @Demetri It uses AVX2 indeed. $\endgroup$
    – gvanas
    Feb 26, 2016 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, 2016 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, 2016 at 21:15
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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