Après l’enlèvement de Soumaïla Cissé, le président de l’Union pour la République et la démocratie (URD), le 25 mars, alors qu’il battait campagne pour les législatives dans sa région de Niafunké, Boubou Cissé, alors Premier ministre, est approché par Moustapha Limam Chafi. Le Mauritanien, ancien conseiller spécial de Blaise Compaoré, est réputé pour ses réseaux au sein des groupes djihadistes dans le nord du Mali, et a déjà été impliqué dans plusieurs libérations d’otages occidentaux au Sahel. Au Premier ministre, Chafi glisse un nom : celui de Chérif Ould Attaher, un Arabe du Tilemsi et ex-membre du Mouvement pour l’unicité et le jihad en Afrique de l’Ouest (Mujao) qui a, lui aussi, déjà pris part à plusieurs négociations pour faire libérer des otages ces dernières années.
Le 5 avril, Boubou Cissé signe un mandat officiel lui donnant autorisation de « conduire toutes les démarches, formalités et de conclure tous les actes nécessaires » à la libération de Soumaïla Cissé. Chérif Ould Attaher demande à être accompagné dans sa mission par le colonel Mamadou Lamine Konaré, alors conseiller du Premier ministre sur les questions de renseignement. La mission des deux hommes est validée par Ibrahim Boubacar Keïta et son Premier ministre dans le plus grand secret, notamment pour éviter que les services français et la direction générale de la sécurité d’Etat (DGSE) malienne n’en soient informés.
Le 8 avril, Chérif Ould Attaher et le colonel Konaré embarquent dans un vol spécial à destination de Gao. Une fois là-bas, ils prennent un pick-up et partent durant quelques jours dans le désert en direction de Kidal. Sur place, ils rencontrent Sedane Ag Hita, le numéro deux du groupe de soutien à l’islam et aux musulmans (GSIM). Celui-ci leur confirme que Soumaïla Cissé est entre leurs mains et qu’il va bien, même si sa santé est fragile. Ag Hita leur remet une feuille manuscrite comportant deux revendications en échange de la libération de Cissé : la libération de membres du GSIM détenus par les autorités maliennes et le paiement d’une rançon de 2 millions d’euros.
De retour à Bamako, les deux hommes font un compte-rendu à Boubou Cissé, qui en fait de même auprès d’Ibrahim Boubacar Keïta. Avant de poursuivre les discussions, les autorités maliennes souhaitent obtenir une preuve de vie. Fin avril, Ould Attaher et Konaré repartent voir les ravisseurs. Après plusieurs jours d’attente, une vidéo de Soumaïla Cissé leur est transmise. Eux leur remettent des médicaments pour l’otage, qui continuera à en recevoir dans les mois qui suivent par différents canaux. La négociation est presque ficelée mais, entre-temps, le général Moussa Diawara, le patron de la DGSE malienne, a eu vent de la médiation. Il peste de ne pas en avoir été informé et réclame que le dossier revienne à ses services. Les services français sont, eux aussi, informés. Ils ne veulent pas entendre parler d’une libération de Soumaïla Cissé avant celle de Sophie Pétronin. Pour ne pas froisser l’opinion publique française, probablement, mais aussi parce qu’ils souhaitent s‘adosser au cas Cissé et ne pas apparaître en première ligne, notamment pour le paiement d’une rancon. Ils plaident donc pour qu’Ahmada Ag Bibi, député de Kidal, reprenne le dossier de Soumaïla Cissé en collaboration avec les services maliens.
Ce notable touareg leur sert déjà d’intermédiaire dans le dossier Pétronin. Il connaît Iyad Ag Ghali depuis les années 1990 et a déjà joué un rôle dans les négociations pour la libération des otages d’Areva et de Vinci, enlevés en 2010 au Niger. En parallèle, le président Emmanuel Macron appelle Ibrahim Boubacar Keïta pour lui demander de confier l’affaire à ces nouveaux intermédiaires. Sous pression francaise, le chef d’Etat malien s’exécute. Ag Bibi et la DGSE malienne, à travers le colonel Ibrahima Sanogo, son chef du renseignement antiterroriste, sont désormais aux manettes.
Ces changements d’interlocuteurs et la jonction avec le cas Pétronin retardent la libération de Soumaïla Cissé. Alors qu’elle était initialement fixée à 2 millions d’euros, la rancon passe à 10 millions d’euros. Ibrahim Boubacar Keïta valide quand même l’opération. La libération des otages se précise pour la fin du mois d’août mais, le 18, le président malien est renversé par un coup d’Etat. Ce tsunami politique à Bamako retarde les ultimes tractations. Une fois investis, le 25 septembre, le président Bah N’Daw et le vice-président Assimi Goïta donnent leur feu vert à l’opération. La rancon est payée, sans que l’on sache pour l’instant d’où proviennent les fonds, et environ 180 personnes inculpées de terrorisme sont libérées par les autorités maliennes, les 3 et 4 octobre.
Alors que l’accord semble presque conclu, le GSIM fait monter les enchères à la dernière minute en exigeant des libérations supplémentaires, qui seront finalement accordées. Au total, 204 prisonniers sont remis en liberté. Parmi eux figurent des responsables de l’attaque de l’hôtel Radisson Blu à Bamako en 2005. Les autorités burkinabè n’ont pas été consultées, et les libérations ont été faites sans être formalisées par un décret.
