Какова этимология фразеологизма: служить верой и правдой?

Служить верой и правдой - это значит служить верно (преданно) и правдиво (честно).

Но ведь это качественные наречия в роли обстоятельства образа действия, которые отвечают на вопрос КАК, а при чем же тут существительные "вера и правда"?

Но не будем забывать, что у Т.п. есть два главных значения: объектный и признаковый, это мы ясно видим из такого простого примера: порезать хлеб ножом (чем? объектное значение) и порезать хлеб ломтиками (как? обстоятельственное значение).

Признаковое значение Т.п. проявляется в данном случае в том, что существительное в Т.п. определяет метод, прием,способ действия, в том числе при абстрактной семантике, например: добиться трудом, подкупить лестью, получить обманом. Также: изогнуться дугой, идти толпой, свернуться калачиком.

Вот и в данном случае веру и правду не следует воспринимать как объектные существительные (с помощью веры и правды), так как они имеют признаковое значение, как и качественные наречия.