I live in Arizona and have been through these areas. I would not even think about being restricted from taking photos from the side of the highway, or even from any place that I could walk to for that matter. The thought of obtaining some kind of permit for photographing any kind of landscape scenery would not cross my mind. The only time I've seen any mention of restricted photography on a reservation was when entering an actuall community, ie, houses, hogans, etc., and that was in New Mexico.
Regards,
Dave