With violent attacks by Ansar Bayt al-Maqdis showing no signs of abating, Cairo is looking to Khartoum for a helping hand.
Cairo - For over two years, the Islamist militant group Ansar Bayt al-Maqdis (ABM) has been launching violent attacks against the Egyptian state in North Sinai.
These fighters have been responsible for killing dozens of Egyptians in coordinated bombings, carrying out a handful of assassination attempts, and earlier this month demonstrated a possible change in tactics when suicide attackers blew up a bus killing three South Korean tourists and the Egyptian driver.
Despite regular claims to have killed or captured key militants, the Egyptian government's attempts to quell the violence from this group have so far proven ineffective. There have been over 300 reported attacks since last July, and the run of attacks shows no sign of abating.
With insecurity in the Sinai peninsula deteriorating and Cairo looking short of options, it is little wonder that it has turned to others for help in tackling the Islamist militancy. However its latest choice of partner may raise some eyebrows.
When Cairo met Khartoum
At the start of February, according to Al-Sayyid Al-Badawi, head of the al-Wafd party, an Egyptian delegation returned from a visit to Sudan. There, the officials had agreed a deal with Khartoum over the deployment of joint military patrols along the Egyptian-Sudanese border.
Shortly after that meeting, another higher-level engagement was arranged with the Sudanese Defence Minister Abdel Rahim Mohamed Hussein who flew to Cairo for talks with Field Marshall Abdel Fattah el-Sisi, his counterpart/Egypt's de facto ruler, and General Sedqi Sobhi, second-in-command of the Egyptian armed forces.
Such meetings are hardly typical of Cairo's current relationship with Khartoum. Relations had been warm during the presidency of the Muslim Brotherhood's Mohammed Morsi, with the country's newfound friendship reaching its apogee in September 2012 when Morsi gave a speech to the United Nations expressing support for President Omar al-Bashir.
But Morsi was toppled in July in a military-led movement. And Egypt's military establishment has never been particularly genial towards al-Bashir and has always maintained that the Sudanese president, who has been indicted by the International Criminal Court for crimes against humanity, should stand trial.
Egypt's relations with Sudan therefore cooled once more when Morsi was deposed. The new military-led government soon went about clamping down on the Brotherhood and eventually designated the group a terrorist organisation, leading many senior Brotherhood members to try to flee to Sudan.
In September, a couple of months after Morsi was deposed and Sisi became Egypt's de facto ruler, the military announced that it was expanding its campaign in Sinai in response to ABM's attempted assassination of the Interior Minister Mohammed Ibrahim.
This fit in with Sisi's general approach to Sinai since being appointed head of the Supreme Council of the Armed Forces (SCAF) in August 2012.
Sisi's predecessor, Mohamed Hussein Tantawi, is known to have been against trying to control Sinai militarily, arguing instead for an informal arrangement whereby the state gave militant groups leeway in return for them confining themselves to specific areas and limiting activity. By contrast, Sisi since taking office has put his own stamp on the government's policy in Sinai, favouring a much more aggressive approach.
"The Sinai campaign as it is today is very much Sisi's campaign," says Issandr el-Amrani, the Cairo-based North Africa Project Director for the International Crisis Group.
"Sisi pushed in January 2013 for a more active campaign, where Egypt now takes advantage of its full military deployment quota in Sinai and goes directly after the militant groups."
Unfortunately for Sisi, however, the results have thus far have not been impressive. Although accurate data is difficult to come by, the number of security forces personnel that have been killed may well be higher than the number of militants.
Indeed, in response to the September announcement that the military would step up its campaign in the region, ABM increased its violent activity.
On 11 September, suicide bombers attacked the military intelligence building in Rafah and an armoured personnel carrier at any army checkpoint killing nine soldiers.
Next, the group bombed the el-Tor Security Directorate, attacked the military intelligence facility in Ismailia, and in November claimed the assassination of intelligence officer Lieutenant Colonel Mohammed Mabrouk.
By December militants had also killed 16 in an attack on a security directorate in Mansoura, bombed the Cairo security directorate in Abdeen, and assassinated senior Interior Ministry official Mohamed Said. On 25 January, the Islamist militants used a SA-18 surface-to-air missile to take down an army helicopter, killing five. And now it seems that it may have adopted a new tactic of also targeting tourists.
My enemy's enemy
It is in the face of this inability to stem to violence that Cairo has called on Khartoum for help. Part of the problem with a military campaign against Sinai militancy is that the groups involved often don't have traditional hierarchical command structures and are highly adept at concealing their plans and communications.
ABM, for example, doesn't have a clearly defined organisational structure, and intelligence is not even confident on basic facts about the group - estimates as to its size vary from 500 to 5,000 members.
Meanwhile the insurgency is not confined to just one group - ABM appears to be the most active, but the likes of al-Salafiya al-Jihadiya, the Mujahideen Shura Council, al-Tawhid Wal Jihad, Ansar al Jihad, and the Egypt Free Army also operate in Sinai.
However, amidst all the uncertainty, one thing about the militants in Sinai is relatively well-accepted, which is that the militants get at least some of their arms from local Bedouin smuggling gangs.
These groups are believed to run weapons from Sudan through routes running along the Red Sea, before passing through the Suez towns or across the Gulf of Suez in small boats.
Egyptian intelligence has been particularly concerned by this flow of weapons since the downing of one of its helicopter with a surface-to-air missile.
Military or military border guards are meant to control the roads along these routes, but shipments still appear to be slipping through.
One explanation is that the smugglers are highly skilled at avoiding main roads and border guards; another is that the security forces - those supplied by the state as well as by private oil and gas companies in the region - are drawn from local Bedouin communities and have ties with the smugglers.
These gangs are also known to engage in the trafficking of humans, particularly of Eritrean refugees who they torture and hold for ransom.
But so far, pressure from international human rights organisations on Egypt and Sudan to coordinate and crackdown on traffickers has largely been unsuccessful, partly perhaps because of the two country's ongoing disagreements over issues such as the Renaissance Dam project and the Hala'ib Triangle border.
However, with insecurity in Sinai growing, this reluctance to combine forces now seems to be waning. Whether increased co-operation in tackling arms smugglers will lead to closer diplomatic ties between Egypt and Sudan remains to be seen, but with attack after attack undermining Sisi's control of the Egyptian state, he is hoping he can find a friend in an old rival.
Tom Stevenson is a reporter primarily focused on North Africa. He was previously employed by the Financial Times, and works with a variety of media outlets from Al Jazeera and Financial Times: ThisIsAfrica, to Le Monde Diplomatique and the New Statesman. Follow him on Twitter @TomStevenson_