The McEliece cryptosystem is a public-key cryptosystem whose
construction is based on the difficulty of decoding general linear
codes.  While the original construction appears to be secure, it is also
inefficient.  Later modifications, such as Sidelnikov's proposal based
on Reed-Muller codes, attempt to remedy this problem while also
maintaining similar security to the original McEliece system.  We will
show how structural properties of Reed-Muller codes can be used to break
the Sidelnikov system.  The attack works well in the low-rate setting in
which Reed-Muller codes are of interest.  In particular, the "secure"
parameters proposed by Sidelnikov are broken on a standard PC in less
than one hour.