  Twisted Reed-Solomon (TRS) codes are a family of codes that contains a large
number of maximum distance separable codes that are non-equivalent to
Reed--Solomon codes. TRS codes were recently proposed as an alternative to
Goppa codes for the McEliece code-based cryptosystem, resulting in a potential
reduction of key sizes. The use of TRS codes in the McEliece cryptosystem has
been motivated by the fact that a large subfamily of TRS codes is resilient to
a direct use of known algebraic key-recovery methods. In this paper, an
efficient key-recovery attack on the TRS variant that was used in the McEliece
cryptosystem is presented. The algorithm exploits a new approach based on
recovering the structure of a well-chosen subfield subcode of the public code.
It is proved that the attack always succeeds and breaks the system for all
practical parameters in $O(n^4)$ field operations. A software implementation of
the algorithm retrieves a valid private key from the public key within a few
minutes, for parameters claiming a security level of 128 bits. The success of
the attack also indicates that, contrary to common beliefs, subfield subcodes
of the public code need to be precisely analyzed when proposing a McEliece-type
code-based cryptosystem. Finally, the paper discusses an attempt to repair the
scheme and a modification of the attack aiming at Gabidulin-Paramonov-Tretjakov
cryptosystems based on twisted Gabidulin codes.
