# How to calculate CPA attack complexity in bits manipulation

The following Forward Errors Correcting FEC is used in our daily devices. But I added a potential security measure.

In one of FEC systems the input is $$K$$ bits and the output code is $$M$$ bits where $$M=3K$$. The legitimate user at the other end uses FEC decoder to get the correct $$K$$ bits.

The proposed security is that if only $$N$$ out of $$M$$ bits are selected for transmission in the same order of $$M$$ in a way the receiver still can decode successfully. The number of $$N$$ bits and there positions in $$M$$ are generated by pseudorandom number generator with nonlinear structure driven by a key that changes every block of $$K$$.

The FEC decoder is able to decode only if $$N$$ and the positions are known so the unselected positions at the sender are filled by $$M-N$$ bit $$0$$ before decoding. The attacker does not know the key so $$N$$ so he won't know $$M$$ and $$K$$. In this system $$K>500$$ bits and the length of PRNG $$n=100$$.

How we calculate the number of CPA attack possibilities here?

The answer would depend on the entropy of the set of bits $$M$$. Let's say $$M$$ is a set of all-zero bits; in that case there would be only $$1$$ possible set of bits you could choose - every bit in every position is zero. If, however, you had a random set of bits for $$M$$ you'd approach ideal security; ideal security meaning $$m\, P\, (n-(n/2))$$ possible keys to brute-force.

How we calculate ideal security:

We know why we use the permutation function, but why use $$n-(n/2)$$? Let's imagine we have a random set of bytes, each unique; we have less than 256 bytes in our set so we can avoid repeats. The possible unique states would become $$\infty$$ meaning $$m\, P\, (n-(n/\infty))=m\, P\, n$$. But if we get each byte twice we end up with half the possible unique sets of choices - for every byte I select I could just as well select another byte and get the same result. As such, for $$n$$ bits the repeats will be defined by $$n / 2$$ since there are $$2$$ unique possible states for each bit. For sets of bytes it would be defined by $$n/256$$ meaning the complexity would me $$m\, P\, (n-(n/256))$$. This is because the frequency of repeats is based on the number of possible non-repeating states.

Therefore, if you want the scheme to be secure you should make $$M$$ as random as possible. A nonrandom value $$M$$, or a value specifically chosen to be weak would cripple the entire system; if $$M$$ is all-zeroes that's effectively a base-1 system which means each (bit-like-thing-with-only-one-state) has only $$1$$ possible state, giving me $$m\, P\, (n-(n/1))=m\, P\, 0=1$$ possible key.

### CPA attack possibilities:

If the attacker can find the value $$N$$ for 1 block, they now know the position of $$n$$ bits within $$M$$. If they repeat this for multiple blocks, they will eventually get enough bits to brute-force the rest; so the difficulty of a CPA comes down to whether the value $$N$$ can be figured out from the plaintext-ciphertext relationship, which is dependent on the specifics of your FEC. This applies in the same way to known-plaintext attacks. Thus, your system would be secure from chosen-plaintext attacks iff (if and only if) it is secure against known-plaintext attacks.

### Update:

I noticed an error where I forget to account for the fact that the repeating bits can themselves be permutated. This lowers the number of possible states significantly. I have updated the formulas accordingly, and the information should be correct now.

• I corrected an error in my math. Please see the updated answer. Sep 6 '20 at 20:54
• No need for over-extensive apologies here ("my apologies" already sounds better than "I'm sorry" in general). Hint for better reception of the answer: help the question along by upvoting and / or by editing it so it is easier to read. The better the visibility of the question, the better the visibility of the answer. Sep 7 '20 at 13:30
• thanks @Serpent27, I am quite sure that chosen-plaintext attack is related to the Pseudo random generator and the cipher-text attack is related to number of possible selection as you detailed. But it is not obvious how to calculate CPA possibilities. Sep 7 '20 at 22:04
• what is $P(\cdot)$? Sep 7 '20 at 22:17
• $m\, P\, n$ is the permutation function of $m$ choices, selecting $n$ elements. Sep 7 '20 at 22:43