SharePoint: Invalid SP Host Web Token - RedirectionStatus is CanNotRedirect after CheckRedirectionStatus

This is one of the most confusing errors I have seen, not because the error message is ambiguous, but rather because it was difficult to find the root cause (at least for me anyway).

This error is thrown at the code in sharepoint context filter:

switch (SharePointContextProvider.CheckRedirectionStatus(filterContext.HttpContext, out redirectUrl))

            {

                case RedirectionStatus.Ok:

                    ok = true;

                    break;

                case RedirectionStatus.ShouldRedirect:

                    filterContext.Result = new RedirectResult(redirectUrl.AbsoluteUri);

                    break;

                case RedirectionStatus.CanNotRedirect:

                    throw new Exception("Invalid SP Host Web Tocken");

            }

Redirection status is determined in SharePointContextProvider class at this line:

if (StringComparer.OrdinalIgnoreCase.Equals(httpContext.Request.HttpMethod, "POST"))

            {

                return RedirectionStatus.CanNotRedirect;

            }

Though this sound bit un-intuitive, this error is caused by AnonymousAuthentication property set to the value 'Enabled'.