1218792Snp/* $OpenBSD: match.c,v 1.44 2023/04/06 03:19:32 djm Exp $ */ 2218792Snp/* 3218792Snp * Author: Tatu Ylonen <ylo@cs.hut.fi> 4218792Snp * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland 5218792Snp * All rights reserved 6218792Snp * Simple pattern matching, with '*' and '?' as wildcards. 7218792Snp * 8218792Snp * As far as I am concerned, the code I have written for this software 9218792Snp * can be used freely for any purpose. Any derived versions of this 10218792Snp * software must be clearly marked as such, and if the derived work is 11218792Snp * incompatible with the protocol description in the RFC file, it must be 12218792Snp * called by a name other than "ssh" or "Secure Shell". 13218792Snp */ 14218792Snp/* 15218792Snp * Copyright (c) 2000 Markus Friedl. All rights reserved. 16218792Snp * 17218792Snp * Redistribution and use in source and binary forms, with or without 18218792Snp * modification, are permitted provided that the following conditions 19218792Snp * are met: 20218792Snp * 1. Redistributions of source code must retain the above copyright 21218792Snp * notice, this list of conditions and the following disclaimer. 22218792Snp * 2. Redistributions in binary form must reproduce the above copyright 23218792Snp * notice, this list of conditions and the following disclaimer in the 24218792Snp * documentation and/or other materials provided with the distribution. 25218792Snp * 26218792Snp * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 27218792Snp * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 28218792Snp * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 29218792Snp * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 30218792Snp * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 31218792Snp * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32218792Snp * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33218792Snp * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34218792Snp * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 35218792Snp * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36218792Snp */ 37218792Snp 38218792Snp#include "includes.h" 39219286Snp 40219286Snp#include <sys/types.h> 41219286Snp 42218792Snp#include <ctype.h> 43218792Snp#include <stdlib.h> 44218792Snp#include <string.h> 45218792Snp#include <stdarg.h> 46218792Snp#include <stdio.h> 47219436Snp 48218792Snp#include "xmalloc.h" 49218792Snp#include "match.h" 50218792Snp#include "misc.h" 51218792Snp 52218792Snp/* 53218792Snp * Returns true if the given string matches the pattern (which may contain ? 54218792Snp * and * as wildcards), and zero if it does not match. 55218792Snp */ 56222003Snpint 57218792Snpmatch_pattern(const char *s, const char *pattern) 58218792Snp{ 59221474Snp for (;;) { 60218792Snp /* If at end of pattern, accept if also at end of string. */ 61218792Snp if (!*pattern) 62218792Snp return !*s; 63222509Snp 64218792Snp if (*pattern == '*') { 65218792Snp /* Skip this and any consecutive asterisks. */ 66218792Snp while (*pattern == '*') 67218792Snp pattern++; 68218792Snp 69218792Snp /* If at end of pattern, accept immediately. */ 70218792Snp if (!*pattern) 71218792Snp return 1; 72218792Snp 73218792Snp /* If next character in pattern is known, optimize. */ 74227843Smarius if (*pattern != '?' && *pattern != '*') { 75218792Snp /* 76218792Snp * Look instances of the next character in 77218792Snp * pattern, and try to match starting from 78218792Snp * those. 79218792Snp */ 80218792Snp for (; *s; s++) 81218792Snp if (*s == *pattern && 82218792Snp match_pattern(s + 1, pattern + 1)) 83218792Snp return 1; 84218792Snp /* Failed. */ 85218792Snp return 0; 86218792Snp } 87218792Snp /* 88218792Snp * Move ahead one character at a time and try to 89218792Snp * match at each position. 90218792Snp */ 91218792Snp for (; *s; s++) 92218792Snp if (match_pattern(s, pattern)) 93218792Snp return 1; 94218792Snp /* Failed. */ 95218792Snp return 0; 96218792Snp } 97218792Snp /* 98218792Snp * There must be at least one more character in the string. 99218792Snp * If we are at the end, fail. 100218792Snp */ 101218792Snp if (!*s) 102218792Snp return 0; 103218792Snp 104218792Snp /* Check if the next character of the string is acceptable. */ 105218792Snp if (*pattern != '?' && *pattern != *s) 106218792Snp return 0; 107218792Snp 108218792Snp /* Move to the next character, both in string and in pattern. */ 109218792Snp s++; 110218792Snp pattern++; 111218792Snp } 112218792Snp /* NOTREACHED */ 113218792Snp} 114218792Snp 115218792Snp/* 116218792Snp * Tries to match the string against the 117218792Snp * comma-separated sequence of subpatterns (each possibly preceded by ! to 118218792Snp * indicate negation). Returns -1 if negation matches, 1 if there is 119218792Snp * a positive match, 0 if there is no match at all. 120218792Snp */ 121218792Snpint 122218792Snpmatch_pattern_list(const char *string, const char *pattern, int dolower) 123228561Snp{ 124228561Snp char sub[1024]; 125228561Snp int negated; 126228561Snp int got_positive; 127228561Snp u_int i, subi, len = strlen(pattern); 128228561Snp 129218792Snp got_positive = 0; 130218792Snp for (i = 0; i < len;) { 131228561Snp /* Check if the subpattern is negated. */ 132218792Snp if (pattern[i] == '!') { 133218792Snp negated = 1; 134218792Snp i++; 135228561Snp } else 136218792Snp negated = 0; 137228561Snp 138228561Snp /* 139228561Snp * Extract the subpattern up to a comma or end. Convert the 140218792Snp * subpattern to lowercase. 141228561Snp */ 142228561Snp for (subi = 0; 143228561Snp i < len && subi < sizeof(sub) - 1 && pattern[i] != ','; 144218792Snp subi++, i++) 145228561Snp sub[subi] = dolower && isupper((u_char)pattern[i]) ? 146228561Snp tolower((u_char)pattern[i]) : pattern[i]; 147228561Snp /* If subpattern too long, return failure (no match). */ 148218792Snp if (subi >= sizeof(sub) - 1) 149228561Snp return 0; 150228561Snp 151228561Snp /* If the subpattern was terminated by a comma, then skip it. */ 152218792Snp if (i < len && pattern[i] == ',') 153228561Snp i++; 154228561Snp 155228561Snp /* Null-terminate the subpattern. */ 156228561Snp sub[subi] = '\0'; 157228561Snp 158228561Snp /* Try to match the subpattern against the string. */ 159228561Snp if (match_pattern(string, sub)) { 160228561Snp if (negated) 161228561Snp return -1; /* Negative */ 162228561Snp else 163228561Snp got_positive = 1; /* Positive */ 164228561Snp } 165228561Snp } 166228561Snp 167228561Snp /* 168228561Snp * Return success if got a positive match. If there was a negative 169228561Snp * match, we have already returned -1 and never get here. 170228561Snp */ 171218792Snp return got_positive; 172218792Snp} 173218792Snp 174228561Snp/* Match a list representing users or groups. */ 175228561Snpint 176228561Snpmatch_usergroup_pattern_list(const char *string, const char *pattern) 177218792Snp{ 178228561Snp#ifdef HAVE_CYGWIN 179228561Snp /* Windows usernames may be Unicode and are not case sensitive */ 180228561Snp return cygwin_ug_match_pattern_list(string, pattern); 181218792Snp#else 182228561Snp /* Case sensitive match */ 183228561Snp return match_pattern_list(string, pattern, 0); 184228561Snp#endif 185218792Snp} 186228561Snp 187228561Snp/* 188228561Snp * Tries to match the host name (which must be in all lowercase) against the 189218792Snp * comma-separated sequence of subpatterns (each possibly preceded by ! to 190218792Snp * indicate negation). Returns -1 if negation matches, 1 if there is 191218792Snp * a positive match, 0 if there is no match at all. 192218792Snp */ 193228561Snpint 194228561Snpmatch_hostname(const char *host, const char *pattern) 195218792Snp{ 196228561Snp char *hostcopy = xstrdup(host); 197228561Snp int r; 198218792Snp 199218792Snp lowercase(hostcopy); 200228561Snp r = match_pattern_list(hostcopy, pattern, 1); 201218792Snp free(hostcopy); 202228561Snp return r; 203228561Snp} 204218792Snp 205218792Snp/* 206228561Snp * returns 0 if we get a negative match for the hostname or the ip 207218792Snp * or if we get no match at all. returns -1 on error, or 1 on 208228561Snp * successful match. 209228561Snp */ 210218792Snpint 211228561Snpmatch_host_and_ip(const char *host, const char *ipaddr, 212228561Snp const char *patterns) 213228561Snp{ 214228561Snp int mhost, mip; 215228561Snp 216228561Snp if ((mip = addr_match_list(ipaddr, patterns)) == -2) 217221474Snp return -1; /* error in ipaddr match */ 218228561Snp else if (host == NULL || ipaddr == NULL || mip == -1) 219228561Snp return 0; /* negative ip address match, or testing pattern */ 220228561Snp 221228561Snp /* negative hostname match */ 222228561Snp if ((mhost = match_hostname(host, patterns)) == -1) 223228561Snp return 0; 224228561Snp /* no match at all */ 225228561Snp if (mhost == 0 && mip == 0) 226228561Snp return 0; 227228561Snp return 1; 228228561Snp} 229228561Snp 230228561Snp/* 231228561Snp * Match user, user@host_or_ip, user@host_or_ip_list against pattern. 232228561Snp * If user, host and ipaddr are all NULL then validate pattern/ 233218792Snp * Returns -1 on invalid pattern, 0 on no match, 1 on match. 234219944Snp */ 235218792Snpint 236228561Snpmatch_user(const char *user, const char *host, const char *ipaddr, 237218792Snp const char *pattern) 238218792Snp{ 239218792Snp char *p, *pat; 240218792Snp int ret; 241228561Snp 242228561Snp /* test mode */ 243228561Snp if (user == NULL && host == NULL && ipaddr == NULL) { 244228561Snp if ((p = strchr(pattern, '@')) != NULL && 245228561Snp match_host_and_ip(NULL, NULL, p + 1) < 0) 246228561Snp return -1; 247218792Snp return 0; 248218792Snp } 249221474Snp 250221474Snp if (user == NULL) 251221474Snp return 0; /* shouldn't happen */ 252221474Snp 253221474Snp if ((p = strchr(pattern, '@')) == NULL) 254222509Snp return match_pattern(user, pattern); 255221474Snp 256221474Snp pat = xstrdup(pattern); 257221474Snp p = strchr(pat, '@'); 258221474Snp *p++ = '\0'; 259218792Snp 260218792Snp if ((ret = match_pattern(user, pat)) == 1) 261218792Snp ret = match_host_and_ip(host, ipaddr, p); 262218792Snp free(pat); 263218792Snp 264218792Snp return ret; 265218792Snp} 266218792Snp 267218792Snp/* 268218792Snp * Returns first item from client-list that is also supported by server-list, 269218792Snp * caller must free the returned string. 270218792Snp */ 271218792Snp#define MAX_PROP 40 272218792Snp#define SEP "," 273218792Snpchar * 274218792Snpmatch_list(const char *client, const char *server, u_int *next) 275228561Snp{ 276228561Snp char *sproposals[MAX_PROP]; 277228561Snp char *c, *s, *p, *ret, *cp, *sp; 278228561Snp int i, j, nproposals; 279228561Snp 280218792Snp c = cp = xstrdup(client); 281218792Snp s = sp = xstrdup(server); 282218792Snp 283218792Snp for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0'; 284218792Snp (p = strsep(&sp, SEP)), i++) { 285218792Snp if (i < MAX_PROP) 286218792Snp sproposals[i] = p; 287228561Snp else 288228561Snp break; 289228561Snp } 290228561Snp nproposals = i; 291228561Snp 292228561Snp for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0'; 293228561Snp (p = strsep(&cp, SEP)), i++) { 294218792Snp for (j = 0; j < nproposals; j++) { 295228561Snp if (strcmp(p, sproposals[j]) == 0) { 296218792Snp ret = xstrdup(p); 297218792Snp if (next != NULL) 298218792Snp *next = (cp == NULL) ? 299218792Snp strlen(c) : (u_int)(cp - c); 300218792Snp free(c); 301228561Snp free(s); 302228561Snp return ret; 303218792Snp } 304218792Snp } 305219436Snp } 306228561Snp if (next != NULL) 307218792Snp *next = strlen(c); 308218792Snp free(c); 309218792Snp free(s); 310218792Snp return NULL; 311218792Snp} 312228561Snp 313228561Snp/* 314228561Snp * Filter proposal using pattern-list filter. 315222551Snp * "denylist" determines sense of filter: 316228561Snp * non-zero indicates that items matching filter should be excluded. 317228561Snp * zero indicates that only items matching filter should be included. 318228561Snp * returns NULL on allocation error, otherwise caller must free result. 319228561Snp */ 320228561Snpstatic char * 321228561Snpfilter_list(const char *proposal, const char *filter, int denylist) 322228561Snp{ 323228561Snp size_t len = strlen(proposal) + 1; 324228561Snp char *fix_prop = malloc(len); 325228561Snp char *orig_prop = strdup(proposal); 326228561Snp char *cp, *tmp; 327219286Snp int r; 328221474Snp 329221474Snp if (fix_prop == NULL || orig_prop == NULL) { 330221474Snp free(orig_prop); 331221474Snp free(fix_prop); 332221474Snp return NULL; 333222552Snp } 334221474Snp 335221474Snp tmp = orig_prop; 336221474Snp *fix_prop = '\0'; 337222509Snp while ((cp = strsep(&tmp, ",")) != NULL) { 338221474Snp r = match_pattern_list(cp, filter, 0); 339221474Snp if ((denylist && r != 1) || (!denylist && r == 1)) { 340228561Snp if (*fix_prop != '\0') 341228561Snp strlcat(fix_prop, ",", len); 342222973Snp strlcat(fix_prop, cp, len); 343228561Snp } 344228561Snp } 345228561Snp free(orig_prop); 346228561Snp return fix_prop; 347228561Snp} 348228561Snp 349219392Snp/* 350218792Snp * Filters a comma-separated list of strings, excluding any entry matching 351218792Snp * the 'filter' pattern list. Caller must free returned string. 352218792Snp */ 353218792Snpchar * 354218792Snpmatch_filter_denylist(const char *proposal, const char *filter) 355218792Snp{ 356218792Snp return filter_list(proposal, filter, 1); 357218792Snp} 358218792Snp 359218792Snp/* 360218792Snp * Filters a comma-separated list of strings, including only entries matching 361218792Snp * the 'filter' pattern list. Caller must free returned string. 362218792Snp */ 363218792Snpchar * 364218792Snpmatch_filter_allowlist(const char *proposal, const char *filter) 365218792Snp{ 366218792Snp return filter_list(proposal, filter, 0); 367218792Snp} 368218792Snp