It is a vast expanse of desert where conditions are so inhospitable that almost no one lives there. But for al-Qaeda – on the run in Iraq and under attack in Pakistan and Afghanistan – this stretch of the Algerian Sahara has proved fertile ground in its quest to open a new front on Europe’s southern doorstep.

Intelligence sources and Western diplomats have told The Times that a new force – an Algerian group calling itself al-Qaeda in the Land of Islamic Maghreb (AQIM) – aims to create an arc of influence throughout North Africa by spreading Osama bin Laden’s “brand” through a fusion of disparate fundamentalist groupings.

Ernst Uhrlau, the head of the German foreign intelligence agency, said recently: “We are watching the activities of al-Qaeda in North Africa with great concern. A handful of groups have become ensconced there, largely unobserved, and are strengthening bin Laden’s terrorist network. What is evolving there brings a completely new quality to the jihad on our doorstep.”

In Tunisia this week the French President echoed this nervousness. “Who could believe that if tomorrow, or after tomorrow, a Taleban-type regime were established in one of your countries in North Africa, Europe and France could feel secure?” President Sarkozy asked.

In 2006, on the fifth anniversary of the September 11 attacks, the Salafist Group for Prayer and Combat – a fundamentalist group that has rejected an Algerian offer of an amnesty and pardon – announced its “merger” with al-Qaeda and an oath of allegiance to bin Laden. “Since then they have adopted wholesale the tactics, techniques and procedures that al-Qaeda has successfully used against coalition forces in Afghanistan and Iraq,” an intelligence source said.

Intelligence sources contacted by The Times in London, France, Spain, Germany and the US as well as in North Africa show a remarkable uniformity when describing the threat posed by AQIM. At present it is not the size of its membership that is causing alarm – one Western intelligence source said that its hardcore numbered about 200 fighters – but the speed with which it has reorganised itself in a region emerging from a conflict that has claimed up to 200,000 lives in the past decade.

While it has continued to attack Algerian forces AQIM has widened its range of targets – including Westerners – using tactics honed in Iraq: suicide attacks and a variety of bombing techniques. “They are definitely growing in sophistication and, taken as a whole, this presents us with a very disturbing picture,” the source said.

“They’ve done all this in a relatively short time, some of it through the use of the internet where they can organise, download training videos, recruit via encrypted forums.

“There are disturbing trends that suggest they have been training others from both the Sahel and the Maghreb countries: Morocco, Tunisia, Libya, Nigeria, Niger, Chad, Senegal, Mauritania and Burkina Faso.”

Although the emir of AQIM, Abu Musab Abdel Wadoud, was hiding in the mountains of the Kabylie region, the strategic base of the group was far to the south, across the lightly guarded border with Mali, the source said. “It’s that ungoverned space across the Sahel. You don’t need a cave to hide there, all you need is to keep on the move – it’s a vast, empty space.

“If you’ve got a small group of four to five trucks with fifteen to twenty men, a few indigenous people, in a huge area all you have to do is keep on the move.”

Chemicals for making bombs – such as those used in the double suicide attack in Algiers in December, which killed 41 people in a UN compound – are arriving in Algeria along traditional Saharan smuggling routes from West Africa. These routes are bringing nomadic Tuaregs into AQIM’s sphere of influence, a relationship described by the intelligence source as a marriage of convenience.

A big part of this trade is drugs, with cocaine featuring ever more strongly as a financial source for the terrorists.

Last month twenty-four al-Qaeda militants were killed; ten were allegedly planning to carry out suicide attacks in the capital. The past twelve months have been bloody, with eight suicide attacks killing more than a hundred people. Ayman al-Zawahiri, bin Laden’s deputy, justified the attacks via an internet forum last week, describing them as “jihad to liberate Algerians from America, France and the children of France”.

A recent report by Europol, the EU crime intelligence agency, claimed that most of the 340 people arrested on terrorism-related charges between October 2005 and December 2006 inside Europe “came from Algeria, Morocco and Tunisia”. Many of them had ties with the Salafists and AQIM.

Under the sands of the Sahara lies the source of wealth in Algeria: huge reserves of oil and gas. Sonatrach, the state energy group in Algeria and the biggest company by revenue in Africa, has just announced record earnings of $19 billion (£9.7 billion) in the first three months of 2008. The country has never been wealthier, yet unemployment is rampant among young men, prompting the popular newspaper cartoonist Dilem to portray the choice facing them as one teenager with a suicide belt, labelled kamikaze, and another with a lifebelt, labelled harraga – the term used to describe those who try to make it across the Mediterranean.

“There is a lack of hope among young Algerians for the future,” a Western diplomat said. “One of the suicide bombers here was only 15 and al-Qaeda is stepping up its propaganda efforts to recruit the very young.”

“It remains the biggest challenge to the Algerian authorities to make these people feel that they have a stake in society.”

THE NORTHERN FRONT

Morocco Moroccan Islamic Combat Group (GICM) is believed to have orchestrated the 2004 Madrid bombings, killing 191 people. Salafia Jihadia, an offshoot, was also involved in the 2003 Casablanca bombings that killed 33

Libya The Libyan Islamic Fighting Group, founded in 1995 by veterans of the war against Soviet forces in Afghanistan, has been linked to al-Qaeda. This month Colonel Gaddafi released 90 imprisoned members, saying they had reformed

Tunisia Last year security forces killed 12 Islamic extremists linked to Algerian terror groups. They had been plotting to attack the British and US embassies in Tunis as well as hotels and nightclubs

Algeria Al-Qaeda-linked group has carried out a series of spectacular suicide attacks including assassination attempts on President Bouteflika

Mauritania Security forces this week arrested five al-Qaeda militants suspected of killing four French tourists in December. The Dakar Rally was cancelled this year because of terrorism fears

Mali North Mali serves as a logistics and training base for the AQIM, according to Western intelligence sources. Its leader Mokhtar Belmokhtar reportedly operates from the region. He was responsible for the 2003 kidnapping of 32 tourists in southern Algeria

Times Recommends

• New York has lost its edge
• Copenhagen will fail – and quite right too
• More than 17,000 new underwater species found