scratchstack_aws_signature/

signature.rs

//! AWS API request signatures verification routines.
//!
//! This is essentially the server-side complement of [rusoto_signature](https://crates.io/crates/rusoto_signature)
//! but follows the implementation of [python-aws-sig](https://github.com/dacut/python-aws-sig).
//!
//! This implements the AWS [SigV4](http://docs.aws.amazon.com/general/latest/gr/signature-version-4.html)
//! and [SigV4S3](https://docs.aws.amazon.com/AmazonS3/latest/API/sig-v4-authenticating-requests.html)
//! algorithms.
//!
use {
    chrono::{DateTime, Duration, NaiveDate, Utc},
    http::{
        header::{HeaderMap, HeaderValue},
        request::Parts,
        Uri,
    },
    lazy_static::lazy_static,
    log::trace,
    regex::Regex,
    ring::digest::{digest, SHA256},
    scratchstack_aws_principal::PrincipalActor,
    std::{
        any::type_name,
        collections::{BTreeMap, HashMap},
        convert::{From, Into},
        error::Error,
        fmt::{Debug, Display, Formatter, Result as FmtResult},
        future::Future,
        io::{Error as IOError, Write},
        str::from_utf8,
        task::{Context, Poll},
    },
    subtle::ConstantTimeEq,
    tower::{BoxError, Service},
};

use crate::{chronoutil::parse_date_str, hmac::hmac_sha256};

/// Content-Type string for HTML forms
const APPLICATION_X_WWW_FORM_URLENCODED: &str = "application/x-www-form-urlencoded";

/// Algorithm for AWS SigV4
const AWS4_HMAC_SHA256: &str = "AWS4-HMAC-SHA256";

/// String included at the end of the AWS SigV4 credential scope
const AWS4_REQUEST: &str = "aws4_request";

/// Header parameter for the authorization
const AUTHORIZATION: &str = "authorization";

/// Content-Type parameter for specifying the character set
const CHARSET: &str = "charset";

/// Signature field for the access key
const CREDENTIAL: &str = "Credential";

/// Header field for the content type
const CONTENT_TYPE: &str = "content-type";

/// Header parameter for the date
const DATE: &str = "date";

/// Compact ISO8601 format used for the string to sign
const ISO8601_COMPACT_FORMAT: &str = "%Y%m%dT%H%M%SZ";

/// SHA-256 of an empty string.
const SHA256_EMPTY: &str = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855";

/// Signature field for the signature itself
const SIGNATURE: &str = "Signature";

/// Authorization header parameter specifying the signed headers
const SIGNEDHEADERS: &str = "SignedHeaders";

/// Query parameter for delivering the access key
const X_AMZ_CREDENTIAL: &str = "X-Amz-Credential";

/// Query parameter for delivering the date
const X_AMZ_DATE: &str = "X-Amz-Date";

/// Header for delivering the alternate date
const X_AMZ_DATE_LOWER: &str = "x-amz-date";

/// Query parameter for delivering the session token
const X_AMZ_SECURITY_TOKEN: &str = "X-Amz-Security-Token";

/// Header for delivering the session token
const X_AMZ_SECURITY_TOKEN_LOWER: &str = "x-amz-security-token";

/// Query parameter for delivering the signature
const X_AMZ_SIGNATURE: &str = "X-Amz-Signature";

/// Query parameter specifying the signed headers
const X_AMZ_SIGNEDHEADERS: &str = "X-Amz-SignedHeaders";

/// Length of a SigV4 signature string.
const SIGV4_SIGNATURE_LEN: usize = 64;

lazy_static! {
    /// Multiple slash pattern for condensing URIs
    static ref MULTISLASH: Regex = Regex::new("//+").unwrap();

    /// Multiple space pattern for condensing header values
    static ref MULTISPACE: Regex = Regex::new("  +").unwrap();

    /// Pattern for the start of an AWS4 signature Authorization header.
    static ref AWS4_HMAC_SHA256_RE: Regex = Regex::new(r"\s*AWS4-HMAC-SHA256(?:\s+|$)").unwrap();
}

/// Error returned when an attempt at validating an AWS SigV4 signature fails.
#[derive(Debug)]
pub enum SignatureError {
    /// Validation failed due to an underlying I/O error.
    IO(IOError),

    /// The request body used an unsupported character set encoding. Currently only UTF-8 is supported.
    InvalidBodyEncoding {
        /// A message describing the error.
        message: String,
    },

    /// The request signature specified an invalid credential -- either the access key was not specified, or the
    /// credential scope (in the form `<code>_date_/_region_/_service_/aws4_request</code>`) did not match the
    /// expected value for the server.
    InvalidCredential {
        /// A message describing the error.
        message: String,
    },

    /// The secret key contains invalid bytes.
    InvalidSecretKey,

    /// The signature passed in the request did not match the calculated signature value.
    InvalidSignature {
        /// A message describing the error.
        message: String,
    },

    /// The type of signing key is incorrect for this operation.
    InvalidSigningKeyKind {
        /// A message describing the error.
        message: String,
    },

    /// The URI path includes invalid components. This can be a malformed hex encoding (e.g. `%0J`), a non-absolute
    /// URI path (`foo/bar`), or a URI path that attempts to navigate above the root (`/x/../../../y`).
    InvalidURIPath {
        /// A message describing the error.
        message: String,
    },

    /// An HTTP header was malformed -- the value could not be decoded as UTF-8, or the header was empty and this is
    /// not allowed (e.g. the `content-type` header), or the header could not be parsed (e.g., the `date` header is
    /// not a valid date).
    MalformedHeader {
        /// A message describing the error.
        message: String,
    },

    /// A query parameter was malformed -- the value could not be decoded as UTF-8, or the parameter was empty and
    /// this is not allowed (e.g. a signature parameter), or the parameter could not be parsed (e.g., the `X-Amz-Date`
    ///  parameter is not a valid date).
    MalformedParameter {
        /// A message describing the error.
        message: String,
    },

    /// The AWS SigV4 signature was malformed in some way. This can include invalid timestamp formats, missing
    /// authorization components, or unparseable components.
    MalformedSignature {
        /// A message describing the error.
        message: String,
    },

    /// A required HTTP header (and its equivalent in the query string) is missing.
    MissingHeader {
        /// The name of the missing header.
        header: String,
    },

    /// A required query parameter is missing. This is used internally in the library; external callers only see
    /// `MissingHeader`.
    MissingParameter {
        /// The name of the missing query parameter.
        parameter: String,
    },

    /// An HTTP header that can be specified only once was specified multiple times.
    MultipleHeaderValues {
        /// The name of the header.
        header: String,
    },

    /// A query parameter that can be specified only once was specified multiple times.
    MultipleParameterValues {
        /// The name of the query parameter.
        parameter: String,
    },

    /// The timestamp in the request is out of the allowed range.
    TimestampOutOfRange {
        /// The minimum allowed timestamp.
        minimum: DateTime<Utc>,

        /// The maximum allowed timestamp.
        maximum: DateTime<Utc>,

        /// The timestamp received in the request.
        received: DateTime<Utc>,
    },

    /// The access key specified in the request is unknown.
    UnknownAccessKey {
        /// The unknown access key.
        access_key: String,
    },

    /// The signature algorithm requested by the caller is unknown. This library only supports the `AWS4-HMAC-SHA256`
    /// algorithm.
    UnknownSignatureAlgorithm {
        /// The unknown signature algorithm.
        algorithm: String,
    },
}

impl Display for SignatureError {
    fn fmt(&self, f: &mut Formatter) -> FmtResult {
        match self {
            Self::IO(ref e) => Display::fmt(e, f),
            Self::InvalidBodyEncoding {
                message,
            } => write!(f, "Invalid body encoding: {}", message),
            Self::InvalidCredential {
                message,
            } => write!(f, "Invalid credential: {}", message),
            Self::InvalidSecretKey => write!(f, "Invalid secret key"),
            Self::InvalidSignature {
                message,
            } => write!(f, "Invalid request signature: {}", message),
            Self::InvalidSigningKeyKind {
                message,
            } => write!(f, "Invalid signing key kind: {}", message),
            Self::InvalidURIPath {
                message,
            } => write!(f, "Invalid URI path: {}", message),
            Self::MalformedHeader {
                message,
            } => write!(f, "Malformed header: {}", message),
            Self::MalformedParameter {
                message,
            } => write!(f, "Malformed query parameter: {}", message),
            Self::MalformedSignature {
                message,
            } => write!(f, "Malformed signature: {}", message),
            Self::MissingHeader {
                header,
            } => write!(f, "Missing header: {}", header),
            Self::MissingParameter {
                parameter,
            } => write!(f, "Missing query parameter: {}", parameter),
            Self::MultipleHeaderValues {
                header,
            } => write!(f, "Multiple values for header: {}", header),
            Self::MultipleParameterValues {
                parameter,
            } => write!(f, "Multiple values for query parameter: {}", parameter),
            Self::TimestampOutOfRange {
                minimum,
                maximum,
                received,
            } => {
                write!(
                    f,
                    "Request timestamp out of range: minimum={}, maximum={}, received={}",
                    minimum, maximum, received
                )
            }
            Self::UnknownAccessKey {
                access_key,
            } => write!(f, "Unknown access key: {}", access_key),
            Self::UnknownSignatureAlgorithm {
                algorithm,
            } => write!(f, "Unknown signature algorithm: {}", algorithm),
        }
    }
}

impl Error for SignatureError {
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        match self {
            Self::IO(ref e) => Some(e),
            _ => None,
        }
    }
}

impl From<IOError> for SignatureError {
    fn from(e: IOError) -> SignatureError {
        SignatureError::IO(e)
    }
}

/// The types of signing key available.
///
/// See [`SigningKey`] for information on the types of keys and how they are derived.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum SigningKeyKind {
    /// KSecret: the raw secret key.
    KSecret,

    /// KDate: `HMAC_SHA256("AWS4" + KSecret, request_date)`, where `request_date` is the date of
    /// the request in the UTC time zone formatted as "YYYYMMDD".
    KDate,

    /// KRegion: `HMAC_SHA256(KDate, region)`.
    KRegion,

    /// KService: `HMAC_SHA256(KRegion, service)`.
    KService,

    /// KSigning: `HMAC_SHA256(KService, "aws4_request")`.
    KSigning,
}

impl Display for SigningKeyKind {
    fn fmt(&self, f: &mut Formatter) -> FmtResult {
        match self {
            SigningKeyKind::KSecret => write!(f, "KSecret"),
            SigningKeyKind::KDate => write!(f, "KDate"),
            SigningKeyKind::KRegion => write!(f, "KRegion"),
            SigningKeyKind::KService => write!(f, "KService"),
            SigningKeyKind::KSigning => write!(f, "KSigning"),
        }
    }
}

/// An AWS SigV4 key for signing requests.
///
/// Signing keys are derived from a secret key and are used to sign requests made to AWS services.
/// The raw secret key is hashed with other attributes in the request to derive the signing key.
///
/// In the table below, `HMAC_SHA256(key, data)` denotes the HMAC SHA-256 function with the given
/// key and data.
///
/// The stages of derivation are:
/// * [`KSecret`][SigningKeyKind::KSecret]: The raw secret key.
/// * [`KDate`][SigningKeyKind::KDate]: The secret key hashed with the request date in UTC formatted
///   as "YYYYMMDD". This is calculated as `HMAC_SHA256("AWS4" + KSecret, request_date)`.
/// * [`KRegion`][SigningKeyKind::KRegion]: The KDate key hashed with the region name. This is
///   calculated as `HMAC_SHA256(KDate, region)`.
/// * [`KService`][SigningKeyKind::KService]: The KRegion key hashed with the service name. This is
///   calculated as `HMAC_SHA256(KRegion, service)`.
/// * [`KSigning`][SigningKeyKind::KSigning]: The KService key hashed with the string
///   `"aws4_request"`. This is calculated as `HMAC_SHA256(KService, "aws4_request")`.
///
/// The `KSigning` key is the most secure key type. If the key is leaked, an attacker can only sign
/// requests for the given date, region, and service. Key store services should never vend anything
/// other than the `KSigning` key to an application service.
///
/// It is not possible to derive an earlier key from a later key—e.g., you cannot derive a
/// `KRegion` key from a `KService` key. However, you can derive a later key from an earlier key.
#[derive(Clone)]
pub struct SigningKey {
    /// The type of signing key.
    pub kind: SigningKeyKind,

    /// The key itself.
    pub key: Vec<u8>,
}

impl Debug for SigningKey {
    fn fmt(&self, f: &mut Formatter) -> FmtResult {
        f.debug_struct("SigningKey")
            .field("kind", &self.kind)
            .field("key", &format!("<{} bytes>", self.key.len()))
            .finish()
    }
}

impl SigningKey {
    /// Convert this key into the specified kind of key.
    ///
    /// It is safe to call this function with the same kind of key as the existing key; this will
    /// return a copy of the existing key.
    ///
    /// # Errors
    /// This function returns an error if the existing key is
    pub fn try_derive<R, S>(
        &self,
        derived_key_kind: SigningKeyKind,
        req_date: &NaiveDate,
        region: R,
        service: S,
    ) -> Result<Self, SignatureError>
    where
        R: AsRef<str>,
        S: AsRef<str>,
    {
        match derived_key_kind {
            SigningKeyKind::KSigning => Ok(self.to_ksigning_key(req_date, &region, &service)),
            SigningKeyKind::KService => self.try_to_kservice_key(req_date, &region, &service),
            SigningKeyKind::KRegion => self.try_to_kregion_key(req_date, &region),
            SigningKeyKind::KDate => self.try_to_kdate_key(req_date),
            SigningKeyKind::KSecret => match self.kind {
                SigningKeyKind::KSecret => Ok(self.clone()),
                _ => Err(SignatureError::InvalidSigningKeyKind {
                    message: format!("Cannot derive {} key from {} key", derived_key_kind, self.kind),
                }),
            },
        }
    }

    /// Return a KService key given a KService, KRegion, KDate, or KSecret key.
    ///
    /// # Errors
    /// [`SignatureError::InvalidSigningKeyKind`] is returned if derivation to an earlier
    /// kind is attempted, e.g. [`KRegion`][SigningKeyKind::KRegion] into [`KDate`][SigningKeyKind::KDate].
    pub fn try_to_kservice_key<R, S>(&self, req_date: &NaiveDate, region: R, service: S) -> Result<Self, SignatureError>
    where
        R: AsRef<str>,
        S: AsRef<str>,
    {
        match self.kind {
            SigningKeyKind::KService => Ok(self.clone()),
            SigningKeyKind::KRegion | SigningKeyKind::KDate | SigningKeyKind::KSecret => {
                let k_region = self.to_kregion_key(req_date, &region);
                Ok(Self {
                    kind: SigningKeyKind::KService,
                    key: hmac_sha256(&k_region.key, service.as_ref().as_bytes()).as_ref().to_vec(),
                })
            }
            _ => Err(SignatureError::InvalidSigningKeyKind {
                message: format!("Can't derive KService key from {}", self.kind),
            }),
        }
    }

    /// Return a [`KRegion`][SigningKeyKind::KRegion] key given a
    /// [`KRegion`][SigningKeyKind::KRegion], [`KDate`][SigningKeyKind::KDate], or
    /// [`KSecret`][SigningKeyKind::KSecret] key.
    ///
    /// # Errors
    /// [`SignatureError::InvalidSigningKeyKind`] is returned if this is given a
    /// [`KSigning`][SigningKeyKind::KSigning] key.
    pub fn try_to_kregion_key<R>(&self, req_date: &NaiveDate, region: R) -> Result<Self, SignatureError>
    where
        R: AsRef<str>,
    {
        match self.kind {
            SigningKeyKind::KRegion => Ok(self.clone()),
            SigningKeyKind::KDate | SigningKeyKind::KSecret => {
                let k_date = self.to_kdate_key(req_date);
                Ok(Self {
                    kind: SigningKeyKind::KRegion,
                    key: hmac_sha256(&k_date.key, region.as_ref().as_bytes()).as_ref().to_vec(),
                })
            }
            _ => Err(SignatureError::InvalidSigningKeyKind {
                message: format!("Can't derive KRegion key from {}", self.kind),
            }),
        }
    }

    /// Return a [`KDate`][SigningKeyKind::KDate] key given a [`KDate`][SigningKeyKind::KDate] or
    /// [`KSecret`][SigningKeyKind::KSecret] key.
    ///
    /// # Errors
    /// [`SignatureError::InvalidSigningKeyKind`] is returned if this is given a
    /// [`KRegion`][SigningKeyKind::KRegion],
    /// [`KService`][SigningKeyKind::KService], or
    /// [`KSigning`][SigningKeyKind::KSigning] key.
    ///
    /// This function returns an error if given a KRegion, KSigning, or KService key.
    pub fn try_to_kdate_key(&self, req_date: &NaiveDate) -> Result<Self, SignatureError> {
        match self.kind {
            // Already the same type.
            SigningKeyKind::KDate => Ok(self.clone()),

            // key is KSecret == AWS4 + secret key.
            // KDate = HMAC(KSecret + req_date)
            SigningKeyKind::KSecret => {
                let ymd = format!("{}", req_date.format("%Y%m%d"));
                let k_secret_str = match from_utf8(&self.key) {
                    Ok(s) => s,
                    Err(_) => return Err(SignatureError::InvalidSecretKey),
                };
                Ok(SigningKey {
                    kind: SigningKeyKind::KDate,
                    key: hmac_sha256(format!("AWS4{}", k_secret_str).as_bytes(), ymd.as_bytes()).as_ref().to_vec(),
                })
            }

            _ => Err(SignatureError::InvalidSigningKeyKind {
                message: format!("Can't derive KDate key from {}", self.kind),
            }),
        }
    }

    /// Convert this key into the specified kind of key.
    ///
    /// # Panics
    /// This function panics if the existing key cannot be derived into the dervied key kind. Use
    /// [`try_derive`][SigningKey::try_derive] for a non-panicking version.
    pub fn derive<R, S>(&self, derived_key_kind: SigningKeyKind, req_date: &NaiveDate, region: R, service: S) -> Self
    where
        R: AsRef<str>,
        S: AsRef<str>,
    {
        match self.try_derive(derived_key_kind, req_date, &region, &service) {
            Ok(s) => s,
            Err(e) => panic!("{}", e),
        }
    }

    /// Return a [`KSigning`][SigningKeyKind::KSigning] key given a
    /// [`KSigning`][SigningKeyKind::KSigning],
    /// [`KService`][SigningKeyKind::KService],
    /// [`KRegion`][SigningKeyKind::KRegion],
    /// [`KDate`][SigningKeyKind::KDate], or
    /// [`KSecret`][SigningKeyKind::KSecret] key.
    ///
    /// This function is infallible; an equivalent `try_to_signing_key()` method does not exist as
    /// as result.
    pub fn to_ksigning_key<R, S>(&self, req_date: &NaiveDate, region: R, service: S) -> Self
    where
        R: AsRef<str>,
        S: AsRef<str>,
    {
        match self.kind {
            SigningKeyKind::KSigning => self.clone(),
            _ => {
                let k_service = self.to_kservice_key(req_date, &region, &service);
                Self {
                    kind: SigningKeyKind::KSigning,
                    key: hmac_sha256(&k_service.key, AWS4_REQUEST.as_bytes()).as_ref().to_vec(),
                }
            }
        }
    }

    /// Return a [`KService`][SigningKeyKind::KService] key given a
    /// [`KService`][SigningKeyKind::KService],
    /// [`KRegion`][SigningKeyKind::KRegion],
    /// [`KDate`][SigningKeyKind::KDate], or
    /// [`KSecret`][SigningKeyKind::KSecret] key.
    ///
    /// # Panics
    /// This function will panic if given a [`KSigning`][SigningKeyKind::KSigning] key. Use
    /// [`try_to_kservice_key`][SigningKey::try_to_kservice_key] for a non-panicking version.
    pub fn to_kservice_key<R, S>(&self, req_date: &NaiveDate, region: R, service: S) -> Self
    where
        R: AsRef<str>,
        S: AsRef<str>,
    {
        match self.try_to_kservice_key(req_date, &region, &service) {
            Ok(s) => s,
            Err(e) => panic!("{}", e),
        }
    }

    /// Return a [`KRegion`][SigningKeyKind::KRegion] key given a
    /// [`KRegion`][SigningKeyKind::KRegion],
    /// [`KDate`][SigningKeyKind::KDate], or
    /// [`KSecret`][SigningKeyKind::KSecret] key.
    ///
    /// # Panics
    /// This function will panic if given a [`KSigning`][SigningKeyKind::KSigning] or
    /// [`KService`][SigningKeyKind::KService] key. Use
    /// [`try_to_kregion_key`][SigningKey::try_to_kregion_key] for a non-panicking version.
    pub fn to_kregion_key<R>(&self, req_date: &NaiveDate, region: R) -> Self
    where
        R: AsRef<str>,
    {
        match self.try_to_kregion_key(req_date, &region) {
            Ok(s) => s,
            Err(e) => panic!("{}", e),
        }
    }

    /// Return a [`KDate`][SigningKeyKind::KDate] key given a
    /// [`KDate`][SigningKeyKind::KDate], or
    /// [`KSecret`][SigningKeyKind::KSecret] key.
    ///
    /// # Panics
    /// This function will panic if given a [`KSigning`][SigningKeyKind::KSigning],
    /// [`KService`][SigningKeyKind::KService], or
    /// [`KRegion`][SigningKeyKind::KRegion] key. Use
    /// [`try_to_kdate_key`][SigningKey::try_to_kdate_key] for a non-panicking version.
    pub fn to_kdate_key(&self, req_date: &NaiveDate) -> Self {
        match self.try_to_kdate_key(req_date) {
            Ok(s) => s,
            Err(e) => panic!("{}", e),
        }
    }
}

/// A trait bound that describes how we obtain a signing key of a given type given a request. If you need to encapsulate
/// additional data (e.g. a database connection) to look up a key, use this to implement a struct.
pub trait GetSigningKey {}

/// A request for retrieving a signing key from an outside source.
pub struct GetSigningKeyRequest {
    /// The type of signing key to retrieve.
    pub signing_key_kind: SigningKeyKind,

    /// The access key to use to retrieve the signing key.
    pub access_key: String,

    /// An optional session token to use to retrieve the signing key.
    pub session_token: Option<String>,

    /// The date of the request.
    pub request_date: NaiveDate,

    /// The region of the service being accessed.
    pub region: String,

    /// The service being accessed.
    pub service: String,
}

impl<F, E> GetSigningKey
    for dyn Service<GetSigningKeyRequest, Response = (PrincipalActor, SigningKey), Error = E, Future = F>
where
    F: Future<Output = Result<(PrincipalActor, SigningKey), SignatureError>> + Send + Sync,
    E: Into<BoxError>,
{
}

/// A wrapper for a function that retrieves a signing key.
///
/// To construct a `GetSigningKeyFn`, use the [`get_signing_key_fn`] function.
///
/// This implements [`Service<GetSigningKeyRequest>`][tower::Service].
#[derive(Clone, Copy)]
pub struct GetSigningKeyFn<F> {
    f: F,
}

/// Wrap an async function taking a signing request and returns a result into a `GetSigningKey` trait implementation.
///
/// The function signature should look like:
/// ```no_run
/// # use { chrono::{DateTime, Utc}, scratchstack_aws_signature::{SignatureError, SigningKey, SigningKeyKind} };
/// use scratchstack_aws_principal::PrincipalActor;
///
/// async fn get_key(
///     kind: SigningKeyKind,
///     access_key: String,
///     session_token: Option<String>,
///     request_date: DateTime<Utc>,
///     region: String, service: String)
/// -> Result<(PrincipalActor, SigningKey), SignatureError>
/// # { todo!() }
/// ```
pub fn get_signing_key_fn<F>(f: F) -> GetSigningKeyFn<F> {
    GetSigningKeyFn {
        f,
    }
}

impl<F> Debug for GetSigningKeyFn<F> {
    fn fmt(&self, f: &mut Formatter) -> FmtResult {
        f.debug_struct("GetSigningKeyFn").field("f", &format_args!("{}", type_name::<F>())).finish()
    }
}

/// Implementation of a [`Service`] for [`GetSigningKeyFn`].
///
/// To send the request, use the [`call`][Service::call] method.
impl<F, Fut, E> Service<GetSigningKeyRequest> for GetSigningKeyFn<F>
where
    F: FnMut(SigningKeyKind, String, Option<String>, NaiveDate, String, String) -> Fut,
    Fut: Future<Output = Result<(PrincipalActor, SigningKey), E>> + Send + Sync,
    E: Into<BoxError>,
{
    type Response = (PrincipalActor, SigningKey);
    type Error = E;
    type Future = Fut;

    fn poll_ready(&mut self, _cx: &mut Context) -> Poll<Result<(), Self::Error>> {
        Poll::Ready(Ok(()))
    }

    /// Invoke the underlying function to retrieve a signing key.
    ///
    /// # Example
    /// ```rust
    /// # use chrono::{NaiveDate, Utc};
    /// # use scratchstack_aws_signature::{GetSigningKeyRequest, SignatureError, SigningKey, SigningKeyKind, get_signing_key_fn};
    /// # use scratchstack_aws_principal::PrincipalActor;
    /// use tower::Service;
    ///
    /// async fn get_key(
    ///     kind: SigningKeyKind,
    ///     access_key: String,
    ///     session_token: Option<String>,
    ///     request_date: NaiveDate,
    ///     region: String,
    ///     service: String)
    /// -> Result<(PrincipalActor, SigningKey), SignatureError> {
    ///     // Replace with your implementation for obtaining a key.
    ///     let actor = PrincipalActor::user(
    ///         "aws", "123456789012", "/", "user", "AIDAQXZEAEXAMPLEUSER").unwrap();
    ///     let key = SigningKey {
    ///         kind: SigningKeyKind::KSecret,
    ///         key: "wJalrXUtnFEMI/K7MDENG/bPxRfiCYEXAMPLEKEY".as_bytes().to_vec()
    ///     };
    ///     Ok((actor, key.try_derive(kind, &request_date, region, service)?))
    /// }
    ///
    /// let mut get_key_service = get_signing_key_fn(get_key);
    /// let req = GetSigningKeyRequest {
    ///     signing_key_kind: SigningKeyKind::KSigning,
    ///     access_key: "AKIAIOSFODNN7EXAMPLE".to_string(),
    ///     session_token: None,
    ///     request_date: NaiveDate::from_ymd_opt(2021, 1, 1).unwrap(),
    ///     region: "us-east-1".to_string(),
    ///     service: "example".to_string(),
    /// };
    /// # tokio_test::block_on(async {
    /// let (actor, key) = get_key_service.call(req).await.unwrap();
    /// # });
    /// ```
    fn call(&mut self, req: GetSigningKeyRequest) -> Self::Future {
        (self.f)(req.signing_key_kind, req.access_key, req.session_token, req.request_date, req.region, req.service)
    }
}

/// A data structure containing the elements of the request (some client-supplied, some service-supplied) involved in
/// the SigV4 verification process.
///
/// This is typically populated from the HTTP request headers and body by using the
/// [`Request::from_http_request_parts`] method.
#[derive(Debug)]
pub struct Request {
    /// The request method (GET, PUT, POST) (client).
    pub request_method: String,

    /// The URI path being accessed (client).
    pub uri: Uri,

    /// The HTTP headers sent with the request (client).
    pub headers: HeaderMap<HeaderValue>,

    /// The request body (if any) (client).
    pub body: Option<Vec<u8>>,
}

impl Request {
    /// Create a Request from an HTTP request.
    ///
    /// # Example
    /// ```rust
    /// # use scratchstack_aws_signature::Request;
    /// let http_req = http::Request::get("https://example.com")
    ///     .header("X-Amz-Date", "20210101T000000Z")
    ///     .body(())
    ///     .unwrap();
    /// let req = Request::from_http_request_parts(&http_req.into_parts().0, None);
    /// ```
    pub fn from_http_request_parts(parts: &Parts, body: Option<Vec<u8>>) -> Self {
        Self {
            request_method: parts.method.as_str().to_string(),
            uri: parts.uri.clone(),
            headers: parts.headers.clone(),
            body,
        }
    }

    /// Returns a [`GetSigningKeyRequest`] from this request.
    ///
    /// This is used to request a signing key from an external source.
    ///
    /// # Example
    /// ```rust
    /// # use chrono::NaiveDate;
    /// # use scratchstack_aws_signature::{GetSigningKeyRequest, Request, SignatureError, SigningKeyKind};
    /// # let http_req = http::Request::get("https://example.com")
    /// #     .header("X-Amz-Date", "20210101T000000Z")
    /// #     .header("Authorization", "AWS4-HMAC-SHA256 \
    /// # Credential=AKIAIOSFODNN7EXAMPLE/20210101/us-east-1/example/aws4_request, \
    /// # SignedHeaders=host;x-amz-date, \
    /// # Signature=3ea4679d2ecf5a8293e1fb10298c82988f024a2e937e9b37876b34bb119da0bc")
    /// #     .body(())
    /// #     .unwrap();
    /// # let req = Request::from_http_request_parts(&http_req.into_parts().0, None);
    /// let gsk_req = req.to_get_signing_key_request(
    ///     SigningKeyKind::KSigning, "us-east-1", "example").unwrap();
    /// assert_eq!(gsk_req.signing_key_kind, SigningKeyKind::KSigning);
    /// assert_eq!(gsk_req.access_key, "AKIAIOSFODNN7EXAMPLE");
    /// assert_eq!(gsk_req.request_date, NaiveDate::from_ymd_opt(2021, 1, 1).unwrap());
    /// assert_eq!(gsk_req.region, "us-east-1");
    /// assert_eq!(gsk_req.service, "example");
    /// ```
    pub fn to_get_signing_key_request<A1, A2>(
        &self,
        signing_key_kind: SigningKeyKind,
        region: A1,
        service: A2,
    ) -> Result<GetSigningKeyRequest, SignatureError>
    where
        A1: AsRef<str>,
        A2: AsRef<str>,
    {
        Ok(GetSigningKeyRequest {
            signing_key_kind,
            access_key: self.get_access_key(&region, &service)?,
            session_token: self.get_session_token()?,
            request_date: self.get_request_date()?,
            region: region.as_ref().to_string(),
            service: service.as_ref().to_string(),
        })
    }

    /// Retrieve a header value, requiring exactly one value be present.
    ///
    /// # Errors
    /// If the header is missing, a `SignatureError::MissingHeader` error is returned.
    ///
    /// If the header contains multiple values, a `SignatureError::MultipleHeaderValues` error is returned.
    ///
    /// If the header value is not valid UTF-8, a `SignatureError::MalformedHeader` error is returned.
    pub(crate) fn get_header_one<S: Into<String>>(&self, header: S) -> Result<String, SignatureError> {
        let header = header.into();
        let mut iter = self.headers.get_all(&header).iter();
        match iter.next() {
            None => Err(SignatureError::MissingHeader {
                header: header.to_string(),
            }),
            Some(value) => match iter.next() {
                None => match from_utf8(value.as_bytes()) {
                    Ok(ref s) => Ok(s.to_string()),
                    Err(_) => Err(SignatureError::MalformedHeader {
                        message: format!("{} cannot does not contain valid UTF-8", header),
                    }),
                },
                Some(_) => Err(SignatureError::MultipleHeaderValues {
                    header: header.to_string(),
                }),
            },
        }
    }

    /// Return query parameters from the request, normalized, as a `HashMap` of parameter names to the list of
    /// values for that parameter.
    pub(crate) fn get_query_parameters(&self) -> Result<HashMap<String, Vec<String>>, SignatureError> {
        match self.uri.query() {
            Some(s) => normalize_query_parameters(s),
            None => Ok(HashMap::new()),
        }
    }

    /// Retrieve a query parameter, requiring exactly one value be present.
    pub(crate) fn get_query_param_one(&self, parameter: &str) -> Result<String, SignatureError> {
        match self.get_query_parameters()?.get(parameter) {
            None => Err(SignatureError::MissingParameter {
                parameter: parameter.to_string(),
            }),
            Some(values) => match values.len() {
                0 => Err(SignatureError::MissingParameter {
                    parameter: parameter.to_string(),
                }),
                1 => Ok(values[0].to_string()),
                _ => Err(SignatureError::MultipleParameterValues {
                    parameter: parameter.to_string(),
                }),
            },
        }
    }

    /// Get the content type and character set used in the body
    pub(crate) fn get_content_type_and_charset(&self) -> Result<(String, String), SignatureError> {
        let content_type_opts = self.get_header_one(CONTENT_TYPE)?;

        let mut parts = content_type_opts.split(';');
        let content_type = match parts.next() {
            Some(s) => s.trim(),
            None => {
                return Err(SignatureError::MalformedHeader {
                    message: "content-type header is empty".to_string(),
                })
            }
        };

        for option in parts {
            let opt_trim = option.trim();
            let opt_parts: Vec<&str> = opt_trim.splitn(2, '=').collect();

            if opt_parts.len() == 2 && opt_parts[0] == CHARSET {
                return Ok((content_type.to_string(), opt_parts[1].trim().to_lowercase()));
            }
        }

        Ok((content_type.to_string(), "utf-8".to_string()))
    }

    /// The canonicalized URI path for a request.
    pub(crate) fn get_canonical_uri_path(&self) -> Result<String, SignatureError> {
        canonicalize_uri_path(self.uri.path())
    }

    /// The canonical query string from the query parameters.
    ///
    /// This takes the query_string from the request, merges it with the body if the request has a body of type
    /// `application/x-www-form-urlencoded`, and orders the parameters.
    pub(crate) fn get_canonical_query_string(&self) -> Result<String, SignatureError> {
        let query_parameters = self.get_query_parameters()?;
        let mut results = Vec::new();

        for (key, values) in query_parameters.iter() {
            // Don't include the signature itself.
            if key != X_AMZ_SIGNATURE {
                for value in values.iter() {
                    results.push(format!("{}={}", key, value));
                }
            }
        }

        if let Ok((content_type, charset)) = self.get_content_type_and_charset() {
            if content_type == APPLICATION_X_WWW_FORM_URLENCODED {
                if charset != "utf-8" && charset != "utf8" {
                    return Err(SignatureError::InvalidBodyEncoding {
                        message: format!("application/x-www-form-urlencoded body uses unsupported charset {}", charset),
                    });
                }

                // Parse the body as a URL string
                let body_utf8 = match &self.body {
                    None => "",
                    Some(body) => match from_utf8(body) {
                        Ok(s) => s,
                        Err(_) => {
                            return Err(SignatureError::InvalidBodyEncoding {
                                message: "application/x-www-form-urlencoded body contains invalid UTF-8 characters"
                                    .to_string(),
                            });
                        }
                    },
                };

                let body_normalized = normalize_query_parameters(body_utf8)?;
                for (key, values) in body_normalized.iter() {
                    for value in values.iter() {
                        results.push(format!("{}={}", key, value));
                    }
                }
            }
        }

        results.sort_unstable();
        Ok(results.join("&"))
    }

    /// The parameters from the Authorization header (only -- not the query parameter). If the Authorization header is not present
    /// or is not an AWS SigV4 header, an Err(SignatureError) is returned.
    pub(crate) fn get_authorization_header_parameters(&self) -> Result<HashMap<String, String>, SignatureError> {
        let auth_headers = self.headers.get_all(AUTHORIZATION);
        let mut parameters_opt: Option<&str> = None;

        let mut auth_iter = auth_headers.iter();
        loop {
            match auth_iter.next() {
                None => break,
                Some(auth_header) => {
                    if let Ok(auth_header) = auth_header.to_str() {
                        if let Some(captures) = AWS4_HMAC_SHA256_RE.captures(auth_header) {
                            if parameters_opt.is_some() {
                                return Err(SignatureError::MultipleHeaderValues {
                                    header: AUTHORIZATION.to_string(),
                                });
                            }

                            parameters_opt = Some(auth_header.split_at(captures.get(0).unwrap().end()).1);
                            trace!("parameters_opt set to {:?}; captures={:?}", parameters_opt, captures);
                        } else {
                            trace!("Not SigV4: {:?}", auth_header);
                        }
                    }
                }
            }
        }

        match parameters_opt {
            None => Err(SignatureError::MissingHeader {
                header: AUTHORIZATION.to_string(),
            }),
            Some(parameters) => {
                if parameters.is_empty() {
                    Err(SignatureError::MalformedSignature {
                        message: "invalid Authorization header: missing parameters".to_string(),
                    })
                } else {
                    let result = split_authorization_header_parameters(parameters)?;
                    if !result.contains_key(CREDENTIAL) {
                        Err(SignatureError::MalformedSignature {
                            message: "invalid Authorization header: missing Credential".to_string(),
                        })
                    } else if !result.contains_key(SIGNATURE) {
                        Err(SignatureError::MalformedSignature {
                            message: "invalid Authorization header: missing Signature".to_string(),
                        })
                    } else if !result.contains_key(SIGNEDHEADERS) {
                        Err(SignatureError::MalformedSignature {
                            message: "invalid Authorization header: missing SignedHeaders".to_string(),
                        })
                    } else {
                        Ok(result)
                    }
                }
            }
        }
    }

    /// Returns a sorted dictionary containing the signed header names and their values.
    pub(crate) fn get_signed_headers(&self) -> Result<BTreeMap<String, Vec<Vec<u8>>>, SignatureError> {
        // See if the signed headers are listed in the query string.
        let qp_result = self.get_query_param_one(X_AMZ_SIGNEDHEADERS);
        let ah_result;
        let ah_signedheaders;

        let signed_headers = match qp_result {
            Ok(ref sh) => sh,
            Err(e) => match e {
                SignatureError::MissingParameter {
                    ..
                } => {
                    ah_result = self.get_authorization_header_parameters();
                    match ah_result {
                        Err(e) => return Err(e),
                        Ok(ref ahp) => {
                            ah_signedheaders = ahp.get(SIGNEDHEADERS);
                            match ah_signedheaders {
                                None => {
                                    return Err(SignatureError::MalformedSignature {
                                        message: "invalid Authorization header: missing SignedHeaders".to_string(),
                                    })
                                }
                                Some(headers) => headers,
                            }
                        }
                    }
                }
                _ => return Err(e),
            },
        };

        // Header names are separated by semicolons.
        let parts: Vec<String> = signed_headers.split(';').map(|s| s.to_string()).collect();

        // Make sure the signed headers list is canonicalized. For security reasons, we consider it an error if it isn't.
        let mut canonicalized = parts.clone();
        canonicalized.sort_unstable_by(|a, b| a.to_lowercase().partial_cmp(&b.to_lowercase()).unwrap());

        if parts != canonicalized {
            return Err(SignatureError::MalformedSignature {
                message: "SignedHeaders is not canonicalized".to_string(),
            });
        }

        let mut result = BTreeMap::<String, Vec<Vec<u8>>>::new();
        for header in canonicalized.iter() {
            let mut header_values = Vec::new();
            let v_iter = self.headers.get_all(header).iter();

            for value in v_iter {
                match from_utf8(value.as_bytes()) {
                    Ok(value) => header_values.push(value.as_bytes().to_vec()),
                    Err(_) => {
                        return Err(SignatureError::MalformedHeader {
                            message: format!("Header {} contains invalid UTF-8 characters", header),
                        })
                    }
                }
            }
            if header_values.is_empty() {
                return Err(SignatureError::MissingHeader {
                    header: header.to_string(),
                });
            }

            result.insert(header.to_string(), header_values);
        }

        Ok(result)
    }

    /// The date of the request.
    pub(crate) fn get_request_date(&self) -> Result<NaiveDate, SignatureError> {
        let timestamp = self.get_request_timestamp()?;
        Ok(timestamp.naive_utc().date())
    }

    /// The timestamp of the request.
    ///
    /// This returns the first value found from:
    ///
    /// * The `X-Amz-Date` query parameter.
    /// * The `X-Amz-Date` HTTP header.
    /// * The `Date` HTTP header.
    ///
    /// The timestamp _should_ be in ISO 8601 `YYYYMMDDTHHMMSSZ` format
    /// without milliseconds (_must_ per [AWS documentation](https://docs.aws.amazon.com/general/latest/gr/sigv4-date-handling.html)).
    /// However, the AWS SigV4 test suite includes a variety of date formats,
    /// including RFC 2822, RFC 3339, and ISO 8601. This routine allows all
    /// of these formats.
    ///
    /// This is unlikely to be useful in regular code; it is exposed for testing purposes.
    ///
    /// # Errors
    /// If the `X-Amz-Date`` query parameter is present but is not a valid timestamp,
    /// [`SignatureError::MalformedParameter`] is returned.
    ///
    /// If the `X-Amz-Date` query parameter is missing and the `X-Amz-Date` header is present but is not a valid
    /// timestamp, [`SignatureError::MalformedHeader`] is returned.
    ///
    /// If the `X-Amz-Date` query parameter and `X-Amz-Date` header are missing and the `Date` header is present
    /// but is not a valid timestamp, [`SignatureError::MalformedHeader`] is returned.
    ///
    /// If none of the above are present, [`SignatureError::MissingHeader`] is returned.
    ///
    /// # Example
    /// ```rust
    /// use chrono::{DateTime, NaiveDate, NaiveDateTime, NaiveTime, Utc};
    /// use http::Request;
    /// use scratchstack_aws_signature::Request as SigRequest;
    ///
    /// let req = Request::get("https://example.com")
    ///     .header("X-Amz-Date", "20210101T000000Z")
    ///     .body(())
    ///     .unwrap();
    /// let req = SigRequest::from_http_request_parts(&req.into_parts().0, None);
    /// let expected = DateTime::<Utc>::from_naive_utc_and_offset(
    ///     NaiveDateTime::new(
    ///         NaiveDate::from_ymd_opt(2021, 1, 1).unwrap(),
    ///         NaiveTime::from_hms_opt(0, 0, 0).unwrap()),
    ///     Utc
    /// );
    /// assert_eq!(req.get_request_timestamp().unwrap(), expected);
    /// ```
    pub fn get_request_timestamp(&self) -> Result<DateTime<Utc>, SignatureError> {
        // It turns out that unrolling this logic is the most straightforward way to return sensible error messages.

        match self.get_query_param_one(X_AMZ_DATE) {
            Ok(date_str) => parse_date_str(
                &date_str,
                SignatureError::MalformedParameter {
                    message: "X-Amz-Date is not a valid timestamp".to_string(),
                },
            ),
            Err(e) => match e {
                SignatureError::MissingParameter {
                    ..
                } => match self.get_header_one(X_AMZ_DATE_LOWER) {
                    Ok(date_str) => parse_date_str(
                        &date_str,
                        SignatureError::MalformedHeader {
                            message: "X-Amz-Date is not a valid timestamp".to_string(),
                        },
                    ),
                    Err(e) => match e {
                        SignatureError::MissingHeader {
                            ..
                        } => match self.get_header_one(DATE) {
                            Ok(date_str) => parse_date_str(
                                &date_str,
                                SignatureError::MalformedHeader {
                                    message: "Date is not a valid timestamp".to_string(),
                                },
                            ),
                            Err(e) => Err(e),
                        },
                        _ => Err(e),
                    },
                },
                _ => Err(e),
            },
        }
    }

    /// The scope of the credentials to use, as calculated by the service's region and name, but using the timestamp
    /// of the request.
    ///
    /// The result is a string in the form `YYYYMMDD/region/service/aws4_request`.
    pub(crate) fn get_credential_scope<A1, A2>(&self, region: A1, service: A2) -> Result<String, SignatureError>
    where
        A1: AsRef<str>,
        A2: AsRef<str>,
    {
        let ts = self.get_request_timestamp()?;
        let date = ts.date_naive().format("%Y%m%d");
        Ok(format!("{}/{}/{}/{}", date, region.as_ref(), service.as_ref(), AWS4_REQUEST))
    }

    /// The access key used to sign the request.
    ///
    /// If the credential scope does not match our expected credential scope, a SignatureError is returned.
    pub(crate) fn get_access_key<A1, A2>(&self, region: A1, service: A2) -> Result<String, SignatureError>
    where
        A1: AsRef<str>,
        A2: AsRef<str>,
    {
        let qp_result = self.get_query_param_one(X_AMZ_CREDENTIAL);
        let auth_headers;

        let credential = match qp_result {
            Ok(ref c) => c,
            Err(e) => match e {
                SignatureError::MissingParameter {
                    ..
                } => {
                    auth_headers = self.get_authorization_header_parameters()?;
                    match auth_headers.get(CREDENTIAL) {
                        Some(c) => c,
                        None => {
                            trace!("auth_headers={:?}", auth_headers);
                            return Err(SignatureError::MalformedSignature {
                                message: "invalid Authorization header: missing Credential".to_string(),
                            });
                        }
                    }
                }
                _ => return Err(e),
            },
        };

        let parts: Vec<&str> = credential.splitn(2, '/').collect();
        if parts.len() != 2 {
            return Err(SignatureError::InvalidCredential {
                message: "Malformed credential".to_string(),
            });
        }

        let access_key = parts[0];
        let request_scope = parts[1];
        let server_scope = self.get_credential_scope(region, service)?;
        if request_scope == server_scope {
            Ok(access_key.to_string())
        } else {
            Err(SignatureError::InvalidCredential {
                message: format!("Invalid credential scope: Expected {} instead of {}", server_scope, request_scope),
            })
        }
    }

    /// The session token sent with the access key.
    ///
    /// Session tokens are used only for temporary credentials. If a long-term credential was used, the result
    /// is `Ok(None)`.
    pub(crate) fn get_session_token(&self) -> Result<Option<String>, SignatureError> {
        let qp_result = self.get_query_param_one(X_AMZ_SECURITY_TOKEN);

        match qp_result {
            Ok(token) => Ok(Some(token)),
            Err(e) => match e {
                SignatureError::MissingParameter {
                    ..
                } => match self.get_header_one(X_AMZ_SECURITY_TOKEN_LOWER) {
                    Ok(token) => Ok(Some(token)),
                    Err(e) => match e {
                        SignatureError::MissingHeader {
                            ..
                        } => Ok(None),
                        _ => Err(e),
                    },
                },
                _ => Err(e),
            },
        }
    }

    /// The signature passed into the request.
    pub(crate) fn get_request_signature(&self) -> Result<String, SignatureError> {
        match self.get_query_param_one(X_AMZ_SIGNATURE) {
            Ok(sig) => Ok(sig),
            Err(e) => match e {
                SignatureError::MissingParameter {
                    ..
                } => {
                    let ah: HashMap<String, String> = self.get_authorization_header_parameters()?;
                    match ah.get(SIGNATURE) {
                        Some(c) => Ok(c.to_string()),
                        None => Err(SignatureError::MalformedSignature {
                            message: "invalid Authorization header: missing Signature".to_string(),
                        }),
                    }
                }
                _ => Err(e),
            },
        }
    }

    /// The AWS SigV4 canonical request given parameters from the HTTP request, as outlined in the
    /// [AWS documentation](http://docs.aws.amazon.com/general/latest/gr/sigv4-create-canonical-request.html).
    ///
    /// The canonical request is:
    /// ```text
    ///     request_method + '\n' +
    ///     canonical_uri_path + '\n' +
    ///     canonical_query_string + '\n' +
    ///     signed_headers + '\n' +
    ///     sha256(body).hexdigest()
    /// ```
    pub(crate) fn get_canonical_request(&self) -> Result<Vec<u8>, SignatureError> {
        let mut result = Vec::<u8>::new();
        let mut header_keys = Vec::<u8>::new();
        let canonical_uri_path = self.get_canonical_uri_path()?;
        let canonical_query_string = self.get_canonical_query_string()?;
        let body_hex_digest = self.get_body_digest()?;

        result.write_all(self.request_method.as_bytes())?;
        result.push(b'\n');
        result.write_all(canonical_uri_path.as_bytes())?;
        result.push(b'\n');
        result.write_all(canonical_query_string.as_bytes())?;
        result.push(b'\n');

        let mut is_first_key = true;

        for (key, values) in self.get_signed_headers()? {
            let key_bytes = key.as_bytes();

            result.write_all(key_bytes)?;
            result.push(b':');

            let mut is_first_value = true;
            for ref value in values {
                if is_first_value {
                    is_first_value = false;
                } else {
                    result.push(b',');
                }

                let value_collapsed_space = MULTISPACE.replace_all(from_utf8(value).unwrap(), " ");
                result.write_all(value_collapsed_space.as_bytes())?;
            }
            result.push(b'\n');

            if is_first_key {
                is_first_key = false;
            } else {
                header_keys.push(b';');
            }

            header_keys.write_all(key_bytes)?;
        }

        result.push(b'\n');
        result.append(&mut header_keys);
        result.push(b'\n');

        match self.get_content_type_and_charset() {
            Ok((content_type, _)) if content_type == APPLICATION_X_WWW_FORM_URLENCODED => {
                result.write(SHA256_EMPTY.as_bytes())?
            }
            _ => result.write(body_hex_digest.as_bytes())?,
        };

        Ok(result)
    }

    /// The SHA-256 hex digest of the body.
    pub(crate) fn get_body_digest(&self) -> Result<String, SignatureError> {
        match &self.body {
            None => Ok(SHA256_EMPTY.to_string()),
            Some(body) => Ok(hex::encode(digest(&SHA256, body).as_ref())),
        }
    }

    /// The string to sign for the request.
    pub(crate) fn get_string_to_sign<A1, A2>(&self, region: A1, service: A2) -> Result<Vec<u8>, SignatureError>
    where
        A1: AsRef<str>,
        A2: AsRef<str>,
    {
        let mut result = Vec::new();
        let timestamp = self.get_request_timestamp()?;
        let credential_scope = self.get_credential_scope(region, service)?;
        let canonical_request = self.get_canonical_request()?;
        trace!("Credential scope: {:?}", credential_scope);
        trace!("Canonical request: {:?}", from_utf8(canonical_request.as_ref()));

        result.write_all(AWS4_HMAC_SHA256.as_bytes())?;
        result.push(b'\n');
        write!(&mut result, "{}", timestamp.format(ISO8601_COMPACT_FORMAT))?;
        result.push(b'\n');
        result.write_all(credential_scope.as_bytes())?;
        result.push(b'\n');
        result.write_all(hex::encode(digest(&SHA256, &canonical_request).as_ref()).as_bytes())?;

        Ok(result)
    }
}

/// Return the expected signature for a request.
pub fn sigv4_get_expected_signature<A1, A2>(
    req: &Request,
    signing_key: &SigningKey,
    region: A1,
    service: A2,
) -> Result<String, SignatureError>
where
    A1: AsRef<str>,
    A2: AsRef<str>,
{
    let k_signing = signing_key.to_ksigning_key(&(req.get_request_date()?), &region, &service);
    let string_to_sign = req.get_string_to_sign(&region, &service)?;
    trace!("String to sign: {:?}", from_utf8(string_to_sign.as_ref()));

    Ok(hex::encode(hmac_sha256(&k_signing.key, &string_to_sign).as_ref()))
}

/// Verify a SigV4 request at a particular point-in-time. This verifies that the request timestamp is not beyond the
/// allowed timestamp mismatch against the specified point-in-time, and that the request signature matches our expected
/// signature.
///
/// This is mainly for unit testing. For general purpose use, use `sigv4_verify`.
///
/// # Errors
/// If the request timestamp is outside the allowed timestamp mismatch, a `SignatureError::TimestampOutOfRange` error
/// is returned.
///
/// If the request signature does not match the expected signature, a `SignatureError::InvalidSignature` error is
/// returned.
///
/// # Panics
/// If the expected signature string is not 64 bytes long, this function will panic. This should never happen.
pub fn sigv4_verify_at<A1, A2>(
    req: &Request,
    signing_key: &SigningKey,
    server_timestamp: &DateTime<Utc>,
    allowed_mismatch: Option<Duration>,
    region: A1,
    service: A2,
) -> Result<(), SignatureError>
where
    A1: AsRef<str>,
    A2: AsRef<str>,
{
    if let Some(mm) = allowed_mismatch {
        let req_ts = req.get_request_timestamp()?;
        let min_ts = server_timestamp.checked_sub_signed(mm).unwrap_or(*server_timestamp);
        let max_ts = server_timestamp.checked_add_signed(mm).unwrap_or(*server_timestamp);

        if req_ts < min_ts || req_ts > max_ts {
            return Err(SignatureError::TimestampOutOfRange {
                minimum: min_ts,
                maximum: max_ts,
                received: req_ts,
            });
        }
    }

    let request_sig_str = req.get_request_signature()?;
    let expected_sig_str = sigv4_get_expected_signature(req, signing_key, &region, &service)?;

    if request_sig_str.len() != SIGV4_SIGNATURE_LEN {
        return Err(SignatureError::InvalidSignature {
            message: format!("Expected {}-byte signature instead of {}", SIGV4_SIGNATURE_LEN, request_sig_str.len()),
        });
    }

    if expected_sig_str.len() != SIGV4_SIGNATURE_LEN {
        panic!("Expected signature is not {SIGV4_SIGNATURE_LEN} bytes long");
    }

    let mut request_sig: [u8; SIGV4_SIGNATURE_LEN] = [0; SIGV4_SIGNATURE_LEN];
    let mut expected_sig: [u8; SIGV4_SIGNATURE_LEN] = [0; SIGV4_SIGNATURE_LEN];

    request_sig.copy_from_slice(request_sig_str.as_bytes());
    expected_sig.copy_from_slice(expected_sig_str.as_bytes());

    // Cryptographically sensitive: we must compare every byte and not short-circuit this, or the
    // we can be vulnerable to timing attacks. `ct_eq` comes from the `Subtle::ConstantTimeEq` trait.
    if expected_sig.ct_eq(&request_sig).unwrap_u8() == 0 {
        Err(SignatureError::InvalidSignature {
            message: format!("Expected {} instead of {}", expected_sig_str, request_sig_str),
        })
    } else {
        Ok(())
    }
}

/// Verify a SigV4 request. This verifies that the request timestamp is not beyond the
/// allowed timestamp mismatch against the current time, and that the request signature matches our expected
/// signature.
///
/// # Errors
/// If the request timestamp is outside the allowed timestamp mismatch, a `SignatureError::TimestampOutOfRange` error
/// is returned.
///
/// If the request signature does not match the expected signature, a `SignatureError::InvalidSignature` error is
/// returned.
///
/// # Panics
/// If the expected signature string is not 64 bytes long, this function will panic. This should never happen.
pub fn sigv4_verify<A1, A2>(
    req: &Request,
    signing_key: &SigningKey,
    allowed_mismatch: Option<Duration>,
    region: A1,
    service: A2,
) -> Result<(), SignatureError>
where
    A1: AsRef<str>,
    A2: AsRef<str>,
{
    sigv4_verify_at(req, signing_key, &Utc::now(), allowed_mismatch, region, service)
}

/// Indicates whether the specified byte is RFC3986 unreserved -- i.e., can be represented without being
/// percent-encoded, e.g. `'?'` -> `'%3F'`.
///
/// # Example
/// ```rust
/// # use scratchstack_aws_signature::is_rfc3986_unreserved;
/// assert!(is_rfc3986_unreserved(b'a'));
/// assert!(!is_rfc3986_unreserved(b' '));
/// ```
pub const fn is_rfc3986_unreserved(c: u8) -> bool {
    c.is_ascii_alphanumeric() || c == b'-' || c == b'.' || c == b'_' || c == b'~'
}

/// Normalize the path component according to RFC 3986.  This performs the following operations:
/// * Alpha, digit, and the symbols `-`, `.`, `_`, and `~` (unreserved characters) are left alone.
/// * Characters outside this range are percent-encoded.
/// * Percent-encoded values are upper-cased (`%2a` becomes `%2A`)
/// * Percent-encoded values in the unreserved space (`%2D`, `%2E`, `%30`-`%39`, `%5F`, `%41`-`%5A`, `%61`-`%7A`,
///   `%7E`) are converted to normal characters.
/// * Plus-encoded spaces (`+`) are converted to `%20`.
///
/// # Errors
/// If a percent encoding is incomplete or is invalid, `SignatureError::InvalidURIPath` is returned.
///
/// # Example
/// ```rust
/// # use scratchstack_aws_signature::normalize_uri_path_component;
/// assert_eq!(normalize_uri_path_component("a b").unwrap(), "a%20b");
/// assert_eq!(normalize_uri_path_component("%61b").unwrap(), "ab");
/// ```
pub fn normalize_uri_path_component(path_component: &str) -> Result<String, SignatureError> {
    let path_component = path_component.as_bytes();
    let mut i = 0;
    let result = &mut Vec::<u8>::new();

    while i < path_component.len() {
        let c = path_component[i];

        if is_rfc3986_unreserved(c) {
            result.push(c);
            i += 1;
        } else if c == b'%' {
            if i + 2 >= path_component.len() {
                // % encoding would go beyond end of string; return an error.
                return Err(SignatureError::InvalidURIPath {
                    message: "Incomplete hex encoding".to_string(),
                });
            }

            let hex_digits = &path_component[i + 1..i + 3];
            match hex::decode(hex_digits) {
                Ok(value) => {
                    assert_eq!(value.len(), 1);
                    let c = value[0];

                    if is_rfc3986_unreserved(c) {
                        result.push(c);
                    } else {
                        // Rewrite the hex-escape so it's always upper-cased.
                        write!(result, "%{:02X}", c)?;
                    }
                    i += 3;
                }
                Err(_) => {
                    return Err(SignatureError::InvalidURIPath {
                        message: format!("Invalid hex encoding: {:?}", hex_digits),
                    })
                }
            }
        } else if c == b'+' {
            // Plus-encoded space. Convert this to %20.
            result.write_all(b"%20")?;
            i += 1;
        } else {
            // Character should have been encoded.
            write!(result, "%{:02X}", c)?;
            i += 1;
        }
    }

    Ok(from_utf8(result.as_slice()).unwrap().to_string())
}

/// Normalizes the specified URI path, removing redundant slashes and relative path components.
///
/// # Errors
/// If the path is not absolute, a `SignatureError::InvalidURIPath` error is returned.
///
/// If any component of the path cannot be normalized per [`normalize_uri_path_component`], a
/// `SignatureError::InvalidURIPath` error is returned.
///
/// # Example
/// ```rust
/// # use scratchstack_aws_signature::canonicalize_uri_path;
/// assert_eq!(canonicalize_uri_path("/a//b/../c").unwrap(), "/a/c");
/// assert_eq!(canonicalize_uri_path("/a/b/./c/../").unwrap(), "/a/b/");
/// ```
pub fn canonicalize_uri_path(uri_path: &str) -> Result<String, SignatureError> {
    // Special case: empty path is converted to '/'; also short-circuit the usual '/' path here.
    if uri_path.is_empty() || uri_path == "/" {
        return Ok("/".to_string());
    }

    // All other paths must be abolute.
    if !uri_path.starts_with('/') {
        return Err(SignatureError::InvalidURIPath {
            message: format!("Path is not absolute: {}", uri_path),
        });
    }

    // Replace double slashes; this makes it easier to handle slashes at the end.
    let uri_path = MULTISLASH.replace_all(uri_path, "/");

    // Examine each path component for relative directories.
    let mut components: Vec<String> = uri_path.split('/').map(|s| s.to_string()).collect();
    let mut i = 1; // Ignore the leading "/"
    while i < components.len() {
        let component = normalize_uri_path_component(&components[i])?;

        if component == "." {
            // Relative path: current directory; remove this.
            components.remove(i);

            // Don't increment i; with the deletion, we're now pointing to the next element in the path.
        } else if component == ".." {
            // Relative path: parent directory.  Remove this and the previous component.

            if i <= 1 {
                // This isn't allowed at the beginning!
                return Err(SignatureError::InvalidURIPath {
                    message: format!("Relative path entry '..' navigates above root: {}", uri_path),
                });
            }

            components.remove(i - 1);
            components.remove(i - 1);

            // Since we've deleted two components, we need to back up one to examine what's now the next component.
            i -= 1;
        } else {
            // Leave it alone; proceed to the next component.
            components[i] = component;
            i += 1;
        }
    }

    assert!(!components.is_empty());
    match components.len() {
        1 => Ok("/".to_string()),
        _ => Ok(components.join("/")),
    }
}

/// Normalize the query parameters by normalizing the keys and values of each parameter and return a `HashMap` mapping
/// each key to a _vector_ of values (since it is valid for a query parameters to appear multiple times).
///
/// The order of the values matches the order that they appeared in the query string -- this is important for SigV4
/// validation.
///
/// Keys and values are normalized according to the rules of [`normalize_uri_path_component`].
///
/// # Errors
/// If any key or value cannot be normalized as a URI path component, a `SignatureError::InvalidURIPath` error is
/// returned.
///
/// # Example
/// ```rust
/// # use scratchstack_aws_signature::normalize_query_parameters;
/// let result = normalize_query_parameters("a=1&b=2&a=3&c=4").unwrap();
///
/// assert_eq!(result.get("a").unwrap(), &vec!["1", "3"]);
/// assert_eq!(result.get("b").unwrap(), &vec!["2"]);
/// assert_eq!(result.get("c").unwrap(), &vec!["4"]);
/// ```
pub fn normalize_query_parameters(query_string: &str) -> Result<HashMap<String, Vec<String>>, SignatureError> {
    if query_string.is_empty() {
        return Ok(HashMap::new());
    }

    // Split the query string into parameters on '&' boundaries.
    let components = query_string.split('&');
    let mut result = HashMap::<String, Vec<String>>::new();

    for component in components {
        if component.is_empty() {
            // Empty component; skip it.
            continue;
        }

        // Split the parameter into key and value portions on the '='
        let parts: Vec<&str> = component.splitn(2, '=').collect();
        let key = parts[0];
        let value = if parts.len() > 1 {
            parts[1]
        } else {
            ""
        };

        // Normalize the key and value.
        let norm_key = normalize_uri_path_component(key)?;
        let norm_value = normalize_uri_path_component(value)?;

        // If we already have a value for this key, append to it; otherwise, create a new vector containing the value.
        if let Some(result_value) = result.get_mut(&norm_key) {
            result_value.push(norm_value);
        } else {
            result.insert(norm_key, vec![norm_value]);
        }
    }

    Ok(result)
}

/// Split `Authorization`` header parameters from key=value parts into a HashMap.
///
/// # Errors
/// If the header is missing an '=' in what should be a `key=value` pair, `SignatureError::MalformedSignature` error
/// is returned.
///
/// If the header contains duplicate keys, a `SignatureError::MalformedSignature` error is returned.
pub(crate) fn split_authorization_header_parameters(
    parameters: &str,
) -> Result<HashMap<String, String>, SignatureError> {
    trace!("split_authorization_header_parameters: parameters={:?}", parameters);
    let mut result = HashMap::<String, String>::new();
    for parameter in parameters.split(',') {
        let parts: Vec<&str> = parameter.splitn(2, '=').collect();
        if parts.len() != 2 {
            return Err(SignatureError::MalformedSignature {
                message: "invalid Authorization header: missing '='".to_string(),
            });
        }

        let key = parts[0].trim_start().to_string();
        let value = parts[1].trim_end().to_string();

        if result.contains_key(&key) {
            return Err(SignatureError::MalformedSignature {
                message: format!("invalid Authorization header: duplicate field {}", key),
            });
        }

        result.insert(key, value);
    }

    Ok(result)
}