[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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: