1
$\begingroup$

I am having trouble understanding where the count of "passes" come in. What constitutes a pass in the context of message authentication codes? How are single-pass MACs achieved?

$\endgroup$
  • 3
    $\begingroup$ Presumably, the number of "passes" is the number of times the algorithm scans the message being authenticated. However, I don't recall hearing of a MAC that can't be implemented in a single pass... $\endgroup$ – poncho Feb 13 '16 at 4:14
  • $\begingroup$ Sounds similar to "rounds" when talking about encryption or hash functions. Don't quote me on this though $\endgroup$ – Daffy Feb 13 '16 at 4:20
  • 2
    $\begingroup$ Could you point to where you ran into a mention of "MAC passes"? Are you sure it wasn't the distinction between encrypt+MAC in single pass vs. a separate MAC pass? $\endgroup$ – otus Feb 13 '16 at 6:53
  • $\begingroup$ Yeah, I think this is about authenticated ciphers rather than single MAC calculations. Those are single pass, "1.5 pass" or double pass. $\endgroup$ – Maarten Bodewes Feb 14 '16 at 2:18
3
$\begingroup$

I suspect the questioner is asking not about MAC's per say, but rather Authenticated Encryption (AE, and if there is additional data, AEAD). I've been wondering this myself, so I asked Phillip Rogaway of UC Davis, who is one of the creators of EAX - a "two pass" "online" operation mode for block ciphers that - since it provides AE (confidentiality and integrity in the same process) does not need a MAC.

His response is really quite helpful - so (with his permission) I'm quoting it here:

There's no standard and rigorous definition of "one pass" vs. "two pass" for AE / AEAD schemes. Focusing only on encryption and the processing of plaintext, people mean either of two things by the terms “one pass” and “two pass”:

  1. “One pass” (or “online”) could mean that the algorithm is constructed so that you can process an arbitrary length plaintext, left-to-right, spitting out the corresponding bits of ciphertext, again left to right, as you go, while you use only constant memory. In this sense, EAX is one-pass. This notion is easy to make rigorous. “Two pass” would then be interpreted to mean that you can make due with two constant-memory left-to-right passes through the plaintext, but not one. And so on.

  2. Alternatively, “two pass” might mean that, when a human being looks at the description of the mode, there is one logical part of the design, this comprising a significant portion of the computational cost, that is clearly designed for privacy; and there is another logical part of the design, again a significant portion of the computational cost, intended for authenticity. One pass would mean that you can’t partition things up like this: that the privacy and authenticity are more tightly interwoven (often with an “authentication tag” being computed cheaply as a byproduct of whatever else is going on for privacy). I don’t know any way to make this concept rigorous, but I think it’s the more traditional use. Under this (informal) notion, EAX is two-pass, despite it being online. To help separate these uses, and stop calling something “two pass” when it could easily be implemented so as to be online, my paper with Krovetz on OCB3 introduced, for sense (2), “integrated” and “composed” instead of “one pass” and “two pass”. I don’t think these terms caught on ;-)

And for the curious, the papers he refers to is (I think) The Software Performance of Authenticated-Encryption Modes

I found (after getting his answer) his FAQ quite helpful - especially this answer.

$\endgroup$

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.