The intelligence services' watchdog began questioning the lawfulness of GCSB's activities five months before the Government says the illegal spying came to light.
The top-secret report prepared by Cabinet Secretary Rebecca Kitteridge on the GCSB is due to be made public today.
The Government has brought forward the release after Fairfax revealed the report found 85 people may have been illegally spied on by the foreign intelligence bureau.
The agency is forbidden from spying on anyone with New Zealand citizenship or permanent residence here.
The Kitteridge report raises questions about when the intelligence services first became aware there was a problem.
Kitteridge said Inspector-General of Intelligence and Security, Paul Neazor, questioned in May 2012 whether long-standing interpretations of the GCSB Act by the intelligence services were correct.
This came five months before the Government says the illegal spying on internet entrepreneur Kim Dotcom came to light.
The problem centres on work the bureau did on behalf of other agencies - particularly the domestic spy bureau Security Intelligence Service (SIS) and the police.
Kitteridge said the issue was the subject of some legal analysis and correspondence, but the matter was still not resolved.
Prime Minister John Key has repeatedly said the agency and the Government only became aware of the illegal spying on Dotcom in September. He ordered Kitteridge be seconded to the bureau for an internal review.
The report reveals that internal legal advice at GCSB had been that it was lawful for agents to assist domestic agencies such as the SIS or police in two circumstances:
* If they were helping the SIS on the basis of SIS warrants. The bar of spying on New Zealanders is contained in Section 14 of the GCSB Act, passed in 2003. But GCSB believed this prohibition did not apply when the bureau was acting under the legal authority of the SIS warrants.
* If they were intercepting "metadata". The GCSB assumed the law allowed them to intercept "metadata" - such as the kind of information that appears on a telephone bill. It was judged not to be a "communication" and could be lawfully obtained from New Zealanders without a warrant. This has now been reviewed by lawyers and the bureau now believes metadata would likely constitute a communication.
Kitteridge says GCSB director Ian Fletcher sought an opinion from the Solicitor-General if the authority of an SIS warrant would override the prohibition in Section 14.
The Solicitor General confirmed the "difficulties of interpretation" and the "risk of an adverse outcome if a court were to consider the question".
Kitteridge has recommended the legislation be reformed.
A freeze was put on helping other agencies in September and no more surveillance will take place until the law is amended.
She said the other 85 cases had been reported to the prime minister so he could take appropriate action.
Kitteridge stressed assistance that was provided to the SIS was to help combat threats to New Zealand security in areas such as counter-terrorism.
She also emphasised there was no evidence agents acted in bad faith nor believed the ends justified the means. They were devastated to learn they may have acted unlawfully, she said.
KEY POINTS OF THE REPORT:
* The GCSB Act 2003, the sole source of authority and law within the agency, is so confused it is not fit for purpose
* The key issue is with Section 14 which states the GCSB may not "take any action for the purpose of intercepting the communications of a person ... who is a New Zealand citizen or a permanent resident"
* Immediate legislative reform is needed to clarify the application of the Act to the GCSB'S work
* The GCSB Act has not kept pace with the internet - the Act is difficult to apply to some of the bureau's work with new technology
* GCSB'S compliance with the Defence Act 1990 and the Privacy Act 1993 is also being analysed - and the agency may not have complied with the Public Records Act 2005
* It will take a year and a really solid effort to address GCSB's problems
* GCSB's organisation was too complex and fragmented, with too many managers
* There was a tendency to tick boxes and make assumptions but not ask questions or seek evidence
* A culture persisted where poor performance was tolerated and problematic staff redeployed internally instead of being held accountable
* There was an aversion to dealing with poor performance because of a security risk from disgruntled former staff and also because vetting of new recruits took so long
* Specialised knowledge was valued over other skills, staff stayed too long in one job and there was some passive resistance to change
* A need-to-know culture created silos
* The bureau is isolated and disconnected from the rest of the public service
* Staff faithfully followed legal advice and it was devastating and abhorrent to learn they were not acting within the law
* There was no evidence they acted in bad faith or believed the end justified the means
* Staff believe it is an organisation spread very thinly - money was directed at operations at the expense of legal and compliance advice.
Does David Cunliffe need to resign as Labour leader?Related story: David Cunliffe's leadership on the line