[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: uniqueness of Message IDs and related issues
Hugh,
This is my interpretation of the use of Message IDs in IKE:
The intention of the Message ID is that it demultiplexes a stream of
messages from a peer and passes each message on to the appropriate state
machine. This allows multiple concurrent exchanges to not interfere with
each other. (So if you are worried about collisions in 2^32 then you might
want to check the generated Message ID against your current state table.)
You don't need to suck up memory by storing all the previously used Message
IDs. Replay protection is provided by making exchanges 3+ messages long and
by using nonces (a message id can function as a nonce for this purpose).
A nonce should be unpredictable to an adversary (although the attacks if it
is not are pretty esoteric). A pseudorandom number generator does this well
enough as long as you keep the seed value secret (of course you still have
to generate the original seed from a truly random value).
A Message ID should also be based off of a truly random seed so that two
hosts running the same code don't consistently generate the same values.
The Message ID is passed in the clear and is visible to an eavesdropper;
therefore, it adds no real entropy to the secret key (against brute force)
and its choice does not have cryptographic significance.
I believe the MUST clause in the draft is a slight bit of hyperbole.
Anyone want to add to/disagree with any of this?
Andrew
--------------------------------------
Beauty with out truth is insubstantial.
Truth without beauty is unbearable.
> -----Original Message-----
> From: owner-ipsec@lists.tislabs.com
> [mailto:owner-ipsec@lists.tislabs.com]On Behalf Of D. Hugh Redelmeier
> Sent: Tuesday, June 20, 2000 8:48 PM
> To: IPsec List
> Subject: uniqueness of Message IDs and related issues
>
>
> [I am sorry that this message is so long and complicated. I'm not
> sure how to safely separate the issues. I think that it is important
> that at least some of these points are nailed down.]
>
> RFC2408 "ISAKMP" 3.1 "ISAKMP Header Format" (near end) states that
> the Message ID must be unique:
>
> o Message ID (4 octets) - Unique Message Identifier used to
> identify protocol state during Phase 2 negotiations.
> This value
> is randomly generated by the initiator of the Phase 2
> negotiation. In the event of simultaneous SA establishments
> (i.e. collisions), the value of this field will likely be
> different because they are independently generated
> and, thus, two
> security associations will progress toward establishment.
> However, it is unlikely there will be absolute simultaneous
> establishments. During Phase 1 negotiations, the value MUST be
> set to 0.
>
> I can find no further clarification about what is meant by "unique".
>
> Clearly we cannot require that the Message ID be unique for all peers
> since they may not be communicating (but no RFC or draft seems to
> state this).
>
> In the past, I've enforced this as unique per peer during the lifetime
> of my IKE daemon (Pluto, of the FreeS/WAN project). In other words,
> whenever Pluto wanted to use a Message ID, it first made sure that the
> Message ID hadn't been used before with the peer in question (at least
> since the Pluto process had started). Whenever a peer started an
> exchange with a previously used Message ID, Pluto rejected that as
> improper.
>
> One problem with this approach is that it requires that Pluto to store
> a growing and unbounded amount of state: the used Message IDs.
>
> I've just made a change that seems reasonable, but I cannot justify it
> from text in an RFC or draft. Pluto now requires that the Message ID
> only be unique within a single ISAKMP SA. Every Message ID seems to
> occur in a context of an ISAKMP SA, so this seems reasonable. There
> still may be a lot of Message IDs to store, but they expire with the
> ISAKMP SA. Furthermore, since an ISAKMP SA does not survive a restart
> of Pluto, it is OK for Pluto to "forget" all previously used Message
> IDs when it is restarted -- a RAM table suffices. And, of course, an
> ISAKMP SA is only between two hosts, so other hosts need not avoid
> Message IDs that they cannot know about.
>
> Perhaps a little encouragement comes from RFC2409 "IKE", section 5.5
> "Phase 2 - Quick Mode":
>
> The message ID in the ISAKMP header identifies a Quick Mode in
> progress for a particular ISAKMP SA which itself is
> identified by the
> cookies in the ISAKMP header.
>
> But another part, 5.7 "ISAKMP Informational Exchanges" says:
>
> As noted the message ID in the ISAKMP header-- and used in the prf
> computation-- is unique to this exchange and MUST NOT be
> the same as
> the message ID of another phase 2 exchange which generated this
> informational exchange.
>
> This does not qualify "unique" in any way. It does clearly use the
> admonition "MUST NOT".
>
> Limiting uniqueness to being within an ISAKMP SA won't work if some
> message refers to some object (say an IPSEC SA) negotiated under a
> different ISAKMP SA using only a Message ID. A quick look at
> draft-ietf-ipsec-notifymsg-02.txt makes me think that this isn't a
> problem, but I'm not sure.
>
> One way of avoiding the storage of Message IDs is to "just hope" that
> they are unique. They usually are. But this can hardly satisfy the
> "MUST NOT".
>
> I have another reason for disliking the "just hope" approach.
> draft-jenkins-ipsec-rekeying-06.txt seems too complicated and awkward
> to me. In "2.2.1.4 Responder Pre-Set-up Security Hole", a simple
> solution (Responder Pre-Set-up) is rejected due to an alleged replay
> attack. If Message IDs are not allowed to be repeated, the replay
> attack cannot succeed.
>
> I looked through many of the list messages for "Message ID" but found
> none of these questions addressed. But I did find the following:
>
> | Date: Mon, 13 Dec 1999 12:37:58 -0500
> | From: Andrew Krywaniuk <akrywaniuk@TimeStep.com>
> | To: Tero Kivinen <kivinen@ssh.fi>
> | Cc: ipsec@lists.tislabs.com
> | Subject: RE: heartbeats (summary of responses)
>
> | > If we start sending hearbeats inside the IKE message we also
> | > might end up consuming our randomness quite fast. For
> each IKE message
> | > we need to create random message id and a random nonce.
> |
> | Hi Tero,
> |
> | I forgot to mention this before. I don't think randomness
> is really an issue
> | here. It is perfectly valid to use a seeded pseudorandom
> number generator
> | without consuming any additional randomness for each heartbeat.
> |
> | As far as I can tell, there is no security implication to using a
> | pseudorandom message id. I suspect that the reason why we
> don't simply use
> | 1,2,3... is actually to avoid collisions and not to
> generate entropy.
>
> Has a cryptologist clearly indicated whether the Message ID needs to
> be random, or is pseudo-random good enough, or is predictable
> acceptable? The part of RFC2408 quoted above clearly uses the phrase
> "randomly generated".
>
> Oops: I just noticed that RFC2409 and some of the drafts refer to
> "message ID", not "Message ID". I think that this is a mistake. But
> it also meant that I didn't find all uses. For the record these are:
>
> draft-ietf-ipsec-ike-01.txt (expired, but I presume it will be
> revived)
> draft-ietf-ipsec-isakmp-mode-cfg-05.txt
> draft-ietf-ipsec-isakmp-xauth-04.txt
> draft-ietf-ipsec-notifymsg-02.txt
>
> draft-ietf-ipsec-ike-01.txt 8 "Security Considerations" says:
>
> The message ID used for all non-Phase 1 exchanges MUST be pseudo-
> randomly generated using a strong random number generator.
>
> So that seems to settle it. Did this change get checked by a
> cryptologist?
>
> The part of RFC2408 quoted at the top uses the phrase "initiator of
> the Phase 2 negotiation" whereas draft-ietf-ipsec-ike-01.txt says "all
> non-Phase 1 exchanges". I'd guess that draft-ietf-ipsec-ike-01.txt's
> formulation should be used in RFC2408 because it is more accurate.
>
>
> I would like these questions clearly resolved. (But perhaps the only
> place they are not clearly resolved is in my mind.)
>
> - What is the scope over which a Message ID is to be unique?
>
> I propose that it be unique within the context of a single
> ISAKMP SA.
>
>
> - "MUST" or "SHOULD" a Message ID be unique?
>
> I propose that it "MUST" be unique.
>
>
> - MUST (SHOULD?) the Message ID be generated randomly,
> pseudo-randomly, or however the implementor feels like doing it?
>
> I propose that it be randomly, until a cryptologist convinces us
> that something less is enough
>
>
> - I think that the documents would be clearer if they always used
> "Message ID" instead of sometimes using "Message ID", MID, and M-ID.
>
> Hugh Redelmeier
> hugh@mimosa.com voice: +1 416 482-8253
>
Follow-Ups:
References: