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?


1 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.


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.

  • $\begingroup$ I corrected an error in my math. Please see the updated answer. $\endgroup$
    – Serpent27
    Commented Sep 6, 2020 at 20:54
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Commented Sep 7, 2020 at 13:30
  • $\begingroup$ 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. $\endgroup$
    – Riva11
    Commented Sep 7, 2020 at 22:04
  • $\begingroup$ what is $P(\cdot)$? $\endgroup$
    – kodlu
    Commented Sep 7, 2020 at 22:17
  • $\begingroup$ $m\, P\, n$ is the permutation function of $m$ choices, selecting $n$ elements. $\endgroup$
    – Serpent27
    Commented Sep 7, 2020 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.