OSX/sec/securityd/nameconstraints.c

   1 /*
   2  * Copyright (c) 2015-2017 Apple Inc. All Rights Reserved.
   3  *
   4  * @APPLE_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. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 /*
  25  * nameconstraints.c - rfc5280 section 4.2.1.10 and later name constraints implementation.
  26  */
  27
  28 #include "nameconstraints.h"
  29 #include <AssertMacros.h>
  30 #include <utilities/SecCFWrappers.h>
  31 #include <Security/SecCertificateInternal.h>
  32 #include <securityd/SecPolicyServer.h>
  33 #include <libDER/asn1Types.h>
  34 #include <libDER/oids.h>
  35
  36 /* RFC 5280 Section 4.2.1.10:
  37  DNS name restrictions are expressed as host.example.com.  Any DNS
  38  name that can be constructed by simply adding zero or more labels to
  39  the left-hand side of the name satisfies the name constraint.  For
  40  example, www.host.example.com would satisfy the constraint but
  41  host1.example.com would not.
  42 */
  43 static bool SecDNSNameConstraintsMatch(CFStringRef DNSName, CFStringRef constraint) {
  44     CFIndex clength = CFStringGetLength(constraint);
  45     CFIndex dlength = CFStringGetLength(DNSName);
  46
  47     if (dlength < clength) return false;
  48
  49     /* Ensure that character to the left of the constraint in the DNSName is a '.'
  50      so that badexample.com does not match example.com, but good.example.com does.
  51      */
  52     if ((dlength != clength) && ('.' != CFStringGetCharacterAtIndex(constraint, 0)) &&
  53         ('.' != CFStringGetCharacterAtIndex(DNSName, dlength - clength -1))) {
  54         return false;
  55     }
  56
  57     CFRange compareRange = { dlength - clength, clength};
  58
  59     if (!CFStringCompareWithOptions(DNSName, constraint, compareRange, kCFCompareCaseInsensitive)) {
  60         return true;
  61     }
  62
  63     return false;
  64 }
  65
  66 /* RFC 5280 Section 4.2.1.10:
  67  For URIs, the constraint applies to the host part of the name.  The
  68  constraint MUST be specified as a fully qualified domain name and MAY
  69  specify a host or a domain.  Examples would be "host.example.com" and
  70  ".example.com".  When the constraint begins with a period, it MAY be
  71  expanded with one or more labels.  That is, the constraint
  72  ".example.com" is satisfied by both host.example.com and
  73  my.host.example.com.  However, the constraint ".example.com" is not
  74  satisfied by "example.com".  When the constraint does not begin with
  75  a period, it specifies a host.
  76  */
  77 static bool SecURIMatch(CFStringRef URI, CFStringRef hostname) {
  78     bool result = false;
  79     CFStringRef URI_hostname =  NULL;
  80     CFCharacterSetRef port_or_path_separator = NULL;
  81     /* URI must have scheme specified */
  82     CFRange URI_scheme = CFStringFind(URI, CFSTR("://"), 0);
  83     require_quiet(URI_scheme.location != kCFNotFound, out);
  84
  85     /* Remove scheme prefix and port or resource path suffix */
  86     CFRange URI_hostname_range = { URI_scheme.location + URI_scheme.length,
  87         CFStringGetLength(URI) - URI_scheme.location - URI_scheme.length };
  88     port_or_path_separator = CFCharacterSetCreateWithCharactersInString(kCFAllocatorDefault, CFSTR(":/"));
  89     CFRange separator = {kCFNotFound, 0};
  90     if(CFStringFindCharacterFromSet(URI, port_or_path_separator, URI_hostname_range, 0, &separator)) {
  91         URI_hostname_range.length -= (CFStringGetLength(URI) - separator.location);
  92     }
  93     URI_hostname = CFStringCreateWithSubstring(kCFAllocatorDefault, URI, URI_hostname_range);
  94
  95     /* Hostname in URI must not begin with '.' */
  96     require_quiet('.' != CFStringGetCharacterAtIndex(URI_hostname, 0), out);
  97
  98     CFIndex ulength = CFStringGetLength(URI_hostname);
  99     CFIndex hlength = CFStringGetLength(hostname);
 100     require_quiet(ulength >= hlength, out);
 101     CFRange compare_range = { 0, hlength };
 102
 103     /* Allow one or more preceding labels */
 104     if ('.' == CFStringGetCharacterAtIndex(hostname, 0)) {
 105         compare_range.location = ulength - hlength;
 106     }
 107
 108     if(kCFCompareEqualTo == CFStringCompareWithOptions(URI_hostname,
 109                                                        hostname,
 110                                                        compare_range,
 111                                                        kCFCompareCaseInsensitive)) {
 112         result = true;
 113     }
 114
 115 out:
 116     CFReleaseNull(port_or_path_separator);
 117     CFReleaseNull(URI_hostname);
 118     return result;
 119 }
 120
 121 /* RFC 5280 Section 4.2.1.10:
 122  A name constraint for Internet mail addresses MAY specify a
 123  particular mailbox, all addresses at a particular host, or all
 124  mailboxes in a domain.  To indicate a particular mailbox, the
 125  constraint is the complete mail address.  For example,
 126  "root@example.com" indicates the root mailbox on the host
 127  "example.com".  To indicate all Internet mail addresses on a
 128  particular host, the constraint is specified as the host name.  For
 129  example, the constraint "example.com" is satisfied by any mail
 130  address at the host "example.com".  To specify any address within a
 131  domain, the constraint is specified with a leading period (as with
 132  URIs).
 133  */
 134 static bool SecRFC822NameMatch(CFStringRef emailAddress, CFStringRef constraint) {
 135     CFRange mailbox_range = CFStringFind(constraint,CFSTR("@"),0);
 136
 137     /* Constraint specifies a particular mailbox. Perform full comparison. */
 138     if (mailbox_range.location != kCFNotFound) {
 139         if (!CFStringCompare(emailAddress, constraint, kCFCompareCaseInsensitive)) {
 140             return true;
 141         }
 142         else return false;
 143     }
 144
 145     mailbox_range = CFStringFind(emailAddress, CFSTR("@"), 0);
 146     require_quiet(mailbox_range.location != kCFNotFound, out);
 147     CFRange hostname_range = {mailbox_range.location + 1,
 148         CFStringGetLength(emailAddress) - mailbox_range.location - 1 };
 149
 150     /* Constraint specificies a particular host. Compare hostname of address. */
 151     if ('.' != CFStringGetCharacterAtIndex(constraint, 0)) {
 152         if (!CFStringCompareWithOptions(emailAddress, constraint, hostname_range, kCFCompareCaseInsensitive)) {
 153             return true;
 154         }
 155         else return false;
 156     }
 157
 158     /* Constraint specificies a domain. Match hostname of address to domain name. */
 159     require_quiet('.' != CFStringGetCharacterAtIndex(emailAddress, mailbox_range.location +1), out);
 160     if (CFStringHasSuffix(emailAddress, constraint)) {
 161         return true;
 162     }
 163
 164 out:
 165     return false;
 166 }
 167
 168 static bool nc_compare_directoryNames(const DERItem *certName, const DERItem *subtreeName) {
 169     /* Get content of certificate name and subtree name */
 170     DERDecodedInfo certName_content;
 171     require_noerr_quiet(DERDecodeItem(certName, &certName_content), out);
 172
 173     DERDecodedInfo subtreeName_content;
 174     require_noerr_quiet(DERDecodeItem(subtreeName, &subtreeName_content), out);
 175
 176     if (certName->length > subtreeName->length) {
 177         if(0 == memcmp(certName_content.content.data,
 178                        subtreeName_content.content.data,
 179                        subtreeName_content.content.length)) {
 180             return true;
 181         }
 182     }
 183
 184 out:
 185     return false;
 186 }
 187
 188 static bool nc_compare_DNSNames(const DERItem *certName, const DERItem *subtreeName) {
 189     bool result = false;
 190     CFStringRef certName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 191                                                        certName->data, certName->length,
 192                                                        kCFStringEncodingUTF8, FALSE);
 193     CFStringRef subtreeName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 194                                                           subtreeName->data, subtreeName->length,
 195                                                           kCFStringEncodingUTF8, FALSE);
 196     require_quiet(certName_str, out);
 197     require_quiet(subtreeName_str, out);
 198
 199     if (SecDNSNameConstraintsMatch(certName_str, subtreeName_str)) {
 200         result = true;
 201     }
 202
 203 out:
 204     CFReleaseNull(certName_str) ;
 205     CFReleaseNull(subtreeName_str);
 206     return result;
 207 }
 208
 209 static bool nc_compare_URIs(const DERItem *certName, const DERItem *subtreeName) {
 210     bool result = false;
 211     CFStringRef certName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 212                                                        certName->data, certName->length,
 213                                                        kCFStringEncodingUTF8, FALSE);
 214     CFStringRef subtreeName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 215                                                           subtreeName->data, subtreeName->length,
 216                                                           kCFStringEncodingUTF8, FALSE);
 217     require_quiet(certName_str, out);
 218     require_quiet(subtreeName_str, out);
 219
 220     if (SecURIMatch(certName_str, subtreeName_str)) {
 221         result = true;
 222     }
 223
 224 out:
 225     CFReleaseNull(certName_str);
 226     CFReleaseNull(subtreeName_str);
 227     return result;
 228 }
 229
 230 static bool nc_compare_RFC822Names(const DERItem *certName, const DERItem *subtreeName) {
 231     bool result = false;
 232     CFStringRef certName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 233                                                        certName->data, certName->length,
 234                                                        kCFStringEncodingUTF8, FALSE);
 235     CFStringRef subtreeName_str = CFStringCreateWithBytes(kCFAllocatorDefault,
 236                                                           subtreeName->data, subtreeName->length,
 237                                                           kCFStringEncodingUTF8, FALSE);
 238     require_quiet(certName_str, out);
 239     require_quiet(subtreeName_str, out);
 240
 241     if (SecRFC822NameMatch(certName_str, subtreeName_str)) {
 242         result = true;
 243     }
 244
 245 out:
 246     CFReleaseNull(certName_str);
 247     CFReleaseNull(subtreeName_str);
 248     return result;
 249 }
 250
 251 static bool nc_compare_IPAddresses(const DERItem *certAddr, const DERItem *subtreeAddr) {
 252     bool result = false;
 253
 254     /* Verify Subtree Address has correct number of bytes for IP and mask */
 255     require_quiet((subtreeAddr->length == 8) || (subtreeAddr->length == 32), out);
 256     /* Verify Cert Address has correct number of bytes for IP */
 257     require_quiet((certAddr->length == 4) || (certAddr->length ==16), out);
 258     /* Verify Subtree Address and Cert Address are the same version */
 259     require_quiet(subtreeAddr->length == 2*certAddr->length, out);
 260
 261     DERByte * mask = subtreeAddr->data + certAddr->length;
 262     for (DERSize i = 0; i < certAddr->length; i++) {
 263         if((subtreeAddr->data[i] & mask[i]) != (certAddr->data[i] & mask[i])) {
 264             return false;
 265         }
 266     }
 267     return true;
 268
 269 out:
 270     return result;
 271 }
 272
 273 typedef struct {
 274     bool present;
 275     bool isMatch;
 276 } match_t;
 277
 278 typedef struct {
 279     const SecCEGeneralNameType gnType;
 280     const DERItem *cert_item;
 281     match_t *match;
 282 } nc_match_context_t;
 283
 284 typedef struct {
 285     const CFArrayRef subtrees;
 286     match_t *match;
 287     bool permit;
 288 } nc_san_match_context_t;
 289
 290 static OSStatus nc_compare_subtree(void *context, SecCEGeneralNameType gnType, const DERItem *generalName) {
 291     nc_match_context_t *item_context = context;
 292     if (item_context && gnType == item_context->gnType
 293         && item_context->match && item_context->cert_item) {
 294
 295         item_context->match->present = true;
 296         /*
 297          * We set isMatch such that if there are multiple subtrees of the same type, matching to any one
 298          * of them is considered a match.
 299          */
 300         switch (gnType) {
 301             case GNT_DirectoryName: {
 302                 item_context->match->isMatch |= nc_compare_directoryNames(item_context->cert_item, generalName);
 303                 return errSecSuccess;
 304             }
 305             case GNT_DNSName: {
 306                 item_context->match->isMatch |= nc_compare_DNSNames(item_context->cert_item, generalName);
 307                 return errSecSuccess;
 308             }
 309             case GNT_URI: {
 310                 item_context->match->isMatch |= nc_compare_URIs(item_context->cert_item, generalName);
 311                 return errSecSuccess;
 312             }
 313             case GNT_RFC822Name: {
 314                 item_context->match->isMatch |= nc_compare_RFC822Names(item_context->cert_item, generalName);
 315                 return errSecSuccess;
 316             }
 317             case  GNT_IPAddress: {
 318                 item_context->match->isMatch |= nc_compare_IPAddresses(item_context->cert_item, generalName);
 319                 return errSecSuccess;
 320             }
 321             default: {
 322                 /* If the name form is not supported, reject the certificate. */
 323                 return errSecInvalidCertificate;
 324             }
 325         }
 326     }
 327
 328     return errSecInvalidCertificate;
 329 }
 330
 331 static void nc_decode_and_compare_subtree(const void *value, void *context) {
 332     CFDataRef subtree = value;
 333     nc_match_context_t *match_context = context;
 334     if (subtree) {
 335         /* convert subtree to DERItem */
 336         const DERItem general_name = { (unsigned char *)CFDataGetBytePtr(subtree), CFDataGetLength(subtree) };
 337         DERDecodedInfo general_name_content;
 338         require_noerr_quiet(DERDecodeItem(&general_name, &general_name_content),out);
 339
 340         OSStatus status = SecCertificateParseGeneralNameContentProperty(general_name_content.tag,
 341                                                                         &general_name_content.content,
 342                                                                         match_context,
 343                                                                         nc_compare_subtree);
 344         if (status == errSecInvalidCertificate) {
 345             secnotice("policy","can't parse general name or not a type we support");
 346         }
 347     }
 348 out:
 349     return;
 350 }
 351
 352 static bool isEmptySubject(CFDataRef subject) {
 353     const DERItem subject_der = { (unsigned char *)CFDataGetBytePtr(subject), CFDataGetLength(subject) };
 354
 355     /* Get content of certificate name */
 356     DERDecodedInfo subject_content;
 357     require_noerr_quiet(DERDecodeItem(&subject_der, &subject_content), out);
 358     if (subject_content.content.length) return false;
 359
 360 out:
 361     return true;
 362 }
 363
 364 /*
 365  * We update match structs as follows:
 366  * 'present' is true if there's any subtree of the same type as any Subject/SAN
 367  * 'match' is false if the subtree(s) and Subject(s)/SAN(s) don't match.
 368  * Note: the state of 'match' is meaningless without 'present' also being true.
 369  */
 370 static void update_match(bool permit, match_t *input_match, match_t *output_match) {
 371     if (!input_match || !output_match) {
 372         return;
 373     }
 374     if (input_match->present) {
 375         output_match->present = true;
 376         if (permit) {
 377             output_match->isMatch &= input_match->isMatch;
 378         } else {
 379             output_match->isMatch |= input_match->isMatch;
 380         }
 381     }
 382 }
 383
 384 static void nc_compare_RFC822Name_to_subtrees(const void *value, void *context) {
 385     CFStringRef rfc822Name = (CFStringRef)value;
 386     char *rfc822NameString = NULL;
 387     nc_san_match_context_t *san_context = context;
 388     CFArrayRef subtrees = NULL;
 389     if (san_context) {
 390         subtrees = san_context->subtrees;
 391     }
 392     if (subtrees) {
 393         CFIndex num_trees = CFArrayGetCount(subtrees);
 394         CFRange range = { 0, num_trees };
 395         match_t match = { false, false };
 396         rfc822NameString = CFStringToCString(rfc822Name);
 397         if (!rfc822NameString) { return; }
 398         const DERItem addr = { (unsigned char *)rfc822NameString,
 399                               CFStringGetLength(rfc822Name) };
 400         nc_match_context_t match_context = {GNT_RFC822Name, &addr, &match};
 401         CFArrayApplyFunction(subtrees, range, nc_decode_and_compare_subtree, &match_context);
 402         free(rfc822NameString);
 403
 404         update_match(san_context->permit, &match, san_context->match);
 405
 406     }
 407 }
 408
 409 static void nc_compare_subject_to_subtrees(SecCertificateRef certificate, CFArrayRef subtrees,
 410                                            bool permit, match_t *match) {
 411     CFDataRef subject = SecCertificateCopySubjectSequence(certificate);
 412     /* An empty subject name is considered not present */
 413     if (!subject || isEmptySubject(subject)) {
 414         CFReleaseNull(subject);
 415         return;
 416     }
 417
 418     /* Compare X.500 distinguished name constraints */
 419     CFIndex num_trees = CFArrayGetCount(subtrees);
 420     CFRange range = { 0, num_trees };
 421     match_t x500_match = { false, false };
 422     const DERItem subject_der = { (unsigned char *)CFDataGetBytePtr(subject), CFDataGetLength(subject) };
 423     nc_match_context_t context = {GNT_DirectoryName, &subject_der, &x500_match};
 424     CFArrayApplyFunction(subtrees, range, nc_decode_and_compare_subtree, &context);
 425     CFReleaseNull(subject);
 426     update_match(permit, &x500_match, match);
 427
 428     /* Compare RFC822 constraints to subject email address */
 429     match_t email_match = { false, permit };
 430     CFArrayRef rfc822Names = SecCertificateCopyRFC822NamesFromSubject(certificate);
 431     if (rfc822Names) {
 432         CFRange emailRange = { 0, CFArrayGetCount(rfc822Names) };
 433         nc_san_match_context_t emailContext = { subtrees, &email_match, permit };
 434         CFArrayApplyFunction(rfc822Names, emailRange, nc_compare_RFC822Name_to_subtrees, &emailContext);
 435     }
 436     CFReleaseNull(rfc822Names);
 437     update_match(permit, &email_match, match);
 438 }
 439
 440 static OSStatus nc_compare_subjectAltName_to_subtrees(void *context, SecCEGeneralNameType gnType, const DERItem *generalName) {
 441     nc_san_match_context_t *san_context = context;
 442     CFArrayRef subtrees = NULL;
 443     if (san_context) {
 444         subtrees = san_context->subtrees;
 445     }
 446     if (subtrees) {
 447         CFIndex num_trees = CFArrayGetCount(subtrees);
 448         CFRange range = { 0, num_trees };
 449         match_t match = { false, false };
 450         nc_match_context_t match_context = {gnType, generalName, &match};
 451         CFArrayApplyFunction(subtrees, range, nc_decode_and_compare_subtree, &match_context);
 452
 453         update_match(san_context->permit, &match, san_context->match);
 454
 455         return errSecSuccess;
 456     }
 457
 458     return errSecInvalidCertificate;
 459 }
 460
 461 OSStatus SecNameContraintsMatchSubtrees(SecCertificateRef certificate, CFArrayRef subtrees, bool *matched, bool permit) {
 462     CFDataRef subject = NULL;
 463     OSStatus status = errSecSuccess;
 464
 465     require_action_quiet(subject = SecCertificateCopySubjectSequence(certificate),
 466                          out,
 467                          status = errSecInvalidCertificate);
 468     const DERItem *subjectAltNames = SecCertificateGetSubjectAltName(certificate);
 469
 470     /* Reject certificates with neither Subject Name nor SubjectAltName */
 471     require_action_quiet(!isEmptySubject(subject) || subjectAltNames, out, status = errSecInvalidCertificate);
 472
 473     /* Verify that the subject name is within all of the subtrees */
 474     match_t subject_match = { false, permit };
 475     nc_compare_subject_to_subtrees(certificate, subtrees, permit, &subject_match);
 476
 477     /* permit tells us whether to start with true or false. If we are looking at permitted
 478      * subtrees, we are going to "and" the matching results because all present types must match
 479      * to permit. For excluded subtrees, we are going to "or" the matching results because
 480      * any matching present types causes exclusion. */
 481     match_t san_match = { false, permit };
 482     nc_san_match_context_t san_context = {subtrees, &san_match, permit};
 483
 484     /* And verify that each of the alternative names in the subjectAltName extension (critical or non-critical)
 485      * is within any of the subtrees for that name type. */
 486     if (subjectAltNames) {
 487         status = SecCertificateParseGeneralNames(subjectAltNames,
 488                                                  &san_context,
 489                                                  nc_compare_subjectAltName_to_subtrees);
 490         /* If failed to parse */
 491         require_action_quiet(status == errSecSuccess, out, *matched = false);
 492     }
 493
 494     /* If we are excluding based on the subtrees, lack of names of the
 495        same type is not a match. But if we are permitting, it is.
 496      */
 497     if (subject_match.present) {
 498         if (san_match.present &&
 499             ((subject_match.isMatch && !san_match.isMatch) ||
 500             (!subject_match.isMatch && san_match.isMatch))) {
 501             /* If both san and subject types are present, but don't agree on match
 502              * we should exclude on the basis of the match and not permit on the
 503              * basis of the failed match. */
 504             *matched = permit ? false : true;
 505         }
 506         else {
 507             /* If san type wasn't present or both had the same result, use the
 508              * result from matching against the subject. */
 509             *matched = subject_match.isMatch;
 510         }
 511     }
 512     else if (san_match.present) {
 513         *matched = san_match.isMatch;
 514     }
 515     else {
 516         /* Neither subject nor san had same type as subtrees, permit and don't
 517          * exclude the cert. */
 518         *matched = permit ? true : false;
 519     }
 520
 521 out:
 522     CFReleaseNull(subject);
 523     return status;
 524 }
 525
 526 typedef struct {
 527     CFMutableArrayRef existing_trees;
 528     CFMutableArrayRef trees_to_add;
 529 } nc_intersect_context_t;
 530
 531 static SecCEGeneralNameType nc_gn_type_convert (DERTag tag) {
 532     switch (tag) {
 533         case ASN1_CONTEXT_SPECIFIC | ASN1_CONSTRUCTED | 0:
 534             return GNT_OtherName;
 535         case ASN1_CONTEXT_SPECIFIC | 1:
 536             return GNT_RFC822Name;
 537         case ASN1_CONTEXT_SPECIFIC | 2:
 538             return GNT_DNSName;
 539         case ASN1_CONTEXT_SPECIFIC | ASN1_CONSTRUCTED | 3:
 540             return GNT_X400Address;
 541         case ASN1_CONTEXT_SPECIFIC | ASN1_CONSTRUCTED | 4:
 542             return GNT_DirectoryName;
 543         case ASN1_CONTEXT_SPECIFIC | ASN1_CONSTRUCTED | 5:
 544             return GNT_EdiPartyName;
 545         case ASN1_CONTEXT_SPECIFIC | ASN1_CONSTRUCTED | 6:
 546         case ASN1_CONTEXT_SPECIFIC | 6:
 547             return GNT_URI;
 548         case ASN1_CONTEXT_SPECIFIC | 7:
 549             return GNT_IPAddress;
 550         case ASN1_CONTEXT_SPECIFIC | 8:
 551             return GNT_RegisteredID;
 552         default:
 553             return GNT_OtherName;
 554     }
 555 }
 556
 557 /* The recommended processing algorithm states:
 558  *    If permittedSubtrees is present in the certificate, set the permitted_subtrees state variable to the intersection
 559  *    of its previous value and the value indicated in the extension field.
 560  * However, in practice, certs are issued with permittedSubtrees whose intersection would be the empty set. For now,
 561  * wherever a new permittedSubtree is a subset of an existing subtree, we'll replace the existing subtree; otherwise,
 562  * we just append the new subtree.
 563  */
 564 static void nc_intersect_tree_with_subtrees (const void *value, void *context) {
 565     CFDataRef new_subtree = value;
 566     nc_intersect_context_t *intersect_context = context;
 567     CFMutableArrayRef existing_subtrees = intersect_context->existing_trees;
 568     CFMutableArrayRef trees_to_append = intersect_context->trees_to_add;
 569
 570     if (!new_subtree || !existing_subtrees) return;
 571
 572     /* convert new subtree to DERItem */
 573     const DERItem general_name = { (unsigned char *)CFDataGetBytePtr(new_subtree), CFDataGetLength(new_subtree) };
 574     DERDecodedInfo general_name_content;
 575     if(DR_Success != DERDecodeItem(&general_name, &general_name_content)) return;
 576
 577     SecCEGeneralNameType gnType;
 578     DERItem *new_subtree_item = &general_name_content.content;
 579
 580     /* Attempt to intersect if one of the supported types: DirectoryName and DNSName.
 581      * Otherwise, just append the new tree. */
 582     gnType = nc_gn_type_convert(general_name_content.tag);
 583     if (!(gnType == GNT_DirectoryName || gnType == GNT_DNSName)) {
 584         CFArrayAppendValue(trees_to_append, new_subtree);
 585     }
 586
 587     CFIndex subtreeIX;
 588     CFIndex num_existing_subtrees = CFArrayGetCount(existing_subtrees);
 589     match_t match = { false, false };
 590     nc_match_context_t match_context = { gnType, new_subtree_item, &match};
 591     for (subtreeIX = 0; subtreeIX < num_existing_subtrees; subtreeIX++) {
 592         CFDataRef candidate_subtree = CFArrayGetValueAtIndex(existing_subtrees, subtreeIX);
 593         /* Convert candidate subtree to DERItem */
 594         const DERItem candidate = { (unsigned char *)CFDataGetBytePtr(candidate_subtree), CFDataGetLength(candidate_subtree) };
 595         DERDecodedInfo candidate_content;
 596         /* We could probably just delete any subtrees in the array that don't decode */
 597         if(DR_Success != DERDecodeItem(&candidate, &candidate_content)) continue;
 598
 599         /* first test whether new tree matches the existing tree */
 600         OSStatus status = SecCertificateParseGeneralNameContentProperty(candidate_content.tag,
 601                                                                         &candidate_content.content,
 602                                                                         &match_context,
 603                                                                         nc_compare_subtree);
 604         if((status == errSecSuccess) && match.present && match.isMatch) {
 605             break;
 606         }
 607
 608         /* then test whether existing tree matches the new tree*/
 609         match_t local_match = { false , false };
 610         nc_match_context_t local_match_context = { nc_gn_type_convert(candidate_content.tag),
 611                                                    &candidate_content.content,
 612                                                    &local_match };
 613         status = SecCertificateParseGeneralNameContentProperty(general_name_content.tag,
 614                                                                &general_name_content.content,
 615                                                                &local_match_context,
 616                                                                nc_compare_subtree);
 617         if((status == errSecSuccess) && local_match.present && local_match.isMatch) {
 618             break;
 619         }
 620     }
 621     if (subtreeIX == num_existing_subtrees) {
 622         /* No matches found. Append new subtree */
 623         CFArrayAppendValue(trees_to_append, new_subtree);
 624     }
 625     else if (match.present && match.isMatch) {
 626         /* new subtree \subseteq existing subtree, replace existing tree */
 627         CFArraySetValueAtIndex(existing_subtrees, subtreeIX, new_subtree);
 628     }
 629     /* existing subtree \subset new subtree, drop the new tree so as not to broaden constraints*/
 630     return;
 631
 632 }
 633
 634 void SecNameConstraintsIntersectSubtrees(CFMutableArrayRef subtrees_state, CFArrayRef subtrees_new) {
 635     assert(subtrees_state);
 636     assert(subtrees_new);
 637
 638     CFIndex num_new_trees = CFArrayGetCount(subtrees_new);
 639     CFRange range = { 0, num_new_trees };
 640
 641     /* if existing subtrees state contains no subtrees, append new subtrees whole */
 642     if (!CFArrayGetCount(subtrees_state)) {
 643         CFArrayAppendArray(subtrees_state, subtrees_new, range);
 644         return;
 645     }
 646
 647     CFMutableArrayRef trees_to_append = NULL;
 648     trees_to_append = CFArrayCreateMutable(NULL, 0, &kCFTypeArrayCallBacks);
 649     nc_intersect_context_t context = { subtrees_state , trees_to_append };
 650     CFArrayApplyFunction(subtrees_new, range, nc_intersect_tree_with_subtrees, &context);
 651
 652     /* don't append to the state until we've processed all the new trees */
 653     num_new_trees = CFArrayGetCount(trees_to_append);
 654     if (trees_to_append && num_new_trees) {
 655         range.length = num_new_trees;
 656         CFArrayAppendArray(subtrees_state, trees_to_append, range);
 657     }
 658
 659     CFReleaseNull(trees_to_append);
 660 }