Dead Sea: "I am a loyal servant of Caesar, and I thank my good fortune for the day that he plucked me as a babe from the shore of the Great Salt Lake."

Now you may think it is possible that instead of the Occom's Razor solution of being a white leg child there is another solution. However Jsawyer elaborates on formspring in an interview associated with Honest Hearts. (Jsawyer wrote and directed Honest Hearts along with creating the white legs).

Dead Sea "plucked from the shores of the great salt lake" and Vulpes are from Utah. How is this so?

Jsaywer: If Dead Sea were a tribal plucked from the shores of the Great Salt Lake and raised by the Legion, what would that make his parents?

Jsawyer gives us a few details here. 1. Dead Sea came from a tribal community from the Great Salt Lake. 2. Jsawyer believes it is quite obvious what group he originated from.
The conclusion here is that indeed the White Legs have been allies with the legion for a while at least long enough for Dead Sea to grow up.

Secondly it appears the Legion has been ordering around the white legs for a while.

"Couldn't let NCR stay in the Divide. Trade route, road the military could use... can't have two roads into the Mojave. Not after the work we'd done to cut off New Canaan, other routes, killing caravans... all we'd done to make the West bleed." - Ulyesses

"Used to be they raided northeast of Caliente, time to time. But then the Desert Rangers fell apart ten years ago, absorbed into the NCR. Eventually the White Legs destroyed the bridges across the Virgin River, over in Arizona. End of discussion." - Stella

With these two combined we can tell that the Legion had taken actions to cut off New Canaan before 2277. We also see the White Legs (who prey on travelers to survive) destroy New Canaan's roadways towards the NCR. This seems to be what Ulysses's is referring to as we never see the Legion cut off New Canaan themselves, and limiting traffic in their territory is directly against the White Leg's own interests.

Many of you may be asking why the legion and white legs would be early allies? They shared enemies particularly the desert rangers who engaged in combat with both factions. They also shared another enemy which was the NCR considering that the NCR Rangers used to fend off White Leg attacks on Interstate 80. They are natural allies.

I decided to make this post since some people didn't seem to think Dead Sea was a white leg or that the white legs and legion interacted before 2277.