0
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

Well, with this cipher, we have:

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

(and the addition operation is adding the matrix elements modulo 256)

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – flinty
    Commented Jan 31 at 23:25
  • 1
    $\begingroup$ @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) $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 1 at 2:19
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ +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. $\endgroup$
    – flinty
    Commented Feb 1 at 11:04

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.