1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
declare(strict_types = 1); |
4
|
|
|
|
5
|
|
|
namespace Sop\X509\CertificationPath\Policy; |
6
|
|
|
|
7
|
|
|
use Sop\X509\Certificate\Certificate; |
8
|
|
|
use Sop\X509\Certificate\Extension\CertificatePolicy\PolicyInformation; |
9
|
|
|
use Sop\X509\CertificationPath\PathValidation\ValidatorState; |
10
|
|
|
|
11
|
|
|
class PolicyTree |
12
|
|
|
{ |
13
|
|
|
/** |
14
|
|
|
* Root node at depth zero. |
15
|
|
|
* |
16
|
|
|
* @var null|PolicyNode |
17
|
|
|
*/ |
18
|
|
|
protected $_root; |
19
|
|
|
|
20
|
|
|
/** |
21
|
|
|
* Constructor. |
22
|
|
|
* |
23
|
|
|
* @param PolicyNode $root Initial root node |
24
|
|
|
*/ |
25
|
50 |
|
public function __construct(PolicyNode $root) |
26
|
|
|
{ |
27
|
50 |
|
$this->_root = $root; |
28
|
50 |
|
} |
29
|
|
|
|
30
|
|
|
/** |
31
|
|
|
* Process policy information from the certificate. |
32
|
|
|
* |
33
|
|
|
* Certificate policies extension must be present. |
34
|
|
|
* |
35
|
|
|
* @param ValidatorState $state |
36
|
|
|
* @param Certificate $cert |
37
|
|
|
* |
38
|
|
|
* @return ValidatorState |
39
|
|
|
*/ |
40
|
14 |
|
public function processPolicies(ValidatorState $state, |
41
|
|
|
Certificate $cert): ValidatorState |
42
|
|
|
{ |
43
|
14 |
|
$policies = $cert->tbsCertificate()->extensions()->certificatePolicies(); |
44
|
14 |
|
$tree = clone $this; |
45
|
|
|
// (d.1) for each policy P not equal to anyPolicy |
46
|
14 |
|
foreach ($policies as $policy) { |
47
|
14 |
|
if ($policy->isAnyPolicy()) { |
48
|
6 |
|
$tree->_processAnyPolicy($policy, $cert, $state); |
49
|
|
|
} else { |
50
|
14 |
|
$tree->_processPolicy($policy, $state); |
51
|
|
|
} |
52
|
|
|
} |
53
|
|
|
// if whole tree is pruned |
54
|
14 |
|
if (!$tree->_pruneTree($state->index() - 1)) { |
55
|
1 |
|
return $state->withoutValidPolicyTree(); |
56
|
|
|
} |
57
|
14 |
|
return $state->withValidPolicyTree($tree); |
58
|
|
|
} |
59
|
|
|
|
60
|
|
|
/** |
61
|
|
|
* Process policy mappings from the certificate. |
62
|
|
|
* |
63
|
|
|
* @param ValidatorState $state |
64
|
|
|
* @param Certificate $cert |
65
|
|
|
* |
66
|
|
|
* @return ValidatorState |
67
|
|
|
*/ |
68
|
3 |
|
public function processMappings(ValidatorState $state, |
69
|
|
|
Certificate $cert): ValidatorState |
70
|
|
|
{ |
71
|
3 |
|
$tree = clone $this; |
72
|
3 |
|
if ($state->policyMapping() > 0) { |
73
|
2 |
|
$tree->_applyMappings($cert, $state); |
74
|
1 |
|
} elseif (0 === $state->policyMapping()) { |
75
|
1 |
|
$tree->_deleteMappings($cert, $state); |
76
|
|
|
} |
77
|
|
|
// if whole tree is pruned |
78
|
3 |
|
if (!$tree->_root) { |
79
|
1 |
|
return $state->withoutValidPolicyTree(); |
80
|
|
|
} |
81
|
2 |
|
return $state->withValidPolicyTree($tree); |
82
|
|
|
} |
83
|
|
|
|
84
|
|
|
/** |
85
|
|
|
* Calculate policy intersection as specified in Wrap-Up Procedure 6.1.5.g. |
86
|
|
|
* |
87
|
|
|
* @param ValidatorState $state |
88
|
|
|
* @param array $policies |
89
|
|
|
* |
90
|
|
|
* @return ValidatorState |
91
|
|
|
*/ |
92
|
6 |
|
public function calculateIntersection(ValidatorState $state, |
93
|
|
|
array $policies): ValidatorState |
94
|
|
|
{ |
95
|
6 |
|
$tree = clone $this; |
96
|
6 |
|
$valid_policy_node_set = $tree->_validPolicyNodeSet(); |
97
|
|
|
// 2. If the valid_policy of any node in the valid_policy_node_set |
98
|
|
|
// is not in the user-initial-policy-set and is not anyPolicy, |
99
|
|
|
// delete this node and all its children. |
100
|
6 |
|
$valid_policy_node_set = array_filter($valid_policy_node_set, |
101
|
|
|
function (PolicyNode $node) use ($policies) { |
102
|
6 |
|
if ($node->isAnyPolicy()) { |
103
|
4 |
|
return true; |
104
|
|
|
} |
105
|
5 |
|
if (in_array($node->validPolicy(), $policies)) { |
106
|
3 |
|
return true; |
107
|
|
|
} |
108
|
3 |
|
$node->remove(); |
109
|
3 |
|
return false; |
110
|
6 |
|
}); |
111
|
|
|
// array of valid policy OIDs |
112
|
6 |
|
$valid_policy_set = array_map( |
113
|
|
|
function (PolicyNode $node) { |
114
|
5 |
|
return $node->validPolicy(); |
115
|
6 |
|
}, $valid_policy_node_set); |
116
|
|
|
// 3. If the valid_policy_tree includes a node of depth n with |
117
|
|
|
// the valid_policy anyPolicy and the user-initial-policy-set |
118
|
|
|
// is not any-policy |
119
|
6 |
|
foreach ($tree->_nodesAtDepth($state->index()) as $node) { |
120
|
4 |
|
if ($node->hasParent() && $node->isAnyPolicy()) { |
121
|
|
|
// a. Set P-Q to the qualifier_set in the node of depth n |
122
|
|
|
// with valid_policy anyPolicy. |
123
|
1 |
|
$pq = $node->qualifiers(); |
124
|
|
|
// b. For each P-OID in the user-initial-policy-set that is not |
125
|
|
|
// the valid_policy of a node in the valid_policy_node_set, |
126
|
|
|
// create a child node whose parent is the node of depth n-1 |
127
|
|
|
// with the valid_policy anyPolicy. |
128
|
1 |
|
$poids = array_diff($policies, $valid_policy_set); |
129
|
1 |
|
foreach ($tree->_nodesAtDepth($state->index() - 1) as $parent) { |
130
|
1 |
|
if ($parent->isAnyPolicy()) { |
131
|
|
|
// Set the values in the child node as follows: |
132
|
|
|
// set the valid_policy to P-OID, set the qualifier_set |
133
|
|
|
// to P-Q, and set the expected_policy_set to {P-OID}. |
134
|
1 |
|
foreach ($poids as $poid) { |
135
|
1 |
|
$parent->addChild(new PolicyNode($poid, $pq, [$poid])); |
136
|
|
|
} |
137
|
1 |
|
break; |
138
|
|
|
} |
139
|
|
|
} |
140
|
|
|
// c. Delete the node of depth n with the |
141
|
|
|
// valid_policy anyPolicy. |
142
|
4 |
|
$node->remove(); |
143
|
|
|
} |
144
|
|
|
} |
145
|
|
|
// 4. If there is a node in the valid_policy_tree of depth n-1 or less |
146
|
|
|
// without any child nodes, delete that node. Repeat this step until |
147
|
|
|
// there are no nodes of depth n-1 or less without children. |
148
|
6 |
|
if (!$tree->_pruneTree($state->index() - 1)) { |
149
|
2 |
|
return $state->withoutValidPolicyTree(); |
150
|
|
|
} |
151
|
4 |
|
return $state->withValidPolicyTree($tree); |
152
|
|
|
} |
153
|
|
|
|
154
|
|
|
/** |
155
|
|
|
* Get policies at given policy tree depth. |
156
|
|
|
* |
157
|
|
|
* @param int $i Depth in range 1..n |
158
|
|
|
* |
159
|
|
|
* @return PolicyInformation[] |
160
|
|
|
*/ |
161
|
6 |
|
public function policiesAtDepth(int $i): array |
162
|
|
|
{ |
163
|
6 |
|
$policies = []; |
164
|
6 |
|
foreach ($this->_nodesAtDepth($i) as $node) { |
165
|
5 |
|
$policies[] = new PolicyInformation( |
166
|
5 |
|
$node->validPolicy(), ...$node->qualifiers()); |
167
|
|
|
} |
168
|
6 |
|
return $policies; |
169
|
|
|
} |
170
|
|
|
|
171
|
|
|
/** |
172
|
|
|
* Process single policy information. |
173
|
|
|
* |
174
|
|
|
* @param PolicyInformation $policy |
175
|
|
|
* @param ValidatorState $state |
176
|
|
|
*/ |
177
|
12 |
|
protected function _processPolicy(PolicyInformation $policy, |
178
|
|
|
ValidatorState $state): void |
179
|
|
|
{ |
180
|
12 |
|
$p_oid = $policy->oid(); |
181
|
12 |
|
$i = $state->index(); |
182
|
12 |
|
$match_count = 0; |
183
|
|
|
// (d.1.i) for each node of depth i-1 in the valid_policy_tree... |
184
|
12 |
|
foreach ($this->_nodesAtDepth($i - 1) as $node) { |
185
|
|
|
// ...where P-OID is in the expected_policy_set |
186
|
12 |
|
if ($node->hasExpectedPolicy($p_oid)) { |
187
|
6 |
|
$node->addChild(new PolicyNode( |
188
|
6 |
|
$p_oid, $policy->qualifiers(), [$p_oid])); |
189
|
12 |
|
++$match_count; |
190
|
|
|
} |
191
|
|
|
} |
192
|
|
|
// (d.1.ii) if there was no match in step (i)... |
193
|
12 |
|
if (!$match_count) { |
194
|
|
|
// ...and the valid_policy_tree includes a node of depth i-1 with |
195
|
|
|
// the valid_policy anyPolicy |
196
|
11 |
|
foreach ($this->_nodesAtDepth($i - 1) as $node) { |
197
|
11 |
|
if ($node->isAnyPolicy()) { |
198
|
11 |
|
$node->addChild(new PolicyNode( |
199
|
11 |
|
$p_oid, $policy->qualifiers(), [$p_oid])); |
200
|
|
|
} |
201
|
|
|
} |
202
|
|
|
} |
203
|
12 |
|
} |
204
|
|
|
|
205
|
|
|
/** |
206
|
|
|
* Process anyPolicy policy information. |
207
|
|
|
* |
208
|
|
|
* @param PolicyInformation $policy |
209
|
|
|
* @param Certificate $cert |
210
|
|
|
* @param ValidatorState $state |
211
|
|
|
*/ |
212
|
6 |
|
protected function _processAnyPolicy(PolicyInformation $policy, |
213
|
|
|
Certificate $cert, ValidatorState $state): void |
214
|
|
|
{ |
215
|
6 |
|
$i = $state->index(); |
216
|
|
|
// if (a) inhibit_anyPolicy is greater than 0 or |
217
|
|
|
// (b) i<n and the certificate is self-issued |
218
|
6 |
|
if (!($state->inhibitAnyPolicy() > 0 || |
219
|
6 |
|
($i < $state->pathLength() && $cert->isSelfIssued()))) { |
220
|
1 |
|
return; |
221
|
|
|
} |
222
|
|
|
// for each node in the valid_policy_tree of depth i-1 |
223
|
6 |
|
foreach ($this->_nodesAtDepth($i - 1) as $node) { |
224
|
|
|
// for each value in the expected_policy_set |
225
|
6 |
|
foreach ($node->expectedPolicies() as $p_oid) { |
226
|
|
|
// that does not appear in a child node |
227
|
6 |
|
if (!$node->hasChildWithValidPolicy($p_oid)) { |
228
|
6 |
|
$node->addChild(new PolicyNode( |
229
|
6 |
|
$p_oid, $policy->qualifiers(), [$p_oid])); |
230
|
|
|
} |
231
|
|
|
} |
232
|
|
|
} |
233
|
6 |
|
} |
234
|
|
|
|
235
|
|
|
/** |
236
|
|
|
* Apply policy mappings to the policy tree. |
237
|
|
|
* |
238
|
|
|
* @param Certificate $cert |
239
|
|
|
* @param ValidatorState $state |
240
|
|
|
*/ |
241
|
2 |
|
protected function _applyMappings(Certificate $cert, ValidatorState $state): void |
242
|
|
|
{ |
243
|
2 |
|
$policy_mappings = $cert->tbsCertificate()->extensions()->policyMappings(); |
244
|
|
|
// (6.1.4. b.1.) for each node in the valid_policy_tree of depth i... |
245
|
2 |
|
foreach ($policy_mappings->flattenedMappings() as $idp => $sdps) { |
246
|
2 |
|
$match_count = 0; |
247
|
2 |
|
foreach ($this->_nodesAtDepth($state->index()) as $node) { |
248
|
|
|
// ...where ID-P is the valid_policy |
249
|
2 |
|
if ($node->validPolicy() === $idp) { |
250
|
|
|
// set expected_policy_set to the set of subjectDomainPolicy |
251
|
|
|
// values that are specified as equivalent to ID-P by |
252
|
|
|
// the policy mappings extension |
253
|
1 |
|
$node->setExpectedPolicies(...$sdps); |
254
|
2 |
|
++$match_count; |
255
|
|
|
} |
256
|
|
|
} |
257
|
|
|
// if no node of depth i in the valid_policy_tree has |
258
|
|
|
// a valid_policy of ID-P... |
259
|
2 |
|
if (!$match_count) { |
260
|
2 |
|
$this->_applyAnyPolicyMapping($cert, $state, $idp, $sdps); |
261
|
|
|
} |
262
|
|
|
} |
263
|
2 |
|
} |
264
|
|
|
|
265
|
|
|
/** |
266
|
|
|
* Apply anyPolicy mapping to the policy tree as specified in 6.1.4 (b)(1). |
267
|
|
|
* |
268
|
|
|
* @param Certificate $cert |
269
|
|
|
* @param ValidatorState $state |
270
|
|
|
* @param string $idp OID of the issuer domain policy |
271
|
|
|
* @param array $sdps Array of subject domain policy OIDs |
272
|
|
|
*/ |
273
|
2 |
|
protected function _applyAnyPolicyMapping(Certificate $cert, |
274
|
|
|
ValidatorState $state, string $idp, array $sdps): void |
275
|
|
|
{ |
276
|
|
|
// (6.1.4. b.1.) ...but there is a node of depth i with |
277
|
|
|
// a valid_policy of anyPolicy |
278
|
2 |
|
foreach ($this->_nodesAtDepth($state->index()) as $node) { |
279
|
2 |
|
if ($node->isAnyPolicy()) { |
280
|
|
|
// then generate a child node of the node of depth i-1 |
281
|
|
|
// that has a valid_policy of anyPolicy as follows... |
282
|
2 |
|
foreach ($this->_nodesAtDepth($state->index() - 1) as $subnode) { |
283
|
2 |
|
if ($subnode->isAnyPolicy()) { |
284
|
|
|
// try to fetch qualifiers of anyPolicy certificate policy |
285
|
|
|
try { |
286
|
2 |
|
$qualifiers = $cert->tbsCertificate() |
287
|
2 |
|
->extensions()->certificatePolicies() |
288
|
2 |
|
->anyPolicy()->qualifiers(); |
289
|
1 |
|
} catch (\LogicException $e) { |
290
|
|
|
// if there's no policies or no qualifiers |
291
|
1 |
|
$qualifiers = []; |
292
|
|
|
} |
293
|
2 |
|
$subnode->addChild(new PolicyNode($idp, $qualifiers, $sdps)); |
294
|
|
|
// bail after first anyPolicy has been processed |
295
|
2 |
|
break; |
296
|
|
|
} |
297
|
|
|
} |
298
|
|
|
// bail after first anyPolicy has been processed |
299
|
2 |
|
break; |
300
|
|
|
} |
301
|
|
|
} |
302
|
2 |
|
} |
303
|
|
|
|
304
|
|
|
/** |
305
|
|
|
* Delete nodes as specified in 6.1.4 (b)(2). |
306
|
|
|
* |
307
|
|
|
* @param Certificate $cert |
308
|
|
|
* @param ValidatorState $state |
309
|
|
|
*/ |
310
|
1 |
|
protected function _deleteMappings(Certificate $cert, |
311
|
|
|
ValidatorState $state): void |
312
|
|
|
{ |
313
|
1 |
|
$idps = $cert->tbsCertificate()->extensions() |
314
|
1 |
|
->policyMappings()->issuerDomainPolicies(); |
315
|
|
|
// delete each node of depth i in the valid_policy_tree |
316
|
|
|
// where ID-P is the valid_policy |
317
|
1 |
|
foreach ($this->_nodesAtDepth($state->index()) as $node) { |
318
|
1 |
|
if (in_array($node->validPolicy(), $idps)) { |
319
|
1 |
|
$node->remove(); |
320
|
|
|
} |
321
|
|
|
} |
322
|
1 |
|
$this->_pruneTree($state->index() - 1); |
323
|
1 |
|
} |
324
|
|
|
|
325
|
|
|
/** |
326
|
|
|
* Prune tree starting from given depth. |
327
|
|
|
* |
328
|
|
|
* @param int $depth |
329
|
|
|
* |
330
|
|
|
* @return int The number of nodes left in a tree |
331
|
|
|
*/ |
332
|
15 |
|
protected function _pruneTree(int $depth): int |
333
|
|
|
{ |
334
|
15 |
|
if (!$this->_root) { |
335
|
1 |
|
return 0; |
336
|
|
|
} |
337
|
14 |
|
for ($i = $depth; $i > 0; --$i) { |
338
|
11 |
|
foreach ($this->_nodesAtDepth($i) as $node) { |
339
|
11 |
|
if (!count($node)) { |
340
|
11 |
|
$node->remove(); |
341
|
|
|
} |
342
|
|
|
} |
343
|
|
|
} |
344
|
|
|
// if root has no children left |
345
|
14 |
|
if (!count($this->_root)) { |
346
|
4 |
|
$this->_root = null; |
347
|
4 |
|
return 0; |
348
|
|
|
} |
349
|
14 |
|
return $this->_root->nodeCount(); |
350
|
|
|
} |
351
|
|
|
|
352
|
|
|
/** |
353
|
|
|
* Get all nodes at given depth. |
354
|
|
|
* |
355
|
|
|
* @param int $i |
356
|
|
|
* |
357
|
|
|
* @return PolicyNode[] |
358
|
|
|
*/ |
359
|
16 |
|
protected function _nodesAtDepth(int $i): array |
360
|
|
|
{ |
361
|
16 |
|
if (!$this->_root) { |
362
|
1 |
|
return []; |
363
|
|
|
} |
364
|
15 |
|
$depth = 0; |
365
|
15 |
|
$nodes = [$this->_root]; |
366
|
15 |
|
while ($depth < $i) { |
367
|
12 |
|
$nodes = self::_gatherChildren(...$nodes); |
368
|
12 |
|
if (!count($nodes)) { |
369
|
2 |
|
break; |
370
|
|
|
} |
371
|
12 |
|
++$depth; |
372
|
|
|
} |
373
|
15 |
|
return $nodes; |
374
|
|
|
} |
375
|
|
|
|
376
|
|
|
/** |
377
|
|
|
* Get the valid policy node set as specified in spec 6.1.5.(g)(iii)1. |
378
|
|
|
* |
379
|
|
|
* @return PolicyNode[] |
380
|
|
|
*/ |
381
|
7 |
|
protected function _validPolicyNodeSet(): array |
382
|
|
|
{ |
383
|
|
|
// 1. Determine the set of policy nodes whose parent nodes have |
384
|
|
|
// a valid_policy of anyPolicy. This is the valid_policy_node_set. |
385
|
7 |
|
$set = []; |
386
|
7 |
|
if (!$this->_root) { |
387
|
1 |
|
return $set; |
388
|
|
|
} |
389
|
|
|
// for each node in a tree |
390
|
6 |
|
$this->_root->walkNodes( |
391
|
|
|
function (PolicyNode $node) use (&$set) { |
392
|
6 |
|
$parents = $node->parents(); |
393
|
|
|
// node has parents |
394
|
6 |
|
if (count($parents)) { |
395
|
|
|
// check that each ancestor is an anyPolicy node |
396
|
6 |
|
foreach ($parents as $ancestor) { |
397
|
6 |
|
if (!$ancestor->isAnyPolicy()) { |
398
|
6 |
|
return; |
399
|
|
|
} |
400
|
|
|
} |
401
|
6 |
|
$set[] = $node; |
402
|
|
|
} |
403
|
6 |
|
}); |
404
|
6 |
|
return $set; |
405
|
|
|
} |
406
|
|
|
|
407
|
|
|
/** |
408
|
|
|
* Gather all children of given nodes to a flattened array. |
409
|
|
|
* |
410
|
|
|
* @param PolicyNode ...$nodes |
411
|
|
|
* |
412
|
|
|
* @return PolicyNode[] |
413
|
|
|
*/ |
414
|
12 |
|
private static function _gatherChildren(PolicyNode ...$nodes): array |
415
|
|
|
{ |
416
|
12 |
|
$children = []; |
417
|
12 |
|
foreach ($nodes as $node) { |
418
|
12 |
|
$children = array_merge($children, $node->children()); |
419
|
|
|
} |
420
|
12 |
|
return $children; |
421
|
|
|
} |
422
|
|
|
} |
423
|
|
|
|