Is there any way to parallelize AES running in CBC mode? (The plan is to parallelize it using OpenMP)
$\begingroup$
$\endgroup$
1
-
$\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 ♦Commented May 31, 2015 at 19:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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 ♦Commented May 31, 2015 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$– ponchoCommented May 31, 2015 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 ♦Commented May 31, 2015 at 19:06
-
$\begingroup$ Though - decryption of the CBC mode can be parallelized :) $\endgroup$– gusto2Commented Dec 23, 2017 at 12:10