Add authorization headers on all requests

Previously we were adding headers only if the
client was challenged.