They arrived posing as Swiss honeymooners, PE teachers, environmental activists and French holidaymakers. They arrived in dribs and drabs in the middle of 1985, most by plane - but four by boat.
The yacht Oueva arrived in Parengarenga Harbour on June 22, carrying four Frenchmen, a Zodiac boat and specialised scuba breathing apparatus that released no tell-tale trail of bubbles.
The sail boat carried other materials to be used in an operation codenamed "Satanic". Hidden, probably in the bilge, was at least 25kg of explosives: more than sufficient to sink a boat - and more than enough to kill Fernando Pereira.
Two weeks after the secretive arrival of the Oueva, there was nothing low-key about the Rainbow Warrior's docking at Marsden Wharf, at the bottom of Queen St in downtown Auckland, on July 7.
Her hero's welcome reflected the sweeping popularity of the anti-nuclear cause - this was only four months after Prime Minister David Lange indelibly stamped "nuclear-free" on the New Zealand identity with his taunt at an Oxford Union debate: "Hold your breath just for a moment. I can smell the uranium on it as you lean toward me!"
For the Greenpeace activists, New Zealand was a pit-stop: somewhere to rest a little before departing for Mururoa Atoll, where they would protest French nuclear testing. So far, the Nuclear-Free Pacific Tour had taken in Hawaii, the Marshall Islands, Kiribati and Vanuatu.
Greenpeace photographer Pereira had documented birth deformities and cancerous thyroids that testified to the Marshall Islands' continuing contamination by radioactive fallout from United States nuclear tests in the 1950s. In three trips over 12 days, the Rainbow Warrior ferried the people of the Rongelap Atoll, with all their belongings and dismantled homes, to another island.
While popular with the public, the Government of the day was initially lukewarm to the ship. A report in the NZ Herald on July 8 notes the Government refused requests to supply the Greenpeace flotilla with dehydrated foodstuffs and supplies for the protest to Mururoa.
Richard Prebble, the then trans-port minister, recalls no hints of the dramatic events that would shortly unfold: "The Rainbow Warrior's presence in Auckland Harbour had only attracted incidental interest. The fact that the French Government was so sensitive about them was a matter of astonishment to us."
July 10 marked the 29th birthday of American Steve Sawyer, director of the South Pacific anti-nuclear project. After evening meetings on the ship, the crew brought out a cake. "Happy birthday", they sang.
But as the cake was cut, French military frogmen Jacques Camurier and Alain Tonel - who had arrived only the day before from Vanuatu - were busy beneath the partying crew. The pair had travelled from Mechanics Bay in a Zodiac. They dived beneath the Rainbow Warrior to attach two bombs - one near the engine room, and the other on the propeller.
After planting their deadly limpets, the pair travelled to meet up with their co-conspirators in a camper van. There they abandoned the Zodiac. This evidence, combined with suspicious locals taking down the van's number plate, would later lead to international notoriety for the couple who had rented the camper van - Dominique Prieur and Alain Mafart.
Around 11.30pm, Sawyer moved the party to Piha Surf Club on the other side of the city. Kiwi deckhand Bunny McDiarmid, who would later rise to executive director of Greenpeace New Zealand, went ashore with her Dutch partner Henk Haazen to stay with her parents.
Among the crew and visitors left on board were first mate Martini Gotje, land-based co-ordinator Rien Achterberg, skipper Pete Wilcox and Pereira. Gotje and Achterberg, both Dutchmen, were good mates, having co-crewed another peace ship, the Fri, along with McDiarmid and Haazen.
On a whim, Danish engineer Hanne Sorensen decided to take a walk. She wandered up Queen St, hassled by drunken locals.
Back on the ship, the unthinkable was about to happen.
The Herald on Sunday can reveal for the first time the dramatic, and unprecedented, efforts by authorities - including the Air Force, secret spy agencies and even the Indonesian military - to try and catch the agents responsible for bombing the Rainbow Warrior 25 years ago.
The controversial deal that saw the two French agents convicted of manslaughter released early was driven by Lange, who kept his Cabinet colleagues in the dark. And previously unreported diplomatic fallout from the affair also shows French spy agencies intimidated officials and ministers at the New Zealand embassy in Paris for years after the bombing.
The sinking of the Rainbow Warrior made New Zealand's anti-nuclear slogan untouchable foreign affairs policy and gave fringe environmental group Greenpeace mainstream credibility. A little country in the Southern Hemisphere was pitched, alone, in a diplomatic and political fight against a nuclear-armed ally.
The incidents helped New Zealand grow up, but none of the above would have come to pass if explosions didn't rock Auckland Harbour late in the evening of July 10.
Gotje, Achterberg and five others were sharing the last beers in the mess room of the Rainbow Warrior. They wondered if the bars would still be open, and someone checked the clock: 11.50pm. Suddenly there was a muffled thud, and Achterberg was lifted from his seat. Then the lights went out and the confusion began.
"There was a big bang," recalls Gotje. "It was not the type of bang you would immediately associate with an explosion."
He went to the engine room, downstairs from the mess, and found it filling with water.
Could another vessel have hit them? This is what was going through Willcox's head as the skipper scrambled out of his bed, wrapped a towel around himself and made his way to the engine room where he found the chief engineer, Dave Edwards, shaking his head and saying: "It's all over, she's finished."
"You ran around like a chicken without a head," Gotje recalls. "I went down to the lower accommodation to look for people."
Those left in the mess formed a chain and picked their way to the deck. "Dave said, It's not the engines," remembers Achterberg. "Then four minutes later: the second explosion. That was the point we thought we better get off the boat."
Gotje was still in the lower cabins. The second bomb detonated almost directly below him. "You could see the water streaming, pissing down from the level above. The ship started to list. And Fernando was standing in the doorway of his cabin. He had his [camera] gear around his neck. I heard Pete Willcox in the alley way: Abandon ship! Abandon ship! Abandon ship!'"
Gotje climbed up on to the wharf, assuming Pereira was behind him. It was only later that he realised he was missing. "I was absolutely soaked and it was so cold. Somebody on a boat gave me some blankets, and a Herald photographer took a picture: I look like a bloody refugee! Willcox was running around stark naked. Then I remembered Fernando."
Within hours, navy divers had recovered Pereira's body. Willcox identified him. It is assumed he was knocked unconscious, or trapped in his cabin, and drowned.
Says Gotje: "It sits in my head ... why the f*** didn't you grab him by the neck?' But he did what he had to do. He didn't have a clue what was going on."
And perhaps if he had lingered, there would have been two men dead.
In a film festival documentary by Suzanne Raes about the Rainbow Warriors now living on Waiheke Island - among them Gotje and McDiarmid - McDiarmid recalls Pereira as a good-natured, easy-going crewmate.
"Fernando didn't want to die for the cause. Nobody did."
Frenchman and BBC News reporter Henri Aster was in Wellington in 1985. He wrote in 2005 of the diplomatic scene that morning after the bombing, where Le Monde didn't get a look-in.
Aster recalls a young diplomat's reaction to the news of the Rainbow Warrior sinking: "The radio ran interviews this morning, and they're all blaming the French! There they go again, as if France would do such a terrible thing."
A military attaché, without knowledge of the bombing, but with cynicism from years of watching French politics, wasn't so sure of his Government's innocence: "It would not surprise me at all," he said.
Detective superintendent Allan Galbraith says he did his best to put such spy novel paranoia to one side. He'd arrived early at Auckland Central police station on July 11, after getting a phone call shortly after midnight.
Theories that morning about international spy agencies being involved were dismissed, he says: "That all seemed a bit extraordinary. We did think the likelihood was that it was a local act, and it didn't immediately jump to mind that it would be French frogmen."
Breaks in the case came quickly, and Mafart later blamed nosey Kiwis in his book, Diaries of a Combat Diver. "Informing the police is a national duty," Mafart sneered.
The camper van hired by Mafart and Prieur was quickly identified as a vehicle of interest, and while the agents were more than happy to abandon their $5000 Zodiac, an attempt to claim a $130 camper van rental deposit led to their arrest.
On July 12, staff at the Newman's rental agency in Mt Wellington recognised the couple from police alerts and stalled until officers arrived. Their cover - Swiss honeymooners with the name "Turenge" - was quickly busted.
"The Swiss told us they were fake and were most upset about it. It then became obvious they were French," says Galbraith.
Prieur and Mafart were charged with murder. The pair pleaded guilty to reduced charges of manslaughter and wilful damage. On November 22, 1985, each was sentenced to 10 years in prison. From this point on, until a controversial Lange-driven settlement that saw them released to French custody the following year, their home would be Paremoremo Prison.
With the revelation that foreign agents were involved, Galbraith's team grew. Initially 30 detectives were assigned, then 66, then more than 100. Where once the New Zealand Government had refused to provide food to Greenpeace, now no expense was spared in tracking down the bombers of the Rainbow Warrior.
Meanwhile, the scale of the operation - and the level to which it was sanctioned by the French Government - was unknown. Up to 13 agents were believed to have been involved and the majority were able to slip out of the country in the coming weeks - but Galbraith's team managed to connect Mafart and Prieur with the Oueva.
Even though the vessel used to bring the explosives into New Zealand had left the country the day before the bombs went off, nine detectives were flown by Air Force Andover to interview the crew and collect evidence when the yacht arrived in Norfolk Island.
As Norfolk Island was Australian territory, there was little New Zealand police could do. At the time Galbraith spoke with some frustration of the lack of evidence or ability to detain the crew of the Oueva. "It would be fair to say that we would have liked to have a longer time to inspect the vessel."
Around the Cabinet table, Prebble also recalls the frustration and a desperate search for solutions as the spies prepared to set sail: "I remember saying, Why don't we send out a Hercules, with SAS guys on board, and raid the yacht?' Lange hadn't thought of that - but by the time we looked into this option the yacht had left."
While elite army troops weren't used, another branch of Government was. The highly classified 1985/86 Annual Report for the Government Communications and Security Bureau was accidentally released to media in 2006 and disclosed its spying work on the "Rainbow Warrior incident".
"A special collection and reporting effort was mounted against French vessels in the New Zealand area, particularly the yacht Oueva (on which some French agents escaped from New Zealand)," the report said. The GCSB also asked its counterpart in the United Kingdom, and the National Security Agency in the US, to tap phones in Paris - and such efforts bore fruit: "Coverage of the Oueva produced some valuable intercepts."
An Air Force Orion was dispatched to track the Oueva, but the plane never found the vessel. As the possibility of catching the fleeing French agents was rapidly diminishing, our then-ambassador to Indonesia Michael Powles was involved in one last, desperate, roll of the dice.
The last reported destination of the Oueva was Noumea, and our man in Jakarta recalls a, late-night request from Wellington. "The one direct flight from Noumea to Paris was via Jakarta - so I had a midnight phone call saying there was a UTA flight the next morning, and please could I have the Indonesians search the plane for these agents?
"I happened to have the home phone number for the Indonesian foreign minister's private secretary. They thought hard about how much they wanted to annoy the French - and then the Indonesians did it, they held the plane up for 24 hours. The French kicked up a fuss - but the agents weren't on board."
The Oueva was never seen again. French newspapers report the yacht sailed to the Coral Sea to join up with French Navy submarine Rubis. The agents apparently scuttled the Oueva, and then clambered aboard the nuclear sub for an undersea voyage home.
Meanwhile, the incident soured relations on both sides of the equator. Almost 20 years before Americans, upset over the refusal of France to sanction the 2003 invasion of Iraq, renamed chips "Freedom Fries", New Zealand bakers began calling baguettes "Kiwi Sticks".
Fury at the New Zealand detention of French citizens, later revealed to be secret agents, raged hot in Paris. Prebble recalls police escorting his car and closing down streets for him when he made an official visit to France several weeks after the bombing.
"I was thinking I might have got a hostile reaction, but this was pretty good treatment. Then the ambassador said to me: The French are extremely worried a far-right extremist is going to assassinate you.' I had an armed guard outside my hotel room that night."
Powles, who had arranged for the plane to be searched in Jakarta in 1985, returned to Wellington to take up a senior role in the Ministry of Foreign Affairs. Lange had authorised his private secretary Christopher Beeby to reach a compromise deal with the French - but the Prime Minister had kept all his colleagues in the dark.
In early 1986 Powles briefed a Cabinet subcommittee on what the deal releasing Prieur and Mafart would look like. He recalls then deputy Prime Minister Geoffrey Palmer blowing his top. "He gave Beeby a dressing down for acting without authority - simply because the person who gave Beeby the authority hadn't told him."
Beeby died last year, but other members of the 1986 Cabinet spoken to by the Herald on Sunday were also unaware of the deal to release Prieur and Mafart until negotiations were well-progressed. Palmer, in Morocco for a meeting of the International Whaling Commission, did not respond to requests for comment.
Now Labour leader Phil Goff casts belated Cabinet acceptance of the deal as grudging: "[The French] were playing hardball politics, and as unprincipled as it was, New Zealand wasn't getting support from the places we'd expected. That's when realpolitik came in. At that point, faced with potentially massive damage to the economy, however ill-principled, we had to find a way through that."
The July 1986 deal, signed off by the United Nations Secretary General, saw $13 million in compensation paid to New Zealand, with the agents to serve out at least three more years of their sentence on Hao Atoll. But both were repatriated home - ostensibly for medical reasons - before this time was served. For this breach, France forked over another $3.5m in penalties.
Lange expressed regret over the deal in My Life: " Why did you give the agents back?' If it is put to me as an issue of principle, I can only acknowledge that it was not dealt with as such. If it was not an issue of principle, I have to ask myself why I made it one, and I cannot answer that."
Powles is skeptical of the former Prime Minister's mea culpa: "There's a lot of difference between what you think when you retire, and how you deal with reality at the time."
Ill-feeling between France and NZ persisted even after deals were cut and relations normalised. Russell Marshall, another member of Lange's Cabinet, says there were stories about overt French meddling in the management of Prieur and Mafart: "The house of the doctor in London, who was assessing the agents, had been burgled. Amongst other things the radio had been left on, tuned into Radio France."
The French Government, approached through its embassy in Wellington, declined to comment for this story. Embassy press attaché Annie Van Herck says: "Dwelling over it only tends to damage relationships between our two countries and reinforce local prejudices against the French people.
"We have worked very hard in the last 25 years to try and improve relationships between France and New Zealand. The New Zealand authorities also wish that the page be turned and that relationships may thrive without constant reference to a past event."
In France, death threats against New Zealand Cabinet ministers slowly gave way to national outrage. Galbraith praises the work of the French press, who slowly prised the truth of the operation from authorities: "The French media were like terriers on this story - as soon as they realised there was a French connection they went very hard," he says.
In September, six weeks after the bombing, Defence Minister Charles Hernu resigned after conceding the operation was conducted by French agents. Shortly after, the head of the DGSE - the intelligence agency that co-ordinated the attack - was fired. A full 20 years after the bombing, Le Monde revealed the operation had been personally signed off by President Francois Mitterrand.
Back in New Zealand, Greenpeace saw a surge of support and goodwill. The following years transformed the organisation from fringe activism to a mainstream, multi-national lobby group. Over the years, critics have argued Greenpeace has been neutered by its larger structure and new financial accountability, but McDiarmid denies Greenpeace has lost its edge.
McDiarmid has given up hoping that justice will be done for Pereira and his family. "What [the agents] did was cowardly. I accept the fact that New Zealand negotiated a settlement because of all the pressure they were under economically. I understand that the nuclear states closed ranks."
Galbraith, the man who did more than anyone else to unravel the complex and deadly plot that killed Pereira and sank the Rainbow Warrior, thinks the bombing was a watershed for New Zealand.
"It helped us grow up in a way and become more aware of the outside world," he says.