We show that gallium-ion-implanted silicon serves as an etch mask for fabrication of high aspect ratio nanostructures by cryogenic plasma etching (deep reactive ion etching). The speed of focused ion beam (FIB) patterning is greatly enhanced by the fact that only a thin approx. 30 nm surface layer needs to be modified to create a mask for the etching step. Etch selectivity between gallium-doped and undoped material is at least 1000:1, greatly decreasing the mask erosion problems. The resolution of the combined FIB-DRIE process is 20 lines microm(-1) with the smallest masked feature size of 40 nm. The maximum achieved aspect ratio is 15:1 (e.g. 600 nm high pillars 40 nm in diameter).