1e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/* Copyright (c) 2014 The Chromium OS Authors. All rights reserved. 2e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Use of this source code is governed by a BSD-style license that can be 3e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * found in the LICENSE file. 4e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 5e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 6e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/* 7e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Implementation of RSA signature verification which uses a pre-processed key 8e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * for computation. The code extends Android's RSA verification code to support 9e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * multiple RSA key lengths and hash digest algorithms. 10e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 11e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 12e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler#include "2sysincludes.h" 13e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler#include "2common.h" 14e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler#include "2rsa.h" 15e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler#include "2sha.h" 16e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 17e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/** 18e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * a[] -= mod 19e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 20e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic void subM(const struct vb2_public_key *key, uint32_t *a) 21e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 22e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int64_t A = 0; 23e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t i; 24e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = 0; i < key->arrsize; ++i) { 25e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler A += (uint64_t)a[i] - key->n[i]; 26e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler a[i] = (uint32_t)A; 27e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler A >>= 32; 28e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 29e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 30e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 31e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/** 32e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Return a[] >= mod 33e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 34e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerint vb2_mont_ge(const struct vb2_public_key *key, uint32_t *a) 35e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 36e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t i; 37e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = key->arrsize; i;) { 38e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler --i; 39e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (a[i] < key->n[i]) 40e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 0; 41e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (a[i] > key->n[i]) 42e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 1; 43e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 44e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 1; /* equal */ 45e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 46e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 47e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/** 48e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Montgomery c[] += a * b[] / R % mod 49e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 50e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic void montMulAdd(const struct vb2_public_key *key, 51e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t *c, 52e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler const uint32_t a, 53e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler const uint32_t *b) 54e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 55e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint64_t A = (uint64_t)a * b[0] + c[0]; 56e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t d0 = (uint32_t)A * key->n0inv; 57e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A; 58e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t i; 59e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 60e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = 1; i < key->arrsize; ++i) { 61e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler A = (A >> 32) + (uint64_t)a * b[i] + c[i]; 62e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A; 63e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler c[i - 1] = (uint32_t)B; 64e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 65e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 66e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler A = (A >> 32) + (B >> 32); 67e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 68e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler c[i - 1] = (uint32_t)A; 69e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 70e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (A >> 32) { 71e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler subM(key, c); 72e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 73e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 74e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 75e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/** 76e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Montgomery c[] = a[] * b[] / R % mod 77e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 78e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic void montMul(const struct vb2_public_key *key, 79e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t *c, 80e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler const uint32_t *a, 81e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler const uint32_t *b) 82e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 83e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t i; 84e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = 0; i < key->arrsize; ++i) { 85e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler c[i] = 0; 86e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 87e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = 0; i < key->arrsize; ++i) { 88e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler montMulAdd(key, c, a[i], b); 89e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 90e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 91e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 92e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/** 93e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * In-place public exponentiation. (65537} 94e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 95e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * @param key Key to use in signing 96e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * @param inout Input and output big-endian byte array 97e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * @param workbuf32 Work buffer; caller must verify this is 98e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * (3 * key->arrsize) elements long. 99e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 100e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic void modpowF4(const struct vb2_public_key *key, uint8_t *inout, 101e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t *workbuf32) 102e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 103e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t *a = workbuf32; 104e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t *aR = a + key->arrsize; 105e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t *aaR = aR + key->arrsize; 106e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t *aaa = aaR; /* Re-use location. */ 107e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int i; 108e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 109e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Convert from big endian byte array to little endian word array. */ 110e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = 0; i < (int)key->arrsize; ++i) { 111e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t tmp = 112e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler (inout[((key->arrsize - 1 - i) * 4) + 0] << 24) | 113e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler (inout[((key->arrsize - 1 - i) * 4) + 1] << 16) | 114e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler (inout[((key->arrsize - 1 - i) * 4) + 2] << 8) | 115e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler (inout[((key->arrsize - 1 - i) * 4) + 3] << 0); 116e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler a[i] = tmp; 117e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 118e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 119e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */ 120e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = 0; i < 16; i+=2) { 121e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ 122e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */ 123e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 124e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */ 125e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 126e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 127e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Make sure aaa < mod; aaa is at most 1x mod too large. */ 128e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (vb2_mont_ge(key, aaa)) { 129e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler subM(key, aaa); 130e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 131e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 132e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Convert to bigendian byte array */ 133e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = (int)key->arrsize - 1; i >= 0; --i) { 134e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t tmp = aaa[i]; 135e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler *inout++ = (uint8_t)(tmp >> 24); 136e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler *inout++ = (uint8_t)(tmp >> 16); 137e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler *inout++ = (uint8_t)(tmp >> 8); 138e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler *inout++ = (uint8_t)(tmp >> 0); 139e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 140e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 141e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 142c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler 143c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spanglerstatic const uint8_t crypto_to_sig[] = { 144c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA1024, 145c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA1024, 146c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA1024, 147c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA2048, 148c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA2048, 149c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA2048, 150c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA4096, 151c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA4096, 152c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA4096, 153c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA8192, 154c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA8192, 155c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler VB2_SIG_RSA8192, 156c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler}; 157c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler 158c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler/** 159c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * Convert vb2_crypto_algorithm to vb2_signature_algorithm. 160c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * 161c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * @param algorithm Crypto algorithm (vb2_crypto_algorithm) 162c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * 163c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * @return The signature algorithm for that crypto algorithm, or 164c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * VB2_SIG_INVALID if the crypto algorithm or its corresponding signature 165c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * algorithm is invalid or not supported. 166c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler */ 167c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spanglerenum vb2_signature_algorithm vb2_crypto_to_signature(uint32_t algorithm) 168c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler{ 169c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler if (algorithm < ARRAY_SIZE(crypto_to_sig)) 170c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler return crypto_to_sig[algorithm]; 171c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler else 172c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler return VB2_SIG_INVALID; 173c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler} 174c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler 175c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangleruint32_t vb2_rsa_sig_size(enum vb2_signature_algorithm sig_alg) 176e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 177c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler switch (sig_alg) { 178c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler case VB2_SIG_RSA1024: 179e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 1024 / 8; 180c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler case VB2_SIG_RSA2048: 181e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 2048 / 8; 182c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler case VB2_SIG_RSA4096: 183e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 4096 / 8; 184c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler case VB2_SIG_RSA8192: 185e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 8192 / 8; 186e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler default: 187e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 0; 188e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 189e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 190e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 191c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangleruint32_t vb2_packed_key_size(enum vb2_signature_algorithm sig_alg) 192e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 193c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler uint32_t sig_size = vb2_rsa_sig_size(sig_alg); 1949504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler 1959504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler if (!sig_size) 196e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 0; 197e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 198e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* 199e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Total size needed by a RSAPublicKey buffer is = 200e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 2 * key_len bytes for the n and rr arrays 201e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * + sizeof len + sizeof n0inv. 202e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 2039504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler return 2 * sig_size + 2 * sizeof(uint32_t); 204e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 205e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 206e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/* 207e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * PKCS 1.5 padding (from the RSA PKCS#1 v2.1 standard) 208e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 209e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Depending on the RSA key size and hash function, the padding is calculated 210e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * as follows: 211e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 212e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 0x00 || 0x01 || PS || 0x00 || T 213e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 214e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * T: DER Encoded DigestInfo value which depends on the hash function used. 215e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 216e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * SHA-1: (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H. 217e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * SHA-256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H. 218e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * SHA-512: (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H. 219e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 220e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Length(T) = 35 octets for SHA-1 221e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Length(T) = 51 octets for SHA-256 222e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Length(T) = 83 octets for SHA-512 223e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 224e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * PS: octet string consisting of {Length(RSA Key) - Length(T) - 3} 0xFF 225e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 226e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic const uint8_t sha1_tail[] = { 227e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2b, 228e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14 229e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler}; 230e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 231e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic const uint8_t sha256_tail[] = { 232e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x00,0x30,0x31,0x30,0x0d,0x06,0x09,0x60, 233e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x01, 234e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x05,0x00,0x04,0x20 235e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler}; 236e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 237e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic const uint8_t sha512_tail[] = { 238e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x00,0x30,0x51,0x30,0x0d,0x06,0x09,0x60, 239e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x03, 240e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x05,0x00,0x04,0x40 241e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler}; 242e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 243c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spanglerint vb2_check_padding(const uint8_t *sig, const struct vb2_public_key *key) 244e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 245e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Determine padding to use depending on the signature type */ 246c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler uint32_t sig_size = vb2_rsa_sig_size(key->sig_alg); 247c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler uint32_t hash_size = vb2_digest_size(key->hash_alg); 248c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler uint32_t pad_size = sig_size - hash_size; 249e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler const uint8_t *tail; 250e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t tail_size; 251e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int result = 0; 252e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int i; 253e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 254c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler if (!sig_size || !hash_size || hash_size > sig_size) 255c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler return VB2_ERROR_RSA_PADDING_SIZE; 256c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler 257c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler switch (key->hash_alg) { 2584eef812d68f64cc501d795131d95f8a2f27223b1Randall Spangler case VB2_HASH_SHA1: 259e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail = sha1_tail; 260e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail_size = sizeof(sha1_tail); 261e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler break; 2624eef812d68f64cc501d795131d95f8a2f27223b1Randall Spangler case VB2_HASH_SHA256: 263e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail = sha256_tail; 264e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail_size = sizeof(sha256_tail); 265e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler break; 2664eef812d68f64cc501d795131d95f8a2f27223b1Randall Spangler case VB2_HASH_SHA512: 267e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail = sha512_tail; 268e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail_size = sizeof(sha512_tail); 269e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler break; 270e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler default: 271b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_PADDING_ALGORITHM; 272e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 273e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 274e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* First 2 bytes are always 0x00 0x01 */ 275e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler result |= *sig++ ^ 0x00; 276e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler result |= *sig++ ^ 0x01; 277e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 278e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Then 0xff bytes until the tail */ 279e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = 0; i < pad_size - tail_size - 2; i++) 280e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler result |= *sig++ ^ 0xff; 281e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 282e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* 283e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Then the tail. Even though there are probably no timing issues 284e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * here, we use vb2_safe_memcmp() just to be on the safe side. 285e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 286e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler result |= vb2_safe_memcmp(sig, tail, tail_size); 287e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 288b9be53640efdee92b1b42e60adda274563236301Randall Spangler return result ? VB2_ERROR_RSA_PADDING : VB2_SUCCESS; 289e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 290e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 2919504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spanglerint vb2_rsa_verify_digest(const struct vb2_public_key *key, 2929504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler uint8_t *sig, 2939504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler const uint8_t *digest, 294a063a43ad776c9831051e62565c0136ce36d0b09Randall Spangler const struct vb2_workbuf *wb) 295e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 296e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler struct vb2_workbuf wblocal = *wb; 297e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t *workbuf32; 298c6fa98d2ed1816d88e8517cd988de186fd6477b8Randall Spangler uint32_t key_bytes; 299c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler int sig_size; 300e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int pad_size; 301e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int rv; 302e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 303e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (!key || !sig || !digest) 304b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_VERIFY_PARAM; 305e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 306c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler sig_size = vb2_rsa_sig_size(key->sig_alg); 307c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler if (!sig_size) { 308e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler VB2_DEBUG("Invalid signature type!\n"); 309b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_VERIFY_ALGORITHM; 310e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 311e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 312e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Signature length should be same as key length */ 313c6fa98d2ed1816d88e8517cd988de186fd6477b8Randall Spangler key_bytes = key->arrsize * sizeof(uint32_t); 314c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler if (key_bytes != sig_size) { 315e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler VB2_DEBUG("Signature is of incorrect length!\n"); 316b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_VERIFY_SIG_LEN; 317e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 318e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 319e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler workbuf32 = vb2_workbuf_alloc(&wblocal, 3 * key_bytes); 320e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (!workbuf32) 321b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_VERIFY_WORKBUF; 322e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 323e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler modpowF4(key, sig, workbuf32); 324e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 325e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler vb2_workbuf_free(&wblocal, 3 * key_bytes); 326e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 327c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler /* 328c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * Check padding. Only fail immediately if the padding size is bad. 329c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * Otherwise, continue on to check the digest to reduce the risk of 330c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler * timing based attacks. 331c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler */ 332c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler rv = vb2_check_padding(sig, key); 333c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler if (rv == VB2_ERROR_RSA_PADDING_SIZE) 334e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return rv; 335e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 336e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* 337e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Check digest. Even though there are probably no timing issues here, 338e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * use vb2_safe_memcmp() just to be on the safe side. (That's also why 339e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * we don't return before this check if the padding check failed.) 340e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 341c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler pad_size = sig_size - vb2_digest_size(key->hash_alg); 342e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (vb2_safe_memcmp(sig + pad_size, digest, key_bytes - pad_size)) { 343e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler VB2_DEBUG("Digest check failed!\n"); 344c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler if (!rv) 345c8c2f023a4914a498c11b855210ef05d4e035d41Randall Spangler rv = VB2_ERROR_RSA_VERIFY_DIGEST; 346e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 347e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 348e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return rv; 349e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 350