With three weeks to go before the Olympics begin, new threats — and a possible security breach — are placing a troubling cloud over the upcoming Winter Games. A video was posted to a Jihadist website over the weekend, in which two young men take credit for two recent terrorist attacks in Volgograd, and promising more bloodshed in Sochi next month.

And in another disturbing report, police in Sochi say they are desperately searching for Dagestani woman known as the "Black Widow" who may have already entered the city undetected, despite being wanted for her connection to previous plots. Those who were not already nervous about the Winter Olympics becoming a terrorist target should now be worried about the security situation in Russia.

In the video, two men in street clothes — who are believed to have carried out twin suicide attacks in Volgograd last month — promised "a surprise package" for Olympics spectators, adding, "If it happens [the Olympics], we'll have a surprise for you. This is for all the Muslim blood that is shed every day around the world, be it in Afghanistan, Somalia, Syria, all around the world. This will be our revenge."

The two men said the Olympic games will be at risk of attack until Russia vacates the country's North Caucasus region, were religious extremists are trying to establish a breakaway Islamist state. The threat is especially credible following several violent incidents leading up to the Olympics. Last week, seven people were killed in a shootout between Russian police and Islamist militants, and at least 34 people were killed last month in attacks by militants, who have seized on the publicity of the games to highlight their quest for independence. Many in the area have Chechen roots and are historically opposed to Russian rule, and have complained of prejudice and marginalization because of their religious beliefs. 

Russian President Vladimir Putin is sending 40,000 police officers to protect Sochi during the Games and has assured visitors that they will be safe, saying "We will protect our air and sea space, as well as the mountain cluster... I hope that it will be arranged so that it will not be evident and, as I have already said, will not depress the participants in the Olympic Games.”

But U.S. officials aren't convinced. The State Department issued a travel warning earlier this month encouraging attendees to be especially careful: 

Russian authorities have indicated to the Embassy that they are taking appropriate measures in light of this information. While we expect the Russian authorities will put in place enhanced security measures in Sochi and though there is no indication of a specific threat to U.S. institutions or citizens, U.S. citizens should be aware of their personal surroundings and follow good security practices. U.S. citizens are urged to remain vigilant and exercise good judgment and discretion when using any form of public transportation.

U.S. officials worry that Sochi's remote location, and it's proximity to areas of unrest, makes it especially vulnerable to attack. And some have expressed frustration with Russia's preparations and lack of cooperation, anticipating that the country will block assistance from Washington. According to the Chicago Tribune

The most formidable roadblock U.S. officials have discussed regarding contingency plans for Sochi is that Russian authorities have historically been reluctant to allow foreign military forces, especially those of the United States, on Russian territory. "No matter what happens," the Russians "are not going to welcome with open arms" any intervention by outsiders, even in a situation where outsiders might only be seeking to rescue their own citizens, the source said.

Republican Representative Mike Rogers added that he believes the Kremlin is withholding information from U.S. officials that could protect American lives. One member of the Senate Intelligence Committee even said he wouldn't attend the games himself, adding "I don't think I would send my family," because of the safety concerns.

The relationship between Washington and Moscow has been strained by Russia's granting temporary asylum to Edward Snowden (and possibly employing him as a spy previously) and by the standoff between Russian and Western leaders over Syria. Putin has remained loyal to Syrian President Bashar al-Assad despite allegations that the Assad regime has contributed to the roughly 115,000 deaths over nearly three years of civil war in the country. Russia also was rumored to have struck a trade deal with Iran that would undermine Western efforts to curb the Iranian nuclear program. The U.S. and Russia did come together, briefly, following the attack on the Boston Marathon — which was carried out by two brothers who have connections to the North Caucasus cause. One had even visited in the year before the Boston attack. 

Officials in Russia are on especially high alert today as the Olympic Torch is set to pass through Volgograd