1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ OK, the "1.5 pass" system is more a way of indicating that GMAC / Poly1305 can be a relatively lightweight operation, we don't assume that it passes over half of the data of course, or even that GMAC takes about half of the time. Or that the same data was passed through "half of an algorithm". $\endgroup$
    – Maarten Bodewes
    Jan 9, 2023 at 15:49
  • 2
    $\begingroup$ See also Phillip Rogaway's take in crypto.stackexchange.com/questions/32702/… $\endgroup$ Jan 9, 2023 at 17:56
  • $\begingroup$ Ah,that question is specifically about 1 or 2 pass MAC (which the author probably misunderstood); the answer is about AEAD schemes. Couldn't find it when looking for a dupe. $\endgroup$
    – Maarten Bodewes
    Jan 9, 2023 at 22:05

1 Answer 1

3
$\begingroup$

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.

$\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.