2nd version -Re: New Proposal for Section 11.1.3 Replay

[Chris Lonvick <clonvick%cisco.com@localhost>]

Hi Joseph,

On Wed, 14 May 2003, Joseph Galbraith wrote:

> > Naturally, if an
> >    attacker does attempt to replay a captured packed before the peers
> >    have rekeyed, then the receiver of the duplicate packet will see that
> >    it has the sequence number of a packet that has already been received
> >    and will discard it.
>
> The packet sequence number is not actually sent on
> the wire, but is maintained independantly by each
> side.
>
> If an attacker replays a captured packet, it will
> be input into the mac routines with the next valid
> sequence number.  Since that is not the sequence
> number that was used in the original computation of
> the mac, it will show up as a MAC error.
>
> Thanks, Chris, for compiling these.
>
> - Joseph

Got it.  Is what I've revised below better?

Also, would anyone object if I took the first paragraph out of this
section (Replay) and turned it into the basis for a separate section on
the importance of a good PRNG?  That would be consistent with the
discussion on the list to emphasize it's importance.

Thanks,
Chris

======================================================================

11.1.3 Replay

   This protocol binds each session key to the session by including
   random data that is specific to the session in the hash used to
   produce session keys.  If the random data here (e.g., DH parameters)
   are pseudo-random then the PRNG should be cryptographically secure
   (i.e., its next output not easily guessed, even when knowing all
   previous outputs) and, furthermore, the PRNG should be seeded with some
   truly random inputs, or as random as can be available.  In any case,
   the amount of entropy available to a given client or server sometimes
   may be less than what is needed to run the protocol, in which case
   either one must resort to PRNGs anyways or refuse to run the protocol.
   In practice implementors will generally rely on some PRNG.  RFC 1750
   [1750] contains more discussion on this.

   The use of a MAC other than 'none' provides integrity and
   authentication.  In addition, the transport protocol provides a
   unique session identifier (bound in part to pseudo-random data that is
   part of the algorithm and key exchange process) that can be used by
   higher level protocols to bind data to a given session and prevent
   replay of data from prior sessions. For example, the authentication
   protocol uses this to prevent replay of signatures from previous
   sessions.  Because public key authentication exchanges are
   cryptographically bound to the session (i.e., to the initial key
   exchange) they cannot be successfully replayed in other sessions.
   Note that the session ID can be made public without harming the
   security of the protocol.

   If two session happen to have the same session ID [hash of key
   exchanges] then packets from one can be replayed against the other.
   It must be stressed that the chances of such an occurrence are,
   needless to say, minimal when using modern cryptographic methods.
   This is all the more so true when specifying larger hash function
   outputs and DH parameters.

   Replay detection using monotonically increasing sequence numbers as
   input to the MAC, or HMAC in some cases, is described in RFC 2085
   [2085], RFC 2246 [2246], RFC 2743 [2743], RFC 1964 [1964], RFC 2025
   [2025], and RFC 1510 [1510].  The underlying construct is discussed in
   RFC 2104 [2104].  Essentially a different sequence number in each
   packet ensures that at least this one input to the MAC function will
   be unique and will provide a nonrecurring MAC output that is not
   predictable to an attacker.  If the session stays active long enough,
   however, this sequence number will wrap.  This event may provide an
   attacker an opportunity to replay a previously recorded packet with an
   identical sequence number but only if the peers have not rekeyed since
   the transmission of the first packet with that sequence number.  If
   the peers have rekeyed, then the replay will be detected as the MAC
   check will fail.  For this reason, it must be emphasized that peers
   MUST rekey before a wrap of the sequence numbers.  Naturally, if an
   attacker does attempt to replay a captured packet before the peers
   have rekeyed, then the receiver of the duplicate packet will not be
   able to validate the MAC and it will be discarded.  The reason that
   the MAC will fail is because the receiver will formulate a MAC based
   upon the packet contents, the shared secret, and the expected sequence
   number.  Since the replayed packet will not be using that expected
   sequence number (the sequence number of the replayed packet will have
   already been passed by the receiver) then the calculated MAC will not
   match the MAC received with the packet.


[1750] Eastlake, D., Crocker, S. and J. Schiller, "Randomness
       Recommendations for Security", RFC 1750, December 1994.

[2246] TLS
[2085] IPsec AH
[2104] HMAC
[2743] GSS-API
[1964] The KerberosV GSS-API mechanism
[2025] SPKM
[1510] Kerberos V


---Notes---

[RJA:  I imagine that a sequence number does help preclude replay attacks,
[RJA:  but I was hoping that someone else had actually done some analysis
[RJA:  that we could cite to justify the claim that this MAC combined with
[RJA:  this kind of sequence numbering would actually provide replay
[RJA:  attack prevention.

---Joseph---vv
If no one knows of something to cite here, I'm
not sure what to do at this point?

Baring someone stepping forward witht the requested
citation, what should we do?  I'd like to move forward.
---Joseph---^^

---Nico---vv
Er, this is a time-honored technique.  Examples of protocols that
support the use of sequence numbers as a replay detection technique are:

 - GSS-API (generally) [RFC2743]
    - The KerberosV GSS-API mechanism (specifically) [RFC1964]
    - The Simple Public-Key GSS-API Mechanism (SPKM) (specifically)
[RFC2025]

 - Kerberos V [RFC1510]

 - TLS 1.0 [RFC2246]

Need I go on?  Probably not.  Each of those documents makes reference to
the use of sequence numbers for replay and out-of-sequence detection.
---Nico---^^

---Ran---vv
Generic comment (applies to above and other places):
        I'd rather delete a claim that the WG can't clearly justify
        than have this document accidentally make a claim that later
        turns out to be inaccurate or misleading.
---Ran--^^

---Heikki---vv
I for one believe replay protection is an important property for the
protocol and I would like this claim to remain in the documents.

IpSec AH uses sequence number with HMAC for replay protection (rfc2085),
so does TLS (rfc2246).

HMAC security considerations are discussed in rfc2104. The document
describes security of the construct in general, and I believe the replay
protection scheme is a small subset compared to that, given the so many
bits an attacker can affect (sequence number, padding).

How about "to our best knowledge"?
---Heikki---^^

   ---Ran---vv
   Does someone want to try to construct a rationale for the
   document about why folks believe the attempted replay
   protection actually works ?

   Barring that, maybe the words should be more tentative
   (edit to taste):

        Through the use of a sequence number and ... and ...,
        the SSH specification seeks to provide protection against
        replay attacks.
   ---Ran---^^

   ---Heikki---vv
   I'm not much of an editor, but maybe someone can slash something out of
   the following:

   Running sequence number gives us an unique input for the MAC
   function regardless of the contents of the packet, as long as the
   sequence number doesn't wrap. With rekeying before the sequence number
   wraps, we get an unique input into the MAC function (well, HMAC at
least)
   regardless of the sequence counter wrapping.

   If an attacker captures a packet and inserts it within the SSH stream
in
   order to replay the packet, either the sequence number or the MAC key
will
   be different, and the MAC check will fail.


   We assume MAC is secure of course, specifically it being infeasible to
   construct x' such that MAC(x) = MAC(x'). For HMACs it is discussed in
   rfc 2104.
   I don't know if it's relevant or not, but given that an attacker wants
to
   re-use data from the packet, there are even less bits to work with,
and,
   even less of a chance of succeeding in creating a valid MAC.
   ---Heikki---^^

---Chris---vv
I'm going to put that last part into the MITM section rather than here in
the Replay section.
---Chris---^^

---David Williams---vv
>   attacker does attempt to replay a captured packed before the peers
>
should read "... packet before the peers"
---David---^^

---Joseph---vv
The packet sequence number is not actually sent on
the wire, but is maintained independantly by each
side.

If an attacker replays a captured packet, it will
be input into the mac routines with the next valid
sequence number.  Since that is not the sequence
number that was used in the original computation of
the mac, it will show up as a MAC error.
---Joseph---^^

   ---Chris---vv
   I knew that.  No, really; I knew that.  S-)
   ---Chris---^^