How to calculate CPA attack complexity in bits manipulation

Question

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?

Answer 1

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.