Line data Source code
1 : #include "fd_rsa.h"
2 : #include "../sha256/fd_sha256.h"
3 : #include "../sha512/fd_sha512.h"
4 : #include <string.h>
5 :
6 : #ifdef FD_HAS_S2NBIGNUM
7 : #include <stdint.h>
8 : #include "../../third_party/s2n-bignum/include/s2n-bignum.h"
9 : #else
10 : #if !FD_HAS_INT128
11 : #error "fd_rsa requires FD_HAS_INT128"
12 : #endif
13 :
14 : /* Portable fallback for the three s2n-bignum routines fd_rsa_public_op
15 : uses. */
16 :
17 : /* Returns -n0^{-1} mod 2^64 (n0 odd) */
18 :
19 : static ulong
20 : fd_rsa_ref_n0inv( ulong n0 ) {
21 : ulong x = n0; /* correct to 3 bits, Newton doubles per step */
22 : for( int i=0; i<6; i++ ) x *= 2UL - n0*x;
23 : return 0UL-x;
24 : }
25 :
26 : /* z := x - n if x >= n (both k limbs) */
27 :
28 : static void
29 : fd_rsa_ref_reduce( ulong k,
30 : ulong * x,
31 : ulong const * n ) {
32 : ulong i = k;
33 : do { i--; } while( i && x[i]==n[i] );
34 : if( x[i]<n[i] ) return;
35 : ulong borrow = 0UL;
36 : for( ulong j=0UL; j<k; j++ ) {
37 : uint128 d = (uint128)x[j] - n[j] - borrow;
38 : x[j] = (ulong)d;
39 : borrow = (ulong)( d>>64 ) & 1UL;
40 : }
41 : }
42 :
43 : /* z := x*y/2^{64k} mod n (CIOS). z must not alias x or y. */
44 :
45 : static void
46 : bignum_montmul( ulong k,
47 : ulong * z,
48 : ulong const * x,
49 : ulong const * y,
50 : ulong const * n ) {
51 : ulong n0inv = fd_rsa_ref_n0inv( n[0] );
52 : ulong t[ FD_RSA_LIMB_CNT_MAX+2UL ];
53 : memset( t, 0, (k+2UL)*sizeof(ulong) );
54 : for( ulong i=0UL; i<k; i++ ) {
55 : uint128 c = 0;
56 : for( ulong j=0UL; j<k; j++ ) {
57 : c += (uint128)t[j] + (uint128)x[j]*y[i];
58 : t[j] = (ulong)c; c >>= 64;
59 : }
60 : c += t[k]; t[k] = (ulong)c; t[k+1UL] = (ulong)( c>>64 );
61 :
62 : ulong m = t[0]*n0inv;
63 : c = (uint128)t[0] + (uint128)m*n[0];
64 : c >>= 64;
65 : for( ulong j=1UL; j<k; j++ ) {
66 : c += (uint128)t[j] + (uint128)m*n[j];
67 : t[j-1UL] = (ulong)c; c >>= 64;
68 : }
69 : c += t[k]; t[k-1UL] = (ulong)c; t[k] = t[k+1UL] + (ulong)( c>>64 );
70 : }
71 : /* t < 2n here, and t[k] is 0 or 1 */
72 : if( t[k] ) {
73 : ulong borrow = 0UL;
74 : for( ulong j=0UL; j<k; j++ ) {
75 : uint128 d = (uint128)t[j] - n[j] - borrow;
76 : t[j] = (ulong)d;
77 : borrow = (ulong)( d>>64 ) & 1UL;
78 : }
79 : } else {
80 : fd_rsa_ref_reduce( k, t, n );
81 : }
82 : memcpy( z, t, k*sizeof(ulong) );
83 : }
84 :
85 : /* z := x/2^{64k} mod n */
86 :
87 : static void
88 : bignum_demont( ulong k,
89 : ulong * z,
90 : ulong const * x,
91 : ulong const * n ) {
92 : ulong one[ FD_RSA_LIMB_CNT_MAX ];
93 : memset( one, 0, k*sizeof(ulong) );
94 : one[0] = 1UL;
95 : bignum_montmul( k, z, x, one, n );
96 : }
97 :
98 : /* z := 2^{128k} mod n, by repeated doubling from 2^{b-1} < n where b
99 : is the bit length of n. */
100 :
101 : static void
102 : bignum_montifier( ulong k,
103 : ulong * z,
104 : ulong const * n,
105 : ulong * t ) {
106 : (void)t;
107 : ulong bits = 64UL*k;
108 : while( !( n[ (bits-1UL)>>6 ] >> ( (bits-1UL)&63UL ) & 1UL ) ) bits--;
109 : memset( z, 0, k*sizeof(ulong) );
110 : z[ (bits-1UL)>>6 ] = 1UL << ( (bits-1UL)&63UL );
111 : for( ulong i=bits-1UL; i<128UL*k; i++ ) {
112 : ulong carry = 0UL;
113 : for( ulong j=0UL; j<k; j++ ) {
114 : ulong next = z[j]>>63;
115 : z[j] = (z[j]<<1) | carry;
116 : carry = next;
117 : }
118 : if( carry ) {
119 : ulong borrow = 0UL;
120 : for( ulong j=0UL; j<k; j++ ) {
121 : uint128 d = (uint128)z[j] - n[j] - borrow;
122 : z[j] = (ulong)d;
123 : borrow = (ulong)( d>>64 ) & 1UL;
124 : }
125 : } else {
126 : fd_rsa_ref_reduce( k, z, n );
127 : }
128 : }
129 : }
130 :
131 : #endif /* FD_HAS_S2NBIGNUM */
132 :
133 : static ulong
134 5340 : fd_rsa_hash_sz( int hash ) {
135 5340 : switch( hash ) {
136 3333 : case FD_RSA_HASH_SHA256: return FD_SHA256_HASH_SZ;
137 957 : case FD_RSA_HASH_SHA384: return FD_SHA384_HASH_SZ;
138 960 : case FD_RSA_HASH_SHA512: return FD_SHA512_HASH_SZ;
139 90 : default: return 0UL;
140 5340 : }
141 5340 : }
142 :
143 : static void
144 : fd_rsa_hash( int hash,
145 : void const * data,
146 : ulong sz,
147 30423 : uchar * out ) {
148 30423 : switch( hash ) {
149 28608 : case FD_RSA_HASH_SHA256: fd_sha256_hash( data, sz, out ); break;
150 984 : case FD_RSA_HASH_SHA384: fd_sha384_hash( data, sz, out ); break;
151 831 : case FD_RSA_HASH_SHA512: fd_sha512_hash( data, sz, out ); break;
152 30423 : }
153 30423 : }
154 :
155 : /* Big endian bytes <-> little endian 64-bit limbs */
156 :
157 : static void
158 : fd_rsa_be_to_limbs( ulong * limbs,
159 : ulong limb_cnt,
160 : uchar const * be,
161 6486 : ulong be_sz ) {
162 6486 : memset( limbs, 0, limb_cnt*sizeof(ulong) );
163 2142078 : for( ulong i=0UL; i<be_sz; i++ )
164 2135592 : limbs[ i>>3 ] |= (ulong)be[ be_sz-1UL-i ] << ( 8UL*(i&7UL) );
165 6486 : }
166 :
167 : FD_FN_UNUSED static void
168 : fd_rsa_limbs_to_be( uchar * be,
169 : ulong be_sz,
170 4989 : ulong const * limbs ) {
171 1728135 : for( ulong i=0UL; i<be_sz; i++ )
172 1723146 : be[ be_sz-1UL-i ] = (uchar)( limbs[ i>>3 ] >> ( 8UL*(i&7UL) ) );
173 4989 : }
174 :
175 : fd_rsa_pubkey_t *
176 : fd_rsa_pubkey_init( fd_rsa_pubkey_t * key,
177 : uchar const * n,
178 : ulong n_sz,
179 : uchar const * e,
180 1470 : ulong e_sz ) {
181 1470 : if( FD_UNLIKELY( !key || !n || !e ) ) return NULL;
182 :
183 4410 : while( n_sz && !n[0] ) { n++; n_sz--; }
184 1488 : while( e_sz && !e[0] ) { e++; e_sz--; }
185 1461 : if( FD_UNLIKELY( !n_sz || n_sz>FD_RSA_MOD_SZ_MAX ) ) return NULL;
186 1452 : if( FD_UNLIKELY( !e_sz || e_sz>sizeof(ulong) ) ) return NULL;
187 :
188 1443 : ulong mod_bits = 8UL*(n_sz-1UL) + (ulong)fd_uchar_find_msb( n[0] ) + 1UL;
189 1443 : if( FD_UNLIKELY( mod_bits<FD_RSA_MOD_BITS_MIN || mod_bits>FD_RSA_MOD_BITS_MAX ) ) return NULL;
190 1437 : if( FD_UNLIKELY( !(n[ n_sz-1UL ] & 1U) ) ) return NULL;
191 :
192 1434 : ulong ev = 0UL;
193 5736 : for( ulong i=0UL; i<e_sz; i++ ) ev = (ev<<8) | (ulong)e[i];
194 1434 : if( FD_UNLIKELY( ev<3UL || !(ev & 1UL) ) ) return NULL;
195 :
196 1425 : memset( key, 0, sizeof(fd_rsa_pubkey_t) );
197 1425 : key->e = ev;
198 1425 : key->limb_cnt = (n_sz+7UL)>>3;
199 1425 : key->n_sz = n_sz;
200 1425 : key->mod_bits = mod_bits;
201 1425 : fd_rsa_be_to_limbs( key->n, key->limb_cnt, n, n_sz );
202 1425 : return key;
203 1434 : }
204 :
205 : /* fd_rsa_public_op computes em = sig^e mod n (RSAVP1, RFC 8017 Section
206 : 5.2.2) and writes it big endian to em[key->n_sz]. Returns 0 if sig
207 : is not a valid signature representative (wrong length or not below
208 : the modulus). */
209 :
210 : static int
211 : fd_rsa_public_op( fd_rsa_pubkey_t const * key,
212 : uchar const * sig,
213 : ulong sig_sz,
214 5250 : uchar * em ) {
215 5250 : if( FD_UNLIKELY( sig_sz!=key->n_sz ) ) return 0;
216 5061 : ulong const k = key->limb_cnt;
217 :
218 5061 : ulong s[ FD_RSA_LIMB_CNT_MAX ];
219 5061 : fd_rsa_be_to_limbs( s, k, sig, sig_sz );
220 :
221 : /* Require s < n */
222 5061 : ulong i = k;
223 7077 : do { i--; } while( i && s[i]==key->n[i] );
224 5061 : if( FD_UNLIKELY( s[i]>=key->n[i] ) ) return 0;
225 :
226 : /* Left-to-right binary exponentiation in the Montgomery domain
227 : (bignum_montmul does not support aliased operands) */
228 4989 : ulong r2 [ FD_RSA_LIMB_CNT_MAX ];
229 4989 : ulong tmp [ FD_RSA_LIMB_CNT_MAX ];
230 4989 : ulong base[ FD_RSA_LIMB_CNT_MAX ];
231 4989 : ulong acc0[ FD_RSA_LIMB_CNT_MAX ];
232 4989 : ulong acc1[ FD_RSA_LIMB_CNT_MAX ];
233 4989 : bignum_montifier( k, r2, key->n, tmp );
234 4989 : bignum_montmul( k, base, s, r2, key->n );
235 4989 : ulong * acc = acc0;
236 4989 : ulong * nxt = acc1;
237 4989 : memcpy( acc, base, k*sizeof(ulong) );
238 76713 : for( int bit=fd_ulong_find_msb( key->e )-1; bit>=0; bit-- ) {
239 71724 : bignum_montmul( k, nxt, acc, acc, key->n );
240 71724 : if( (key->e>>bit) & 1UL ) {
241 4989 : bignum_montmul( k, acc, nxt, base, key->n );
242 66735 : } else {
243 66735 : ulong * t = acc; acc = nxt; nxt = t;
244 66735 : }
245 71724 : }
246 4989 : bignum_demont( k, tmp, acc, key->n );
247 4989 : fd_rsa_limbs_to_be( em, key->n_sz, tmp );
248 4989 : return 1;
249 5061 : }
250 :
251 : /* DER DigestInfo prefixes (RFC 8017 Section 9.2 Note 1) */
252 :
253 : static uchar const fd_rsa_digest_info_sha256[ 19 ] = {
254 : 0x30,0x31,0x30,0x0d,0x06,0x09,0x60,0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x01,0x05,0x00,0x04,0x20 };
255 : static uchar const fd_rsa_digest_info_sha384[ 19 ] = {
256 : 0x30,0x41,0x30,0x0d,0x06,0x09,0x60,0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x02,0x05,0x00,0x04,0x30 };
257 : static uchar const fd_rsa_digest_info_sha512[ 19 ] = {
258 : 0x30,0x51,0x30,0x0d,0x06,0x09,0x60,0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x03,0x05,0x00,0x04,0x40 };
259 :
260 : int
261 : fd_rsa_verify_pkcs1_v15( fd_rsa_pubkey_t const * key,
262 : uchar const * sig,
263 : ulong sig_sz,
264 : uchar const * msg,
265 : ulong msg_sz,
266 1542 : int hash ) {
267 1542 : ulong h_sz = fd_rsa_hash_sz( hash );
268 1542 : if( FD_UNLIKELY( !h_sz ) ) return FD_RSA_FAILURE;
269 1497 : uchar const * prefix;
270 1497 : switch( hash ) {
271 546 : case FD_RSA_HASH_SHA256: prefix = fd_rsa_digest_info_sha256; break;
272 471 : case FD_RSA_HASH_SHA384: prefix = fd_rsa_digest_info_sha384; break;
273 480 : default: prefix = fd_rsa_digest_info_sha512; break;
274 1497 : }
275 :
276 1497 : uchar em[ FD_RSA_MOD_SZ_MAX ];
277 1497 : if( FD_UNLIKELY( !fd_rsa_public_op( key, sig, sig_sz, em ) ) ) return FD_RSA_FAILURE;
278 :
279 : /* Rebuild the one valid encoding for this modulus size and compare
280 : it whole (RFC 8017 Section 8.2.2 step 4), so no partial parse of
281 : em can accept an alternative padding. */
282 1371 : ulong const em_sz = key->n_sz;
283 1371 : ulong const t_sz = 19UL + h_sz;
284 1371 : if( FD_UNLIKELY( em_sz < t_sz+11UL ) ) return FD_RSA_FAILURE;
285 :
286 1371 : uchar expected[ FD_RSA_MOD_SZ_MAX ];
287 1371 : ulong ps_sz = em_sz - t_sz - 3UL;
288 1371 : expected[0] = 0x00;
289 1371 : expected[1] = 0x01;
290 1371 : memset( expected+2UL, 0xff, ps_sz );
291 1371 : expected[ 2UL+ps_sz ] = 0x00;
292 1371 : memcpy( expected+3UL+ps_sz, prefix, 19UL );
293 1371 : fd_rsa_hash( hash, msg, msg_sz, expected+em_sz-h_sz );
294 :
295 1371 : return fd_memeq( em, expected, em_sz ) ? FD_RSA_SUCCESS : FD_RSA_FAILURE;
296 1371 : }
297 :
298 : int
299 : fd_rsa_verify_pss( fd_rsa_pubkey_t const * key,
300 : uchar const * sig,
301 : ulong sig_sz,
302 : uchar const * msg,
303 : ulong msg_sz,
304 3798 : int hash ) {
305 3798 : ulong h_sz = fd_rsa_hash_sz( hash );
306 3798 : if( FD_UNLIKELY( !h_sz ) ) return FD_RSA_FAILURE;
307 3753 : ulong const s_sz = h_sz;
308 :
309 3753 : uchar em_buf[ FD_RSA_MOD_SZ_MAX ];
310 3753 : if( FD_UNLIKELY( !fd_rsa_public_op( key, sig, sig_sz, em_buf ) ) ) return FD_RSA_FAILURE;
311 :
312 : /* EMSA-PSS-VERIFY (RFC 8017 Section 9.1.2) with emBits = modBits-1.
313 : When modBits-1 is a multiple of 8, em is one byte shorter than the
314 : modulus and the public op result must have a zero leading byte. */
315 3618 : ulong const em_bits = key->mod_bits-1UL;
316 3618 : ulong const em_sz = (em_bits+7UL)>>3;
317 3618 : uchar const * em = em_buf;
318 3618 : if( em_sz<key->n_sz ) {
319 261 : if( FD_UNLIKELY( em_buf[0] ) ) return FD_RSA_FAILURE;
320 246 : em++;
321 246 : }
322 :
323 3603 : if( FD_UNLIKELY( em_sz < h_sz+s_sz+2UL ) ) return FD_RSA_FAILURE;
324 3603 : if( FD_UNLIKELY( em[ em_sz-1UL ]!=0xbc ) ) return FD_RSA_FAILURE;
325 :
326 2454 : ulong const db_sz = em_sz - h_sz - 1UL;
327 2454 : uchar const * masked_db = em;
328 2454 : uchar const * h = em + db_sz;
329 :
330 : /* The leftmost 8*emLen-emBits bits of maskedDB must be zero */
331 2454 : ulong const top_bits = 8UL*em_sz - em_bits;
332 2454 : if( FD_UNLIKELY( masked_db[0] & (uchar)( 0xff00U>>top_bits ) ) ) return FD_RSA_FAILURE;
333 :
334 : /* DB = maskedDB xor MGF1(H, dbLen) */
335 2454 : uchar db[ FD_RSA_MOD_SZ_MAX ];
336 2454 : uchar mgf_in[ FD_SHA512_HASH_SZ+4UL ];
337 2454 : memcpy( mgf_in, h, h_sz );
338 26826 : for( ulong off=0UL, ctr=0UL; off<db_sz; off+=h_sz, ctr++ ) {
339 24372 : FD_STORE( uint, mgf_in+h_sz, fd_uint_bswap( (uint)ctr ) );
340 24372 : uchar mask[ FD_SHA512_HASH_SZ ];
341 24372 : fd_rsa_hash( hash, mgf_in, h_sz+4UL, mask );
342 24372 : ulong n = fd_ulong_min( h_sz, db_sz-off );
343 817758 : for( ulong i=0UL; i<n; i++ ) db[ off+i ] = (uchar)( masked_db[ off+i ] ^ mask[ i ] );
344 24372 : }
345 2454 : db[0] = (uchar)( db[0] & (uchar)( 0xffU>>top_bits ) );
346 :
347 : /* DB = PS (zeros) || 0x01 || salt */
348 2454 : ulong const ps_sz = em_sz - h_sz - s_sz - 2UL;
349 2454 : uchar acc = 0;
350 711402 : for( ulong i=0UL; i<ps_sz; i++ ) acc |= db[i];
351 2454 : if( FD_UNLIKELY( acc || db[ ps_sz ]!=0x01 ) ) return FD_RSA_FAILURE;
352 2340 : uchar const * salt = db + ps_sz + 1UL;
353 :
354 : /* H' = Hash( 0x00 x8 || mHash || salt ) */
355 2340 : uchar m_prime[ 8UL + 2UL*FD_SHA512_HASH_SZ ];
356 2340 : memset( m_prime, 0, 8UL );
357 2340 : fd_rsa_hash( hash, msg, msg_sz, m_prime+8UL );
358 2340 : memcpy( m_prime+8UL+h_sz, salt, s_sz );
359 2340 : uchar h_prime[ FD_SHA512_HASH_SZ ];
360 2340 : fd_rsa_hash( hash, m_prime, 8UL+h_sz+s_sz, h_prime );
361 :
362 2340 : return fd_memeq( h_prime, h, h_sz ) ? FD_RSA_SUCCESS : FD_RSA_FAILURE;
363 2454 : }
|
