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 0 : fd_rsa_hash_sz( int hash ) {
135 0 : switch( hash ) {
136 0 : case FD_RSA_HASH_SHA256: return FD_SHA256_HASH_SZ;
137 0 : case FD_RSA_HASH_SHA384: return FD_SHA384_HASH_SZ;
138 0 : case FD_RSA_HASH_SHA512: return FD_SHA512_HASH_SZ;
139 0 : default: return 0UL;
140 0 : }
141 0 : }
142 :
143 : static void
144 : fd_rsa_hash( int hash,
145 : void const * data,
146 : ulong sz,
147 0 : uchar * out ) {
148 0 : switch( hash ) {
149 0 : case FD_RSA_HASH_SHA256: fd_sha256_hash( data, sz, out ); break;
150 0 : case FD_RSA_HASH_SHA384: fd_sha384_hash( data, sz, out ); break;
151 0 : case FD_RSA_HASH_SHA512: fd_sha512_hash( data, sz, out ); break;
152 0 : }
153 0 : }
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 0 : ulong be_sz ) {
162 0 : memset( limbs, 0, limb_cnt*sizeof(ulong) );
163 0 : for( ulong i=0UL; i<be_sz; i++ )
164 0 : limbs[ i>>3 ] |= (ulong)be[ be_sz-1UL-i ] << ( 8UL*(i&7UL) );
165 0 : }
166 :
167 : FD_FN_UNUSED static void
168 : fd_rsa_limbs_to_be( uchar * be,
169 : ulong be_sz,
170 0 : ulong const * limbs ) {
171 0 : for( ulong i=0UL; i<be_sz; i++ )
172 0 : be[ be_sz-1UL-i ] = (uchar)( limbs[ i>>3 ] >> ( 8UL*(i&7UL) ) );
173 0 : }
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 0 : ulong e_sz ) {
181 0 : if( FD_UNLIKELY( !key || !n || !e ) ) return NULL;
182 :
183 0 : while( n_sz && !n[0] ) { n++; n_sz--; }
184 0 : while( e_sz && !e[0] ) { e++; e_sz--; }
185 0 : if( FD_UNLIKELY( !n_sz || n_sz>FD_RSA_MOD_SZ_MAX ) ) return NULL;
186 0 : if( FD_UNLIKELY( !e_sz || e_sz>sizeof(ulong) ) ) return NULL;
187 :
188 0 : ulong mod_bits = 8UL*(n_sz-1UL) + (ulong)fd_uchar_find_msb( n[0] ) + 1UL;
189 0 : if( FD_UNLIKELY( mod_bits<FD_RSA_MOD_BITS_MIN || mod_bits>FD_RSA_MOD_BITS_MAX ) ) return NULL;
190 0 : if( FD_UNLIKELY( !(n[ n_sz-1UL ] & 1U) ) ) return NULL;
191 :
192 0 : ulong ev = 0UL;
193 0 : for( ulong i=0UL; i<e_sz; i++ ) ev = (ev<<8) | (ulong)e[i];
194 0 : if( FD_UNLIKELY( ev<3UL || !(ev & 1UL) ) ) return NULL;
195 :
196 0 : memset( key, 0, sizeof(fd_rsa_pubkey_t) );
197 0 : key->e = ev;
198 0 : key->limb_cnt = (n_sz+7UL)>>3;
199 0 : key->n_sz = n_sz;
200 0 : key->mod_bits = mod_bits;
201 0 : fd_rsa_be_to_limbs( key->n, key->limb_cnt, n, n_sz );
202 0 : return key;
203 0 : }
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 0 : uchar * em ) {
215 0 : if( FD_UNLIKELY( sig_sz!=key->n_sz ) ) return 0;
216 0 : ulong const k = key->limb_cnt;
217 :
218 0 : ulong s[ FD_RSA_LIMB_CNT_MAX ];
219 0 : fd_rsa_be_to_limbs( s, k, sig, sig_sz );
220 :
221 : /* Require s < n */
222 0 : ulong i = k;
223 0 : do { i--; } while( i && s[i]==key->n[i] );
224 0 : 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 0 : ulong r2 [ FD_RSA_LIMB_CNT_MAX ];
229 0 : ulong tmp [ FD_RSA_LIMB_CNT_MAX ];
230 0 : ulong base[ FD_RSA_LIMB_CNT_MAX ];
231 0 : ulong acc0[ FD_RSA_LIMB_CNT_MAX ];
232 0 : ulong acc1[ FD_RSA_LIMB_CNT_MAX ];
233 0 : bignum_montifier( k, r2, key->n, tmp );
234 0 : bignum_montmul( k, base, s, r2, key->n );
235 0 : ulong * acc = acc0;
236 0 : ulong * nxt = acc1;
237 0 : memcpy( acc, base, k*sizeof(ulong) );
238 0 : for( int bit=fd_ulong_find_msb( key->e )-1; bit>=0; bit-- ) {
239 0 : bignum_montmul( k, nxt, acc, acc, key->n );
240 0 : if( (key->e>>bit) & 1UL ) {
241 0 : bignum_montmul( k, acc, nxt, base, key->n );
242 0 : } else {
243 0 : ulong * t = acc; acc = nxt; nxt = t;
244 0 : }
245 0 : }
246 0 : bignum_demont( k, tmp, acc, key->n );
247 0 : fd_rsa_limbs_to_be( em, key->n_sz, tmp );
248 0 : return 1;
249 0 : }
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 0 : int hash ) {
267 0 : ulong h_sz = fd_rsa_hash_sz( hash );
268 0 : if( FD_UNLIKELY( !h_sz ) ) return FD_RSA_FAILURE;
269 0 : uchar const * prefix;
270 0 : switch( hash ) {
271 0 : case FD_RSA_HASH_SHA256: prefix = fd_rsa_digest_info_sha256; break;
272 0 : case FD_RSA_HASH_SHA384: prefix = fd_rsa_digest_info_sha384; break;
273 0 : default: prefix = fd_rsa_digest_info_sha512; break;
274 0 : }
275 :
276 0 : uchar em[ FD_RSA_MOD_SZ_MAX ];
277 0 : 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 0 : ulong const em_sz = key->n_sz;
283 0 : ulong const t_sz = 19UL + h_sz;
284 0 : if( FD_UNLIKELY( em_sz < t_sz+11UL ) ) return FD_RSA_FAILURE;
285 :
286 0 : uchar expected[ FD_RSA_MOD_SZ_MAX ];
287 0 : ulong ps_sz = em_sz - t_sz - 3UL;
288 0 : expected[0] = 0x00;
289 0 : expected[1] = 0x01;
290 0 : memset( expected+2UL, 0xff, ps_sz );
291 0 : expected[ 2UL+ps_sz ] = 0x00;
292 0 : memcpy( expected+3UL+ps_sz, prefix, 19UL );
293 0 : fd_rsa_hash( hash, msg, msg_sz, expected+em_sz-h_sz );
294 :
295 0 : return fd_memeq( em, expected, em_sz ) ? FD_RSA_SUCCESS : FD_RSA_FAILURE;
296 0 : }
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 0 : int hash ) {
305 0 : ulong h_sz = fd_rsa_hash_sz( hash );
306 0 : if( FD_UNLIKELY( !h_sz ) ) return FD_RSA_FAILURE;
307 0 : ulong const s_sz = h_sz;
308 :
309 0 : uchar em_buf[ FD_RSA_MOD_SZ_MAX ];
310 0 : 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 0 : ulong const em_bits = key->mod_bits-1UL;
316 0 : ulong const em_sz = (em_bits+7UL)>>3;
317 0 : uchar const * em = em_buf;
318 0 : if( em_sz<key->n_sz ) {
319 0 : if( FD_UNLIKELY( em_buf[0] ) ) return FD_RSA_FAILURE;
320 0 : em++;
321 0 : }
322 :
323 0 : if( FD_UNLIKELY( em_sz < h_sz+s_sz+2UL ) ) return FD_RSA_FAILURE;
324 0 : if( FD_UNLIKELY( em[ em_sz-1UL ]!=0xbc ) ) return FD_RSA_FAILURE;
325 :
326 0 : ulong const db_sz = em_sz - h_sz - 1UL;
327 0 : uchar const * masked_db = em;
328 0 : uchar const * h = em + db_sz;
329 :
330 : /* The leftmost 8*emLen-emBits bits of maskedDB must be zero */
331 0 : ulong const top_bits = 8UL*em_sz - em_bits;
332 0 : if( FD_UNLIKELY( masked_db[0] & (uchar)( 0xff00U>>top_bits ) ) ) return FD_RSA_FAILURE;
333 :
334 : /* DB = maskedDB xor MGF1(H, dbLen) */
335 0 : uchar db[ FD_RSA_MOD_SZ_MAX ];
336 0 : uchar mgf_in[ FD_SHA512_HASH_SZ+4UL ];
337 0 : memcpy( mgf_in, h, h_sz );
338 0 : for( ulong off=0UL, ctr=0UL; off<db_sz; off+=h_sz, ctr++ ) {
339 0 : FD_STORE( uint, mgf_in+h_sz, fd_uint_bswap( (uint)ctr ) );
340 0 : uchar mask[ FD_SHA512_HASH_SZ ];
341 0 : fd_rsa_hash( hash, mgf_in, h_sz+4UL, mask );
342 0 : ulong n = fd_ulong_min( h_sz, db_sz-off );
343 0 : for( ulong i=0UL; i<n; i++ ) db[ off+i ] = (uchar)( masked_db[ off+i ] ^ mask[ i ] );
344 0 : }
345 0 : db[0] = (uchar)( db[0] & (uchar)( 0xffU>>top_bits ) );
346 :
347 : /* DB = PS (zeros) || 0x01 || salt */
348 0 : ulong const ps_sz = em_sz - h_sz - s_sz - 2UL;
349 0 : uchar acc = 0;
350 0 : for( ulong i=0UL; i<ps_sz; i++ ) acc |= db[i];
351 0 : if( FD_UNLIKELY( acc || db[ ps_sz ]!=0x01 ) ) return FD_RSA_FAILURE;
352 0 : uchar const * salt = db + ps_sz + 1UL;
353 :
354 : /* H' = Hash( 0x00 x8 || mHash || salt ) */
355 0 : uchar m_prime[ 8UL + 2UL*FD_SHA512_HASH_SZ ];
356 0 : memset( m_prime, 0, 8UL );
357 0 : fd_rsa_hash( hash, msg, msg_sz, m_prime+8UL );
358 0 : memcpy( m_prime+8UL+h_sz, salt, s_sz );
359 0 : uchar h_prime[ FD_SHA512_HASH_SZ ];
360 0 : fd_rsa_hash( hash, m_prime, 8UL+h_sz+s_sz, h_prime );
361 :
362 0 : return fd_memeq( h_prime, h, h_sz ) ? FD_RSA_SUCCESS : FD_RSA_FAILURE;
363 0 : }
|
