Between 1994 and 1997, the Bundesnachtrichtendienst, or BND, shredded 581 documents about the aide to Adolf Eichmann, the German news magazine Der Spiegel reported on July 20, citing Bodo Hechelhammer, a scholar who heads a research team commissioned to explore the history of the foreign intelligence agency.
The report has reinforced speculation that Brunner, a former officer in Adolf Hitler's paramilitary organisation, the SS, who was responsible for the deportation of more than 128,500 Jews to concentration camps, worked for the BND after the war.
The disclosure has also led to renewed public pressure for a detailed investigation into the post-war lives of former Nazi officials who escaped Germany to the Middle East as allied troops closed in - in Brunner's case, to Syria.
Efraim Zuroff, the director of the Jerusalem office of the Simon Wiesenthal Centre, which among its activities, campaigns for the prosecution of Nazi war criminals, said the latest revelations about the BND cast Germany, as well as the agency itself, in an especially bad light.
"It flies in the face of our whole perception that Germany had done a complete turnabout and was totally committed to democracy and to atoning and compensating for the crimes. We see here that the public face of Germany was doing the right thing, while the private face was doing the exact opposite," Mr Zuroff said.
The document destruction, Mr Zuroff said, "clearly shows" the BND "have something to hide".