The Tuareg tribesmen of the Sahara have a saying, something along the lines of "Patience comes from God, haste comes from the devil". I wish somebody had told our Tuareg driver. The adage, doubtless well-suited to life lived at camel's pace under the scorching sun, is rather less pertinent when you're tearing across the desert at upwards of 60mph in that latter-day ship of the desert, the Toyota Land Cruiser.
There is only one main road linking the populous southern part of Mali, around the capital Bamako, with our destination, way up in the north-east - and we left the road behind at Gao, on the Niger river. It's another 200 miles across desert scrubland littered with boulders and trees bearing spines the size of toothpicks, following the hundreds of criss-crossing vehicle tracks over what is aptly known as a piste, to Kidal, the home base of Tinariwen, the Tuareg band whose latest album Aman Iman (Water Is Life) has just been released to huge acclaim.
By the time we reach Kidal, the suspension on two of our four vehicles has broken, their sturdy iron bars snapping like twigs as we slough around in sand and bounce over rocks and potholes. Not for nothing do the Tuareg have another saying: "The desert rules you, you don't rule the desert." Frankly, you don't even get a vote.
And nor will the Tuareg, if the government in Bamako has its way. Back in the winter of 2005, the Itinerant Voting Bureau - set up by the former French colonial administration specifically to cater to the electoral needs of the nomadic tribesmen - was cut by presidential decree, a move regarded in Kidal as a deliberate attempt to disenfranchise the Tuareg.
Six months of ignored complaints later, the Tuareg did what they have done periodically ever since independence was granted back in 1960, and launched a rebellion, led by a disillusioned army officer, Lt-Col Hassan Fagaga. An army barracks in Kidal was attacked, and arms stolen by Fagaga's rebels. Five people died in the skirmishes.
When reinforcements were sent from Bamako to quash the rebellion, the rebels headed for the hills, where they are invincible, swiftly followed by most of the ordinary townsfolk. They remembered what had happened in the uprising of 1963, when many innocent Tuareg - some of them unaware the rebellion had taken place while they were tending their herds in the desert, - were massacred.
Among the dead then were the parents of Ibrahim Ag Alhabib, the charismatic, tousle-haired frontman of Tinariwen. Out of spite, the family's herd was also slaughtered and left to rot. Four-year-old Ibrahim and his grandmother fled on foot to Algeria, where he grew up into a feckless rapscallion, doing menial jobs in Tamanrasset and Oran, and nursing fantasies of revenge. It was in Tamanrasset that he was first exposed to Western rock music, acquiring cassette tapes of Jimi Hendrix and Led Zeppelin; it offered a sense of purpose and creative fulfilment to his life, and in 1979, he formed a band with Alhassane Ag Touhami and another friend, having taught himself to play on a guitar he had made from a stick, a can and some wire.
Instead of singing the traditional songs, they wrote new lyrics about the political situation and the problems facing their embattled culture, which in itself constituted a revolution in Tuareg music. When Colonel Gaddafi, keen to foster his vision of a single North African Berber state, offered to train and arm the disgruntled Tuareg exiles and fund their fight for autonomy, Ibrahim and Alhassane were two of the first to sign up.
It was in the Libyan training camps that they acquired the skills that would be put to use in rebellions throughout the Eighties, establishing the romantic - but apparently true - legend of Tinariwen riding into battle with Kalashnikovs in their arms and Stratocasters across their backs.
"I got involved specifically with the idea of seeking revenge for my father," explains Ibrahim, "because I don't like the idea of being a soldier at all. I am a musician, not a soldier. I did learn some skills, such as self-discipline and endurance, which serve me well when I am travelling.
"But I had long ago realised that I was a musician and poet, and that these were better weapons with which to achieve what I wanted. Since I have grown older, I have learnt more - I fought a war, and that helped to expunge the desire for revenge. Also, the repressive regime that used to rule Mali has changed, and things are changing for the better."
It doesn't seem that way in Kidal when we finally reach there. The various checkpoints we passed through, manned by sullen, suspicious soldiers, had been disquieting enough, but the 900-odd troops still garrisoned in the town, months after the peace accord which resolved the issues behind the 23 May rebellion, mean there is a permanent sense of unease about the town.
As in Sudan, the antipathy has an evident racial element, there being no confusing the tall, thin, lighter-skinned, Arab-featured Tuareg with the stockier, black west African soldiers, most of whom are from the Bambara culture of the south. The town itself has little to recommend it. The streets are bumpy, potholed dirt-tracks, and most of the buildings are built from bricks made from the same dirt. The lavatory is a hole in the ground. The TV only broadcasts for a few hours a day, and the only programme sounds like someone reading government proclamations.
And the diet is - well, for nine days I eat only overcooked pasta with bits of goat in it, twice a day, until I get so sick I can't keep anything down. In between bouts of copious vomiting, the black humour of another Tuareg adage becomes grimly mocking: the life of a Tuareg, they say, has three stages - one day you are happy, the next day you are sad, and the third day you are dead.
It's a huge relief, then, when we load up the Land Cruisers again and head for the desert to camp out for a few nights. Around a campfire, beneath a glitterball sky full of stars, with the three guitarists of Tinariwen jamming long, intertwining blues lines, even the goat pasta seems palatable. With the camel-gait rhythms and serpentine improvisations, they sound like the African equivalent of the Grateful Dead in open-ended mode, unhurriedly pursuing the threads of melody as they uncoil.
"Basically," says the band's English manager, Andy Morgan, "Tinariwen is just a jam session that has lasted for 25 years." He's not exaggerating: in Gao, we had managed to purchase some bootleg Tinariwen cassettes dating back to the Eighties, when they were so influential in rousing Tuareg youth to rebellion that the mere possession of one was deemed an act of sedition. Since then, they have won over some of the biggest names in rock, including Robert Plant, who has played with them, and Radiohead's Thom Yorke.
Now Ibrahim spends many nights alone in the desert, communing with the spirits, or djinns, who he says give him inspiration for his music. "Alone in the bush at night, I sometimes get this powerful feeling of a presence around me, and I find I can create things more easily: images and music come into my head, like a muse," he says. "Ali Farka Touré claimed that his muses were the water spirits of the Niger river, and it's a similar thing for me in the desert - there's this other world that is constantly present, and that's what I commune with out there."
The spirit world is very real to the Tuareg, whose origin myth, according to the band's friend and adviser Issa Dicko, involves a sort of spiritual intercourse. "The first Tuareg was a djinn who wanted to possess a woman," Dicko explains. "He was the son of a human and a supernatural being. The other African peoples are wary of the Tuareg, because they know there is this supernatural origin, that they are fundamentally different."
Indeed, while the phrase Kel Tinariwen, from which the band take their name, means "the people of the tenere (desert)", it can also mean "the djinns of the desert" too. This, chuckles Dicko, is because when you see a djinn in the desert, it usually turns out to be a Tuareg. Another name often applied to the Tuareg is Kel Assouf, which means "the people of loneliness".
This was not the case on our second night out here, however, as Tinariwen stage a bush concert for their nomadic tribespeople, who materialise out of the bush like djinns or packed into 4x4s, all driven with the same maniacal glee as ours. In front of a crescent-shaped Berber tent, with the generator puttering gently 50 yards away, the band slip with casual ease into their set, while onlooking Tuareg womenfolk show their approval in blood-curdling ululations.
Lines of tall, elegant youths - some wearing robes and cheche headdress, some in trendy three-quarter-length leather jackets - dance on the mats spread in front of the band, their small, subtle foot movements betokening the infinite restraint that must be required to live in this environment. Patience, after all, comes from God.
For many Tuareg that God is Allah, though their form of Islam has little connection to the Saudi or Pakistani strain of the religion. Indeed, visiting clerics from those countries seeking to convert the Tuareg to their ways have struggled to make any impact at all. "Well, do you see any mosques out here?" asks Dicko rhetorically, explaining that in the desert there is no third-party intercession between a Tuareg Muslim and his God, no imam to instruct or interpret the individual's belief. And anyway, he adds: "They don't use the term 'Islam' here, it's a pejorative term. And if there is a conflict between religion and tradition, tradition will triumph."
This hasn't stopped the government trying to tar the Tuareg with the terrorist brush, in order to gain international approval (and foreign aid) for their prosecution of "the Tuareg problem". It has not worked: the old colonial ties with Europe have worked to the Tuaregs' advantage in eliciting sympathy for their plight, and even the Americans seem to like them. Whether this has anything to do with the rumoured oil deposits in north-eastern Mali, and the possibility of some future Tuareg secession from the Malian state, remains a matter of conjecture.
Back in Kidal, we are taken to meet the rebels' representatives, who helped negotiate the June peace accord. They outline their grievances, many of which are blindingly apparent to any visitor. The general deprivation here is on a scale unimaginable even on the worst of our sink estates, with few reliable utilities, streets strewn with rubbish, and little or no effective hygiene, as I learnt to my cost. Over the 260,000 square miles of the Kidal region, there is not one single yard of proper road. And as I learn from a French volunteer doctor on my way home, there is no hospital for 300 miles in any direction - indeed, the sole medical provision for this vast area, he claims, is one young nurse, who works with her baby on her back.
Small wonder, then, that the rebellion continues, with spurts of violent activity on both sides. Just the day before, the rebel representatives tell us, an attempt was made to blow up the house of the mayor of Tessalit, Ibrahim's home town, a hundred miles north of Kidal.
He won't be swapping his guitar for the gun again, however. He has other duties to carry out, and these days his aim is closer to home than the government in Bamako, focusing as much on the shortcomings of Tuareg society as on their state-inflicted oppression.
"When we were young, we wanted to create a new Tuareg society, devoid of the archaic feudal hierarchies," he explains. "We wanted to establish a meritocracy, so that jobs and positions would be decided by talent rather than birth. We want to educate the population, something the old chiefs had always been against, so that people can live in the modern world and be effective on an international scale, and end our isolation. In Tuareg society, it is the poet's role to tell the truth, even if it makes people uncomfortable."
Join our new commenting forum
Join thought-provoking conversations, follow other Independent readers and see their replies