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.