Replay window and replay packet id

[reynir]

The current implementation expects the replay packet id to be always be increasing by one without gap starting at 1. The openvpn-rfc says it is a monotonically increasing sequence. Another part of the rfc draft suggests keeping a sliding window of 32. For tls-crypt-v2 the sequence can start at 0x0f000001 (I believe) to signal early negotiation support (for hmac cookie only for now). The only requirement seems to be that the replay packet id is not zero.

miragevpn/src/engine.ml

Lines 807 to 824 in 35a8d96

	(* TODO deal with it, properly: packets may be lost (e.g. udp)
	both from their side, and acks from our side *)
	guard
	(Int32.equal session.their_packet_id hdr.Packet.packet_id)
	(`Non_monotonic_packet_id (transport, hdr))
	>>= fun () ->
	opt_guard
	(Int32.equal transport.their_message_id)
	msg_id
	(`Non_monotonic_message_id (transport, msg_id, hdr))
	>>| fun () ->
	let session =
	{
	session with
	their_session_id = hdr.Packet.local_session;
	their_packet_id = Int32.succ hdr.Packet.packet_id;
	}
	in

https://github.com/OpenVPN/openvpn-rfc/blob/bbde60d7f28a5436e21b3f475788f7922e0d9339/openvpn-wire-protocol.xml#L365-L375
https://github.com/OpenVPN/openvpn-rfc/blob/bbde60d7f28a5436e21b3f475788f7922e0d9339/openvpn-wire-protocol.xml#L1057-L1071

[hannesm]

This is related to #53, with the sliding window code suggested by @cfcs in #37 (comment)

module Sliding_window : sig
  type t
  val make : int -> t
  val add : int -> t -> (t, string) result
  val mem : t -> int -> bool
  val pp : Format.formatter -> t -> unit
end = struct
  type t = { window: int; counter: int; }
  let make counter = { window = 1; counter }
  let add n {window; counter} =
    if n <= counter then begin
      let diff = counter -n in
      if diff >= Sys.int_size
      then Error "n not in sliding window"
      else Ok {window = window lor (1 lsl diff); counter}
    end else begin (* counter > n; always succeeds *)
      let diff = n - counter in
      if diff >= Sys.int_size
      then Ok (make n) (* new window *)
      else Ok {window = (window lsl diff) lor 1; counter = n}
    end

  let pp ppf {window;counter} =
    Fmt.pf ppf "{ window = %d; counter = %d }" window counter

  let mem {window;counter} n =
    let diff = counter - n in
    if counter < n || diff > Sys.int_size
    then false
    else 0 <> window land (1 lsl diff)
end

[hannesm]

For more clarity: as far as I understand the OpenVPN, we should accept any replay id that is larger then the previous one.

Also, the sequence number should be increasing without gaps. Both is not correct in our implementation (but works incredible well).

[reynir]

I think the sliding window implementation is interesting. The default window size (see option --replay-window in openvpn) is 64, so 62 is maybe acceptable. On the other hand they write the following:

          If  you  are using a network link with a large pipeline (meaning
          that the product of bandwidth and latency is high), you may want
          to use a larger value for n. Satellite links in particular often
          require this.

This also depends on the CPU architecture; maybe a window size of 30 is undesirable(?)

[hannesm]

FWIW, since a4b6595#diff-8df08bfd0d3762c5d7dad8c2f8a61b80c929c7e43e21ec8c228f547ff3e35e25R889 the replay ID does not need to be exactly equal anymore, but greater or equal is fine.