The decision closely followed Halliburton Company's decision to launch a multi-million dollar publicity campaign aimed at repairing its image tarnished by allegations of financial improprieties.
"The Defence Criminal Investigative Service, the criminal investigative arm of the Office of the Inspector General, is investigating allegations of fraud on the part of Kellogg Brown and Root, including the potential overpricing of fuel delivered to Baghdad by a KBR subcontractor," said the Pentagon official who spoke on condition of anonymity.
Kellogg Brown and Root is a subsidiary of Halliburton, a Houston, Texas-based energy giant which Cheney headed for five years until he joined President George Bush's presidential campaign in 2000.
"The allegations were included in a 13 January, 2004, referral
to the inspector general from the Defence Contract Audit Agency," the official explained.
The Pentagon gave no indication of how long the probe was expected to last.
The company responded by repeating its denials of any wrongdoing, but welcoming the probe as "a step toward resolution of the issue."
"The facts show KBR delivered fuel to Iraq at the best value, the best price and the best terms," said Wendy Hall, director of public relations for the conglomerate.
"We will work with all government agencies to establish that our contracts are not only good for the United States, but also the company is the best and most qualified contractor to perform these difficult and dangerous tasks," she added.
"The overcharging by Halliburton is so extreme that one expert has privately called it highway robbery"
The Pentagon said last month its auditors had been inclined to conclude that a subcontractor employed by Halliburton, which has secured an exclusive oil supply contract in Iraq, might have tricked the US government into paying $61 million more than the fair market price.
The scandal dates back to October, when Democratic lawmakers Henry Waxman and John Dingell wrote to the White House insisting the Texas company might be overcharging the US government between 65 and 75 cents for every gallon of gasoline it shipped to Iraq from Kuwait.
Under the deal, the US government paid Halliburton between 1.62 and 1.70 dollars a gallon of that gasoline, including a 91-to-99-cent transportation fee, according to the members of the House of Representatives.
But Waxman and Dingell said they had been assured by industry experts it was possible to bring gasoline from Kuwait for between 15 cents and 25 cents a gallon.
"The overcharging by Halliburton is so extreme that one expert has privately called it 'highway robbery,'" the lawmakers said.
"It's unfair to accuse Halliburton of paying too much for Kuwaiti fuel when we were told to buy the fuel and given approval to purchase it from a specific supplier"
Hall countered by saying the Army Corps of Engineers had chosen to ship oil from Kuwait for its own reasons, even though it was possible to buy it cheaper from Turkey.
"It's unfair to accuse Halliburton of paying too much for Kuwaiti fuel when we were told to buy the fuel and given approval to purchase it from a specific supplier," said the spokeswoman.
The arrangement is also under investigation by the Kuwaiti
The criminal probe comes on the heels of another damaging imbroglio over allegedly overpriced meals served by Halliburton to the US military in Iraq and Kuwait, which forced the company last week to suspend 140 million dollars worth of disputed invoices.
To counter the avalanche of bad news, Halliburton is running a television commercial in which company President David Lesar argues: "We're serving the troops because of what we know, not who we know."