1 /* routines for state objects
2 * Copyright (C) 1997 Angelos D. Keromytis.
3 * Copyright (C) 1998-2001 D. Hugh Redelmeier.
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; either version 2 of the License, or (at your
8 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * RCSID $Id: state.c,v 1.96 2002/03/25 07:05:16 dhr Exp $
22 #include <sys/types.h>
23 #include <sys/socket.h>
24 #include <netinet/in.h>
25 #include <arpa/inet.h>
30 #include "constants.h"
34 #include "connections.h" /* needs id.h */
38 #include "packet.h" /* so we can calculate sizeof(struct isakmp_hdr) */
39 #include "preshared.h" /* for free_public_key */
43 #include "demux.h" /* needs packet.h */
44 #include "ipsec_doi.h" /* needs demux.h and state.h */
48 #include "crypto.h" /* requires sha1.h and md5.h */
51 * Global variables: had to go somewhere, might as well be this file.
54 u_int16_t pluto_port = IKE_UDP_PORT; /* Pluto's port */
57 * This file has the functions that handle the
58 * state hash table and the Message ID list.
63 * A Message ID is contained in each IKE message header.
64 * For Phase 1 exchanges (Main and Aggressive), it will be zero.
65 * For other exchanges, which must be under the protection of an
66 * ISAKMP SA, the Message ID must be unique within that ISAKMP SA.
67 * Effectively, this labels the message as belonging to a particular
69 * BTW, we feel this uniqueness allows rekeying to be somewhat simpler
70 * than specified by draft-jenkins-ipsec-rekeying-06.txt.
72 * A MessageID is a 32 bit unsigned number. We represent the value
73 * internally in network order -- they are just blobs to us.
74 * They are unsigned numbers to make hashing and comparing easy.
76 * The following mechanism is used to allocate message IDs. This
77 * requires that we keep track of which numbers have already been used
78 * so that we don't allocate one in use.
83 msgid_t msgid; /* network order */
84 struct msgid_list *next;
88 reserve_msgid(struct state *isakmp_sa, msgid_t msgid)
92 passert(IS_ISAKMP_SA_ESTABLISHED(isakmp_sa->st_state));
94 for (p = isakmp_sa->st_used_msgids; p != NULL; p = p->next)
95 if (p->msgid == msgid)
98 p = alloc_thing(struct msgid_list, "msgid");
100 p->next = isakmp_sa->st_used_msgids;
101 isakmp_sa->st_used_msgids = p;
106 generate_msgid(struct state *isakmp_sa)
108 int timeout = 100; /* only try so hard for unique msgid */
111 passert(IS_ISAKMP_SA_ESTABLISHED(isakmp_sa->st_state));
115 get_rnd_bytes((void *) &msgid, sizeof(msgid));
116 if (msgid != 0 && reserve_msgid(isakmp_sa, msgid))
121 log("gave up looking for unique msgid; using 0x%08lx",
122 (unsigned long) msgid);
130 /* state table functions */
132 #define STATE_TABLE_SIZE 32
134 static struct state *statetable[STATE_TABLE_SIZE];
136 static struct state **
137 state_hash(const u_char *icookie, const u_char *rcookie, const ip_address *peer)
140 const unsigned char *byte_ptr;
141 size_t length = addrbytesptr(peer, &byte_ptr);
143 DBG(DBG_RAW | DBG_CONTROL,
144 DBG_dump("ICOOKIE:", icookie, COOKIE_SIZE);
145 DBG_dump("RCOOKIE:", rcookie, COOKIE_SIZE);
146 DBG_dump("peer:", byte_ptr, length));
148 /* XXX the following hash is pretty pathetic */
150 for (j = 0; j < COOKIE_SIZE; j++)
151 i = i * 407 + icookie[j] + rcookie[j];
153 for (j = 0; j < length; j++)
154 i = i * 613 + byte_ptr[j];
156 i = i % STATE_TABLE_SIZE;
158 DBG(DBG_CONTROL, DBG_log("state hash entry %d", i));
160 return &statetable[i];
164 * Replace the instances for the old peer address with the
168 state_rehash(struct connection *c)
170 struct state **st_p = NULL;
171 struct state *old_st = NULL;
172 struct state *new_list = NULL;
173 struct state *current_st = NULL;
174 struct state **p = NULL;
177 for (i = 0; i < STATE_TABLE_SIZE; i++)
180 for (st_p = &statetable[i]; (*st_p) != NULL;)
182 if ((*st_p)->st_connection == c)
185 *st_p = (*st_p)->st_hashchain_next;
186 old_st->st_hashchain_next = NULL;
188 (*st_p)->st_hashchain_prev = old_st->st_hashchain_prev;
189 old_st->st_hashchain_prev = NULL;
190 if (new_list == NULL) {
193 current_st->st_hashchain_next = old_st;
197 st_p = &(*st_p)->st_hashchain_next;
202 for (old_st = new_list; new_list != NULL;)
205 new_list = new_list->st_hashchain_next;
206 old_st->st_hashchain_next = NULL;
207 p = state_hash(old_st->st_icookie, old_st->st_rcookie, &old_st->st_connection->that.host_addr);
211 passert((*p)->st_hashchain_prev == NULL);
212 (*p)->st_hashchain_prev = old_st;
214 old_st->st_hashchain_next = *p;
219 /* Get a state object.
220 * Caller must schedule an event for this object so that it doesn't leak.
221 * Caller must insert_state().
226 static const struct state blank_state; /* initialized all to zero & NULL */
227 static so_serial_t next_so = SOS_FIRST;
230 st = clone_thing(blank_state, "struct state in new_state()");
231 st->st_serialno = next_so++;
232 passert(next_so > SOS_FIRST); /* overflow can't happen! */
233 st->st_whack_sock = NULL_FD;
234 DBG(DBG_CONTROL, DBG_log("creating state object #%lu at %p",
235 st->st_serialno, (void *) st));
240 * Initialize the state table (and mask*).
247 for (i = 0; i < STATE_TABLE_SIZE; i++)
248 statetable[i] = (struct state *) NULL;
251 /* Find the state object with this serial number.
252 * This allows state object references that don't turn into dangerous
253 * dangling pointers: reference a state by its serial number.
254 * Returns NULL if there is no such state.
255 * If this turns out to be a significant CPU hog, it could be
256 * improved to use a hash table rather than sequential seartch.
259 state_with_serialno(so_serial_t sn)
266 for (i = 0; i < STATE_TABLE_SIZE; i++)
267 for (st = statetable[i]; st != NULL; st = st->st_hashchain_next)
268 if (st->st_serialno == sn)
274 /* Insert a state object in the hash table. The object is inserted
275 * at the begining of list.
276 * Needs cookies, connection, and msgid.
279 insert_state(struct state *st)
281 struct state **p = state_hash(st->st_icookie, st->st_rcookie
282 , &st->st_connection->that.host_addr);
284 passert(st->st_hashchain_prev == NULL && st->st_hashchain_next == NULL);
288 passert((*p)->st_hashchain_prev == NULL);
289 (*p)->st_hashchain_prev = st;
291 st->st_hashchain_next = *p;
294 /* Ensure that somebody is in charge of killing this state:
295 * if no event is scheduled for it, schedule one to discard the state.
296 * If nothing goes wrong, this event will be replaced by
297 * a more appropriate one.
299 if (st->st_event == NULL) {
300 event_schedule(EVENT_SO_DISCARD, 0, st);
304 /* unlink a state object from the hash table, but don't free it
307 unhash_state(struct state *st)
309 /* unlink from forward chain */
310 struct state **p = st->st_hashchain_prev == NULL
311 ? state_hash(st->st_icookie, st->st_rcookie, &st->st_connection->that.host_addr)
312 : &st->st_hashchain_prev->st_hashchain_next;
314 /* unlink from forward chain */
316 *p = st->st_hashchain_next;
318 /* unlink from backward chain */
319 if (st->st_hashchain_next != NULL)
321 passert(st->st_hashchain_next->st_hashchain_prev == st);
322 st->st_hashchain_next->st_hashchain_prev = st->st_hashchain_prev;
325 st->st_hashchain_next = st->st_hashchain_prev = NULL;
328 /* Free the Whack socket file descriptor.
329 * This has the side effect of telling Whack that we're done.
332 release_whack(struct state *st)
334 close_any(st->st_whack_sock);
337 /* delete a state object */
339 delete_state(struct state *st)
341 struct connection *const c = st->st_connection;
342 struct state *old_cur_state = cur_state == st? NULL : cur_state;
345 if (st->st_dpd_event != NULL)
346 delete_dpd_event(st);
348 /* if there is a suspended state transition, disconnect us */
349 if (st->st_suspended_md != NULL)
351 passert(st->st_suspended_md->st == st);
352 st->st_suspended_md->st = NULL;
355 /* tell the other side of any IPSEC SAs that are going down */
356 if (IS_IPSEC_SA_ESTABLISHED(st->st_state) ||
357 IS_ISAKMP_SA_ESTABLISHED(st->st_state))
360 delete_event(st); /* delete any pending timer event */
362 /* Ditch anything pending on ISAKMP SA being established.
363 * Note: this must be done before the unhash_state to prevent
364 * flush_pending_by_state inadvertently and prematurely
365 * deleting our connection.
367 flush_pending_by_state(st);
369 /* effectively, this deletes any ISAKMP SA that this state represents */
372 /* tell kernel to delete any IPSEC SA
373 * ??? we ought to tell peer to delete IPSEC SAs
375 if (IS_IPSEC_SA_ESTABLISHED(st->st_state))
376 delete_ipsec_sa(st, FALSE);
377 else if (IS_ONLY_INBOUND_IPSEC_SA_ESTABLISHED(st->st_state))
378 delete_ipsec_sa(st, TRUE);
380 if (c->newest_ipsec_sa == st->st_serialno)
381 c->newest_ipsec_sa = SOS_NOBODY;
383 if (c->newest_isakmp_sa == st->st_serialno)
384 c->newest_isakmp_sa = SOS_NOBODY;
386 st->st_connection = NULL; /* we might be about to free it */
387 cur_state = old_cur_state; /* without st_connection, st isn't complete */
388 connection_discard(c);
392 /* from here on we are just freeing RAM */
395 struct msgid_list *p = st->st_used_msgids;
399 struct msgid_list *q = p;
405 free_public_keys(&st->st_peer_pubkey);
407 if (st->st_sec_in_use)
408 mpz_clear(&(st->st_sec));
410 pfreeany(st->st_tpacket.ptr);
411 pfreeany(st->st_rpacket.ptr);
412 pfreeany(st->st_p1isa.ptr);
413 pfreeany(st->st_gi.ptr);
414 pfreeany(st->st_gr.ptr);
415 pfreeany(st->st_shared.ptr);
416 pfreeany(st->st_ni.ptr);
417 pfreeany(st->st_nr.ptr);
418 pfreeany(st->st_skeyid.ptr);
419 pfreeany(st->st_skeyid_d.ptr);
420 pfreeany(st->st_skeyid_a.ptr);
421 pfreeany(st->st_skeyid_e.ptr);
422 pfreeany(st->st_enc_key.ptr);
423 pfreeany(st->st_ah.our_keymat);
424 pfreeany(st->st_ah.peer_keymat);
425 pfreeany(st->st_esp.our_keymat);
426 pfreeany(st->st_esp.peer_keymat);
431 /* Is a connection in use by some state? */
433 states_use_connection(struct connection *c)
435 /* are there any states still using it? */
436 struct state *st = NULL;
439 for (i = 0; st == NULL && i < STATE_TABLE_SIZE; i++)
440 for (st = statetable[i]; st != NULL; st = st->st_hashchain_next)
441 if (st->st_connection == c)
448 delete_states_by_connection(struct connection *c)
451 /* this kludge avoids an n^2 algorithm */
452 enum connection_kind ck = c->kind;
454 if (ck == CK_INSTANCE)
455 c->kind = CK_GOING_AWAY;
457 /* We take two passes so that we delete any ISAKMP SAs last.
458 * This allows Delete Notifications to be sent.
459 * ?? We could probably double the performance by caching any
460 * ISAKMP SA states found in the first pass, avoiding a second.
462 for (pass = 0; pass != 2; pass++)
466 /* For each hash chain... */
467 for (i = 0; i < STATE_TABLE_SIZE; i++)
471 /* For each state in the hash chain... */
472 for (st = statetable[i]; st != NULL; )
474 struct state *this = st;
476 st = st->st_hashchain_next; /* before this is deleted */
478 if (this->st_connection == c
479 && (pass == 1 || !IS_ISAKMP_SA_ESTABLISHED(this->st_state)))
481 struct state *old_cur_state
482 = cur_state == this? NULL : cur_state;
484 unsigned int old_cur_debugging = cur_debugging;
488 log("deleting state (%s)"
489 , enum_show(&state_names, this->st_state));
490 passert(this->st_event != NULL);
492 cur_state = old_cur_state;
494 cur_debugging = old_cur_debugging;
501 passert(c->newest_ipsec_sa == SOS_NOBODY
502 && c->newest_isakmp_sa == SOS_NOBODY
503 && c->eroute_owner == SOS_NOBODY
504 && c->routing != RT_ROUTED_TUNNEL);
506 if (ck == CK_INSTANCE)
509 delete_connection(c);
513 /* Duplicate a Phase 1 state object, to create a Phase 2 object.
514 * Caller must schedule an event for this object so that it doesn't leak.
515 * Caller must insert_state().
518 duplicate_state(const struct state *st)
522 DBG(DBG_CONTROL, DBG_log("duplicating state object #%lu",
527 memcpy(nst->st_icookie, st->st_icookie, COOKIE_SIZE);
528 memcpy(nst->st_rcookie, st->st_rcookie, COOKIE_SIZE);
529 nst->st_connection = st->st_connection;
531 nst->st_doi = st->st_doi;
532 nst->st_situation = st->st_situation;
534 # define clone_chunk(ch, name) \
535 clonetochunk(nst->ch, st->ch.ptr, st->ch.len, name)
537 clone_chunk(st_skeyid_d, "st_skeyid_d in duplicate_state");
538 clone_chunk(st_skeyid_a, "st_skeyid_a in duplicate_state");
539 clone_chunk(st_skeyid_e, "st_skeyid_e in duplicate_state");
540 clone_chunk(st_enc_key, "st_enc_key in duplicate_state");
544 /* no obvious reason to copy st_peeridentity_protocol and st_peeridentity_port */
546 nst->st_oakley = st->st_oakley;
552 void for_each_state(void *(f)(struct state *, void *data), void *data)
554 struct state *st, *ocs = cur_state;
556 for (i=0; i<STATE_TABLE_SIZE; i++) {
557 for (st = statetable[i]; st != NULL; st = st->st_hashchain_next) {
567 * Find a state object.
570 find_state(const u_char *icookie, const u_char *rcookie,
571 const ip_address *peer, msgid_t /*network order*/ msgid)
573 struct state *st = *state_hash(icookie, rcookie, peer);
575 while (st != (struct state *) NULL)
576 if (sameaddr(peer, &st->st_connection->that.host_addr)
577 && memcmp(icookie, st->st_icookie, COOKIE_SIZE) == 0
578 && memcmp(rcookie, st->st_rcookie, COOKIE_SIZE) == 0
579 && msgid == st->st_msgid)
582 st = st->st_hashchain_next;
586 DBG_log("state object not found");
588 DBG_log("state object #%lu found, in %s",
590 enum_show(&state_names, st->st_state)));
595 /* Find the state that sent a packet
596 * ??? this could be expensive -- it should be rate-limited to avoid DoS
599 find_sender(size_t packet_len, u_char *packet)
604 if (packet_len >= sizeof(struct isakmp_hdr))
605 for (i = 0; i < STATE_TABLE_SIZE; i++)
606 for (st = statetable[i]; st != NULL; st = st->st_hashchain_next)
607 if (st->st_tpacket.ptr != NULL
608 && st->st_tpacket.len == packet_len
609 && memcmp(st->st_tpacket.ptr, packet, packet_len) == 0)
616 find_phase2_state_to_delete(const struct state *p1st, u_int8_t protoid,
617 ipsec_spi_t spi, bool *bogus)
622 if (bogus) *bogus = FALSE;
623 for (i = 0; i < STATE_TABLE_SIZE; i++)
624 for (st = statetable[i]; st != NULL; st = st->st_hashchain_next)
625 if ( (IS_IPSEC_SA_ESTABLISHED(st->st_state))
626 && (p1st->st_connection->host_pair == st->st_connection->host_pair)
627 && (same_peer_ids(p1st->st_connection, st->st_connection, NULL)))
629 if ((protoid == PROTO_IPSEC_ESP) && (st->st_esp.present)
630 &&(st->st_esp.attrs.spi == spi))
632 else if ((protoid == PROTO_IPSEC_AH) && (st->st_ah.present)
633 && (st->st_ah.attrs.spi == spi))
635 else if ((protoid == PROTO_IPSEC_ESP) && (st->st_esp.present)
636 && (st->st_esp.our_spi == spi) && (bogus))
638 else if ((protoid == PROTO_IPSEC_AH) && (st->st_ah.present)
639 && (st->st_ah.our_spi == spi) && (bogus))
646 find_phase1_state_to_delete(const struct state *p1st,
647 const u_char *icookie, const u_char *rcookie)
652 for (i = 0; i < STATE_TABLE_SIZE; i++)
653 for (st = statetable[i]; st != NULL; st = st->st_hashchain_next)
654 if ( (IS_ISAKMP_SA_ESTABLISHED(st->st_state))
655 && (memcmp(icookie, st->st_icookie, COOKIE_SIZE) == 0)
656 && (memcmp(rcookie, st->st_rcookie, COOKIE_SIZE) == 0)
657 && (p1st->st_connection->host_pair == st->st_connection->host_pair)
658 && (same_peer_ids(p1st->st_connection, st->st_connection, NULL)) ) {
664 /* Find newest Phase 1 negotiation state object for suitable for connection c
667 find_phase1_state(const struct connection *c, bool established)
674 for (i = 0; i < STATE_TABLE_SIZE; i++)
675 for (st = statetable[i]; st != NULL; st = st->st_hashchain_next)
676 if (IS_PHASE1(st->st_state)
677 && (!established || IS_ISAKMP_SA_ESTABLISHED(st->st_state))
678 && c->host_pair == st->st_connection->host_pair
679 && same_peer_ids(c, st->st_connection, NULL)
680 && (best == NULL || best->st_serialno < st->st_serialno))
686 time_t get_born_time(struct state *st) {
688 switch (st->st_state) {
691 if (st->st_ah.present)
692 return (st->st_ah.attrs.born);
693 if (st->st_esp.present)
694 return (st->st_esp.attrs.born);
695 if (st->st_ipcomp.present)
696 return (st->st_ipcomp.attrs.born);
700 return (st->st_oakley.born);
707 show_states_status(void)
712 for (i = 0; i < STATE_TABLE_SIZE; i++)
716 for (st = statetable[i]; st != NULL; st = st->st_hashchain_next)
718 /* what the heck is interesting about a state? */
719 const struct connection *c = st->st_connection;
720 long delta = st->st_event->ev_time >= n
721 ? (long)(st->st_event->ev_time - n)
722 : -(long)(n - st->st_event->ev_time);
723 char inst[CONN_INST_BUF];
724 const char *np1 = c->newest_isakmp_sa == st->st_serialno
725 ? "; newest ISAKMP" : "";
726 const char *np2 = c->newest_ipsec_sa == st->st_serialno
727 ? "; newest IPSEC" : "";
728 const char *eo = c->eroute_owner == st->st_serialno
729 ? "; eroute owner" : "";
731 passert(st->st_event != 0);
733 fmt_conn_instance(c, inst);
736 , "#%lu: \"%s\"%s %s (%s); born:%lds; %s in %lds%s%s%s"
739 , enum_name(&state_names, st->st_state)
740 , state_story[st->st_state - STATE_MAIN_R0]
742 , enum_name(&timer_event_names, st->st_event->ev_type)
746 /* print out SPIs if SAs are established */
747 if (IS_IPSEC_SA_ESTABLISHED(st->st_state))
749 char buf[SATOT_BUF*6 + 1];
752 # define add_said(adst, aspi, aproto) { \
755 initsaid(adst, aspi, aproto, &s); \
756 if (p < &buf[sizeof(buf)-1]) \
759 p += satot(&s, 0, p, &buf[sizeof(buf)] - p) - 1; \
765 if (st->st_ah.present)
767 add_said(&c->that.host_addr, st->st_ah.attrs.spi, SA_AH);
768 add_said(&c->this.host_addr, st->st_ah.our_spi, SA_AH);
770 if (st->st_esp.present)
772 add_said(&c->that.host_addr, st->st_esp.attrs.spi, SA_ESP);
773 add_said(&c->this.host_addr, st->st_esp.our_spi, SA_ESP);
775 if (st->st_ipcomp.present)
777 add_said(&c->that.host_addr, st->st_ipcomp.attrs.spi, SA_COMP);
778 add_said(&c->this.host_addr, st->st_ipcomp.our_spi, SA_COMP);
781 if (st->st_ah.attrs.encapsulation == ENCAPSULATION_MODE_TUNNEL
782 || st->st_esp.attrs.encapsulation == ENCAPSULATION_MODE_TUNNEL
783 || st->st_ipcomp.attrs.encapsulation == ENCAPSULATION_MODE_TUNNEL)
785 add_said(&c->that.host_addr, st->st_tunnel_out_spi, SA_IPIP);
786 add_said(&c->this.host_addr, st->st_tunnel_in_spi, SA_IPIP);
801 /* Given that we've used up a range of unused CPI's,
802 * search for a new range of currently unused ones.
803 * Note: this is very expensive when not trivial!
804 * If we can't find one easily, choose 0 (a bad SPI,
805 * no matter what order) indicating failure.
808 find_my_cpi_gap(cpi_t *latest_cpi, cpi_t *first_busy_cpi)
811 cpi_t base = *latest_cpi;
816 closest = ~0; /* not close at all */
817 for (i = 0; i < STATE_TABLE_SIZE; i++)
821 for (st = statetable[i]; st != NULL; st = st->st_hashchain_next)
823 if (st->st_ipcomp.present)
825 cpi_t c = ntohl(st->st_ipcomp.our_spi) - base;
831 /* oops: next spot is occupied; start over */
835 *latest_cpi = *first_busy_cpi = 0;
839 if (base > IPCOMP_LAST_NEGOTIATED)
840 base = IPCOMP_FIRST_NEGOTIATED;
841 goto startover; /* really a tail call */
848 *latest_cpi = base; /* base is first in next free range */
849 *first_busy_cpi = closest + base; /* and this is the roof */
852 /* Muck with high-order 16 bits of this SPI in order to make
853 * the corresponding SAID unique.
854 * Its low-order 16 bits hold a well-known IPCOMP CPI.
855 * Oh, and remember that SPIs are stored in network order.
856 * Kludge!!! So I name it with the non-English word "uniquify".
857 * If we can't find one easily, return 0 (a bad SPI,
858 * no matter what order) indicating failure.
861 uniquify_his_cpi(ipsec_spi_t cpi, struct state *st)
868 /* network order makes first two bytes our target */
869 get_rnd_bytes((u_char *)&cpi, 2);
871 /* Make sure that the result is unique.
872 * Hard work. If there is no unique value, we'll loop forever!
874 for (i = 0; i < STATE_TABLE_SIZE; i++)
878 for (s = statetable[i]; s != NULL; s = s->st_hashchain_next)
880 if (s->st_ipcomp.present
881 && sameaddr(&s->st_connection->that.host_addr
882 , &st->st_connection->that.host_addr)
883 && cpi == s->st_ipcomp.attrs.spi)
886 return 0; /* FAILURE */