The legal authority for US spy agencies' collection of Americans' phone records and other data expired at midnight on Sunday after the US Senate failed to pass legislation extending the powers.

After debate pitting Americans' distrust of intrusive government against fears of terrorist attacks, the Senate voted to advance reform legislation that would replace the bulk phone records program revealed two years ago by former National Security Agency contractor Edward Snowden.

Although the Senate did not act in time to keep the program from expiring, the vote was at least a partial victory for Democratic President Barack Obama, who had pushed for the reform measure as a compromise addressing privacy concerns while preserving a tool to help protect the country from attack.

But final Senate passage was delayed until at least Tuesday by objections from Senator Rand Paul, a libertarian Republican presidential hopeful who has fulminated against the NSA program as illegal and unconstitutional.

As a result, the government's collection and search of phone records terminated at midnight (0400 GMT on Monday) when key provisions of a post-Sept. 11, 2001, law known as the USA Patriot Act expired.

In addition, US law enforcement and security agencies will lose authority to conduct other programs.

Those allow for "roving wiretaps" aimed at terrorism suspects who use multiple disposable cell phones; permit authorities to target "lone wolf" suspects with no connection to specific terrorist groups, and make it easier to seize personal and business records of suspects and their associates.

Still, eventual resumption of the phone records program in another form, and the other government powers, appeared likely after the Senate voted 77-17 to take up the reform legislation, called the USA Freedom Act.

"This bill will ultimately pass," Paul acknowledged after the procedural vote.

The Senate abruptly reversed course during a rare Sunday session to let the bill go ahead, after Republican Majority Leader Mitch McConnell reluctantly acknowledged that Paul had stymied his efforts to extend the Patriot Act provisions.

Intelligence experts say a lapse of only a few days would have little immediate effect. The government is allowed to continue collecting information related to any foreign intelligence investigation that began before the deadline.

Obama strongly backed the Freedom Act, as have most Democrats. It passed the House of Representatives on May 13 by 338-88.

After the Senate adjourned, the White House issued a statement calling on the Senate to "put aside partisan motivations and act swiftly."

The measure could face more debate in Congress. Republican Senator Richard Burr offered several amendments, including one to extend the existing program for 12 months to provide more time to adopt changes mandated by the Freedom Act.

That could be a problem for some House members, because it doubles the transition period in their version of the bill.

Sen. Ranbd Paul (R-KY) responds to reporters' questions as he leaves the Senate floor after making remarks on a rare working Sunday, on Capitol Hill, in Washington May 31, 2015. Lawmakers were called back from recess to debate the expiration of the Patriot Act, which has divided Congress because of its domestic surveillance programs. Photo: Reuters

'DEMAGOGUERY AND DISINFORMATION'

Republicans have been deeply divided on the issue. Security hawks wanted the NSA program to continue as is, and libertarians like Paul want to kill it altogether.

The Senate debate was angry.

Paul said the Patriot Act provisions wasted resources better spent targeting those planning attacks. He even accused some of his critics of wanting an attack on the United States "so they can blame it on me."

McConnell accused Paul, his fellow Kentucky Republican, and other Patriot Act opponents of waging "a campaign of demagoguery and disinformation" based on revelations from Snowden "who was last seen in Russia."

McConnell has endorsed Paul for president. But he wanted to extend the Patriot Act provisions, unchanged, for five years, and agreed only reluctantly to allow a vote on the Freedom Act despite what he called its "serious flaws."

Several senators accused Paul of using the issue to raise money for his presidential campaign.

"He obviously has a higher priority for his fundraising and political ambitions than for the security of the nation," Senator John McCain, the 2008 Republican presidential nominee, told reporters.

The Senate resumed consideration of the legislation at 4 p.m. EDT (2000 GMT), just as security officials said they had to begin shutting down the NSA program to meet the deadline.

The Freedom Act would end spy agencies' bulk collection of domestic telephone "metadata" and replace it with a more targeted system.

The records would be held by telecommunications companies, not the government, and the NSA would have to get court approval to gain access to specific data. Neither the current nor proposed new system gives the government access to the content of phone conversations.

Many civil liberties groups feel the Freedom Act does not go far enough in protecting privacy.

"Congress should take advantage of this sunset to pass far reaching surveillance reform, instead of the weak bill currently under consideration," Michael Macleod-Ball, acting director of the American Civil Liberties Union's Washington Legislative Office, said in a statement.

A review panel Obama established in 2013 concluded that the metadata collection program had not been essential to preventing any terrorist attack. Security officials counter that it provides important data they can combine with other intelligence to help stop attacks.