What weaknesses are worth investigating in this non-linear matrix cipher?

I have an interesting cipher based on matrix products that I've not seen before.

Given plaintext bytes $$p\in[0,255]$$, pad to a perfect square length and write into the entries of an $$n\times n$$ matrix $$\mathbf{P}$$.

Given a key $$k$$, apply some key derivation function $$f$$ to it to produce another $$n\times n$$ matrix $$\mathbf{K}=f(k)\in[0,255]^{n\times n}$$. We assume $$f$$ is ideal in some sense, so not considering $$f$$ itself as an attack vector here.

Assume $$f$$ is designed such that $$\mathrm{gcd}(\det(\mathbf{K}), 256) = 1$$.

To encrypt, we do $$\mathbf{C} = \mathcal{E}(p) = \mathbf{K}^\top \mathbf{P} \mathbf{K} \mod 256$$.

To decrypt a given ciphertext $$\mathbf{C}$$ and knowing $$k$$ and thus $$\mathbf{K}$$ we just do this (all modulo 256):

$$\mathbf{P} = \mathbf{K}^{-\top}\mathbf{C}\mathbf{K}^{-1}$$

The $$\mathrm{gcd}$$ condition mentioned earlier should ensure that an inverse exists. The problem appears to be much harder than the linear Hill cipher because it is quadratic in entries of $$\mathbf{K}$$. A single incorrect entry in a close guess of $$\mathbf{K}$$ produces a seemingly random output, so the problem has no easy gradient to follow for some kind of greedy search or hill-climb.

I am only aware of a known plaintext attack where if $$\mathbf{P}$$ happens to be a positive definite matrix, then we can write $$\mathbf{P}=\mathbf{Y}^\top\mathbf{Y}$$ and potentially do Cholesky decomposition or find a lattice isomorphism between $$\mathbf{P}$$ and $$\mathbf{C}$$. This particular integer matrix equation is also documented little online. From a cryptography standpoint, what other methods might make an attack more feasible than brute force?

An obvious problem with the above is when $$\mathbf{P} = \mathbf{0}$$ then $$\mathbf{C}=\mathbf{0}$$, and more generally it leaks information about zero entries in the plaintext. To mitigate this we could also derive an extra matrix $$g(k)=\mathbf{A}$$ from the key, and do $$\mathbf{C}=\mathbf{K}^\top \mathbf{P} \mathbf{K} + \mathbf{A}$$. For decryption we'd need to subtract this matrix from the ciphertext matrix first, then proceed as before.

Well, with this cipher, we have:

$$\mathcal{E}(p) + \mathcal{E}(q) = \mathcal{E}(p+q)$$

That is, it is linear; the standard linear attacks work just fine. A sufficient number of known plaintexts would be sufficient to allow you to decrypt anything.

Adding in the constant $$A$$ makes the cipher affine rather than linear; that just means we need a single extra known plaintext...

• I see... $\mathbf{C}_1 + \mathbf{C}_2 = \mathbf{K}^\top\mathbf{P}_1\mathbf{K} + \mathbf{K}^\top\mathbf{P}_2\mathbf{K} = \mathbf{K}^\top(\mathbf{P}_1 + \mathbf{P}_2)\mathbf{K}$ so enough pairs of $\mathbf{P}_i,\mathbf{C}_i$ should determine $\mathbf{K}$. Doesn't the number of pairs grow as $n^2$ though, or is there a lower complexity? Jan 31 at 23:25
• @filnty Being linear is enough to mean the cipher cannot be $\mathsf{IND}-\mathsf{CPA}$ secure, the lowest acceptable notion of security for a cipher. This is to say what poncho has demonstrated is generally enough to be seen as a full attack already (though you are correct that given enough samples, key recovery should be possible as well) Feb 1 at 2:19

As poncho mentioned, your cipher is linear. You seemed initially to think that it was quadratic. This is just an answer to say that it is well-known that your equation can be rewritten to be of the form $$P = A_K B_P$$, where $$A, B$$ are matrices that depend on $$K$$ and $$P$$. This is done via the Kronecker product. In particular, one can rewrite it as

$$\mathcal{E}(p) = \mathbf{K}^{-T}\mathbf{P}\mathbf{K} = (\mathbf{K}^{-T}\otimes \mathbf{K})\mathsf{vec}(\mathbf{P})$$

Here, we are required to reshape the matrix $$\mathbf{P}$$ to get the math to work out. Read the wikipedia page if you're interested.

In general your cipher construction is somewhat close to something that actually works. In LWE-based cryptography, one can define a cipher

$$\mathsf{Enc}_{\vec s}(\vec m) = (\mathbf{A}, \mathbf{A}\vec s + \vec e + (q/2)\vec m)\bmod q$$

Here, the secret $$\vec s\gets \mathbb{Z}/q\mathbb{Z}^n$$, $$\vec e\gets\{-B, -B+1,\dots, B\}^n$$, and $$\mathbf{A}\gets \mathbb{Z}/q\mathbb{Z}^{n\times n}$$. Standard choices of parameters are $$n\approx 700$$, $$B\approx 10$$, and $$q\approx 3000$$. I haven't verified all the details for these ballpark parameters, but under well-accepted hardness assumptions the above will be correct and secure. It is also closely-related to the new (public key) replacement for Elliptic Curve cryptography that has just been standardized.

• +1 Useful info. There's a mistake, it should be $\mathbf{K}^\top\mathbf{P}\mathbf{K}$ and $(\mathbf{K}^\top \otimes \mathbf{K}^\top) \mathrm{vec}(\mathbf{P})$ if $\mathrm{vec}$ is the row-wise instead of the usual columnwise vec. Feb 1 at 11:04