# Security of stream cipher based on Matrix multiplication GF(256) with randomized padding

The actual question is stated at the end of the text. Suppose you have a (grossly inefficient) confidentiality stream cipher with the following components:

1. The keyed function $F_k:\{0,1\}^{8n}\mapsto\{0,1\}^{16n}$ based on vectors with randomized padding multiplied with a key dependent matrix as described in a previous question. Let $E_k$ be the $2n\times 2n$ encoding matrix and $D_k$ be the $n\times 2n$ decoding matrix.
2. A permutation $Perm_0:\{0,1\}^{8n}\mapsto\{0,1\}^{8n}$.
3. A permutation $Perm_1:\{0,1\}^{16n}\mapsto\{0,1\}^{16n}$.
4. A function $Stretch:\{0,1\}^{8n}\mapsto\{0,1\}^*$.

Divide the (padded) input plain text $PT$ into $p$ blocks each $8n$ bits long. Insert a random $8n$ bit block after every $n-1$ block.

1. Generate $16n$ bits random $IV$ and set $ct_0=IV$.
2. for each $i$ from 1 to $p + \lfloor{p/(n-1)}\rfloor$:

a. if $i\mod8=0$,

i. Use $Stretch(pt_i)$ for generating an invertible $2n\times2n$ matrix A.

ii. Let $E_k = E_kA$.

b. Let $h_i = Perm_1(ct_{i-1})$.

c. Let $m_i = MSB_{8n}(h_i)\oplus Perm_0(LSB_{8n}(h_i)\oplus pt_i)$

d. Let $ct_i = F_k(m_i)$.

Now, it ought to be provable that this cipher is secure if the functions $Perm_0$, $Perm_1$ and $Stretch$ are secretly keyed and pseudo random, but do they have to be? Does it suffice that they are "non-linear" or "weakly pseudo random" and how should those terms in such case be defined?

Note: This is a purely hypothetical cipher, but it is interesting mostly because the randomized padding could be used as a covert channel. If the randomized padding is used as a covert channel, an attacker who is given access to the decryption key will not be able to determine if that key decrypts the actual plain text or the alternative plain text. In that sense the scheme would be an example of deniable encryption. Because of that, the question could be understood as whether anyone in their right mind would have any rational reason for using this cipher for anything except deniable encryption. For instance, would it be plausible that anyone would use it with AES, SHACAL-2 and PBKDF2, and claim the purpose is to preserve long term confidentiality?

-