Questions regarding parallel AES CTR with merkle trees

Question

I'm planning to implement a parallelizable variant of AES to end-to-end-encrypt files in a web application.

As a mode of operation I'm most likely gonna use CTR mode with a 64 bit IV and 64 bit counter, since that allows for easy parallelization.

Now it would also be great to be able to verify that the message wasn't manipulated, so I have to hash it somehow. However, most "normal" hash methods don't work in parallel, which is why I want to use a merkle tree.

From my understanding, it should be possible to encrypt, decrypt and verify the data completely in parallel, is that true?

In addition to that, I've seen that a lot of hashing methods (like GCM) verify the length of the ciphertext. Is that necessary with a merkle tree? I'd assume that the way such a tree builds the hash, it would be really hard to manipulate the length.

Also, should I hash the plaintext or ciphertext? and how should I encrypt the hash value?

Note: I'd like to avoid GCM, since it performs quite poorly on some devices I have to support.

Answer 1

Since it's a bad habit to answer questions in comments, I'll take my comments, and put them as an answer.

First off, you appear to be looking at designing your own homebrew method to do parallelizable MACing; don't do it. There are too many ways to get it wrong, and you don't know what to avoid.

However, since you asked specific questions, I'll try to answer them:

From my understanding, it should be possible to encrypt, decrypt and verify the data completely in parallel, is that true?

Obviously, yes, for example, with GCM. You said that GCM doesn't work for you; it still is a proof of concept that parallelization is possible.

In addition to that, I've seen that a lot of hashing methods (like GCM) verify the length of the ciphertext. Is that necessary with a merkle tree?

Maybe; GCM includes the length so that you cannot come up with two different ciphertexts/AADs that map to the same GHASH polynomial; one way an attacker could do that (if you don't include the length) is just prepend a 0 block to the ciphertext; that doesn't change the polynomial evaluation at all, no matter what the internal $H$ is.

Does your Merkle tree construction require something similar? Without knowing the details of your construction, it is literally impossible to say.

Also, should I hash the plaintext or ciphertext? and how should I encrypt the hash value?

Again, without knowing the details of your scheme, I can't really say.

---

On the other hand, if you're interested in a parallelizable authenticated encryption mode which is not GCM, you might want to consider CWC; it was designed by people who know what they're doing. It's similar to GCM internally (and actually predates it a bit), however it uses software-friendly operations internally (additions and multiplications modulo $2^{127}-1$), rather than the $GF(2^{128})$ multiplications in GCM.

That may work out better for you.