The following is a script from "Common Enemy" which aired on Nov. 22, 2015. Lara Logan is the correspondent. Max McClellan, producer.
In the aftermath of the attacks in Paris, France stepped up its air campaign against the Islamic State.
But on the ground in Iraq, the fight has been left to the Kurds, Iraqi security forces and Shiite militias backed by Iran -- some of those same Shiite militias that were killing and wounding American soldiers during the Iraq War just a few years ago. Today, they have a common enemy in the Islamic State.
It's a difficult and awkward arrangement and there aren't many Americans who are more familiar with it than Major General Peter Gersten, a combat veteran from the Iraq War and now one of the top commanders in this fight.
(Gen. Gersten: "We're in the Combined Joint Operations Center...")
General Gersten took us into the war room in Baghdad, where Iraqis and Americans have been sitting side-by-side for more than a year. Thousands of calls for U.S. and coalition airstrikes have come through here.
Lara Logan: Who is bringing the intelligence that feeds these calls?
Gen. Gersten: We have our own intelligence. We have national intelligence. Everything's fusing in different parts of this building and coming to this strike cell and that's where it's checked and coordinated and approved.
On their screens, live feeds from drones that record every minute of the war and scenes from inside Islamic State-held territory, like this one in a town in western Iraq that Gersten and the Iraqis were watching on September 11th this year.
These are ISIS photographs that General Gersten confirmed were from the same scene. In the town square, 12 Islamic State fighters were preparing to execute this man.
Gen. Gersten: They brought small children and brought 'em to the very front of the crowd. And we sat there helplessly. Calls are coming for a strike. We strike now. Let's go after these 12 individuals. They're going to assassinate this person in front of these children. But we can't because they're children. And we had to watch that.
Moments later the execution took place and the victim lay dead, shot by this man, once in the head, then once more in the body. The American drone stayed with the 12 terrorists.
Gen. Gersten: We followed them as they got into three vehicles and drove out of town. And then they made a mistake, because they always make mistakes. And they, all 12, went into a building on the side of a river. And none of those 12 came out.
Gersten told us this is the airstrike that destroyed that building. It's one of more than 5,000 strikes to support the Iraqi army and Kurdish Forces on the ground over the past year. Yet the Islamic State remains entrenched in its strongholds.
Fallujah was the first city to fall in January 2014. Five months later, Mosul, the country's second largest city fell and the Iraqi army collapsed. Islamic State terrorists quickly advanced toward the Iraqi capital, attempting to encircle Baghdad, infiltrating towns and villages right on the outskirts.
With the Iraqi army largely absent from the fight, it was the Shiite militias, backed by Shiite Iran, Iraq's neighbor to the east, that helped push back the Sunni militants of the Islamic State.
One of the Shiite militias that led the counterattack was the Badr Organization -- now officially part of what's known here as the Popular Mobilization Forces. After months of negotiation they agreed to take us up to the front, a treacherous journey we could not have made without them.
For more than a year, the Islamic State held this ground. Badr fighters told us they fought hard to win it back. Now, through desolate landscape scarred by recent battles, they were taking us toward their frontline just outside Fallujah, an impenetrable Islamic State base for almost two years.
Lara Logan: We're going up to the part of the frontline that is closest to Fallujah. We're told that this point is only a mile away and the biggest threat here is from snipers.
It was in Fallujah in 2004 that 82 Americans died, fighting the bloodiest battle of the Iraq War.
Ali Abrawi, the local commander here, showed us a tunnel Islamic State terrorists used to move undetected from American planes and he showed us unexploded bombs they left behind. This river, he said, is the distance between his fighters and the enemy.
Lara Logan: This is a lot of spent rounds, huh? Look at all this.
Brig General (translator): That's about two months.
Lara Logan: This is about two months of shooting?
Lara Logan: So they used the buildings for cover and they come and attack in small groups?
Brig General (translator): Sometimes they fight from the houses. And sometimes they use the trees and the bushes for cover.
The task that lies ahead of trying to liberate Fallujah and Mosul, the major cities still occupied by the enemy, is daunting. But it remains the eventual goal of their leader, who was among the first to rush into battle against the Islamic State or Daesh, as they call it here.
Hadi al-Amiri (translator): I consider myself a fighter defending my country against Daesh with all that I can.
Hadi al-Amiri is one of the most powerful and feared men in Iraq, known for his brutal tactics against Iraq's Sunni population in the civil war that followed the U.S. invasion.
This is him as a young man, in footage from Iranian TV. He spent much of his life in exile in Iran as a commander in the resistance against Saddam Hussein, and he still has deep ties to the Iranian regime.
Hadi al-Amiri (translator): Everyone who fights alongside us is a friend. Everyone who fights alongside Daesh is an enemy.
Lara Logan: So that means America in this fight is your friend?
Hadi al-Amiri (translator): No, only if they seriously fight Daesh.
Lara Logan: Are you saying they're not seriously fighting Daesh now?
Hadi al-Amiri (translator): Frankly, well below expectations.
Gen. Gerten: We have struck thousands and thousands of enemy positions. We are giving a considerable amount of equipment, effort, money and training to securing the government of Iraq.
Lara Logan: The perception among Iraqis is that you're in the fight, but you're not really in the fight, not 100 percent.
Gen. Gerten: We have thousands of coalition members here. I have spent 25 years in this region. I would find that hard to believe that we're not interested in the safety and security of the government of Iraq.
It's part of General Gersten's job to know where Hadi al-Amiri's men are on the battlefield. Amiri commands the largest Shiite force in the country, seen here in images they captured this spring as they helped secure a major victory, winning back Saddam Hussein's hometown, Tikrit, from the Islamic State. But they're fighting without weapons or support from the U.S.
Amiri's fighters, like these men at a training camp we visited deep in the south of the country, are among more than 100,000 volunteers that make up the Popular Mobilization Forces. Men who rushed into the fight in the days after the Iraqi army fell apart. Now, hardened in battle, they come to camps like this to continue their training in between deployments to the frontline.
Hadi al-Amiri (translator): These young people took their weapons and defended Baghdad from being overrun. Then they carried on and returned vast areas of Iraq to government control. Everyone accepts now that if it wasn't for them, not only Baghdad, but the entirety of Iraq would have been overrun by Daesh.
Lara Logan: How many men have been lost so far?
Hadi al-Amiri (translator): A significant number, more than 2,000 martyrs in this war.
More than 2,000 militia fighters and thousands more Iraqi police and soldiers. The faces of the dead line the streets of the capital, stretching for blocks. It's one of the first things we noticed as we drove around the city. Many of these men killed by ISIS fighters using a weapon so lethal, General Gersten told us the Americans have given it a name: Frankentruck.
Gen. Gersten: These Frankentrucks are something out of a movie, something you see in a science-fiction movie. These are vehicles that they've welded metal plates to, loaded them with high explosives, put a suicide bomber inside of them and set themselves off. That is their precision weapon.
Lara Logan: And they used six to eight of those in one operation?
Gen. Gersten: Lara, they use typically six to eight of those in every operation they do, as high as 15.
This is what's believed to be a Frankentruck racing toward Kurdish troops in the battle to retake the town of Sinjar last week, before the soldiers managed to hit it just in time. Kurdish forces do most of the fighting in the north. And the Iraqi army, now reorganized fights with the Shiite militias in the rest of the country. But with raids like this one in northern Iraq a few weeks ago, the U.S. is still being drawn deeper into this war. American Special Operations soldiers helped rescue 70 Iraqi hostages, but lost one of their own -- the first American to die in combat here since the end of the Iraq War.
Lara Logan: Would you like to see America having a greater role on the ground in Iraq?
Lara Logan: No? (over Amiri shaking his head)
Amiri told us he would not welcome a return to the days when thousands of U.S. troops were deployed here.
Hadi al-Amiri (translator): Why do you need to bring American soldiers to die on Iraqi ground? We have young Iraqi men who are able to defend their country if they had the equipment. It would be shameful for us.
On our trip with Amiri's men, they delivered food donated by private citizens to Shiite forces along the frontline, eager to portray this as an army of all Iraq's people. But there are very few Sunnis among their ranks, and the Shiite militias have been accused of revenge attacks against Sunni civilians in areas they've liberated. Amiri's own sectarian past was detailed in a U.S. diplomatic cable we read to him, including allegations that he may have personally ordered attacks on up to 2,000 Sunnis during the civil war that followed the U.S. invasion.
Lara Logan: "One of his preferred methods of killing allegedly involved using a power drill to pierce the skulls of his adversaries."
Hadi al-Amiri (translator): If you have the slightest evidence of even one attack carried out by us against the Sunnis, you can blame me.
Lara Logan: So are you saying there is no evidence or are you saying it's not true?
Hadi al-Amiri (translator): Absolutely. I say it never happened.
When Hadi al-Amiri's men are in the fight, U.S. warplanes are not allowed to bomb in support of them. American weapons and airpower are reserved for those under the control of the Iraqi government. And we were stunned when General Gersten told us only a small percentage of the Shiite militias fighting the Islamic State meet the requirements for U.S. support.
Gen. Gersten: Roughly we're running around 15-20 percent of forces that are aligned to the government of Iraq, we've identified those forces.
Lara Logan: Only 15-20 percent?
Gen. Gersten: Fifteen percent to 20 percent. The rest are not aligned officially to the government of Iraq.
For now, these forces are focused on the Islamic State, and we didn't find anyone who thinks ISIS can be defeated without these militias. But with every piece of ground they help win back, their power and influence grows.
Lara Logan: Isn't there a price you pay for that down the line?
Gen. Gersten: Those are policy decisions that are above what I'm doing here now, here to destroy Daesh.
Lara Logan: You have guys in this fight who were killing and wounding Americans in the war that you fought in. Does that not trouble you?
Gen. Gersten: I'm very concerned. That is something that we work every day. Right now the focus is on destroying Daesh. We have a common enemy, a common cancer that we have to go after at this point. Otherwise, it will continue to affect all the world.