authorization_set.cpp revision ba0d5d01bde427b7d7a22cec84cd9304c00b4e14 
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 <new>
25
26#include <keymaster/android_keymaster_utils.h>
27#include <keymaster/logger.h>
28
29namespace keymaster {
30
31static 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
35const size_t STARTING_ELEMS_CAPACITY = 8;
36
37AuthorizationSet::AuthorizationSet(AuthorizationSetBuilder& builder) {
38    elems_ = builder.set.elems_;
39    builder.set.elems_ = NULL;
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_ = NULL;
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
60AuthorizationSet::~AuthorizationSet() {
61    FreeData();
62}
63
64bool 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 == NULL) {
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
82bool 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 == NULL) {
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
106void 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
123bool AuthorizationSet::Reinitialize(const keymaster_key_param_t* elems, const size_t count) {
124    FreeData();
125
126    if (elems == NULL || 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
144void AuthorizationSet::set_invalid(Error error) {
145    FreeData();
146    error_ = error;
147}
148
149void AuthorizationSet::Sort() {
150    qsort(elems_, elems_size_, sizeof(*elems_),
151          reinterpret_cast<int (*)(const void*, const void*)>(keymaster_param_compare));
152}
153
154void 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
182void AuthorizationSet::CopyToParamSet(keymaster_key_param_set_t* set) const {
183    assert(set);
184
185    set->length = size();
186    set->params =
187        reinterpret_cast<keymaster_key_param_t*>(malloc(sizeof(keymaster_key_param_t) * size()));
188
189    for (size_t i = 0; i < size(); ++i) {
190        const keymaster_key_param_t src = (*this)[i];
191        keymaster_key_param_t& dst(set->params[i]);
192
193        dst = src;
194        keymaster_tag_type_t type = keymaster_tag_get_type(src.tag);
195        if (type == KM_BIGNUM || type == KM_BYTES) {
196            void* tmp = malloc(src.blob.data_length);
197            memcpy(tmp, src.blob.data, src.blob.data_length);
198            dst.blob.data = reinterpret_cast<uint8_t*>(tmp);
199        }
200    }
201}
202
203int AuthorizationSet::find(keymaster_tag_t tag, int begin) const {
204    if (is_valid() != OK)
205        return -1;
206
207    int i = ++begin;
208    while (i < (int)elems_size_ && elems_[i].tag != tag)
209        ++i;
210    if (i == (int)elems_size_)
211        return -1;
212    else
213        return i;
214}
215
216bool AuthorizationSet::erase(int index) {
217    if (index < 0 || index >= static_cast<int>(size()))
218        return false;
219
220    --elems_size_;
221    for (size_t i = index; i < elems_size_; ++i)
222        elems_[i] = elems_[i + 1];
223    return true;
224}
225
226keymaster_key_param_t empty_param = {KM_TAG_INVALID, {}};
227keymaster_key_param_t& AuthorizationSet::operator[](int at) {
228    if (is_valid() == OK && at < (int)elems_size_) {
229        return elems_[at];
230    }
231    empty_param = {KM_TAG_INVALID, {}};
232    return empty_param;
233}
234
235keymaster_key_param_t AuthorizationSet::operator[](int at) const {
236    if (is_valid() == OK && at < (int)elems_size_) {
237        return elems_[at];
238    }
239    empty_param = {KM_TAG_INVALID, {}};
240    return empty_param;
241}
242
243bool AuthorizationSet::push_back(const keymaster_key_param_set_t& set) {
244    if (is_valid() != OK)
245        return false;
246
247    if (!reserve_elems(elems_size_ + set.length))
248        return false;
249
250    if (!reserve_indirect(indirect_data_size_ + ComputeIndirectDataSize(set.params, set.length)))
251        return false;
252
253    for (size_t i = 0; i < set.length; ++i)
254        if (!push_back(set.params[i]))
255            return false;
256
257    return true;
258}
259
260bool AuthorizationSet::push_back(keymaster_key_param_t elem) {
261    if (is_valid() != OK)
262        return false;
263
264    if (elems_size_ >= elems_capacity_)
265        if (!reserve_elems(elems_capacity_ ? elems_capacity_ * 2 : STARTING_ELEMS_CAPACITY))
266            return false;
267
268    if (is_blob_tag(elem.tag)) {
269        if (indirect_data_capacity_ - indirect_data_size_ < elem.blob.data_length)
270            if (!reserve_indirect(2 * (indirect_data_capacity_ + elem.blob.data_length)))
271                return false;
272
273        memcpy(indirect_data_ + indirect_data_size_, elem.blob.data, elem.blob.data_length);
274        elem.blob.data = indirect_data_ + indirect_data_size_;
275        indirect_data_size_ += elem.blob.data_length;
276    }
277
278    elems_[elems_size_++] = elem;
279    return true;
280}
281
282static size_t serialized_size(const keymaster_key_param_t& param) {
283    switch (keymaster_tag_get_type(param.tag)) {
284    case KM_INVALID:
285        return sizeof(uint32_t);
286    case KM_ENUM:
287    case KM_ENUM_REP:
288    case KM_UINT:
289    case KM_UINT_REP:
290        return sizeof(uint32_t) * 2;
291    case KM_ULONG:
292    case KM_ULONG_REP:
293    case KM_DATE:
294        return sizeof(uint32_t) + sizeof(uint64_t);
295    case KM_BOOL:
296        return sizeof(uint32_t) + 1;
297    case KM_BIGNUM:
298    case KM_BYTES:
299        return sizeof(uint32_t) * 3;
300    }
301
302    return sizeof(uint32_t);
303}
304
305static uint8_t* serialize(const keymaster_key_param_t& param, uint8_t* buf, const uint8_t* end,
306                          const uint8_t* indirect_base) {
307    buf = append_uint32_to_buf(buf, end, param.tag);
308    switch (keymaster_tag_get_type(param.tag)) {
309    case KM_INVALID:
310        break;
311    case KM_ENUM:
312    case KM_ENUM_REP:
313        buf = append_uint32_to_buf(buf, end, param.enumerated);
314        break;
315    case KM_UINT:
316    case KM_UINT_REP:
317        buf = append_uint32_to_buf(buf, end, param.integer);
318        break;
319    case KM_ULONG:
320    case KM_ULONG_REP:
321        buf = append_uint64_to_buf(buf, end, param.long_integer);
322        break;
323    case KM_DATE:
324        buf = append_uint64_to_buf(buf, end, param.date_time);
325        break;
326    case KM_BOOL:
327        if (buf < end)
328            *buf = static_cast<uint8_t>(param.boolean);
329        buf++;
330        break;
331    case KM_BIGNUM:
332    case KM_BYTES:
333        buf = append_uint32_to_buf(buf, end, param.blob.data_length);
334        buf = append_uint32_to_buf(buf, end, param.blob.data - indirect_base);
335        break;
336    }
337    return buf;
338}
339
340static bool deserialize(keymaster_key_param_t* param, const uint8_t** buf_ptr, const uint8_t* end,
341                        const uint8_t* indirect_base, const uint8_t* indirect_end) {
342    if (!copy_uint32_from_buf(buf_ptr, end, &param->tag))
343        return false;
344
345    switch (keymaster_tag_get_type(param->tag)) {
346    case KM_INVALID:
347        return false;
348    case KM_ENUM:
349    case KM_ENUM_REP:
350        return copy_uint32_from_buf(buf_ptr, end, &param->enumerated);
351    case KM_UINT:
352    case KM_UINT_REP:
353        return copy_uint32_from_buf(buf_ptr, end, &param->integer);
354    case KM_ULONG:
355    case KM_ULONG_REP:
356        return copy_uint64_from_buf(buf_ptr, end, &param->long_integer);
357    case KM_DATE:
358        return copy_uint64_from_buf(buf_ptr, end, &param->date_time);
359        break;
360    case KM_BOOL:
361        if (*buf_ptr < end) {
362            param->boolean = static_cast<bool>(**buf_ptr);
363            (*buf_ptr)++;
364            return true;
365        }
366        return false;
367
368    case KM_BIGNUM:
369    case KM_BYTES: {
370        uint32_t offset;
371        if (!copy_uint32_from_buf(buf_ptr, end, &param->blob.data_length) ||
372            !copy_uint32_from_buf(buf_ptr, end, &offset))
373            return false;
374        if (param->blob.data_length + offset < param->blob.data_length ||  // Overflow check
375            static_cast<ptrdiff_t>(offset) > indirect_end - indirect_base ||
376            static_cast<ptrdiff_t>(offset + param->blob.data_length) > indirect_end - indirect_base)
377            return false;
378        param->blob.data = indirect_base + offset;
379        return true;
380    }
381    }
382
383    return false;
384}
385
386size_t AuthorizationSet::SerializedSizeOfElements() const {
387    size_t size = 0;
388    for (size_t i = 0; i < elems_size_; ++i) {
389        size += serialized_size(elems_[i]);
390    }
391    return size;
392}
393
394size_t AuthorizationSet::SerializedSize() const {
395    return sizeof(uint32_t) +           // Size of indirect_data_
396           indirect_data_size_ +        // indirect_data_
397           sizeof(uint32_t) +           // Number of elems_
398           sizeof(uint32_t) +           // Size of elems_
399           SerializedSizeOfElements();  // elems_
400}
401
402uint8_t* AuthorizationSet::Serialize(uint8_t* buf, const uint8_t* end) const {
403    buf = append_size_and_data_to_buf(buf, end, indirect_data_, indirect_data_size_);
404    buf = append_uint32_to_buf(buf, end, elems_size_);
405    buf = append_uint32_to_buf(buf, end, SerializedSizeOfElements());
406    for (size_t i = 0; i < elems_size_; ++i) {
407        buf = serialize(elems_[i], buf, end, indirect_data_);
408    }
409    return buf;
410}
411
412bool AuthorizationSet::DeserializeIndirectData(const uint8_t** buf_ptr, const uint8_t* end) {
413    UniquePtr<uint8_t[]> indirect_buf;
414    if (!copy_size_and_data_from_buf(buf_ptr, end, &indirect_data_size_, &indirect_buf)) {
415        LOG_E("Malformed data found in AuthorizationSet deserialization", 0);
416        set_invalid(MALFORMED_DATA);
417        return false;
418    }
419    indirect_data_ = indirect_buf.release();
420    return true;
421}
422
423bool AuthorizationSet::DeserializeElementsData(const uint8_t** buf_ptr, const uint8_t* end) {
424    uint32_t elements_count;
425    uint32_t elements_size;
426    if (!copy_uint32_from_buf(buf_ptr, end, &elements_count) ||
427        !copy_uint32_from_buf(buf_ptr, end, &elements_size)) {
428        LOG_E("Malformed data found in AuthorizationSet deserialization", 0);
429        set_invalid(MALFORMED_DATA);
430        return false;
431    }
432
433    // Note that the following validation of elements_count is weak, but it prevents allocation of
434    // elems_ arrays which are clearly too large to be reasonable.
435    if (static_cast<ptrdiff_t>(elements_size) > end - *buf_ptr ||
436        elements_count * sizeof(uint32_t) > elements_size ||
437        *buf_ptr + (elements_count * sizeof(*elems_)) < *buf_ptr) {
438        LOG_E("Malformed data found in AuthorizationSet deserialization", 0);
439        set_invalid(MALFORMED_DATA);
440        return false;
441    }
442
443    if (!reserve_elems(elements_count))
444        return false;
445
446    uint8_t* indirect_end = indirect_data_ + indirect_data_size_;
447    const uint8_t* elements_end = *buf_ptr + elements_size;
448    for (size_t i = 0; i < elements_count; ++i) {
449        if (!deserialize(elems_ + i, buf_ptr, elements_end, indirect_data_, indirect_end)) {
450            LOG_E("Malformed data found in AuthorizationSet deserialization", 0);
451            set_invalid(MALFORMED_DATA);
452            return false;
453        }
454    }
455    elems_size_ = elements_count;
456    return true;
457}
458
459bool AuthorizationSet::Deserialize(const uint8_t** buf_ptr, const uint8_t* end) {
460    FreeData();
461
462    if (!DeserializeIndirectData(buf_ptr, end) || !DeserializeElementsData(buf_ptr, end))
463        return false;
464
465    if (indirect_data_size_ != ComputeIndirectDataSize(elems_, elems_size_)) {
466        LOG_E("Malformed data found in AuthorizationSet deserialization", 0);
467        set_invalid(MALFORMED_DATA);
468        return false;
469    }
470    return true;
471}
472
473void AuthorizationSet::Clear() {
474    memset_s(elems_, 0, elems_size_ * sizeof(keymaster_key_param_t));
475    memset_s(indirect_data_, 0, indirect_data_size_);
476    elems_size_ = 0;
477    indirect_data_size_ = 0;
478}
479
480void AuthorizationSet::FreeData() {
481    Clear();
482
483    delete[] elems_;
484    delete[] indirect_data_;
485
486    elems_ = NULL;
487    indirect_data_ = NULL;
488    elems_capacity_ = 0;
489    indirect_data_capacity_ = 0;
490    error_ = OK;
491}
492
493/* static */
494size_t AuthorizationSet::ComputeIndirectDataSize(const keymaster_key_param_t* elems, size_t count) {
495    size_t size = 0;
496    for (size_t i = 0; i < count; ++i) {
497        if (is_blob_tag(elems[i].tag)) {
498            size += elems[i].blob.data_length;
499        }
500    }
501    return size;
502}
503
504void AuthorizationSet::CopyIndirectData() {
505    memset_s(indirect_data_, 0, indirect_data_capacity_);
506
507    uint8_t* indirect_data_pos = indirect_data_;
508    for (size_t i = 0; i < elems_size_; ++i) {
509        assert(indirect_data_pos <= indirect_data_ + indirect_data_capacity_);
510        if (is_blob_tag(elems_[i].tag)) {
511            memcpy(indirect_data_pos, elems_[i].blob.data, elems_[i].blob.data_length);
512            elems_[i].blob.data = indirect_data_pos;
513            indirect_data_pos += elems_[i].blob.data_length;
514        }
515    }
516    assert(indirect_data_pos == indirect_data_ + indirect_data_capacity_);
517    indirect_data_size_ = indirect_data_pos - indirect_data_;
518}
519
520size_t AuthorizationSet::GetTagCount(keymaster_tag_t tag) const {
521    size_t count = 0;
522    for (int pos = -1; (pos = find(tag, pos)) != -1;)
523        ++count;
524    return count;
525}
526
527bool AuthorizationSet::GetTagValueEnum(keymaster_tag_t tag, uint32_t* val) const {
528    int pos = find(tag);
529    if (pos == -1) {
530        return false;
531    }
532    *val = elems_[pos].enumerated;
533    return true;
534}
535
536bool AuthorizationSet::GetTagValueEnumRep(keymaster_tag_t tag, size_t instance,
537                                          uint32_t* val) const {
538    size_t count = 0;
539    int pos = -1;
540    while (count <= instance) {
541        pos = find(tag, pos);
542        if (pos == -1) {
543            return false;
544        }
545        ++count;
546    }
547    *val = elems_[pos].enumerated;
548    return true;
549}
550
551bool AuthorizationSet::GetTagValueInt(keymaster_tag_t tag, uint32_t* val) const {
552    int pos = find(tag);
553    if (pos == -1) {
554        return false;
555    }
556    *val = elems_[pos].integer;
557    return true;
558}
559
560bool AuthorizationSet::GetTagValueIntRep(keymaster_tag_t tag, size_t instance,
561                                         uint32_t* val) const {
562    size_t count = 0;
563    int pos = -1;
564    while (count <= instance) {
565        pos = find(tag, pos);
566        if (pos == -1) {
567            return false;
568        }
569        ++count;
570    }
571    *val = elems_[pos].integer;
572    return true;
573}
574
575bool AuthorizationSet::GetTagValueLong(keymaster_tag_t tag, uint64_t* val) const {
576    int pos = find(tag);
577    if (pos == -1) {
578        return false;
579    }
580    *val = elems_[pos].long_integer;
581    return true;
582}
583
584bool AuthorizationSet::GetTagValueLongRep(keymaster_tag_t tag, size_t instance,
585                                          uint64_t* val) const {
586    size_t count = 0;
587    int pos = -1;
588    while (count <= instance) {
589        pos = find(tag, pos);
590        if (pos == -1) {
591            return false;
592        }
593        ++count;
594    }
595    *val = elems_[pos].long_integer;
596    return true;
597}
598
599bool AuthorizationSet::GetTagValueDate(keymaster_tag_t tag, uint64_t* val) const {
600    int pos = find(tag);
601    if (pos == -1) {
602        return false;
603    }
604    *val = elems_[pos].date_time;
605    return true;
606}
607
608bool AuthorizationSet::GetTagValueBlob(keymaster_tag_t tag, keymaster_blob_t* val) const {
609    int pos = find(tag);
610    if (pos == -1) {
611        return false;
612    }
613    *val = elems_[pos].blob;
614    return true;
615}
616
617bool AuthorizationSet::GetTagValueBool(keymaster_tag_t tag) const {
618    int pos = find(tag);
619    if (pos == -1) {
620        return false;
621    }
622    assert(elems_[pos].boolean);
623    return elems_[pos].boolean;
624}
625
626bool AuthorizationSet::ContainsEnumValue(keymaster_tag_t tag, uint32_t value) const {
627    for (auto& entry : *this)
628        if (entry.tag == tag && entry.enumerated == value)
629            return true;
630    return false;
631}
632
633bool AuthorizationSet::ContainsIntValue(keymaster_tag_t tag, uint32_t value) const {
634    for (auto& entry : *this)
635        if (entry.tag == tag && entry.integer == value)
636            return true;
637    return false;
638}
639
640}  // namespace keymaster
641