This key exchange is broken.

The first thing one should do to break this key exchange is to reduce this problem to a simpler problem and then break the simpler problem. Suppose that $\mathbf{y}$ is a column vector. Then to break this key exchange, it suffices to produce an efficient algorithm that can always produce the vector $M_{A}M_{B}\mathbf{y}$ using just the public information.

Observe that $M_{A}M_{B}\mathbf{y}=M_{A}P_{B}X_{B}^{-1}\mathbf{y}=S_{A}X_{B}^{-1}\mathbf{y}$.

In particular, if $\mathbf{z}=X_{B}^{-1}\mathbf{y}$, then $M_{A}M_{B}\mathbf{y}=S_{A}\mathbf{z}$ and $\mathbf{X}_{B}\mathbf{z}=\mathbf{y}$. An adversary will be able to recover $M_{A}M_{B}\mathbf{y}$ if the adversary can compute a pair (which we will call a pseudo private key) that behaves like $(M_{B},\mathbf{z})$.

Let $\langle M_{0}\rangle$ be the algebra generated by $M_{0}$.

A pseudo private key is a pair $(M_{B}^{p},\mathbf{z}_{E})$ where $M_{B}^{p}\in\langle M_{0}\rangle$ and $M_{B}^{p}\mathbf{y}=P_{B}\mathbf{z}_{E}$ and $S_{B}=M_{B}^{p}P_{A}.$

Proposition: If $(M_{B}^{p},\mathbf{z}_{E})$ is a pseudo private key, then $M_{A}M_{B}\mathbf{y}=S_{A}\mathbf{z}_{E}$.

Proof:

$$S_{A}\mathbf{z}_{E}=M_{A}P_{B}\mathbf{z}_{E}=M_{A}M_{B}^{p}\mathbf{y} =M_{B}^{p}M_{A}\mathbf{y}=M_{B}^{p}P_{A}X_{A}^{-1}\mathbf{y}$$ $$=S_{B}X_{A}^{-1}\mathbf{y}=M_{B}M_{A}\mathbf{y}=M_{A}M_{B}\mathbf{y}.\square$$

It is not too hard to compute a basis for the affine space of all pseudo private keys $(M_{B}^{p},\mathbf{z}_{E})$ and there will always be some pseudo private key.

This key exchange is broken.

For this problem, let $\langle M_{0}\rangle$ denote the algebra generated by $M_{0}$.

Set $Z_{A}=X_{A}^{-1},Z_{B}=X_{B}^{-1}$. Then $M_{A}=P_{A}Z_{A},M_{B}=P_{B}Z_{B}$. In particular, $S_{B}=P_{B}Z_{B}P_{A}$.

A pseudo key is a matrix $Z_{B}^{p}$ such that $P_{B}Z_{B}^{p}\in\langle M_{0}\rangle$ and where $S_{B}=P_{B}Z_{B}^{p}P_{A}$. The affine space of all pseudo keys can be computed simply by solving a system of linear equations.

If $Z_{B}^{p}$ is a pseudo key, then $$M_{B}M_{A}=P_{B}Z_{B}P_{A}Z_{A}=S_{B}Z_{A}=P_{B}Z_{B}^{p}P_{A}Z_{A}=P_{B}Z_{B}^{p}S_{A},$$ so the secret key $M_{B}M_{A}$ is recoverable from a pseudo key $Z_{B}^{p}$ and the public information $S_{A}$.

This key exchange is broken.

The first thing one should do to break this key exchange is to reduce this problem to a simpler problem and then break the simpler problem. Suppose that $\mathbf{y}$ is a column vector. Then to break this key exchange, it suffices to produce an efficient algorithm that can always produce the vector $M_{A}M_{B}\mathbf{y}$ using just the public information.

Observe that $M_{A}M_{B}\mathbf{y}=M_{A}P_{B}X_{B}^{-1}\mathbf{y}=S_{A}X_{B}^{-1}\mathbf{y}$.

In particular, if $\mathbf{z}=X_{B}^{-1}\mathbf{y}$, then $M_{A}M_{B}\mathbf{y}=S_{A}\mathbf{z}$ and $\mathbf{X}_{B}\mathbf{z}=\mathbf{y}$. An adversary will be able to recover $M_{A}M_{B}\mathbf{y}$ if the adversary has access to a pair like $(M_{B},\mathbf{z})$.

Let $\langle M_{0}\rangle$ be the algebra generated by $M_{0}$.

A pseudo private key is a pair $(M_{B}^{p},\mathbf{z}_{E})$ where $M_{B}^{p}\in\langle M_{0}\rangle$ and $M_{B}^{p}\mathbf{y}=P_{B}\mathbf{z}_{E}$ and $S_{B}=M_{B}^{p}P_{A}.$

Proposition: If $(M_{B}^{p},\mathbf{z}_{E})$ is a pseudo private key, then $M_{A}M_{B}\mathbf{y}=S_{A}\mathbf{z}_{E}$.

Proof:

$$S_{A}\mathbf{z}_{E}=M_{A}P_{B}\mathbf{z}_{E}=M_{A}M_{B}^{p}\mathbf{y} =M_{B}^{p}M_{A}\mathbf{y}=M_{B}^{p}P_{A}X_{A}^{-1}\mathbf{y}$$ $$=S_{B}X_{A}^{-1}\mathbf{y}=M_{B}M_{A}\mathbf{y}=M_{A}M_{B}\mathbf{y}.\square$$

It is not too hard to compute a basis for the affine space of all pseudo private keys $(M_{B}^{p},\mathbf{z}_{E})$ and there will always be some pseudo private key.

This key exchange is broken.

The first thing one should do to break this key exchange is to reduce this problem to a simpler problem and then break the simpler problem. Suppose that $\mathbf{y}$ is a column vector. Then to break this key exchange, it suffices to produce an efficient algorithm that can always produce the vector $M_{A}M_{B}\mathbf{y}$ using just the public information.

Observe that $M_{A}M_{B}\mathbf{y}=M_{A}P_{B}X_{B}^{-1}\mathbf{y}=S_{A}X_{B}^{-1}\mathbf{y}$.

In particular, if $\mathbf{z}=X_{B}^{-1}\mathbf{y}$, then $M_{A}M_{B}\mathbf{y}=S_{A}\mathbf{z}$ and $\mathbf{X}_{B}\mathbf{z}=\mathbf{y}$. An adversary will be able to recover $M_{A}M_{B}\mathbf{y}$ if the adversary can compute a pair (which we will call a pseudo private key) that behaves like $(M_{B},\mathbf{z})$.

Let $\langle M_{0}\rangle$ be the algebra generated by $M_{0}$.

A pseudo private key is a pair $(M_{B}^{p},\mathbf{z}_{E})$ where $M_{B}^{p}\in\langle M_{0}\rangle$ and $M_{B}^{p}\mathbf{y}=P_{B}\mathbf{z}_{E}$ and $S_{B}=M_{B}^{p}P_{A}.$

Proposition: If $(M_{B}^{p},\mathbf{z}_{E})$ is a pseudo private key, then $M_{A}M_{B}\mathbf{y}=S_{A}\mathbf{z}_{E}$.

Proof:

$$S_{A}\mathbf{z}_{E}=M_{A}P_{B}\mathbf{z}_{E}=M_{A}M_{B}^{p}\mathbf{y} =M_{B}^{p}M_{A}\mathbf{y}=M_{B}^{p}P_{A}X_{A}^{-1}\mathbf{y}$$ $$=S_{B}X_{A}^{-1}\mathbf{y}=M_{B}M_{A}\mathbf{y}=M_{A}M_{B}\mathbf{y}.\square$$

It is not too hard to compute a basis for the affine space of all pseudo private keys $(M_{B}^{p},\mathbf{z}_{E})$ and there will always be some pseudo private key.