One of the earliest NSA surveillance techniques revealed by whistle-blower Edward Snowden was XKEYSCORE, software that allows the agency to sift targets out of vast volumes of internet traffic.
Using just a single "selector" – identifying information such as an email address, phone number or often-used password – a target could be tracked across multiple accounts for communications services such as email and social media.
The NSA demonstrated the tool to Germany's domestic intelligence agency, the Office for the Protection of the Constitution (BfV), in late 2011, and impressed the Germans into making a deal to acquire the software for themselves.
On Thursday, Die Zeit published details of the April 2013 contract signed between the BfV and the NSA to allow the German spies to use XKEYSCORE – at a price.
"BfV will... To the maximum extent possible share all data relevant to NSA's mission," a key clause reads.
Unlike Germany's foreign intelligence agency, the Bundesnachrichtendienst (BND), the BfV does not conduct 'dragnet' surveillance of all internet traffic.
Instead, it only watches specific people who are under suspicion with permission from a special committee of the Bundestag (German parliament).
Such spying is known as "G-10 measures", referring to the 10th article of the German constitution which allows for people's fundamental rights to be infringed in this way.
But as well as the contents of messages, emails, phone calls and other communications, the BfV collects metadata about targets' conversations – the details of when, where, with who, how and for how long communication took place.
These data points can be just as useful as the actual content of communications in building up a picture of a surveillance target's life, including their networks of contacts as well as their daily movements and routines.
With software like XKEYSCORE, agents are able to construct detailed pictures of people's lives from the metadata the BfV collects incidentally during the course of 'ordinary' surveillance.
This can be a massive addition to the value of surveillance for the security services, allowing them to make connections they might otherwise never have thought of.
Metadata remain a legal grey area in Germany, with some constitutional lawyers arguing that they aren't fair game under G-10 rules.
And while the secret services see things differently because of how valuable they can be, sections of the BfV were warning as early as 2012 that there might be "far-reaching legal consequences" to a deal with the NSA.
How much did the NSA see?
While no one disputes that cooperation between intelligence agencies is useful – and that failures to share information often precede terrorist attacks – news of the XKEYSCORE agreement has prompted anger at the BfV's acting without political oversight.
As Die Zeit points out, no one outside the BfV knows just how much information on the dozens of people targeted by the agency under G-10 rules has been passed to the NSA.
Documents related to the XKEYSCORE deal show that the BfV initially insisted that it would not provide data when that was against German law.
Later communications show the NSA pushing for the software to be "used productively" and for the deal to show "working results" - part of a campaign of "high internal pressure" from the Americans for the Germans to feed them data.
Finally, BfV agents convinced themselves that they could justify "regular" deliveries of data to "foreign partner agencies", as they described their dealings in a report to the Interior Ministry in January 2014, saying that a specialist lawyer would sign off on each transfer of data.
No external oversight
BfV officials were very happy with the deal, Die Zeit reports, calling it a "proof of trust [in us by the NSA]" and a chance to use a "cool system".
But there was no external oversight of which data exactly would be delivered to the Americans under the agreement.
Germany has several authorities who might have had something to say about the contract, including the parliamentary intelligence oversight committee and the data protection commissioner.
"I knew nothing about such a payment-in-kind deal," former data protection commissioner Peter Schaar told Die Zeit. "And this is the first time I've heard of a test using real data."
"Once again, I have had to learn about a new contract between the BfV and the NSA and unapproved transmission of German data to the American secret services from the press," Green party MP and intelligence oversight committee member Hans-Christian Ströbele complained to Die Zeit.
The parliamentary oversight committee had been aware that the BfV was using the American software – but only after Snowden revealed its existence to the world and MPs asked specific questions about it.
And the lawmakers said they had no clue that the BfV had made such a critical agreement on information-sharing until this week.
Now, MPs on the parliamentary oversight committee and the NSA inquiry committee will have another file to add to their stack of incidents that have seen German intelligence bosses overstep their authority - a pile that has prompted them to push for reinforcement of the oversight system.