(Refiles to add dropped word "charges" in paragraph 11)
* Russia calls U.S. rhetoric primitive and loutish
* Trump says relations 'may be at all time low'
* Volley of hostile statements timed as Tillerson sits for talks
* Putin doubles down on support for Assad
By Yeganeh Torbati and Denis Dyomkin
MOSCOW, April 12 (Reuters) - Russian President Vladimir Putin said on Wednesday trust had eroded between the United States and Russia under President Donald Trump as Moscow delivered an unusually hostile reception to Secretary of State Rex Tillerson in a face-off over Syria.
Any hope in Russia that the Trump administration would herald less confrontational relations has been dashed in the past week after the new U.S. leader fired missiles at Syria to punish Moscow's ally for its suspected use of poison gas.
In Washington, Trump said the United States was not getting along "at all" with Moscow, adding that the relationship "may be at an all-time low."
Trump had frequently called during the 2016 U.S. presidential election campaign for warmer ties with Putin, despite criticism from lawmakers in his own Republican Party.
But the civil war in Syria has driven a wedge between Moscow and Washington, upending what many in Russia hoped would be a transformation in relations, which reached a post-Cold War low under Trump's predecessor Barack Obama.
As Tillerson sat down for talks with his Russian counterpart Sergei Lavrov on Wednesday, a senior Russian official assailed the "primitiveness and loutishness" of U.S. rhetoric, part of a volley of statements that appeared timed to maximise the awkwardness during the first visit to Moscow by a member of Trump's cabinet.
"One could say that the level of trust on a working level, especially on the military level, has not improved but has rather deteriorated," Putin said in an interview broadcast on Russian television.
He doubled down on Russia's support for Syrian President Bashar al-Assad, repeating denials that Assad's government was to blame for the gas attack last week and adding a new theory that it may have been faked by Assad's enemies.
Tillerson reiterated the U.S. position that Assad must eventually relinquish power in Syria.
"We discussed our view that Russia as their closest ally in the conflict perhaps has the best means of helping Assad recognise this reality," he said.
Asked whether Assad could be subject to war crimes charges, Tillerson said people were working to make such a case, though he cautioned that would require clearing a high legal hurdle.
Lavrov had greeted Tillerson with unusually icy remarks, denouncing the missile strike on Syria as illegal and accusing Washington of behaving unpredictably.
One of Lavrov's deputies was even more undiplomatic.
"In general, primitiveness and loutishness are very characteristic of the current rhetoric coming out of Washington," Deputy Foreign Minister Sergei Ryabkov told Russia's state-owned RIA news agency.
But Lavrov said some progress had been made on Syria at the meeting and that a working group would be set up to examine the poor state of U.S.-Russia ties. He also said that Putin had agreed to reactivate a U.S.-Russian air safety agreement over Syria which Moscow suspended after the U.S. missile strikes.
Tillerson noted the low level of trust between the two countries. "The world's two foremost nuclear powers cannot have this kind of relationship," he said.
Moscow's hostility to Trump administration figures is a sharp change from last year, when Putin hailed Trump as a strong figure and Russian state television was often full of effusive praise for him.
In another possible setback to a thaw with Moscow, Trump said on Wednesday that NATO is not obsolete, as he had declared during the election campaign last year. But he told a news conference at the White House with NATO Secretary General Jens Stoltenberg that alliance members still need to pay their fair share for the European security umbrella.
Trump said U.S. relations with Russia were not going well.
"Right now, we’re not getting along with Russia at all. We may be at an all-time low in terms of a relationship with Russia. This has built for a long period of time. But we’re going to see what happens," Trump told the news conference.
In an interview with the Wall Street Journal, Trump said his administration's policy was not to demand Assad step down as part of a "peaceful resolution to the conflict", in some contrast to Tillerson's remarks in Moscow.
"Are we insisting on it? No. But I do think it’s going to happen at a certain point," Trump said.
The Wall Street Journal cited Trump as saying that Assad's use of chemical weapons again would elicit another military response but he also said he would not intervene in depth in the conflict.
The White House has accused Moscow of trying to cover up Assad's use of chemical weapons after the attack on a rebel-held Syrian town last week killed 87 people last week.
Trump responded to the gas attack by firing 59 cruise missiles at a Syrian air base on Friday. Washington warned Moscow, and Russian troops at the base were not hit.
Moscow has stood by Assad, saying the poison gas belonged to rebels, an explanation Washington dismisses as beyond credible.
Russia blocked a Western effort at the U.N. Security Council on Wednesday to condemn the gas attack and push Assad to cooperate with international inquiries into the incident.
Trump came to the presidency promising greater cooperation with Russia in fighting against their common enemy in Syria, Islamic State. Tillerson is a former oil executive who was awarded Russia's Order of Friendship by Putin.
Trump's relations with Russia are also a domestic issue, as U.S. intelligence agencies have accused Moscow of using computer hacking to intervene in the election to help Trump win. The FBI is investigating whether any Trump campaign figures colluded with Moscow, which the White House denies.
Additional reporting by Polina Devitt, Andrew Osborn and Vladimir Soldatkin and Jeff Mason in Washington; Writing by Peter Graff, Anna Willard and Dustin Volz; Editing by Yara Bayoumy and Alistair Bell