Is there any way to parallelize AES running in CBC mode? (The plan is to parallelize it using OpenMP)

  • $\begingroup$ Usually CTR mode is used if AES requires parallelization. It's very easy to parallize CTR, especially because you can split the ciphertext anywhere you want (preferably on block size boundaries of course). $\endgroup$
    – Maarten Bodewes
    May 31 '15 at 19:11

Normal CBC mode cannot be parallelized during encryption; that's because CBC mode encryption is defined as:

$$C_i = E_k(C_{i-1} + P_i)$$

That is, what you encrypt during the processing of block $i$ depends on ciphertext of block $i-1$; hence you can't start the next block until you've completed processing of the previous block. You can't do any parallelization, except for that parallelization that's inherent within AES.

On the other hand, CBC mode in decryption can be parallelized, and it's fairly straightforward.

In addition, there is a variant of CBC mode where you don't xor in the immediately previous ciphertext block, you xor in one $n$ blocks ago, as in:

$$C_i = E_k( C_{i-n} + P_i )$$

This is effectively running $n$ different CBC mode encryptions in parallel; this can be paralleized $n$ ways.

  • $\begingroup$ I quickly tried to google this variant but I could not find any reference. Do you maybe have one? This one (for your entertainment only) is not it :) $\endgroup$
    – Maarten Bodewes
    May 31 '15 at 17:15
  • $\begingroup$ Best I could find is books.google.com/… It's mentioned in some ISO standards, but I can't give a pointer to those. $\endgroup$
    – poncho
    May 31 '15 at 18:01
  • 1
    $\begingroup$ Both papers call this ICBC for Interleaved CBC. Although the Indian paper is terribly badly written, they use it on RSA. The paper from Mauritania seems a lot better. It does seem indeed that it requires an IV of $n$ blocks, which was what I was looking up. It may be a good idea to pair it with a KDF expand over the IV to generate enough IV material (or a similar scheme, possibly AES-CBC encrypt over the IV value followed by bits set to zero) if you want to minimize the IV bytes send. $\endgroup$
    – Maarten Bodewes
    May 31 '15 at 19:06
  • $\begingroup$ Though - decryption of the CBC mode can be parallelized :) $\endgroup$
    – gusto2
    Dec 23 '17 at 12:10

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.