1/*
2 * Copyright (c) 2002-2017 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29/*-
30 * Copyright (c) 2008 Michael J. Silbersack.
31 * All rights reserved.
32 *
33 * Redistribution and use in source and binary forms, with or without
34 * modification, are permitted provided that the following conditions
35 * are met:
36 * 1. Redistributions of source code must retain the above copyright
37 * notice unmodified, this list of conditions, and the following
38 * disclaimer.
39 * 2. Redistributions in binary form must reproduce the above copyright
40 * notice, this list of conditions and the following disclaimer in the
41 * documentation and/or other materials provided with the distribution.
42 *
43 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
44 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
45 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
46 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
47 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
48 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
49 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
50 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
51 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
52 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
53 */
54
55/*
56 * IP ID generation is a fascinating topic.
57 *
58 * In order to avoid ID collisions during packet reassembly, common sense
59 * dictates that the period between reuse of IDs be as large as possible.
60 * This leads to the classic implementation of a system-wide counter, thereby
61 * ensuring that IDs repeat only once every 2^16 packets.
62 *
63 * Subsequent security researchers have pointed out that using a global
64 * counter makes ID values predictable. This predictability allows traffic
65 * analysis, idle scanning, and even packet injection in specific cases.
66 * These results suggest that IP IDs should be as random as possible.
67 *
68 * The "searchable queues" algorithm used in this IP ID implementation was
69 * proposed by Amit Klein. It is a compromise between the above two
70 * viewpoints that has provable behavior that can be tuned to the user's
71 * requirements.
72 *
73 * The basic concept is that we supplement a standard random number generator
74 * with a queue of the last L IDs that we have handed out to ensure that all
75 * IDs have a period of at least L.
76 *
77 * To efficiently implement this idea, we keep two data structures: a
78 * circular array of IDs of size L and a bitstring of 65536 bits.
79 *
80 * To start, we ask the RNG for a new ID. A quick index into the bitstring
81 * is used to determine if this is a recently used value. The process is
82 * repeated until a value is returned that is not in the bitstring.
83 *
84 * Having found a usable ID, we remove the ID stored at the current position
85 * in the queue from the bitstring and replace it with our new ID. Our new
86 * ID is then added to the bitstring and the queue pointer is incremented.
87 *
88 * The lower limit of 512 was chosen because there doesn't seem to be much
89 * point to having a smaller value. The upper limit of 32768 was chosen for
90 * two reasons. First, every step above 32768 decreases the entropy. Taken
91 * to an extreme, 65533 would offer 1 bit of entropy. Second, the number of
92 * attempts it takes the algorithm to find an unused ID drastically
93 * increases, killing performance. The default value of 4096 was chosen
94 * because it provides a good tradeoff between randomness and non-repetition,
95 * while taking performance into account.
96 *
97 * With L=4096, the queue will use 8K of memory. The bitstring always uses
98 * 8K of memory (2^16/8). This yields to around 7% ID collisions. No memory
99 * is allocated until the use of random ids is enabled.
100 */
101
102#include <sys/param.h>
103#include <sys/time.h>
104#include <sys/kernel.h>
105#include <sys/random.h>
106#include <sys/protosw.h>
107#include <sys/bitstring.h>
108#include <kern/locks.h>
109#include <net/if_var.h>
110#include <netinet/in.h>
111#include <netinet/in_var.h>
112#include <netinet/ip_var.h>
113#include <dev/random/randomdev.h>
114
115/*
116 * Size of L (see comments above on the lower and upper limits.)
117 */
118#define ARRAY_SIZE (4096)
119
120static uint16_t *id_array = NULL;
121static bitstr_t *id_bits = NULL;
122static uint32_t array_ptr = 0;
123static uint32_t random_id_statistics = 0;
124static uint64_t random_id_collisions = 0;
125static uint64_t random_id_total = 0;
126
127decl_lck_mtx_data(static, ipid_lock);
128static lck_attr_t *ipid_lock_attr;
129static lck_grp_t *ipid_lock_grp;
130static lck_grp_attr_t *ipid_lock_grp_attr;
131
132SYSCTL_UINT(_net_inet_ip, OID_AUTO, random_id_statistics,
133 CTLFLAG_RW | CTLFLAG_LOCKED, &random_id_statistics, 0,
134 "Enable IP ID statistics");
135SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_collisions,
136 CTLFLAG_RD | CTLFLAG_LOCKED, &random_id_collisions,
137 "Count of IP ID collisions");
138SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_total,
139 CTLFLAG_RD | CTLFLAG_LOCKED, &random_id_total,
140 "Count of IP IDs created");
141
142/*
143 * Called once from ip_init().
144 */
145void
146ip_initid(void)
147{
148 VERIFY(id_array == NULL);
149 VERIFY(id_bits == NULL);
150
151 _CASSERT(ARRAY_SIZE >= 512 && ARRAY_SIZE <= 32768);
152
153 ipid_lock_grp_attr = lck_grp_attr_alloc_init();
154 ipid_lock_grp = lck_grp_alloc_init("ipid", ipid_lock_grp_attr);
155 ipid_lock_attr = lck_attr_alloc_init();
156 lck_mtx_init(&ipid_lock, ipid_lock_grp, ipid_lock_attr);
157
158 id_array = (uint16_t *)_MALLOC(ARRAY_SIZE * sizeof (uint16_t),
159 M_TEMP, M_WAITOK | M_ZERO);
160 id_bits = (bitstr_t *)_MALLOC(bitstr_size(65536), M_TEMP,
161 M_WAITOK | M_ZERO);
162 if (id_array == NULL || id_bits == NULL) {
163 /* Just in case; neither or both. */
164 if (id_array != NULL) {
165 _FREE(id_array, M_TEMP);
166 id_array = NULL;
167 }
168 if (id_bits != NULL) {
169 _FREE(id_bits, M_TEMP);
170 id_bits = NULL;
171 }
172 }
173}
174
175uint16_t
176ip_randomid(void)
177{
178 uint16_t new_id;
179
180 /*
181 * If net.inet.ip.random_id is disabled, revert to incrementing ip_id.
182 * Given that we don't allow the size of the array to change, accessing
183 * id_array and id_bits prior to acquiring the lock below is safe.
184 */
185 if (id_array == NULL || ip_use_randomid == 0)
186 return (htons(ip_id++));
187
188 /*
189 * To avoid a conflict with the zeros that the array is initially
190 * filled with, we never hand out an id of zero. bit_test() below
191 * uses single memory access, therefore no lock is needed.
192 */
193 new_id = 0;
194 do {
195 if (random_id_statistics && new_id != 0)
196 random_id_collisions++;
197 read_random(&new_id, sizeof (new_id));
198 } while (bitstr_test(id_bits, new_id) || new_id == 0);
199
200 /*
201 * These require serialization to maintain correctness.
202 */
203 lck_mtx_lock_spin(&ipid_lock);
204 bitstr_clear(id_bits, id_array[array_ptr]);
205 bitstr_set(id_bits, new_id);
206 id_array[array_ptr] = new_id;
207 if (++array_ptr == ARRAY_SIZE)
208 array_ptr = 0;
209 lck_mtx_unlock(&ipid_lock);
210
211 if (random_id_statistics)
212 random_id_total++;
213
214 return (new_id);
215}
216