Elytron HTTP Digest Nonce Handling - Design

Version 2

    This design is to consider a new nonce handling strategy for HTTP Digest authentication for the HTTP Digest authentication mechanism being provided under issue [ELY-286] HTTP Digest Authentication - JBoss Issue Tracker

     

    For the purpose of this development I will be referring to the latest proposed standard RFC 7616 - HTTP Digest Access Authentication, the main changes from RFC 2617 - HTTP Authentication: Basic and Digest Access Authentication  are: -

    • Support for two new algorithms SHA2-256 as mandatory and SHA2-512/256 as backup as well as defining algorithm negotiation.
      • The MD5 algorithm is supported but for backwards compatibility.
    • Introduces username hashing mainly for privacy reasons.
    • Adds various internationisation considerations.
    • Deprecates backwards compatibility with RFC 2069.

     

    The RFCs for HTTP Digest authentication make use of nonces however the exact handling of nonces is left to the implementation of the mechanisms with some guidance offered by the RFC.

     

    The design here is for the default and only nonce handling strategy to be used by the mechanism, however at a later point additional strategies could be defined with different  characteristics for use in different situations.

     

    Objectives

    • Replay protection to prevent a previously intercepted response being replayed regardless of the resource being accessed.
    • Avoiding risk of denial of service attacks based on initial challenges.
    • Supporting concurrent requests from clients.

    Proposed Implementation

    I am proposing a solution that is based on having no internal storage of issued nonces but an internal record of all nonces used for the duration that they could be replayed against the server.

     

    This offers a trade off of no resource overhead for unauthenticated clients triggering a high demand for resources on the server by asking for a lot of newly created nonces whilst using server side resources for each successfully authenticated request.

     

    There is one exception to this, if authentication fails due to the realm being unavailable the nonce should be cached with the set of used nonces as the request could have contained a valid response

    so could be used in a replay if the realm becomes available before the nonce expires.

     

    The solution is based on structuring a nonce similar to how nonces are described here RFC 7616 - HTTP Digest Access Authentication,, however instead of relying on the EType header that we can not rely on for all requests within the server we will be cross checking against previously received nonces to detect replays.

     

    Configuration Parameters

    This solution will make use of the following configuration parameters which can be used to tune the resources required to store the history of used nonces offset against how often nonces are reissued to the client.

     

    ParameterDescription
    Initial Validity PeriodHow long  is a server issued nonce valid for before the first time we see it.
    Next Nonce ThresholdHow long before a nonce expires should a server start issuing the next nonce in the sequence and how soon should it start accepting the next nonce.
    Secret SizeHow large should the server side secret be.
    ScopeThe state used for handling nonces can be scoped to the Factory, Application, or Session
    Maximum Time ThresholdThe maximum time an expired nonce should be considered for continuing the sequence.
    Nonce Hash AlgorithmThe hash algorithm to use when hashing the nonce data with the secret, this can be independent of and stronger than the hash actually used by the mechanism.
    Nonce Session TimeAfter a nonce was last used how long in minutes is it valid for, where nonce counts are in use allows an actively used nonce to be kept alive beyond it's initial validity.
    Track Maximum RangesThe maximum number of ranges to track in the nonce count gap tracking array, once the limit is reached lower ranges will be dropped.

     

    Server Side Secret

    Using a SecureRandom source a server side secret will be generated, this will be held in the configured scope for the mechanism and will never be sent to the client, this secret will be used to 'sign' nonces sent to the client so when they are received back from the client it can be verified that the nonce was actually issued by the server.

     

         secret = <SecureRandom bytes>

     

    Other options could be considered later such as obtaining the actual secret from configuration, possibly from a cache or even reading from file to ensure the same secret is used across a cluster.

     

    Additionally we could consider re-creating the secret at certain intervals but that would most likely incur an overhead of caching previous secrets and cross referencing whether the current or previous secret should be used.

     

    Nonce Structure

     

    The overall nonce will be base64 encoded however the internal structure will be: -

     

         nonce = <counter + sequence + create_time_stamp + H(counter + sequence + create_time_stamp + secret)>

     

    Will consider if we use fixed size fields or delimiters but that is not the main point here.

     

    The fields contained within the nonce are: -

     

    FieldDescription
    counterA counter associated to the scope and incremented as each new nonce is issued, should two nonces be issued at the same time they will still have a unique counter.
    sequenceA newly issued nonce will always have a sequence of '0', as subsequent nonces are issued to the client the sequence will be incremented by 1 each time.
    create_time_stampThe system time in milliseconds that the nonce was created.
    H(counter + sequence + create_time_stamp + secret)A hash using the configured nonce hash algorithm of the counter, sequence, timestamp, and the secret.

     

    Tracking Used Nonces

    A used nonce will be stored in a Map keyed on the nonce and associated with the following: -

    • Time last used (Minute precision should be sufficient)
    • ScheduledFuture for removal
    • Array representing ranges on unseen nonce counts.

     

    At the outset the array contents would be: -

     

    { 1, Integer.MAX_VALUE} 
    

     

    Say we see nonce counts 1, and 3 the resulting array would become: -

     

    { 2, 2, 4, Integer.MAX_VALUE}
    

     

    We may then see a 7 so the array becomes: -

     

    { 2, 2, 4, 6, 8, Integer.MAX_VALUE}
    

     

    Searching to find an applicable range we can perform a binary search, we have two possibilities for the search: -

    1. Search the lower ranges to find two values our nonce count is between and then check the upper bound of that range.
    2. Search the ranges directly.

    Identifying the seen nonce count fits within a range confirms to us it can be used but we also need to know which range so we can modify it.

    • If the nonce count is the lower bound that can be incremented by one.
    • If the nonce count is the upper bound that can be incremented by one.
      • In both these cases it could mean that range is exhaused and can be removed.
    • If the nonce count falls within a range that range is now going to need to be split into two ranges with the used nonce count excluded.

     

    This leads onto free space within the array, it is likely to be better to grow more proactively rather than adding two elements per request, additionally as ranges are exhausted we likely don't want to be allocating reduced size arrays immediately.  On that final example say we now receive nonce counts 4, 5, and 6 the middle range is no longer needed: -

    { 2{ 2, 2, 4, 6, 8, I

    { 2, 2, -1, -1, 8, Integer.MAX_VALUE } 
    

    T

    The problem with this however is searches will now be hitting dead ranges, also when we want to split a range we are going to want to search for the optimum empty range above or below the current range being split to adjust the array contents.  We could move the free space to the end.

     

    { 2, 2, 8, Integer.MAX_VALUE, -1, -1}
    

     

    As the last range is the largest it could be reasonable to assume the majority of range splits would apply to the last range.

     

    To optimise the search the first element of the array could track the number of ranges in use, this means we can also save some housekeeping operations.

     

    { 2, 2, 2, 8, Integer.MAX_VALUE, 8, Integer.MAX-VALUE }
    

     

    So it contains two ranges 2..2, and 8..Integer.MAX_VALUE - although the last two elements contain values we know they are meaningless as they are in the third currently unused range.

     

    For backwards compatibility with older clients RFC2069 will remain supported, in the case of messages received without a nonce count an empty range of unseen counts will be stored, i.e. we assume immediately all nonce counts are used.  We can still choose to operate in two modes, firstly we can still treat it as a session being kept alive by each request, this is risky for replays but may be applicable in some situations - alternatively we can still make strictly single use.  For performance reasons it will be recommended to use a client that support RFC2617 or later so that a single nonce can be reused with unique nonce counts.

     

    Subsequent Nonce Generation

    The data portion of a subsequent nonce will be generated in a predictable way, the reason for this is so that if concurrent requests are received from a single client all responses will return consistent results.  The overall nonce however will still not be predictable due to the final hash including the server side secret.

     

    The subsequent nonce will be generated by making the following adjustments to the data contained within the nonce.

    • Re-use the counter unmodified from the previous nonce.
    • Take the sequence from the previous nonce and increment by 1.
    • Take the create_time_stamp and increment by the validity period.

     

    If there has been a gap in client activity but the create_time_stamp of the nonce received is still within the maximum time threshold of the above steps do not produce a valid nonce they will be repeated until a valid nonce is generated.

     

    Once the data fields have been calculated the hash portion of the nonce will be created based on the new values.

     

    Nonce Validation

    Within the HTTP Digest mechanism nonce validation happens after validation of the incoming response, this is so that a client can be notified that their response was potentially valid but it being rejected due to an invalid nonce so assuming the client does have the credentials it can generate a new response using a new nonce without having to prompt the user for their credentials again.

     

    The following validation will occur: -

    • Check formatting of nonce received.
    • Taking the data portion of the received nonce can the hashed portion be re-created using the secret held by the mechanism?
    • Is the current time after the create_time_stamp but before the create_time_stamp + Validity Period? or Is the sequence greater than 0 and the current time before the create_time_stamp but not before create_time_stamp - Next Nonce Threshold?
    • Do we already have this nonce along with the same nonce count in the cache of used nonces?

     

    If the nonce validation fails but the response validation was a success a subsequent challenge will be sent to the client indicating that the the nonce is stale, if subsequent nonce can be generated it will be - otherwise a new nonce starting with a sequence of 0 will be created and used instead.

     

    Advanced Subsequent Nonce

    Where the RFC2617 or later form of Digest is in use (Which can be detected by the client using the nonce count field) it is possible to pro-actively inform the client the next nonce the client should switch to using.

     

    If the nonce received from the client is valid (and authentication was successful) but the received nonce will expire within the configured 'next nonce threshold' then in the reply sent to the client a subsequent nonce will be generated and passed to the client using the next nonce header.

     

    If the client has multiple concurrent requests in parallel these will continue to be processed provided the other nonce validation rules are not broken.  As the subsequent nonce is generated based on the previous nonce all requests should be prompted to switch to the same nonce.

     

     

    If All Else Fails

    If any of the following situations occur a new nonce will be issued starting the sequence back at 0: -

    • Validation against the secret fails.
    • Badly formatted nonce.
    • An old previously valid nonce received but older than the maximum time threshold.
    • The sequence reaches Integer.MAX_VALUE

     

    Scopes

    The state for handling nonces can be stored in one of three different scopes, the state to store will be the generated secret along with the counter associated with the secret and the tracking of used nonces.  It is absolutely essential that these items are stored in the same scope to prevent replays taking advantage of the different scopes.

     

    ScopeDescription
    FactoryThe state is stored within the mechanism factory, all applications using the same factory will share the same state.  Where multiple applications use the same scope it could mean a much larger store of history to search and update for each request.  The state will be specific to a single node.
    ApplicationThe state will be scoped to the application being accessed, each application will then have it's own secret and own history of historic nonces.  As each application has it's own secret knowledge of the other applications history is not required.  The size of the history state is now reduced down just for the requests for a specific application.  This state will also be for a single node.
    SessionStoring the state in sessions will mean that sessions need to be supported and authentication will cause the creation of a session.  The size of the state being manipulated will be much smaller.  The session is also potentially replicatable across a cluster although appropriate replication settings will be required to avoid possibly replay windows for used nonces.  Invalidation of a session will mean that any client will be treated as a new client for a subsequent request and will be issued with a new nonce with a sequence back at 0.