2rsa.c revision 9504754fee346569b4cdcaae9f54fa65cf3005d9
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 142e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangleruint32_t vb2_rsa_sig_size(uint32_t algorithm) 143e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 144e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler switch (algorithm) { 145e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA1024_SHA1: 146e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA1024_SHA256: 147e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA1024_SHA512: 148e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 1024 / 8; 149e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA2048_SHA1: 150e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA2048_SHA256: 151e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA2048_SHA512: 152e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 2048 / 8; 153e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA4096_SHA1: 154e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA4096_SHA256: 155e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA4096_SHA512: 156e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 4096 / 8; 157e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA8192_SHA1: 158e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA8192_SHA256: 159e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA8192_SHA512: 160e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 8192 / 8; 161e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler default: 162e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 0; 163e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 164e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 165e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 166e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangleruint32_t vb2_packed_key_size(uint32_t algorithm) 167e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 1689504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler uint32_t sig_size = vb2_rsa_sig_size(algorithm); 1699504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler 1709504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler if (!sig_size) 171e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return 0; 172e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 173e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* 174e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Total size needed by a RSAPublicKey buffer is = 175e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 2 * key_len bytes for the n and rr arrays 176e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * + sizeof len + sizeof n0inv. 177e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 1789504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler return 2 * sig_size + 2 * sizeof(uint32_t); 179e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 180e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 181e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/* 182e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * PKCS 1.5 padding (from the RSA PKCS#1 v2.1 standard) 183e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 184e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Depending on the RSA key size and hash function, the padding is calculated 185e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * as follows: 186e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 187e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 0x00 || 0x01 || PS || 0x00 || T 188e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 189e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * T: DER Encoded DigestInfo value which depends on the hash function used. 190e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 191e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * SHA-1: (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H. 192e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * SHA-256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H. 193e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * SHA-512: (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H. 194e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 195e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Length(T) = 35 octets for SHA-1 196e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Length(T) = 51 octets for SHA-256 197e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Length(T) = 83 octets for SHA-512 198e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 199e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * PS: octet string consisting of {Length(RSA Key) - Length(T) - 3} 0xFF 200e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 201e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic const uint8_t sha1_tail[] = { 202e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2b, 203e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14 204e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler}; 205e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 206e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic const uint8_t sha256_tail[] = { 207e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x00,0x30,0x31,0x30,0x0d,0x06,0x09,0x60, 208e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x01, 209e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x05,0x00,0x04,0x20 210e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler}; 211e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 212e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerstatic const uint8_t sha512_tail[] = { 213e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x00,0x30,0x51,0x30,0x0d,0x06,0x09,0x60, 214e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x03, 215e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 0x05,0x00,0x04,0x40 216e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler}; 217e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 218e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler/** 219e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Check pkcs 1.5 padding bytes 220e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * 221e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * @param sig Signature to verify 222e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * @param algorithm Key algorithm 223e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * @return VB2_SUCCESS, or non-zero if error. 224e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 225e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spanglerint vb2_check_padding(uint8_t *sig, int algorithm) 226e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 227e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Determine padding to use depending on the signature type */ 228e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t pad_size = vb2_rsa_sig_size(algorithm) - 229e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler vb2_digest_size(algorithm); 230e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler const uint8_t *tail; 231e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t tail_size; 232e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int result = 0; 233e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 234e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int i; 235e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 236e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler switch (algorithm) { 237e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA1024_SHA1: 238e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA2048_SHA1: 239e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA4096_SHA1: 240e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA8192_SHA1: 241e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail = sha1_tail; 242e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail_size = sizeof(sha1_tail); 243e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler break; 244e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA1024_SHA256: 245e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA2048_SHA256: 246e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA4096_SHA256: 247e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA8192_SHA256: 248e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail = sha256_tail; 249e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail_size = sizeof(sha256_tail); 250e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler break; 251e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA1024_SHA512: 252e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA2048_SHA512: 253e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA4096_SHA512: 254e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler case VB2_ALG_RSA8192_SHA512: 255e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail = sha512_tail; 256e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler tail_size = sizeof(sha512_tail); 257e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler break; 258e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler default: 259b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_PADDING_ALGORITHM; 260e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 261e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 262e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* First 2 bytes are always 0x00 0x01 */ 263e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler result |= *sig++ ^ 0x00; 264e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler result |= *sig++ ^ 0x01; 265e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 266e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Then 0xff bytes until the tail */ 267e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler for (i = 0; i < pad_size - tail_size - 2; i++) 268e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler result |= *sig++ ^ 0xff; 269e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 270e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* 271e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Then the tail. Even though there are probably no timing issues 272e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * here, we use vb2_safe_memcmp() just to be on the safe side. 273e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 274e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler result |= vb2_safe_memcmp(sig, tail, tail_size); 275e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 276b9be53640efdee92b1b42e60adda274563236301Randall Spangler return result ? VB2_ERROR_RSA_PADDING : VB2_SUCCESS; 277e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 278e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 2799504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spanglerint vb2_rsa_verify_digest(const struct vb2_public_key *key, 2809504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler uint8_t *sig, 2819504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler const uint8_t *digest, 2829504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler struct vb2_workbuf *wb) 283e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler{ 284e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler struct vb2_workbuf wblocal = *wb; 285e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler uint32_t *workbuf32; 286c6fa98d2ed1816d88e8517cd988de186fd6477b8Randall Spangler uint32_t key_bytes; 287e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int pad_size; 288e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler int rv; 289e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 290e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (!key || !sig || !digest) 291b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_VERIFY_PARAM; 292e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 2939504754fee346569b4cdcaae9f54fa65cf3005d9Randall Spangler if (key->algorithm > VB2_ALG_RSA8192_SHA512) { 294e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler VB2_DEBUG("Invalid signature type!\n"); 295b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_VERIFY_ALGORITHM; 296e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 297e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 298e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Signature length should be same as key length */ 299c6fa98d2ed1816d88e8517cd988de186fd6477b8Randall Spangler key_bytes = key->arrsize * sizeof(uint32_t); 300e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (key_bytes != vb2_rsa_sig_size(key->algorithm)) { 301e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler VB2_DEBUG("Signature is of incorrect length!\n"); 302b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_VERIFY_SIG_LEN; 303e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 304e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 305e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler workbuf32 = vb2_workbuf_alloc(&wblocal, 3 * key_bytes); 306e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (!workbuf32) 307b9be53640efdee92b1b42e60adda274563236301Randall Spangler return VB2_ERROR_RSA_VERIFY_WORKBUF; 308e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 309e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler modpowF4(key, sig, workbuf32); 310e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 311e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler vb2_workbuf_free(&wblocal, 3 * key_bytes); 312e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 313e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* Check padding */ 314e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler rv = vb2_check_padding(sig, key->algorithm); 315e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (rv) 316e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return rv; 317e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 318e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler /* 319e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * Check digest. Even though there are probably no timing issues here, 320e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * use vb2_safe_memcmp() just to be on the safe side. (That's also why 321e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler * we don't return before this check if the padding check failed.) 322e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler */ 323e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler pad_size = vb2_rsa_sig_size(key->algorithm) - 324e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler vb2_digest_size(key->algorithm); 325e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 326e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler if (vb2_safe_memcmp(sig + pad_size, digest, key_bytes - pad_size)) { 327e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler VB2_DEBUG("Digest check failed!\n"); 328b9be53640efdee92b1b42e60adda274563236301Randall Spangler rv = VB2_ERROR_RSA_VERIFY_DIGEST; 329e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler } 330e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler 331e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler return rv; 332e166d04e797b605dd2f6784bc863a262c418c0c4Randall Spangler} 333