# Interleaved CBC

I've been researching cryptographic modes and came across an obscure mode called interleaved CBC (ICBC). I can't find a lot about it and am wondering if anyone knows anything more.

It's basically CBC but where instead of chaining the last block you chain the n-mth block where m is some constant. This allows some amount of parallelization. For example if m is 8 you can do 8 blocks at a time. For message indistinguishability you'd also need an IV as wide as the block cipher times m, which could probably be expanded from a shorter IV.

Anyone know what this is? I suppose it would be considered obsolete but it would perhaps have some desirable properties in certain applications.

Edit: as near as I can tell this would be identical security-wise to splitting the message into m smaller messages and encrypting each with CBC. The fact that the message is split by being "striped" rather than split into chunks seems irrelevant. Does this basically just reduce to CBC (assuming the IV is unique per stripe)?

Also this would have to be authenticated of course to prevent padding oracle attacks.

• The statement "chain the n-m^{th} block" is vague. Please explain with a mathematical equation. – kodlu Feb 12 '20 at 4:02
• So, is your question whether this mode is (CPA) secure? Or is it how this mode compares to more standard (CPA-secure) modes? Or something else? – SEJPM Feb 12 '20 at 8:52
• I guess you could encrypt the initial IV followed by n-1 zero valued plaintext blocks using normal CBC over zero-valued plaintext blocks (and a zero value IV). Then you'd just need to transmit a 16 byte IV again. Pretty sure, but asked here just to be certain - and it was not secure (big 'd-oh from my side) but another scheme was proposed by fgrieu. – Maarten Bodewes Feb 12 '20 at 14:29

Although it does offer some parallel processing, I must say that there are some issues on how it handles it. Generally, if you would perform multi-threading, you would use a divide and conquer method that simply would cut the plaintext in chunks and have the other processor handle it. This method requires a stream of blocks of a specific size - the block size. Worse, it requires the same procedure when putting the stuff together.

If you use $$s$$ streams and you have $$x$$ processors that perform the encryption service where $$x \not= s$$ then it will be relatively tricky to divide the streams among the services. Generally devs try to give a relatively large amount of blocks to a block cipher implementation to avoid latency issues. If you do that then you will have to concatenate the blocks together only to split them up again. If one of the streams slows down then you may have to buffer many small blocks.

I'm not saying that these kind of problems cannot be solved, but it does require quite a lot of work from the developer to process everything efficiently.

Now compare this with CTR. You provide a processor a nice big chunk of plaintext with the nonce & counter for the chunk and you leave it up to the encryption service to return it as soon as possible. The ciphertext can be send back with the counter value, and you can just put it into a thread safe prio-map until it is required (or you run out of buffer space, of course). You can make the chunks as large as you want, and split the procedure over as many services as you want. Flexibility at every step, and only limited splitting / concatenation necessary.

Only a small nonce is necessary, not a huge IV (although there are tricks around the latter).

Basically, as long as you can avoid problems with the nonce repeating, CTR would be vastly preferable to this scheme when it comes to parallel processing (and most other properties as well, such as better skipping properties for large ciphertext).

• The main sort of parallelism of interest in most applications today that deal with small messages (not disk encryption which has its own modes) is instruction level parallelism. A lot of modern CPUs can do 2-4 AES operations at once if the instructions are interleaved. This would allow that with CBC. CTR allows that too of course. Simple linear CBC does not, at least for encryption. You're right that for SMP parallelization you'd be better to chunk the input, and you're right that CTR is more flexible. – Adam Ierymenko Feb 12 '20 at 17:25
• One advantage of CBC is that IV re-use is not catastrophic. Duplicate IVs can reveal coarse message structure or message duplication but do not reveal plaintext. CTR and all other XOR-with-a-PRNG-output stream modes fail catastrophically on IV/nonce reuse. – Adam Ierymenko Feb 12 '20 at 17:30
• You are correct, but I already made that point in the last section. – Maarten Bodewes Feb 12 '20 at 17:39

I have never met interleaved CBC in actual use, but I can imagine it was used for VPNs and the like. Yes it is obsolete, since it does not provide authenticated encryption, and is inferior to CTR in most respects (in particular, CTR easily parallelize and requires no padding).

Yes, if the IVs in all stripes are independent, security w.r.t. the goal of data confidentiality follows from that of CBC, with the cavetat that the limitation to the amount of data enciphered without key renewal applies to all the stripes combined; for probability $$\epsilon=1/2^s$$ that a $$b$$-bit block occurs twice in the ciphertext, we should change the key before $$2^{(b-s+1)/2}\,b$$ bits.

Since CBC does not provide good security w.r.t. the goal of data integrity, it is not worth discussing how these properties translate.

• All modes need authentication to be secure in a modern system, CBC and CTR included. GCM is CTR combined with GMAC authentication. CBC has gotten a bad rap security-wise because of older implementations with nonexistent, poor, or broken authentication. If one used CBC (interleaved or not) you'd have to pair it with CMAC, GMAC, HMAC, Poly1305, etc. You are correct that CTR is more flexible in terms of parallelization which is another reason it's become so popular. – Adam Ierymenko Feb 12 '20 at 17:27