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

Maarten Bodewes

1/9/24, 3:39 PM

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?

117

1 + 3

block-cipher

algorithm-design

performance

Maarten Bodewes

1/9/24, 3:49 PM

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".

Gilles 'SO- stop being evil'

1/9/24, 5:56 PM

See also Phillip Rogaway's take in https://crypto.stackexchange.com/questions/32702/difference-between-single-pass-and-two-pass-macs/35244#35244

Maarten Bodewes

1/9/24, 10:05 PM

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.

Score:3

Crypto

poncho

1/9/24, 4:48 PM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.