xref: /openbsd/usr.bin/ssh/match.c (revision 3cab2bb3)
1 /* $OpenBSD: match.c,v 1.42 2020/07/05 23:59:45 djm Exp $ */
2 /*
3  * Author: Tatu Ylonen <ylo@cs.hut.fi>
4  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
5  *                    All rights reserved
6  * Simple pattern matching, with '*' and '?' as wildcards.
7  *
8  * As far as I am concerned, the code I have written for this software
9  * can be used freely for any purpose.  Any derived versions of this
10  * software must be clearly marked as such, and if the derived work is
11  * incompatible with the protocol description in the RFC file, it must be
12  * called by a name other than "ssh" or "Secure Shell".
13  */
14 /*
15  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
16  *
17  * Redistribution and use in source and binary forms, with or without
18  * modification, are permitted provided that the following conditions
19  * are met:
20  * 1. Redistributions of source code must retain the above copyright
21  *    notice, this list of conditions and the following disclaimer.
22  * 2. Redistributions in binary form must reproduce the above copyright
23  *    notice, this list of conditions and the following disclaimer in the
24  *    documentation and/or other materials provided with the distribution.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
27  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
28  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
29  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
30  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
31  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
35  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36  */
37 
38 #include <sys/types.h>
39 
40 #include <ctype.h>
41 #include <stdlib.h>
42 #include <string.h>
43 #include <stdarg.h>
44 #include <stdio.h>
45 
46 #include "xmalloc.h"
47 #include "match.h"
48 #include "misc.h"
49 
50 /*
51  * Returns true if the given string matches the pattern (which may contain ?
52  * and * as wildcards), and zero if it does not match.
53  */
54 
55 int
56 match_pattern(const char *s, const char *pattern)
57 {
58 	for (;;) {
59 		/* If at end of pattern, accept if also at end of string. */
60 		if (!*pattern)
61 			return !*s;
62 
63 		if (*pattern == '*') {
64 			/* Skip the asterisk. */
65 			pattern++;
66 
67 			/* If at end of pattern, accept immediately. */
68 			if (!*pattern)
69 				return 1;
70 
71 			/* If next character in pattern is known, optimize. */
72 			if (*pattern != '?' && *pattern != '*') {
73 				/*
74 				 * Look instances of the next character in
75 				 * pattern, and try to match starting from
76 				 * those.
77 				 */
78 				for (; *s; s++)
79 					if (*s == *pattern &&
80 					    match_pattern(s + 1, pattern + 1))
81 						return 1;
82 				/* Failed. */
83 				return 0;
84 			}
85 			/*
86 			 * Move ahead one character at a time and try to
87 			 * match at each position.
88 			 */
89 			for (; *s; s++)
90 				if (match_pattern(s, pattern))
91 					return 1;
92 			/* Failed. */
93 			return 0;
94 		}
95 		/*
96 		 * There must be at least one more character in the string.
97 		 * If we are at the end, fail.
98 		 */
99 		if (!*s)
100 			return 0;
101 
102 		/* Check if the next character of the string is acceptable. */
103 		if (*pattern != '?' && *pattern != *s)
104 			return 0;
105 
106 		/* Move to the next character, both in string and in pattern. */
107 		s++;
108 		pattern++;
109 	}
110 	/* NOTREACHED */
111 }
112 
113 /*
114  * Tries to match the string against the
115  * comma-separated sequence of subpatterns (each possibly preceded by ! to
116  * indicate negation).  Returns -1 if negation matches, 1 if there is
117  * a positive match, 0 if there is no match at all.
118  */
119 int
120 match_pattern_list(const char *string, const char *pattern, int dolower)
121 {
122 	char sub[1024];
123 	int negated;
124 	int got_positive;
125 	u_int i, subi, len = strlen(pattern);
126 
127 	got_positive = 0;
128 	for (i = 0; i < len;) {
129 		/* Check if the subpattern is negated. */
130 		if (pattern[i] == '!') {
131 			negated = 1;
132 			i++;
133 		} else
134 			negated = 0;
135 
136 		/*
137 		 * Extract the subpattern up to a comma or end.  Convert the
138 		 * subpattern to lowercase.
139 		 */
140 		for (subi = 0;
141 		    i < len && subi < sizeof(sub) - 1 && pattern[i] != ',';
142 		    subi++, i++)
143 			sub[subi] = dolower && isupper((u_char)pattern[i]) ?
144 			    tolower((u_char)pattern[i]) : pattern[i];
145 		/* If subpattern too long, return failure (no match). */
146 		if (subi >= sizeof(sub) - 1)
147 			return 0;
148 
149 		/* If the subpattern was terminated by a comma, then skip it. */
150 		if (i < len && pattern[i] == ',')
151 			i++;
152 
153 		/* Null-terminate the subpattern. */
154 		sub[subi] = '\0';
155 
156 		/* Try to match the subpattern against the string. */
157 		if (match_pattern(string, sub)) {
158 			if (negated)
159 				return -1;		/* Negative */
160 			else
161 				got_positive = 1;	/* Positive */
162 		}
163 	}
164 
165 	/*
166 	 * Return success if got a positive match.  If there was a negative
167 	 * match, we have already returned -1 and never get here.
168 	 */
169 	return got_positive;
170 }
171 
172 /* Match a list representing users or groups. */
173 int
174 match_usergroup_pattern_list(const char *string, const char *pattern)
175 {
176 	/* Case sensitive match */
177 	return match_pattern_list(string, pattern, 0);
178 }
179 
180 /*
181  * Tries to match the host name (which must be in all lowercase) against the
182  * comma-separated sequence of subpatterns (each possibly preceded by ! to
183  * indicate negation).  Returns -1 if negation matches, 1 if there is
184  * a positive match, 0 if there is no match at all.
185  */
186 int
187 match_hostname(const char *host, const char *pattern)
188 {
189 	char *hostcopy = xstrdup(host);
190 	int r;
191 
192 	lowercase(hostcopy);
193 	r = match_pattern_list(hostcopy, pattern, 1);
194 	free(hostcopy);
195 	return r;
196 }
197 
198 /*
199  * returns 0 if we get a negative match for the hostname or the ip
200  * or if we get no match at all.  returns -1 on error, or 1 on
201  * successful match.
202  */
203 int
204 match_host_and_ip(const char *host, const char *ipaddr,
205     const char *patterns)
206 {
207 	int mhost, mip;
208 
209 	if ((mip = addr_match_list(ipaddr, patterns)) == -2)
210 		return -1; /* error in ipaddr match */
211 	else if (host == NULL || ipaddr == NULL || mip == -1)
212 		return 0; /* negative ip address match, or testing pattern */
213 
214 	/* negative hostname match */
215 	if ((mhost = match_hostname(host, patterns)) == -1)
216 		return 0;
217 	/* no match at all */
218 	if (mhost == 0 && mip == 0)
219 		return 0;
220 	return 1;
221 }
222 
223 /*
224  * Match user, user@host_or_ip, user@host_or_ip_list against pattern.
225  * If user, host and ipaddr are all NULL then validate pattern/
226  * Returns -1 on invalid pattern, 0 on no match, 1 on match.
227  */
228 int
229 match_user(const char *user, const char *host, const char *ipaddr,
230     const char *pattern)
231 {
232 	char *p, *pat;
233 	int ret;
234 
235 	/* test mode */
236 	if (user == NULL && host == NULL && ipaddr == NULL) {
237 		if ((p = strchr(pattern, '@')) != NULL &&
238 		    match_host_and_ip(NULL, NULL, p + 1) < 0)
239 			return -1;
240 		return 0;
241 	}
242 
243 	if ((p = strchr(pattern, '@')) == NULL)
244 		return match_pattern(user, pattern);
245 
246 	pat = xstrdup(pattern);
247 	p = strchr(pat, '@');
248 	*p++ = '\0';
249 
250 	if ((ret = match_pattern(user, pat)) == 1)
251 		ret = match_host_and_ip(host, ipaddr, p);
252 	free(pat);
253 
254 	return ret;
255 }
256 
257 /*
258  * Returns first item from client-list that is also supported by server-list,
259  * caller must free the returned string.
260  */
261 #define	MAX_PROP	40
262 #define	SEP	","
263 char *
264 match_list(const char *client, const char *server, u_int *next)
265 {
266 	char *sproposals[MAX_PROP];
267 	char *c, *s, *p, *ret, *cp, *sp;
268 	int i, j, nproposals;
269 
270 	c = cp = xstrdup(client);
271 	s = sp = xstrdup(server);
272 
273 	for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0';
274 	    (p = strsep(&sp, SEP)), i++) {
275 		if (i < MAX_PROP)
276 			sproposals[i] = p;
277 		else
278 			break;
279 	}
280 	nproposals = i;
281 
282 	for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0';
283 	    (p = strsep(&cp, SEP)), i++) {
284 		for (j = 0; j < nproposals; j++) {
285 			if (strcmp(p, sproposals[j]) == 0) {
286 				ret = xstrdup(p);
287 				if (next != NULL)
288 					*next = (cp == NULL) ?
289 					    strlen(c) : (u_int)(cp - c);
290 				free(c);
291 				free(s);
292 				return ret;
293 			}
294 		}
295 	}
296 	if (next != NULL)
297 		*next = strlen(c);
298 	free(c);
299 	free(s);
300 	return NULL;
301 }
302 
303 /*
304  * Filter proposal using pattern-list filter.
305  * "denylist" determines sense of filter:
306  * non-zero indicates that items matching filter should be excluded.
307  * zero indicates that only items matching filter should be included.
308  * returns NULL on allocation error, otherwise caller must free result.
309  */
310 static char *
311 filter_list(const char *proposal, const char *filter, int denylist)
312 {
313 	size_t len = strlen(proposal) + 1;
314 	char *fix_prop = malloc(len);
315 	char *orig_prop = strdup(proposal);
316 	char *cp, *tmp;
317 	int r;
318 
319 	if (fix_prop == NULL || orig_prop == NULL) {
320 		free(orig_prop);
321 		free(fix_prop);
322 		return NULL;
323 	}
324 
325 	tmp = orig_prop;
326 	*fix_prop = '\0';
327 	while ((cp = strsep(&tmp, ",")) != NULL) {
328 		r = match_pattern_list(cp, filter, 0);
329 		if ((denylist && r != 1) || (!denylist && r == 1)) {
330 			if (*fix_prop != '\0')
331 				strlcat(fix_prop, ",", len);
332 			strlcat(fix_prop, cp, len);
333 		}
334 	}
335 	free(orig_prop);
336 	return fix_prop;
337 }
338 
339 /*
340  * Filters a comma-separated list of strings, excluding any entry matching
341  * the 'filter' pattern list. Caller must free returned string.
342  */
343 char *
344 match_filter_denylist(const char *proposal, const char *filter)
345 {
346 	return filter_list(proposal, filter, 1);
347 }
348 
349 /*
350  * Filters a comma-separated list of strings, including only entries matching
351  * the 'filter' pattern list. Caller must free returned string.
352  */
353 char *
354 match_filter_allowlist(const char *proposal, const char *filter)
355 {
356 	return filter_list(proposal, filter, 0);
357 }
358