0
$\begingroup$

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.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ IMHO, if you have to ask these questions, you're not qualified to design your own mode for real use... $\endgroup$ – poncho Jul 28 '16 at 11:30
  • $\begingroup$ @poncho I'm not designing a mode of operation, because I know it's really easy to make mistakes in doing that. I just want to know, how parallel verification would be possible when using AES-CTR. I'd actually be perfectly happy if anybody could name an "accepted" verification method that can work in parallel. $\endgroup$ – Dodekeract Jul 28 '16 at 11:32
  • 2
    $\begingroup$ Well, if you like GCM except that it's inconvienent to work in $GF(2^{128})$, you might consider CWC csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/cwc/… ; that's similar to GCM (and can be parallelized just as well), but it works modulo $2^{127}-1$; that might be a bit easier for you $\endgroup$ – poncho Jul 28 '16 at 11:37
  • 1
    $\begingroup$ also see "Is (AES-)GCM parallelizable?" $\endgroup$ – SEJPM♦ Jul 28 '16 at 11:46
  • $\begingroup$ The real-world need for CTR is to range request out of ciphertext. Authentication of partial ciphertext is the real need, with parallel authentication of the whole thing being just a minor optimization. $\endgroup$ – Rob Jul 28 '16 at 12:19
1
$\begingroup$

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.

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