What exactly is a "pass" when talking about hashing, ciphers and MAC algorithms?

Question

I was very surprised when I said that hashing the same data twice was "double pass" and a comment came in that this wasn't the case if the hashing could be performed in parallel. This would mean that calling CCM/EAX a "two pass" system or GCM a 1.5 pass system would be wrong.

I've always understood that if data is "passed through", a primitive (possibly using some mode of operation in case of a block cipher) that this counts as a "pass". Here, "passed through" would mean that the data is transformed or taken into account for a calculation (generally through an "update" function for an implementation of an algorithm).

However, there might be a difference in having to go back to the start of the algorithm, e.g. for AES-SIV, or if the operations such as MAC-then-encrypt can be performed in parallel. In the latter case I could imagine somebody arguing that you would "pass over" the data once where "pass" is read more as "traversing" over it while taking it into account.

Is there a clear definition of something being a "pass" or a common understanding of the term? If it means "pass over" do we have another term for requiring the data through two cryptographic primitives?

Answer 1

I don't know if there is a formal definition; here is the working understanding that I use:

• If the algorithm can be implemented by reading the input (plaintext) in pieces in succession (and never needing to refer to a previous piece once the next one is submitted), then this is a 'one-pass' algorithm.

Notes:

• The algorithm can have a bounded (ideally small) amount of state; the restriction of bounded implies that we cannot read the input into the state and then process it as needed

• If the algorithm generates output (e.g. it's an encryption algorithm), the output is also generated in pieces (and again, the algorithm never needs to refer to a previously generated output).

• It doesn't matter if the algorithm has several internal pieces that independently process the data; this allows GCM and MAC-and-encrypt to be implemented in a one-pass manner.

What this implies for encryption algorithms that, in a one-pass algorithm, the latter parts of the plaintext cannot affect the early parts of the ciphertext; hence any such encryption algorithm needs to be either randomized (e.g. AES-CBC) or stateful (e.g. GCM with sequential nonces). In AES-SIV, all parts of the plaintext affect all parts of the ciphertext, hence it cannot be implemented one-pass.

We define things this way not (solely) because we like defining terms, but because the distinction is useful. There are a number of reasons why we may prefer a one-pass algorithm; we may not have the entire plaintext at once (it might not fit in memory, or it is generated in pieces), or we might want to be cache-friendly.