Act of defiance: Pussy Riot perform at the Cathedral of Christ the Savior in Moscow.

Act of defiance: Pussy Riot perform at the Cathedral of Christ the Savior in Moscow.

Pussy Riot rules: wear tights and balaclavas that are brightly coloured but don't match; use an alias; never tell the police your real name. The feminist punks were a collective, anonymous even after they became the most celebrated dissidents in Russia. To record interviews, they crowded around a laptop in restaurant bathrooms, balaclavas on.

For their debut performance, Release the Cobblestones, they climbed scaffolding in the Moscow metro, a dozen times at different stations, to shout, dance and tear a pillow apart, showering feathers on the bemused commuters below. The guitar part was unoriginal, but the message was unambiguous: "Turn Red Square into Tahrir".

When the police gave chase, the women usually managed to run away or talk themselves out of trouble. On November 7, 2011 – the 94th anniversary of Russia's October Revolution, and Pussy Riot member Nadya Tolokonnikova's 22nd birthday – they posted their first video. The lyrics urged demonstrators against Vladimir Putinand Dmitry Medvedev's government to throw rocks at the riot police.

Silent protest:  Wearing Pussy Riot's trademark balaclavas, and with their mouths taped, supporters of the group demonstrate in front of the Russian Embassy in Warsaw, Poland, in 2012.

Silent protest: Wearing Pussy Riot's trademark balaclavas, and with their mouths taped, supporters of the group demonstrate in front of the Russian Embassy in Warsaw, Poland, in 2012. Photo: AFP

These were days of hope for the Russian protest movement. When a few thousand people came out to protest in December, optimistic activists dubbed it "the Snow Revolution" and treated getting arrested as a badge of honour. Pussy Riot scaled a garage next to the detention centre to scream their support. A month later, in Red Square, they performed a song called Putin Has Pissed Himself, and although two women were arrested and charged with letting off a smoke bomb, they got off with a fine.

Kirill I, Patriarch of the Russian Orthodox Church, had urged believers to vote for Putin in the presidential elections, so for their next target, Pussy Riot chose the Cathedral of Christ the Saviour. This time, the authorities would not be so lenient.

There are six women in the video for Punk Prayer: Mother of God, Drive Putin Away, some of which was filmed in another church, but the night before the action, one backed out. Of the five who took part, only three were caught. And of the three who were caught, only two were sent to prison, which is how a collective of anonymous dissidents became a cult of personality, and Nadya Tolokonnikova and Masha Alyokhina became synonymous with Pussy Riot.

Out in the open: Nadya Tolokonnikova, left, and Masha Alyokhina have not been subdued by their time in Russian labour camps.

Out in the open: Nadya Tolokonnikova, left, and Masha Alyokhina have not been subdued by their time in Russian labour camps. Photo: Frank Bauer/Contour

There they are on The Colbert Report, here posing with Hillary Clinton, there at a Vanity Fair fashion shoot on a New York rooftop, dressed in gauzy, brightly coloured skirts with green smoke swirling around them. Next week, they will be in Sydney for the Festival of Dangerous Ideas. Tolokonnikova and Alyokhina, Pussy Riot, one and the same.

It is not quite as simple as that, of course. In February, on the day Tolokonnikova and Alyokhina were special guests at an Amnesty International concert in Brooklyn, introduced by Madonna, some women calling themselves Pussy Riot published an open letter saying the pair had been kicked out of the group, because their celebrity was incompatible with "the rebel feminist punk image" and harmful to the collective.

"It happened by chance, because they caught us and put us in a cage and it's very difficult to sit in court with a balaclava," Tolokonnikova tells me, which is glib, but more true than not. With the masks on, they were one more group of provocateurs. It was when the disguises came off, to reveal beautiful, eloquent, defiant young women, unafraid to face down the Russian security state, that Pussy Riot became a cause celebre to everyone from Aung San Suu Kyi to Lady Gaga, and a potent signifier of rebel chic.

I was told they would be in Baltimore, on the waterfront.

This turns out to be a pavement cafe at the Four Seasons hotel, where they are crowded around a table with three Macbook Airs open, one each for Tolokonnikova, Alyokhina and Tolokonnikova's husband Petya Verzilov, her partner in dissident art since the days of the Voina ("War") collective, which staged an orgy in the Moscow Biology Museum and welded the doors shut at an exclusive restaurant, among many other pranks.

They have come to the city for meetings but refuse to say with whom. Pro-Putin conspiracy theorists will note that Baltimore is the stop before Washington DC, the closest one can get to the seat of US Government without being seen there.

It is a passing visit. They live in Moscow – Alyokhina with her seven-year-old son, Tolokonnikova and Verzilov with their six-year-old daughter – and still do most of their work in Russia, as Pussy Riot and with the prisoners' rights organisation, Zona Prava, which they formed after they were released from labour camps last December. In March, while they were in the city of Nizhny Novgorod to visit a penal colony, a gang of youths attacked them with green dye as they ate breakfast at McDonalds.

Says Alyokhina: "They are always saying that we hate Russia."

Tolokonnikova: "That we were brought by the US Senate and the State Department."

Alyokhina: "'Dirty whores, go to America!'"

They laugh at the memory of it. It has sometimes been said they are unsmiling, but in the hour we spend together, they are charming company, alive to any opportunity to take the piss.

Alyokhina, who has eyes the colour of pale denim, chain-smokes Parliament cigarettes that she has brought from Russia. Tolokonnikova, with a classic jawline offset by Angelina Jolie lips, wears a T-shirt showing the parliament building on fire. She has dyed her reverse-cut bob green.

"I colour my hair green, because I won't have the opportunity to colour it in prison," she says. Are they afraid to go back there? "We don't think about it too much," said Alyokhina. "If they decide to put us in jail, it will be the next step in our life. We will think about it after."

If the administration had ignored Pussy Riot, the collective would have fizzled out by now. Putting Alyokhina, Tolokonnikova and Kat Samutsevich on trial provided them with a platform. Because there was no doubt about the verdict and the proceedings were often farcical, it inevitably recalled a Soviet-era show trial.

The charge was "hooliganism motivated by religious hatred", obscuring the political nature of the case. One parishioner who witnessed the performance testified that seeing the "devilish jerkings" had caused her "huge moral damage". Another said "they basically spat in my face, in my soul, in my Lord's soul".

By locking the three young women in a glass "aquarium" in court, the state placed them in the dissident lineage of writers Joseph Brodsky and Aleksandr Solzhenitsyn. They rose to the occasion. Their closing statements are worth watching in full.

"We are in a cage. But I don't think that we have been defeated," said Tolokonnikova. "Just as the dissidents were not defeated. They were lost in psychiatric wards and the jails, but it was they who pronounced the regime's verdict."

"I am not afraid of you," Alyokhina told the judge. "I am not afraid of lies and fictions and of poorly coded deception in the verdict of this so-called court, because all you can do is take away my so-called freedom, the only sort that exists in the Russian Federation. But no one can take away my inner freedom."

The trial was part of a wider crackdown on dissent. Most of the demonstrators swept up by the police in Bolotnaya Square on May 6, 2012, are still in detention. Anti-corruption campaigner Alexei Navalny, the opposition's most prominent figure, was found guilty of embezzlement and sentenced to five years, only to be set free, then later put under house arrest.

"It is very sad," Alyokhina tells me. "People who are against Putin are working, like us, trying to build something. They continue their work, but not in the streets. They see that if they go to the streets, they go to jail, so they are afraid.

"For middle-class, intelligence people …" Tolokonnikova and Verzilov crack up. "Intelligent," Alyokhina corrects herself, but it is too late and now they are all laughing, tickled by the thought of Putin's secret service friends protesting against the government, a dark vein of humour that is no doubt funnier when you are accustomed to being followed and threatened, your offices are bugged and your private phone conversations are posted online by government news agencies.

Alyokhina and Tolokonnikova were sentenced to two years hard labour (Samutsevich's sentence was suspended on appeal). Conditions in the camps are brutal, particularly in IK-14, the old Gulag outpost in Mordovia to which Tolokonnikova was sent. Inmates sew uniforms for 16 hours a day. Beatings are common, administered by prisoners loyal to the regime. The only bathroom holds five women, and is used by 800.

On September 23, 2013, Tolokonnikova went on hunger strike. She lasted five days before ending up in hospital. But she presents the 21 months she spent in the camps as a vital part of her education. "I learnt how to write in prison," she tells me.

Alyokhina became a jailhouse lawyer. By studying the penal code, she earned the right to wash her hair every day and to see her attorney without undergoing a body cavity search, among other small victories.

The two women were released three months early, last December, under an amnesty transparently intended to curry international favour in advance of the Winter Olympics in Sochi. "We didn't ask for any pardon … I don't need mercy from Putin," Alyokhina told the New York Times. They began to plan their next Pussy Riot action.

Putin Will Teach You to Love the Motherland has the most impact of all their videos. As Pussy Riot perform, this time a group of five women and one man with a guitar, they are attacked by members of the Cossack militia, who look like Hell's Angels dressed in Tsarist military uniform. The men beat them with whips and rip off their balaclavas. "Get out of here while we ask you nicely. This is not America here."

It must be tempting to leave Russia, but they will not. Everywhere they go in the US, they are feted. Reading the shockingly biased coverage of events in Ukraine in the US press, it is easy to understand the appeal of Pussy Riot here. We like our dissidents foreign. The Russian media covered Chelsea Manning's trial more diligently than anyone.

"It's quite obvious why Hillary Clinton posed with us – it's an echo of the Cold War," said Tolokonnikova. Does she regret it? "Of course no. We have to communicate with all people."

While they were in New York, they made a point of visiting Occupy Wall Street activist Cecily McMillan, at Rikers Island prison, to stress that the injustices against which they campaign are not limited to Russia.

For now, their energies are devoted to Zona Prava. Putin, already a hugely popular figure in Russia, has become even more so thanks to his aggressive assertion of Russian patrimony in eastern Ukraine. "In wartime, it's really hard to comment on things using theatre. We can't dance and sing songs about planes that crash." Tolokonnikova says.

"The only topic in Russia now is Ukraine," continues Alyokhina. "And it's hard to make a performance about somewhere where people are dying every day."

At the Festival of Dangerous Ideas, they will talk about "how to build a human rights organisation and not go to prison". They have been arrested seven times since being released and their colleagues are constantly threatened. "They prefer to put pressure on people working with us, not directly on us," says Alyokhina. "It's like in prison when you are kind of a celebrity …" Tolokonnikova: "A star!" She grins. Alyokhina: "A prison star! They threaten your friends. They tell people, 'Don't get within two steps of her'."

At the camp, Alyokhina organised a group of inmates to protest against working conditions. Most were young, uneducated drug users, but they wrote letters to the court, even though they were punished for doing so, and the working day was cut from 12 hours to eight. Alyokhina learnt a lesson that sustains her in her activism: "If you continuously explain to people, step by step, about their rights and the influence they have, they will do it and they will not be afraid." With or without balaclavas, they are Pussy Riot.

Nadya Tolokonnikova and Masha Alyokhina will speak at the Sydney Opera House during the Festival of Dangerous Ideas, August 30-31.