1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include <keymaster/authorization_set.h> 18 19 #include <assert.h> 20 #include <stddef.h> 21 #include <stdlib.h> 22 #include <string.h> 23 24 #include <keymaster/new.h> 25 26 #include <keymaster/android_keymaster_utils.h> 27 #include <keymaster/logger.h> 28 29 namespace keymaster { 30 31 static inline bool is_blob_tag(keymaster_tag_t tag) { 32 return (keymaster_tag_get_type(tag) == KM_BYTES || keymaster_tag_get_type(tag) == KM_BIGNUM); 33 } 34 35 const size_t STARTING_ELEMS_CAPACITY = 8; 36 37 AuthorizationSet::AuthorizationSet(AuthorizationSetBuilder& builder) { 38 elems_ = builder.set.elems_; 39 builder.set.elems_ = nullptr; 40 41 elems_size_ = builder.set.elems_size_; 42 builder.set.elems_size_ = 0; 43 44 elems_capacity_ = builder.set.elems_capacity_; 45 builder.set.elems_capacity_ = 0; 46 47 indirect_data_ = builder.set.indirect_data_; 48 builder.set.indirect_data_ = nullptr; 49 50 indirect_data_capacity_ = builder.set.indirect_data_capacity_; 51 builder.set.indirect_data_capacity_ = 0; 52 53 indirect_data_size_ = builder.set.indirect_data_size_; 54 builder.set.indirect_data_size_ = 0; 55 56 error_ = builder.set.error_; 57 builder.set.error_ = OK; 58 } 59 60 AuthorizationSet::~AuthorizationSet() { 61 FreeData(); 62 } 63 64 bool AuthorizationSet::reserve_elems(size_t count) { 65 if (is_valid() != OK) 66 return false; 67 68 if (count > elems_capacity_) { 69 keymaster_key_param_t* new_elems = new (std::nothrow) keymaster_key_param_t[count]; 70 if (new_elems == nullptr) { 71 set_invalid(ALLOCATION_FAILURE); 72 return false; 73 } 74 memcpy(new_elems, elems_, sizeof(*elems_) * elems_size_); 75 delete[] elems_; 76 elems_ = new_elems; 77 elems_capacity_ = count; 78 } 79 return true; 80 } 81 82 bool AuthorizationSet::reserve_indirect(size_t length) { 83 if (is_valid() != OK) 84 return false; 85 86 if (length > indirect_data_capacity_) { 87 uint8_t* new_data = new (std::nothrow) uint8_t[length]; 88 if (new_data == nullptr) { 89 set_invalid(ALLOCATION_FAILURE); 90 return false; 91 } 92 memcpy(new_data, indirect_data_, indirect_data_size_); 93 94 // Fix up the data pointers to point into the new region. 95 for (size_t i = 0; i < elems_size_; ++i) { 96 if (is_blob_tag(elems_[i].tag)) 97 elems_[i].blob.data = new_data + (elems_[i].blob.data - indirect_data_); 98 } 99 delete[] indirect_data_; 100 indirect_data_ = new_data; 101 indirect_data_capacity_ = length; 102 } 103 return true; 104 } 105 106 void AuthorizationSet::MoveFrom(AuthorizationSet& set) { 107 elems_ = set.elems_; 108 elems_size_ = set.elems_size_; 109 elems_capacity_ = set.elems_capacity_; 110 indirect_data_ = set.indirect_data_; 111 indirect_data_size_ = set.indirect_data_size_; 112 indirect_data_capacity_ = set.indirect_data_capacity_; 113 error_ = set.error_; 114 set.elems_ = nullptr; 115 set.elems_size_ = 0; 116 set.elems_capacity_ = 0; 117 set.indirect_data_ = nullptr; 118 set.indirect_data_size_ = 0; 119 set.indirect_data_capacity_ = 0; 120 set.error_ = OK; 121 } 122 123 bool AuthorizationSet::Reinitialize(const keymaster_key_param_t* elems, const size_t count) { 124 FreeData(); 125 126 if (elems == nullptr || count == 0) { 127 error_ = OK; 128 return true; 129 } 130 131 if (!reserve_elems(count)) 132 return false; 133 134 if (!reserve_indirect(ComputeIndirectDataSize(elems, count))) 135 return false; 136 137 memcpy(elems_, elems, sizeof(keymaster_key_param_t) * count); 138 elems_size_ = count; 139 CopyIndirectData(); 140 error_ = OK; 141 return true; 142 } 143 144 void AuthorizationSet::set_invalid(Error error) { 145 FreeData(); 146 error_ = error; 147 } 148 149 void AuthorizationSet::Sort() { 150 qsort(elems_, elems_size_, sizeof(*elems_), 151 reinterpret_cast<int (*)(const void*, const void*)>(keymaster_param_compare)); 152 } 153 154 void AuthorizationSet::Deduplicate() { 155 Sort(); 156 157 size_t invalid_count = 0; 158 for (size_t i = 1; i < size(); ++i) { 159 if (elems_[i - 1].tag == KM_TAG_INVALID) 160 ++invalid_count; 161 else if (keymaster_param_compare(elems_ + i - 1, elems_ + i) == 0) { 162 // Mark dups as invalid. Note that this "leaks" the data referenced by KM_BYTES and 163 // KM_BIGNUM entries, but those are just pointers into indirect_data_, so it will all 164 // get cleaned up. 165 elems_[i - 1].tag = KM_TAG_INVALID; 166 ++invalid_count; 167 } 168 } 169 if (size() > 0 && elems_[size() - 1].tag == KM_TAG_INVALID) 170 ++invalid_count; 171 172 if (invalid_count == 0) 173 return; 174 175 Sort(); 176 177 // Since KM_TAG_INVALID == 0, all of the invalid entries are first. 178 elems_size_ -= invalid_count; 179 memmove(elems_, elems_ + invalid_count, size() * sizeof(*elems_)); 180 } 181 182 void AuthorizationSet::Union(const keymaster_key_param_set_t& set) { 183 if (set.length == 0) 184 return; 185 186 push_back(set); 187 Deduplicate(); 188 } 189 190 void AuthorizationSet::Difference(const keymaster_key_param_set_t& set) { 191 if (set.length == 0) 192 return; 193 194 Deduplicate(); 195 196 for (size_t i = 0; i < set.length; i++) { 197 int index = -1; 198 do { 199 index = find(set.params[i].tag, index); 200 if (index != -1 && keymaster_param_compare(&elems_[index], &set.params[i]) == 0) { 201 erase(index); 202 break; 203 } 204 } while (index != -1); 205 } 206 } 207 208 void AuthorizationSet::CopyToParamSet(keymaster_key_param_set_t* set) const { 209 assert(set); 210 211 set->length = size(); 212 set->params = 213 reinterpret_cast<keymaster_key_param_t*>(malloc(sizeof(keymaster_key_param_t) * size())); 214 215 for (size_t i = 0; i < size(); ++i) { 216 const keymaster_key_param_t src = (*this)[i]; 217 keymaster_key_param_t& dst(set->params[i]); 218 219 dst = src; 220 keymaster_tag_type_t type = keymaster_tag_get_type(src.tag); 221 if (type == KM_BIGNUM || type == KM_BYTES) { 222 void* tmp = malloc(src.blob.data_length); 223 memcpy(tmp, src.blob.data, src.blob.data_length); 224 dst.blob.data = reinterpret_cast<uint8_t*>(tmp); 225 } 226 } 227 } 228 229 int AuthorizationSet::find(keymaster_tag_t tag, int begin) const { 230 if (is_valid() != OK) 231 return -1; 232 233 int i = ++begin; 234 while (i < (int)elems_size_ && elems_[i].tag != tag) 235 ++i; 236 if (i == (int)elems_size_) 237 return -1; 238 else 239 return i; 240 } 241 242 bool AuthorizationSet::erase(int index) { 243 if (index < 0 || index >= static_cast<int>(size())) 244 return false; 245 246 --elems_size_; 247 for (size_t i = index; i < elems_size_; ++i) 248 elems_[i] = elems_[i + 1]; 249 return true; 250 } 251 252 keymaster_key_param_t empty_param = {KM_TAG_INVALID, {}}; 253 keymaster_key_param_t& AuthorizationSet::operator[](int at) { 254 if (is_valid() == OK && at < (int)elems_size_) { 255 return elems_[at]; 256 } 257 empty_param = {KM_TAG_INVALID, {}}; 258 return empty_param; 259 } 260 261 const keymaster_key_param_t& AuthorizationSet::operator[](int at) const { 262 if (is_valid() == OK && at < (int)elems_size_) { 263 return elems_[at]; 264 } 265 empty_param = {KM_TAG_INVALID, {}}; 266 return empty_param; 267 } 268 269 bool AuthorizationSet::push_back(const keymaster_key_param_set_t& set) { 270 if (is_valid() != OK) 271 return false; 272 273 if (!reserve_elems(elems_size_ + set.length)) 274 return false; 275 276 if (!reserve_indirect(indirect_data_size_ + ComputeIndirectDataSize(set.params, set.length))) 277 return false; 278 279 for (size_t i = 0; i < set.length; ++i) 280 if (!push_back(set.params[i])) 281 return false; 282 283 return true; 284 } 285 286 bool AuthorizationSet::push_back(keymaster_key_param_t elem) { 287 if (is_valid() != OK) 288 return false; 289 290 if (elems_size_ >= elems_capacity_) 291 if (!reserve_elems(elems_capacity_ ? elems_capacity_ * 2 : STARTING_ELEMS_CAPACITY)) 292 return false; 293 294 if (is_blob_tag(elem.tag)) { 295 if (indirect_data_capacity_ - indirect_data_size_ < elem.blob.data_length) 296 if (!reserve_indirect(2 * (indirect_data_capacity_ + elem.blob.data_length))) 297 return false; 298 299 memcpy(indirect_data_ + indirect_data_size_, elem.blob.data, elem.blob.data_length); 300 elem.blob.data = indirect_data_ + indirect_data_size_; 301 indirect_data_size_ += elem.blob.data_length; 302 } 303 304 elems_[elems_size_++] = elem; 305 return true; 306 } 307 308 static size_t serialized_size(const keymaster_key_param_t& param) { 309 switch (keymaster_tag_get_type(param.tag)) { 310 case KM_INVALID: 311 return sizeof(uint32_t); 312 case KM_ENUM: 313 case KM_ENUM_REP: 314 case KM_UINT: 315 case KM_UINT_REP: 316 return sizeof(uint32_t) * 2; 317 case KM_ULONG: 318 case KM_ULONG_REP: 319 case KM_DATE: 320 return sizeof(uint32_t) + sizeof(uint64_t); 321 case KM_BOOL: 322 return sizeof(uint32_t) + 1; 323 case KM_BIGNUM: 324 case KM_BYTES: 325 return sizeof(uint32_t) * 3; 326 } 327 328 return sizeof(uint32_t); 329 } 330 331 static uint8_t* serialize(const keymaster_key_param_t& param, uint8_t* buf, const uint8_t* end, 332 const uint8_t* indirect_base) { 333 buf = append_uint32_to_buf(buf, end, param.tag); 334 switch (keymaster_tag_get_type(param.tag)) { 335 case KM_INVALID: 336 break; 337 case KM_ENUM: 338 case KM_ENUM_REP: 339 buf = append_uint32_to_buf(buf, end, param.enumerated); 340 break; 341 case KM_UINT: 342 case KM_UINT_REP: 343 buf = append_uint32_to_buf(buf, end, param.integer); 344 break; 345 case KM_ULONG: 346 case KM_ULONG_REP: 347 buf = append_uint64_to_buf(buf, end, param.long_integer); 348 break; 349 case KM_DATE: 350 buf = append_uint64_to_buf(buf, end, param.date_time); 351 break; 352 case KM_BOOL: 353 if (buf < end) 354 *buf = static_cast<uint8_t>(param.boolean); 355 buf++; 356 break; 357 case KM_BIGNUM: 358 case KM_BYTES: 359 buf = append_uint32_to_buf(buf, end, param.blob.data_length); 360 buf = append_uint32_to_buf(buf, end, param.blob.data - indirect_base); 361 break; 362 } 363 return buf; 364 } 365 366 static bool deserialize(keymaster_key_param_t* param, const uint8_t** buf_ptr, const uint8_t* end, 367 const uint8_t* indirect_base, const uint8_t* indirect_end) { 368 if (!copy_uint32_from_buf(buf_ptr, end, ¶m->tag)) 369 return false; 370 371 switch (keymaster_tag_get_type(param->tag)) { 372 case KM_INVALID: 373 return false; 374 case KM_ENUM: 375 case KM_ENUM_REP: 376 return copy_uint32_from_buf(buf_ptr, end, ¶m->enumerated); 377 case KM_UINT: 378 case KM_UINT_REP: 379 return copy_uint32_from_buf(buf_ptr, end, ¶m->integer); 380 case KM_ULONG: 381 case KM_ULONG_REP: 382 return copy_uint64_from_buf(buf_ptr, end, ¶m->long_integer); 383 case KM_DATE: 384 return copy_uint64_from_buf(buf_ptr, end, ¶m->date_time); 385 break; 386 case KM_BOOL: 387 if (*buf_ptr < end) { 388 uint8_t temp = **buf_ptr; 389 // Bools are converted to 0 or 1 when serialized so only accept 390 // one of these values when deserializing. 391 if (temp <= 1) { 392 param->boolean = static_cast<bool>(temp); 393 (*buf_ptr)++; 394 return true; 395 } 396 } 397 return false; 398 399 case KM_BIGNUM: 400 case KM_BYTES: { 401 uint32_t offset; 402 if (!copy_uint32_from_buf(buf_ptr, end, ¶m->blob.data_length) || 403 !copy_uint32_from_buf(buf_ptr, end, &offset)) 404 return false; 405 if (param->blob.data_length + offset < param->blob.data_length || // Overflow check 406 static_cast<ptrdiff_t>(offset) > indirect_end - indirect_base || 407 static_cast<ptrdiff_t>(offset + param->blob.data_length) > indirect_end - indirect_base) 408 return false; 409 param->blob.data = indirect_base + offset; 410 return true; 411 } 412 } 413 414 return false; 415 } 416 417 size_t AuthorizationSet::SerializedSizeOfElements() const { 418 size_t size = 0; 419 for (size_t i = 0; i < elems_size_; ++i) { 420 size += serialized_size(elems_[i]); 421 } 422 return size; 423 } 424 425 size_t AuthorizationSet::SerializedSize() const { 426 return sizeof(uint32_t) + // Size of indirect_data_ 427 indirect_data_size_ + // indirect_data_ 428 sizeof(uint32_t) + // Number of elems_ 429 sizeof(uint32_t) + // Size of elems_ 430 SerializedSizeOfElements(); // elems_ 431 } 432 433 uint8_t* AuthorizationSet::Serialize(uint8_t* buf, const uint8_t* end) const { 434 buf = append_size_and_data_to_buf(buf, end, indirect_data_, indirect_data_size_); 435 buf = append_uint32_to_buf(buf, end, elems_size_); 436 buf = append_uint32_to_buf(buf, end, SerializedSizeOfElements()); 437 for (size_t i = 0; i < elems_size_; ++i) { 438 buf = serialize(elems_[i], buf, end, indirect_data_); 439 } 440 return buf; 441 } 442 443 bool AuthorizationSet::DeserializeIndirectData(const uint8_t** buf_ptr, const uint8_t* end) { 444 UniquePtr<uint8_t[]> indirect_buf; 445 if (!copy_size_and_data_from_buf(buf_ptr, end, &indirect_data_size_, &indirect_buf)) { 446 LOG_E("Malformed data found in AuthorizationSet deserialization", 0); 447 set_invalid(MALFORMED_DATA); 448 return false; 449 } 450 indirect_data_ = indirect_buf.release(); 451 return true; 452 } 453 454 bool AuthorizationSet::DeserializeElementsData(const uint8_t** buf_ptr, const uint8_t* end) { 455 uint32_t elements_count; 456 uint32_t elements_size; 457 if (!copy_uint32_from_buf(buf_ptr, end, &elements_count) || 458 !copy_uint32_from_buf(buf_ptr, end, &elements_size)) { 459 LOG_E("Malformed data found in AuthorizationSet deserialization", 0); 460 set_invalid(MALFORMED_DATA); 461 return false; 462 } 463 464 // Note that the following validation of elements_count is weak, but it prevents allocation of 465 // elems_ arrays which are clearly too large to be reasonable. 466 size_t elems_refs_size; 467 size_t elems_alloc_size; 468 bool refs_size_overflow = __builtin_mul_overflow(elements_count, sizeof(uint32_t), 469 &elems_refs_size); 470 bool alloc_size_overflow = __builtin_mul_overflow(elements_count, sizeof(*elems_), 471 &elems_alloc_size); 472 /* elements_size must fit in the buffer */ 473 if (static_cast<ptrdiff_t>(elements_size) > end - *buf_ptr || 474 /* The element refs must all fit within elements_size */ 475 elems_refs_size > elements_size || 476 /* If our pointer math would overflow, bail */ 477 refs_size_overflow || 478 /* If the resulting allocation would overflow, bail */ 479 alloc_size_overflow) { 480 LOG_E("Malformed data found in AuthorizationSet deserialization", 0); 481 set_invalid(MALFORMED_DATA); 482 return false; 483 } 484 485 if (!reserve_elems(elements_count)) 486 return false; 487 488 uint8_t* indirect_end = indirect_data_ + indirect_data_size_; 489 const uint8_t* elements_end = *buf_ptr + elements_size; 490 for (size_t i = 0; i < elements_count; ++i) { 491 if (!deserialize(elems_ + i, buf_ptr, elements_end, indirect_data_, indirect_end)) { 492 LOG_E("Malformed data found in AuthorizationSet deserialization", 0); 493 set_invalid(MALFORMED_DATA); 494 return false; 495 } 496 } 497 498 // Check if all the elements were consumed. If not, something was malformed as the 499 // retrieved elements_count and elements_size are not consistent with each other. 500 if (*buf_ptr != elements_end) { 501 LOG_E("Malformed data found in AuthorizationSet deserialization", 0); 502 set_invalid(MALFORMED_DATA); 503 return false; 504 } 505 506 elems_size_ = elements_count; 507 return true; 508 } 509 510 bool AuthorizationSet::Deserialize(const uint8_t** buf_ptr, const uint8_t* end) { 511 FreeData(); 512 513 if (!DeserializeIndirectData(buf_ptr, end) || !DeserializeElementsData(buf_ptr, end)) 514 return false; 515 516 if (indirect_data_size_ != ComputeIndirectDataSize(elems_, elems_size_)) { 517 LOG_E("Malformed data found in AuthorizationSet deserialization", 0); 518 set_invalid(MALFORMED_DATA); 519 return false; 520 } 521 return true; 522 } 523 524 void AuthorizationSet::Clear() { 525 memset_s(elems_, 0, elems_capacity_ * sizeof(keymaster_key_param_t)); 526 memset_s(indirect_data_, 0, indirect_data_capacity_); 527 elems_size_ = 0; 528 indirect_data_size_ = 0; 529 error_ = OK; 530 } 531 532 void AuthorizationSet::FreeData() { 533 Clear(); 534 535 delete[] elems_; 536 delete[] indirect_data_; 537 538 elems_ = nullptr; 539 indirect_data_ = nullptr; 540 elems_capacity_ = 0; 541 indirect_data_capacity_ = 0; 542 error_ = OK; 543 } 544 545 /* static */ 546 size_t AuthorizationSet::ComputeIndirectDataSize(const keymaster_key_param_t* elems, size_t count) { 547 size_t size = 0; 548 for (size_t i = 0; i < count; ++i) { 549 if (is_blob_tag(elems[i].tag)) { 550 size += elems[i].blob.data_length; 551 } 552 } 553 return size; 554 } 555 556 void AuthorizationSet::CopyIndirectData() { 557 memset_s(indirect_data_, 0, indirect_data_capacity_); 558 559 uint8_t* indirect_data_pos = indirect_data_; 560 for (size_t i = 0; i < elems_size_; ++i) { 561 assert(indirect_data_pos <= indirect_data_ + indirect_data_capacity_); 562 if (is_blob_tag(elems_[i].tag)) { 563 memcpy(indirect_data_pos, elems_[i].blob.data, elems_[i].blob.data_length); 564 elems_[i].blob.data = indirect_data_pos; 565 indirect_data_pos += elems_[i].blob.data_length; 566 } 567 } 568 assert(indirect_data_pos == indirect_data_ + indirect_data_capacity_); 569 indirect_data_size_ = indirect_data_pos - indirect_data_; 570 } 571 572 size_t AuthorizationSet::GetTagCount(keymaster_tag_t tag) const { 573 size_t count = 0; 574 for (int pos = -1; (pos = find(tag, pos)) != -1;) 575 ++count; 576 return count; 577 } 578 579 bool AuthorizationSet::GetTagValueEnum(keymaster_tag_t tag, uint32_t* val) const { 580 int pos = find(tag); 581 if (pos == -1) { 582 return false; 583 } 584 *val = elems_[pos].enumerated; 585 return true; 586 } 587 588 bool AuthorizationSet::GetTagValueEnumRep(keymaster_tag_t tag, size_t instance, 589 uint32_t* val) const { 590 size_t count = 0; 591 int pos = -1; 592 while (count <= instance) { 593 pos = find(tag, pos); 594 if (pos == -1) { 595 return false; 596 } 597 ++count; 598 } 599 *val = elems_[pos].enumerated; 600 return true; 601 } 602 603 bool AuthorizationSet::GetTagValueInt(keymaster_tag_t tag, uint32_t* val) const { 604 int pos = find(tag); 605 if (pos == -1) { 606 return false; 607 } 608 *val = elems_[pos].integer; 609 return true; 610 } 611 612 bool AuthorizationSet::GetTagValueIntRep(keymaster_tag_t tag, size_t instance, 613 uint32_t* val) const { 614 size_t count = 0; 615 int pos = -1; 616 while (count <= instance) { 617 pos = find(tag, pos); 618 if (pos == -1) { 619 return false; 620 } 621 ++count; 622 } 623 *val = elems_[pos].integer; 624 return true; 625 } 626 627 bool AuthorizationSet::GetTagValueLong(keymaster_tag_t tag, uint64_t* val) const { 628 int pos = find(tag); 629 if (pos == -1) { 630 return false; 631 } 632 *val = elems_[pos].long_integer; 633 return true; 634 } 635 636 bool AuthorizationSet::GetTagValueLongRep(keymaster_tag_t tag, size_t instance, 637 uint64_t* val) const { 638 size_t count = 0; 639 int pos = -1; 640 while (count <= instance) { 641 pos = find(tag, pos); 642 if (pos == -1) { 643 return false; 644 } 645 ++count; 646 } 647 *val = elems_[pos].long_integer; 648 return true; 649 } 650 651 bool AuthorizationSet::GetTagValueDate(keymaster_tag_t tag, uint64_t* val) const { 652 int pos = find(tag); 653 if (pos == -1) { 654 return false; 655 } 656 *val = elems_[pos].date_time; 657 return true; 658 } 659 660 bool AuthorizationSet::GetTagValueBlob(keymaster_tag_t tag, keymaster_blob_t* val) const { 661 int pos = find(tag); 662 if (pos == -1) { 663 return false; 664 } 665 *val = elems_[pos].blob; 666 return true; 667 } 668 669 bool AuthorizationSet::GetTagValueBool(keymaster_tag_t tag) const { 670 int pos = find(tag); 671 if (pos == -1) { 672 return false; 673 } 674 assert(elems_[pos].boolean); 675 return elems_[pos].boolean; 676 } 677 678 bool AuthorizationSet::ContainsEnumValue(keymaster_tag_t tag, uint32_t value) const { 679 for (auto& entry : *this) 680 if (entry.tag == tag && entry.enumerated == value) 681 return true; 682 return false; 683 } 684 685 bool AuthorizationSet::ContainsIntValue(keymaster_tag_t tag, uint32_t value) const { 686 for (auto& entry : *this) 687 if (entry.tag == tag && entry.integer == value) 688 return true; 689 return false; 690 } 691 692 } // namespace keymaster 693