Home | History | Annotate | Download | only in keymaster
      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/keymaster_enforcement.h>
     18 
     19 #include <assert.h>
     20 #include <limits.h>
     21 #include <string.h>
     22 
     23 #include <openssl/evp.h>
     24 
     25 #include <hardware/hw_auth_token.h>
     26 #include <keymaster/android_keymaster_utils.h>
     27 #include <keymaster/logger.h>
     28 
     29 #include "List.h"
     30 
     31 using android::List;
     32 
     33 namespace keymaster {
     34 
     35 class AccessTimeMap {
     36   public:
     37     AccessTimeMap(uint32_t max_size) : max_size_(max_size) {}
     38 
     39     /* If the key is found, returns true and fills \p last_access_time.  If not found returns
     40      * false. */
     41     bool LastKeyAccessTime(km_id_t keyid, uint32_t* last_access_time) const;
     42 
     43     /* Updates the last key access time with the currentTime parameter.  Adds the key if
     44      * needed, returning false if key cannot be added because list is full. */
     45     bool UpdateKeyAccessTime(km_id_t keyid, uint32_t current_time, uint32_t timeout);
     46 
     47   private:
     48     struct AccessTime {
     49         km_id_t keyid;
     50         uint32_t access_time;
     51         uint32_t timeout;
     52     };
     53     android::List<AccessTime> last_access_list_;
     54     const uint32_t max_size_;
     55 };
     56 
     57 class AccessCountMap {
     58   public:
     59     AccessCountMap(uint32_t max_size) : max_size_(max_size) {}
     60 
     61     /* If the key is found, returns true and fills \p count.  If not found returns
     62      * false. */
     63     bool KeyAccessCount(km_id_t keyid, uint32_t* count) const;
     64 
     65     /* Increments key access count, adding an entry if the key has never been used.  Returns
     66      * false if the list has reached maximum size. */
     67     bool IncrementKeyAccessCount(km_id_t keyid);
     68 
     69   private:
     70     struct AccessCount {
     71         km_id_t keyid;
     72         uint64_t access_count;
     73     };
     74     android::List<AccessCount> access_count_list_;
     75     const uint32_t max_size_;
     76 };
     77 
     78 bool is_public_key_algorithm(const AuthorizationSet& auth_set) {
     79     keymaster_algorithm_t algorithm;
     80     return auth_set.GetTagValue(TAG_ALGORITHM, &algorithm) &&
     81            (algorithm == KM_ALGORITHM_RSA || algorithm == KM_ALGORITHM_EC);
     82 }
     83 
     84 static keymaster_error_t authorized_purpose(const keymaster_purpose_t purpose,
     85                                             const AuthorizationSet& auth_set) {
     86     switch (purpose) {
     87     case KM_PURPOSE_VERIFY:
     88     case KM_PURPOSE_ENCRYPT:
     89     case KM_PURPOSE_SIGN:
     90     case KM_PURPOSE_DECRYPT:
     91         if (auth_set.Contains(TAG_PURPOSE, purpose))
     92             return KM_ERROR_OK;
     93         return KM_ERROR_INCOMPATIBLE_PURPOSE;
     94 
     95     default:
     96         return KM_ERROR_UNSUPPORTED_PURPOSE;
     97     }
     98 }
     99 
    100 inline bool is_origination_purpose(keymaster_purpose_t purpose) {
    101     return purpose == KM_PURPOSE_ENCRYPT || purpose == KM_PURPOSE_SIGN;
    102 }
    103 
    104 inline bool is_usage_purpose(keymaster_purpose_t purpose) {
    105     return purpose == KM_PURPOSE_DECRYPT || purpose == KM_PURPOSE_VERIFY;
    106 }
    107 
    108 KeymasterEnforcement::KeymasterEnforcement(uint32_t max_access_time_map_size,
    109                                            uint32_t max_access_count_map_size)
    110     : access_time_map_(new (std::nothrow) AccessTimeMap(max_access_time_map_size)),
    111       access_count_map_(new (std::nothrow) AccessCountMap(max_access_count_map_size)) {}
    112 
    113 KeymasterEnforcement::~KeymasterEnforcement() {
    114     delete access_time_map_;
    115     delete access_count_map_;
    116 }
    117 
    118 keymaster_error_t KeymasterEnforcement::AuthorizeOperation(const keymaster_purpose_t purpose,
    119                                                            const km_id_t keyid,
    120                                                            const AuthorizationSet& auth_set,
    121                                                            const AuthorizationSet& operation_params,
    122                                                            keymaster_operation_handle_t op_handle,
    123                                                            bool is_begin_operation) {
    124     if (is_public_key_algorithm(auth_set)) {
    125         switch (purpose) {
    126         case KM_PURPOSE_ENCRYPT:
    127         case KM_PURPOSE_VERIFY:
    128             /* Public key operations are always authorized. */
    129             return KM_ERROR_OK;
    130 
    131         case KM_PURPOSE_DECRYPT:
    132         case KM_PURPOSE_SIGN:
    133         case KM_PURPOSE_DERIVE_KEY:
    134             break;
    135         };
    136     };
    137 
    138     if (is_begin_operation)
    139         return AuthorizeBegin(purpose, keyid, auth_set, operation_params);
    140     else
    141         return AuthorizeUpdateOrFinish(auth_set, operation_params, op_handle);
    142 }
    143 
    144 // For update and finish the only thing to check is user authentication, and then only if it's not
    145 // timeout-based.
    146 keymaster_error_t
    147 KeymasterEnforcement::AuthorizeUpdateOrFinish(const AuthorizationSet& auth_set,
    148                                               const AuthorizationSet& operation_params,
    149                                               keymaster_operation_handle_t op_handle) {
    150     int auth_type_index = -1;
    151     for (size_t pos = 0; pos < auth_set.size(); ++pos) {
    152         switch (auth_set[pos].tag) {
    153         case KM_TAG_NO_AUTH_REQUIRED:
    154         case KM_TAG_AUTH_TIMEOUT:
    155             // If no auth is required or if auth is timeout-based, we have nothing to check.
    156             return KM_ERROR_OK;
    157 
    158         case KM_TAG_USER_AUTH_TYPE:
    159             auth_type_index = pos;
    160             break;
    161 
    162         default:
    163             break;
    164         }
    165     }
    166 
    167     // Note that at this point we should be able to assume that authentication is required, because
    168     // authentication is required if KM_TAG_NO_AUTH_REQUIRED is absent.  However, there are legacy
    169     // keys which have no authentication-related tags, so we assume that absence is equivalent to
    170     // presence of KM_TAG_NO_AUTH_REQUIRED.
    171     //
    172     // So, if we found KM_TAG_USER_AUTH_TYPE or if we find KM_TAG_USER_SECURE_ID then authentication
    173     // is required.  If we find neither, then we assume authentication is not required and return
    174     // success.
    175     bool authentication_required = (auth_type_index != -1);
    176     for (auto& param : auth_set) {
    177         if (param.tag == KM_TAG_USER_SECURE_ID) {
    178             authentication_required = true;
    179             int auth_timeout_index = -1;
    180             if (AuthTokenMatches(auth_set, operation_params, param.long_integer, auth_type_index,
    181                                  auth_timeout_index, op_handle, false /* is_begin_operation */))
    182                 return KM_ERROR_OK;
    183         }
    184     }
    185 
    186     if (authentication_required)
    187         return KM_ERROR_KEY_USER_NOT_AUTHENTICATED;
    188 
    189     return KM_ERROR_OK;
    190 }
    191 
    192 keymaster_error_t KeymasterEnforcement::AuthorizeBegin(const keymaster_purpose_t purpose,
    193                                                        const km_id_t keyid,
    194                                                        const AuthorizationSet& auth_set,
    195                                                        const AuthorizationSet& operation_params) {
    196     // Find some entries that may be needed to handle KM_TAG_USER_SECURE_ID
    197     int auth_timeout_index = -1;
    198     int auth_type_index = -1;
    199     int no_auth_required_index = -1;
    200     for (size_t pos = 0; pos < auth_set.size(); ++pos) {
    201         switch (auth_set[pos].tag) {
    202         case KM_TAG_AUTH_TIMEOUT:
    203             auth_timeout_index = pos;
    204             break;
    205         case KM_TAG_USER_AUTH_TYPE:
    206             auth_type_index = pos;
    207             break;
    208         case KM_TAG_NO_AUTH_REQUIRED:
    209             no_auth_required_index = pos;
    210             break;
    211         default:
    212             break;
    213         }
    214     }
    215 
    216     keymaster_error_t error = authorized_purpose(purpose, auth_set);
    217     if (error != KM_ERROR_OK)
    218         return error;
    219 
    220     // If successful, and if key has a min time between ops, this will be set to the time limit
    221     uint32_t min_ops_timeout = UINT32_MAX;
    222 
    223     bool update_access_count = false;
    224     bool caller_nonce_authorized_by_key = false;
    225     bool authentication_required = false;
    226     bool auth_token_matched = false;
    227 
    228     for (auto& param : auth_set) {
    229 
    230         // KM_TAG_PADDING_OLD and KM_TAG_DIGEST_OLD aren't actually members of the enum, so we can't
    231         // switch on them.  There's nothing to validate for them, though, so just ignore them.
    232         if (param.tag == KM_TAG_PADDING_OLD || param.tag == KM_TAG_DIGEST_OLD)
    233             continue;
    234 
    235         switch (param.tag) {
    236 
    237         case KM_TAG_ACTIVE_DATETIME:
    238             if (!activation_date_valid(param.date_time))
    239                 return KM_ERROR_KEY_NOT_YET_VALID;
    240             break;
    241 
    242         case KM_TAG_ORIGINATION_EXPIRE_DATETIME:
    243             if (is_origination_purpose(purpose) && expiration_date_passed(param.date_time))
    244                 return KM_ERROR_KEY_EXPIRED;
    245             break;
    246 
    247         case KM_TAG_USAGE_EXPIRE_DATETIME:
    248             if (is_usage_purpose(purpose) && expiration_date_passed(param.date_time))
    249                 return KM_ERROR_KEY_EXPIRED;
    250             break;
    251 
    252         case KM_TAG_MIN_SECONDS_BETWEEN_OPS:
    253             min_ops_timeout = param.integer;
    254             if (!MinTimeBetweenOpsPassed(min_ops_timeout, keyid))
    255                 return KM_ERROR_KEY_RATE_LIMIT_EXCEEDED;
    256             break;
    257 
    258         case KM_TAG_MAX_USES_PER_BOOT:
    259             update_access_count = true;
    260             if (!MaxUsesPerBootNotExceeded(keyid, param.integer))
    261                 return KM_ERROR_KEY_MAX_OPS_EXCEEDED;
    262             break;
    263 
    264         case KM_TAG_USER_SECURE_ID:
    265             if (no_auth_required_index != -1) {
    266                 // Key has both KM_TAG_USER_SECURE_ID and KM_TAG_NO_AUTH_REQUIRED
    267                 return KM_ERROR_INVALID_KEY_BLOB;
    268             }
    269 
    270             if (auth_timeout_index != -1) {
    271                 authentication_required = true;
    272                 if (AuthTokenMatches(auth_set, operation_params, param.long_integer,
    273                                      auth_type_index, auth_timeout_index, 0 /* op_handle */,
    274                                      true /* is_begin_operation */))
    275                     auth_token_matched = true;
    276             }
    277             break;
    278 
    279         case KM_TAG_CALLER_NONCE:
    280             caller_nonce_authorized_by_key = true;
    281             break;
    282 
    283         /* Tags should never be in key auths. */
    284         case KM_TAG_INVALID:
    285         case KM_TAG_AUTH_TOKEN:
    286         case KM_TAG_ROOT_OF_TRUST:
    287         case KM_TAG_APPLICATION_DATA:
    288         case KM_TAG_ATTESTATION_CHALLENGE:
    289             return KM_ERROR_INVALID_KEY_BLOB;
    290 
    291         /* Tags used for cryptographic parameters in keygen.  Nothing to enforce. */
    292         case KM_TAG_PURPOSE:
    293         case KM_TAG_ALGORITHM:
    294         case KM_TAG_KEY_SIZE:
    295         case KM_TAG_BLOCK_MODE:
    296         case KM_TAG_DIGEST:
    297         case KM_TAG_MAC_LENGTH:
    298         case KM_TAG_PADDING:
    299         case KM_TAG_NONCE:
    300         case KM_TAG_MIN_MAC_LENGTH:
    301         case KM_TAG_KDF:
    302         case KM_TAG_EC_CURVE:
    303 
    304         /* Tags not used for operations. */
    305         case KM_TAG_BLOB_USAGE_REQUIREMENTS:
    306         case KM_TAG_EXPORTABLE:
    307 
    308         /* Algorithm specific parameters not used for access control. */
    309         case KM_TAG_RSA_PUBLIC_EXPONENT:
    310         case KM_TAG_ECIES_SINGLE_HASH_MODE:
    311 
    312         /* Informational tags. */
    313         case KM_TAG_CREATION_DATETIME:
    314         case KM_TAG_ORIGIN:
    315         case KM_TAG_ROLLBACK_RESISTANT:
    316 
    317         /* Tags handled when KM_TAG_USER_SECURE_ID is handled */
    318         case KM_TAG_NO_AUTH_REQUIRED:
    319         case KM_TAG_USER_AUTH_TYPE:
    320         case KM_TAG_AUTH_TIMEOUT:
    321 
    322         /* Tag to provide data to operations. */
    323         case KM_TAG_ASSOCIATED_DATA:
    324 
    325         /* Tags that are implicitly verified by secure side */
    326         case KM_TAG_ALL_APPLICATIONS:
    327         case KM_TAG_APPLICATION_ID:
    328         case KM_TAG_OS_VERSION:
    329         case KM_TAG_OS_PATCHLEVEL:
    330 
    331         /* Ignored pending removal */
    332         case KM_TAG_USER_ID:
    333         case KM_TAG_ALL_USERS:
    334 
    335         /* TODO(swillden): Handle these */
    336         case KM_TAG_INCLUDE_UNIQUE_ID:
    337         case KM_TAG_UNIQUE_ID:
    338         case KM_TAG_RESET_SINCE_ID_ROTATION:
    339         case KM_TAG_ALLOW_WHILE_ON_BODY:
    340             break;
    341 
    342         case KM_TAG_BOOTLOADER_ONLY:
    343             return KM_ERROR_INVALID_KEY_BLOB;
    344         }
    345     }
    346 
    347     if (authentication_required && !auth_token_matched) {
    348         LOG_E("Auth required but no matching auth token found", 0);
    349         return KM_ERROR_KEY_USER_NOT_AUTHENTICATED;
    350     }
    351 
    352     if (!caller_nonce_authorized_by_key && is_origination_purpose(purpose) &&
    353         operation_params.find(KM_TAG_NONCE) != -1)
    354         return KM_ERROR_CALLER_NONCE_PROHIBITED;
    355 
    356     if (min_ops_timeout != UINT32_MAX) {
    357         if (!access_time_map_) {
    358             LOG_S("Rate-limited keys table not allocated.  Rate-limited keys disabled", 0);
    359             return KM_ERROR_MEMORY_ALLOCATION_FAILED;
    360         }
    361 
    362         if (!access_time_map_->UpdateKeyAccessTime(keyid, get_current_time(), min_ops_timeout)) {
    363             LOG_E("Rate-limited keys table full.  Entries will time out.", 0);
    364             return KM_ERROR_TOO_MANY_OPERATIONS;
    365         }
    366     }
    367 
    368     if (update_access_count) {
    369         if (!access_count_map_) {
    370             LOG_S("Usage-count limited keys tabel not allocated.  Count-limited keys disabled", 0);
    371             return KM_ERROR_MEMORY_ALLOCATION_FAILED;
    372         }
    373 
    374         if (!access_count_map_->IncrementKeyAccessCount(keyid)) {
    375             LOG_E("Usage count-limited keys table full, until reboot.", 0);
    376             return KM_ERROR_TOO_MANY_OPERATIONS;
    377         }
    378     }
    379 
    380     return KM_ERROR_OK;
    381 }
    382 
    383 class EvpMdCtx {
    384   public:
    385     EvpMdCtx() { EVP_MD_CTX_init(&ctx_); }
    386     ~EvpMdCtx() { EVP_MD_CTX_cleanup(&ctx_); }
    387 
    388     EVP_MD_CTX* get() { return &ctx_; }
    389 
    390   private:
    391     EVP_MD_CTX ctx_;
    392 };
    393 
    394 /* static */
    395 bool KeymasterEnforcement::CreateKeyId(const keymaster_key_blob_t& key_blob, km_id_t* keyid) {
    396     EvpMdCtx ctx;
    397 
    398     uint8_t hash[EVP_MAX_MD_SIZE];
    399     unsigned int hash_len;
    400     if (EVP_DigestInit_ex(ctx.get(), EVP_sha256(), nullptr /* ENGINE */) &&
    401         EVP_DigestUpdate(ctx.get(), key_blob.key_material, key_blob.key_material_size) &&
    402         EVP_DigestFinal_ex(ctx.get(), hash, &hash_len)) {
    403         assert(hash_len >= sizeof(*keyid));
    404         memcpy(keyid, hash, sizeof(*keyid));
    405         return true;
    406     }
    407 
    408     return false;
    409 }
    410 
    411 bool KeymasterEnforcement::MinTimeBetweenOpsPassed(uint32_t min_time_between, const km_id_t keyid) {
    412     if (!access_time_map_)
    413         return false;
    414 
    415     uint32_t last_access_time;
    416     if (!access_time_map_->LastKeyAccessTime(keyid, &last_access_time))
    417         return true;
    418     return min_time_between <= static_cast<int64_t>(get_current_time()) - last_access_time;
    419 }
    420 
    421 bool KeymasterEnforcement::MaxUsesPerBootNotExceeded(const km_id_t keyid, uint32_t max_uses) {
    422     if (!access_count_map_)
    423         return false;
    424 
    425     uint32_t key_access_count;
    426     if (!access_count_map_->KeyAccessCount(keyid, &key_access_count))
    427         return true;
    428     return key_access_count < max_uses;
    429 }
    430 
    431 bool KeymasterEnforcement::AuthTokenMatches(const AuthorizationSet& auth_set,
    432                                             const AuthorizationSet& operation_params,
    433                                             const uint64_t user_secure_id,
    434                                             const int auth_type_index, const int auth_timeout_index,
    435                                             const keymaster_operation_handle_t op_handle,
    436                                             bool is_begin_operation) const {
    437     assert(auth_type_index < static_cast<int>(auth_set.size()));
    438     assert(auth_timeout_index < static_cast<int>(auth_set.size()));
    439 
    440     keymaster_blob_t auth_token_blob;
    441     if (!operation_params.GetTagValue(TAG_AUTH_TOKEN, &auth_token_blob)) {
    442         LOG_E("Authentication required, but auth token not provided", 0);
    443         return false;
    444     }
    445 
    446     if (auth_token_blob.data_length != sizeof(hw_auth_token_t)) {
    447         LOG_E("Bug: Auth token is the wrong size (%d expected, %d found)", sizeof(hw_auth_token_t),
    448               auth_token_blob.data_length);
    449         return false;
    450     }
    451 
    452     hw_auth_token_t auth_token;
    453     memcpy(&auth_token, auth_token_blob.data, sizeof(hw_auth_token_t));
    454     if (auth_token.version != HW_AUTH_TOKEN_VERSION) {
    455         LOG_E("Bug: Auth token is the version %d (or is not an auth token). Expected %d",
    456               auth_token.version, HW_AUTH_TOKEN_VERSION);
    457         return false;
    458     }
    459 
    460     if (!ValidateTokenSignature(auth_token)) {
    461         LOG_E("Auth token signature invalid", 0);
    462         return false;
    463     }
    464 
    465     if (auth_timeout_index == -1 && op_handle && op_handle != auth_token.challenge) {
    466         LOG_E("Auth token has the challenge %llu, need %llu", auth_token.challenge, op_handle);
    467         return false;
    468     }
    469 
    470     if (user_secure_id != auth_token.user_id && user_secure_id != auth_token.authenticator_id) {
    471         LOG_I("Auth token SIDs %llu and %llu do not match key SID %llu", auth_token.user_id,
    472               auth_token.authenticator_id, user_secure_id);
    473         return false;
    474     }
    475 
    476     if (auth_type_index < 0 || auth_type_index > static_cast<int>(auth_set.size())) {
    477         LOG_E("Auth required but no auth type found", 0);
    478         return false;
    479     }
    480 
    481     assert(auth_set[auth_type_index].tag == KM_TAG_USER_AUTH_TYPE);
    482     if (auth_set[auth_type_index].tag != KM_TAG_USER_AUTH_TYPE)
    483         return false;
    484 
    485     uint32_t key_auth_type_mask = auth_set[auth_type_index].integer;
    486     uint32_t token_auth_type = ntoh(auth_token.authenticator_type);
    487     if ((key_auth_type_mask & token_auth_type) == 0) {
    488         LOG_E("Key requires match of auth type mask 0%uo, but token contained 0%uo",
    489               key_auth_type_mask, token_auth_type);
    490         return false;
    491     }
    492 
    493     if (auth_timeout_index != -1 && is_begin_operation) {
    494         assert(auth_set[auth_timeout_index].tag == KM_TAG_AUTH_TIMEOUT);
    495         if (auth_set[auth_timeout_index].tag != KM_TAG_AUTH_TIMEOUT)
    496             return false;
    497 
    498         if (auth_token_timed_out(auth_token, auth_set[auth_timeout_index].integer)) {
    499             LOG_E("Auth token has timed out", 0);
    500             return false;
    501         }
    502     }
    503 
    504     // Survived the whole gauntlet.  We have authentage!
    505     return true;
    506 }
    507 
    508 bool AccessTimeMap::LastKeyAccessTime(km_id_t keyid, uint32_t* last_access_time) const {
    509     for (auto& entry : last_access_list_)
    510         if (entry.keyid == keyid) {
    511             *last_access_time = entry.access_time;
    512             return true;
    513         }
    514     return false;
    515 }
    516 
    517 bool AccessTimeMap::UpdateKeyAccessTime(km_id_t keyid, uint32_t current_time, uint32_t timeout) {
    518     List<AccessTime>::iterator iter;
    519     for (iter = last_access_list_.begin(); iter != last_access_list_.end();) {
    520         if (iter->keyid == keyid) {
    521             iter->access_time = current_time;
    522             return true;
    523         }
    524 
    525         // Expire entry if possible.
    526         assert(current_time >= iter->access_time);
    527         if (current_time - iter->access_time >= iter->timeout)
    528             iter = last_access_list_.erase(iter);
    529         else
    530             ++iter;
    531     }
    532 
    533     if (last_access_list_.size() >= max_size_)
    534         return false;
    535 
    536     AccessTime new_entry;
    537     new_entry.keyid = keyid;
    538     new_entry.access_time = current_time;
    539     new_entry.timeout = timeout;
    540     last_access_list_.push_front(new_entry);
    541     return true;
    542 }
    543 
    544 bool AccessCountMap::KeyAccessCount(km_id_t keyid, uint32_t* count) const {
    545     for (auto& entry : access_count_list_)
    546         if (entry.keyid == keyid) {
    547             *count = entry.access_count;
    548             return true;
    549         }
    550     return false;
    551 }
    552 
    553 bool AccessCountMap::IncrementKeyAccessCount(km_id_t keyid) {
    554     for (auto& entry : access_count_list_)
    555         if (entry.keyid == keyid) {
    556             // Note that the 'if' below will always be true because KM_TAG_MAX_USES_PER_BOOT is a
    557             // uint32_t, and as soon as entry.access_count reaches the specified maximum value
    558             // operation requests will be rejected and access_count won't be incremented any more.
    559             // And, besides, UINT64_MAX is huge.  But we ensure that it doesn't wrap anyway, out of
    560             // an abundance of caution.
    561             if (entry.access_count < UINT64_MAX)
    562                 ++entry.access_count;
    563             return true;
    564         }
    565 
    566     if (access_count_list_.size() >= max_size_)
    567         return false;
    568 
    569     AccessCount new_entry;
    570     new_entry.keyid = keyid;
    571     new_entry.access_count = 1;
    572     access_count_list_.push_front(new_entry);
    573     return true;
    574 }
    575 }; /* namespace keymaster */
    576