1263970Sdes/* $OpenBSD: match.c,v 1.29 2013/11/20 20:54:10 deraadt Exp $ */ 257429Smarkm/* 357429Smarkm * Author: Tatu Ylonen <ylo@cs.hut.fi> 457429Smarkm * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland 557429Smarkm * All rights reserved 657429Smarkm * Simple pattern matching, with '*' and '?' as wildcards. 760573Skris * 865668Skris * As far as I am concerned, the code I have written for this software 965668Skris * can be used freely for any purpose. Any derived versions of this 1065668Skris * software must be clearly marked as such, and if the derived work is 1165668Skris * incompatible with the protocol description in the RFC file, it must be 1265668Skris * called by a name other than "ssh" or "Secure Shell". 1357429Smarkm */ 1476259Sgreen/* 1576259Sgreen * Copyright (c) 2000 Markus Friedl. All rights reserved. 1676259Sgreen * 1776259Sgreen * Redistribution and use in source and binary forms, with or without 1876259Sgreen * modification, are permitted provided that the following conditions 1976259Sgreen * are met: 2076259Sgreen * 1. Redistributions of source code must retain the above copyright 2176259Sgreen * notice, this list of conditions and the following disclaimer. 2276259Sgreen * 2. Redistributions in binary form must reproduce the above copyright 2376259Sgreen * notice, this list of conditions and the following disclaimer in the 2476259Sgreen * documentation and/or other materials provided with the distribution. 2576259Sgreen * 2676259Sgreen * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 2776259Sgreen * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2876259Sgreen * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2976259Sgreen * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 3076259Sgreen * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 3176259Sgreen * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3276259Sgreen * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3376259Sgreen * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3476259Sgreen * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 3576259Sgreen * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3676259Sgreen */ 3757429Smarkm 3857429Smarkm#include "includes.h" 3957429Smarkm 40162852Sdes#include <sys/types.h> 41162852Sdes 42162852Sdes#include <ctype.h> 43263970Sdes#include <stdlib.h> 44162852Sdes#include <string.h> 45162852Sdes 46162852Sdes#include "xmalloc.h" 4776259Sgreen#include "match.h" 4857429Smarkm 4957429Smarkm/* 5057429Smarkm * Returns true if the given string matches the pattern (which may contain ? 5157429Smarkm * and * as wildcards), and zero if it does not match. 5257429Smarkm */ 5357429Smarkm 5460573Skrisint 5557429Smarkmmatch_pattern(const char *s, const char *pattern) 5657429Smarkm{ 5757429Smarkm for (;;) { 5857429Smarkm /* If at end of pattern, accept if also at end of string. */ 5957429Smarkm if (!*pattern) 6057429Smarkm return !*s; 6157429Smarkm 6257429Smarkm if (*pattern == '*') { 6357429Smarkm /* Skip the asterisk. */ 6457429Smarkm pattern++; 6557429Smarkm 6657429Smarkm /* If at end of pattern, accept immediately. */ 6757429Smarkm if (!*pattern) 6857429Smarkm return 1; 6957429Smarkm 7057429Smarkm /* If next character in pattern is known, optimize. */ 7157429Smarkm if (*pattern != '?' && *pattern != '*') { 7257429Smarkm /* 7357429Smarkm * Look instances of the next character in 7457429Smarkm * pattern, and try to match starting from 7557429Smarkm * those. 7657429Smarkm */ 7757429Smarkm for (; *s; s++) 7857429Smarkm if (*s == *pattern && 7957429Smarkm match_pattern(s + 1, pattern + 1)) 8057429Smarkm return 1; 8157429Smarkm /* Failed. */ 8257429Smarkm return 0; 8357429Smarkm } 8457429Smarkm /* 8557429Smarkm * Move ahead one character at a time and try to 8657429Smarkm * match at each position. 8757429Smarkm */ 8857429Smarkm for (; *s; s++) 8957429Smarkm if (match_pattern(s, pattern)) 9057429Smarkm return 1; 9157429Smarkm /* Failed. */ 9257429Smarkm return 0; 9357429Smarkm } 9457429Smarkm /* 9557429Smarkm * There must be at least one more character in the string. 9657429Smarkm * If we are at the end, fail. 9757429Smarkm */ 9857429Smarkm if (!*s) 9957429Smarkm return 0; 10057429Smarkm 10157429Smarkm /* Check if the next character of the string is acceptable. */ 10257429Smarkm if (*pattern != '?' && *pattern != *s) 10357429Smarkm return 0; 10457429Smarkm 10557429Smarkm /* Move to the next character, both in string and in pattern. */ 10657429Smarkm s++; 10757429Smarkm pattern++; 10857429Smarkm } 10957429Smarkm /* NOTREACHED */ 11057429Smarkm} 11158582Skris 11258582Skris/* 11392555Sdes * Tries to match the string against the 11458582Skris * comma-separated sequence of subpatterns (each possibly preceded by ! to 11565668Skris * indicate negation). Returns -1 if negation matches, 1 if there is 11665668Skris * a positive match, 0 if there is no match at all. 11758582Skris */ 11858582Skris 11958582Skrisint 12092555Sdesmatch_pattern_list(const char *string, const char *pattern, u_int len, 12192555Sdes int dolower) 12258582Skris{ 12358582Skris char sub[1024]; 12458582Skris int negated; 12558582Skris int got_positive; 12676259Sgreen u_int i, subi; 12758582Skris 12858582Skris got_positive = 0; 12958582Skris for (i = 0; i < len;) { 13058582Skris /* Check if the subpattern is negated. */ 13158582Skris if (pattern[i] == '!') { 13258582Skris negated = 1; 13358582Skris i++; 13458582Skris } else 13558582Skris negated = 0; 13658582Skris 13758582Skris /* 13858582Skris * Extract the subpattern up to a comma or end. Convert the 13958582Skris * subpattern to lowercase. 14058582Skris */ 14158582Skris for (subi = 0; 14292555Sdes i < len && subi < sizeof(sub) - 1 && pattern[i] != ','; 14392555Sdes subi++, i++) 144263970Sdes sub[subi] = dolower && isupper((u_char)pattern[i]) ? 145263970Sdes tolower((u_char)pattern[i]) : pattern[i]; 14658582Skris /* If subpattern too long, return failure (no match). */ 14758582Skris if (subi >= sizeof(sub) - 1) 14858582Skris return 0; 14958582Skris 15058582Skris /* If the subpattern was terminated by a comma, skip the comma. */ 15158582Skris if (i < len && pattern[i] == ',') 15258582Skris i++; 15358582Skris 15458582Skris /* Null-terminate the subpattern. */ 15558582Skris sub[subi] = '\0'; 15658582Skris 15792555Sdes /* Try to match the subpattern against the string. */ 15892555Sdes if (match_pattern(string, sub)) { 15958582Skris if (negated) 16065668Skris return -1; /* Negative */ 16158582Skris else 16265668Skris got_positive = 1; /* Positive */ 16358582Skris } 16458582Skris } 16558582Skris 16658582Skris /* 16758582Skris * Return success if got a positive match. If there was a negative 16865668Skris * match, we have already returned -1 and never get here. 16958582Skris */ 17058582Skris return got_positive; 17158582Skris} 17276259Sgreen 17392555Sdes/* 17492555Sdes * Tries to match the host name (which must be in all lowercase) against the 17592555Sdes * comma-separated sequence of subpatterns (each possibly preceded by ! to 17692555Sdes * indicate negation). Returns -1 if negation matches, 1 if there is 17792555Sdes * a positive match, 0 if there is no match at all. 17892555Sdes */ 17992555Sdesint 18092555Sdesmatch_hostname(const char *host, const char *pattern, u_int len) 18192555Sdes{ 18292555Sdes return match_pattern_list(host, pattern, len, 1); 18392555Sdes} 18476259Sgreen 18592555Sdes/* 18692555Sdes * returns 0 if we get a negative match for the hostname or the ip 187181111Sdes * or if we get no match at all. returns -1 on error, or 1 on 188181111Sdes * successful match. 18992555Sdes */ 19092555Sdesint 19192555Sdesmatch_host_and_ip(const char *host, const char *ipaddr, 19292555Sdes const char *patterns) 19392555Sdes{ 19492555Sdes int mhost, mip; 19592555Sdes 196181111Sdes /* error in ipaddr match */ 197181111Sdes if ((mip = addr_match_list(ipaddr, patterns)) == -2) 198181111Sdes return -1; 199181111Sdes else if (mip == -1) /* negative ip address match */ 20092555Sdes return 0; 201181111Sdes 20292555Sdes /* negative hostname match */ 20392555Sdes if ((mhost = match_hostname(host, patterns, strlen(patterns))) == -1) 20492555Sdes return 0; 20592555Sdes /* no match at all */ 20692555Sdes if (mhost == 0 && mip == 0) 20792555Sdes return 0; 20892555Sdes return 1; 20992555Sdes} 21092555Sdes 21192555Sdes/* 21292555Sdes * match user, user@host_or_ip, user@host_or_ip_list against pattern 21392555Sdes */ 21492555Sdesint 21592555Sdesmatch_user(const char *user, const char *host, const char *ipaddr, 21692555Sdes const char *pattern) 21792555Sdes{ 21892555Sdes char *p, *pat; 21992555Sdes int ret; 22092555Sdes 22192555Sdes if ((p = strchr(pattern,'@')) == NULL) 22292555Sdes return match_pattern(user, pattern); 22392555Sdes 22492555Sdes pat = xstrdup(pattern); 22592555Sdes p = strchr(pat, '@'); 22692555Sdes *p++ = '\0'; 22792555Sdes 22892555Sdes if ((ret = match_pattern(user, pat)) == 1) 22992555Sdes ret = match_host_and_ip(host, ipaddr, p); 230263970Sdes free(pat); 23192555Sdes 23292555Sdes return ret; 23392555Sdes} 23492555Sdes 23592555Sdes/* 23692555Sdes * Returns first item from client-list that is also supported by server-list, 237263970Sdes * caller must free the returned string. 23892555Sdes */ 23992555Sdes#define MAX_PROP 40 24076259Sgreen#define SEP "," 24176259Sgreenchar * 24276259Sgreenmatch_list(const char *client, const char *server, u_int *next) 24376259Sgreen{ 24476259Sgreen char *sproposals[MAX_PROP]; 24576259Sgreen char *c, *s, *p, *ret, *cp, *sp; 24676259Sgreen int i, j, nproposals; 24776259Sgreen 24876259Sgreen c = cp = xstrdup(client); 24976259Sgreen s = sp = xstrdup(server); 25076259Sgreen 25176259Sgreen for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0'; 25292555Sdes (p = strsep(&sp, SEP)), i++) { 25376259Sgreen if (i < MAX_PROP) 25476259Sgreen sproposals[i] = p; 25576259Sgreen else 25676259Sgreen break; 25776259Sgreen } 25876259Sgreen nproposals = i; 25976259Sgreen 26076259Sgreen for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0'; 26192555Sdes (p = strsep(&cp, SEP)), i++) { 26276259Sgreen for (j = 0; j < nproposals; j++) { 26376259Sgreen if (strcmp(p, sproposals[j]) == 0) { 26476259Sgreen ret = xstrdup(p); 26576259Sgreen if (next != NULL) 26676259Sgreen *next = (cp == NULL) ? 267149749Sdes strlen(c) : (u_int)(cp - c); 268263970Sdes free(c); 269263970Sdes free(s); 27076259Sgreen return ret; 27176259Sgreen } 27276259Sgreen } 27376259Sgreen } 27476259Sgreen if (next != NULL) 27576259Sgreen *next = strlen(c); 276263970Sdes free(c); 277263970Sdes free(s); 27876259Sgreen return NULL; 27976259Sgreen} 280