Line data Source code
1 : #include "fd_keyguard.h"
2 : #include "../../ballet/shred/fd_shred.h"
3 : #include "../../ballet/txn/fd_compact_u16.h"
4 : #include "../../flamenco/gossip/fd_gossip_value.h"
5 : #include "../../disco/repair/fd_repair_serde.h"
6 :
7 : /* fd_keyguard_match fingerprints signing requests and checks them for
8 : ambiguity.
9 :
10 : Supported message types are as follows:
11 :
12 : - Legacy transaction messages
13 : - Version 0 transaction messages
14 : - Version 1 transaction messages
15 : - Legacy shred signed payloads
16 : - Merkle shred roots
17 : - TLS CertificateVerify challenges
18 : - Gossip message signed payloads (CrdsData)
19 :
20 : ### Fake Signing Attacks
21 :
22 : The main goal of fd_keyguard_match is to defeat "fake signing"
23 : attacks. These are attacks in which the keyguard signs a request for
24 : which the client is not authorized. Such attacks use a combination
25 : of vulnerabilities: Key reuse, and type confusion.
26 :
27 : Key reuse is particularly prevalent with the validator identity key,
28 : the hot Ed25519 key that a validator uses in almost all protocols
29 : that it actively participates in.
30 :
31 : Type confusion occurs when the message payload being signed can be
32 : interpreted as multiple different message types. Usually, this is
33 : categorically prevented by using "signing domains".
34 :
35 : Such attacks are particularly dangerous to validators because their
36 : validator identity key holds an amount of native tokens to
37 : participate in Tower BFT voting. In the worst case, an attacker
38 : could trick a validator into signing an innocuous message (e.g. a
39 : gossip message) that can also be interpreted as a transaction
40 : withdrawing these tokens.
41 :
42 : ### Code Verification
43 :
44 : The safety of this module can be verified using a number of CBMC
45 : proofs composed via deductive reasoning.
46 :
47 : - fd_txn_minsz_proof verifies the constant FD_TXN_MIN_SERIALIZED_SZ.
48 : - fd_txn_ambiguity_gossip_proof verifies that gossip messages cannot
49 : be parsed as transactions.
50 : - fd_keyguard_match_txn_harness verifies that the txn fingerprinting
51 : logic is free of false negatives.
52 : - fd_keyguard_ambiguity_proof verifies that any input up to 2048 byte
53 : size are unambiguous, i.e. either detected by one or none of the
54 : fingerprinting functions.
55 :
56 : Under the hood, CBMC executes the keyguard logic with all possible
57 : inputs (>=2^16384 unique inputs) via symbolic execution. The CBMC
58 : machine model also verifies that the code is free of common
59 : vulnerability classes (memory unsoundness, undefined behavior, …).
60 :
61 : As a result, we know with a high degree of certainty that type
62 : detection logic is free of false negatives. For example, when
63 : fd_keyguard_match sees a transaction, it will always reliably detect
64 : it as one. (fd_keyguard_match might also wrongly fingerprint
65 : arbitrary other inputs as, e.g. transactions. But this is not a
66 : problem, as strict checks follow later on in fd_keyguard_authorize.)
67 :
68 : ### Deployment Context
69 :
70 : fd_keyguard_match is exposed to untrusted "signing request" inputs
71 : and implements the first line of authorization checks in the
72 : keyguard. It is thus a critical component for securing the identity
73 : key.
74 :
75 : ### Implementation Approach
76 :
77 : This code looks awful and scary, but is carefully crafted to meet the
78 : aforementioned high assurance and formal verification requirements.
79 :
80 : Although parsers for the supported message types are available
81 : elsewhere in the codebase, they were not used here due to their time
82 : complexity exceeding the capabilities of CBMC. The time complexity
83 : of all parsers in this compile unit is O(1), which allowed for
84 : complete CBMC coverage.
85 :
86 : TLDR: The following code implements the least possible logic
87 : required to reliably detect types of identity key signing
88 : payloads without false negatives. */
89 :
90 : FD_FN_PURE static int
91 : fd_keyguard_payload_matches_txn_msg( uchar const * data,
92 : ulong sz,
93 7092 : int sign_type ) {
94 :
95 7092 : uchar const * end = data + sz;
96 :
97 7092 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
98 :
99 : /* txn_msg_min_sz is the smallest valid size of a transaction msg. A
100 : transaction is the concatenation of (signature count, signatures,
101 : msg). The smallest size of a txn is FD_TXN_MIN_SERIALIZED_SZ
102 : (formally proven with CBMC in fd_txn_minsz_proof.c). We know the
103 : smallest sizes of "signature count" and "signatures", thus we can
104 : derive the smallest size of "msg". */
105 :
106 6549 : ulong const txn_msg_min_sz =
107 6549 : FD_TXN_MIN_SERIALIZED_SZ
108 6549 : - 1UL /* min sz of signature count (compact_u16 encoding) */
109 6549 : - 64UL; /* min sz of signature list (array of Ed25519 sigs) */
110 6549 : if( sz<txn_msg_min_sz ) return 0;
111 :
112 : /* Message type check.
113 :
114 : Bit patterns of first bytes are as follows
115 :
116 : - 0aaaaaaa bbbbbbbb cccccccc (Legacy txns)
117 : - 10000000 aaaaaaaa bbbbbbbb cccccccc (v0 txns)
118 : - 10000001 aaaaaaaa bbbbbbbb cccccccc (v1 txns)
119 :
120 : Where 'a' are the bits that make up the 'required signature count'
121 : ... 'b' .... 'readonly signed count'
122 : ... 'c' .... 'readonly unsigned count' */
123 :
124 6507 : uchar const * cursor = data;
125 6507 : uint header_b0 = *cursor;
126 6507 : cursor++;
127 6507 : uint sig_cnt; /* sig count (ignoring compact_u16 encoding) */
128 6507 : if( header_b0 & 0x80UL ) {
129 : /* Versioned message, v0 and v1 recognized so far */
130 6453 : uint version = header_b0 & 0x7F;
131 6453 : if( version!=FD_TXN_V0 && version!=FD_TXN_V1 ) return 0;
132 :
133 : /* Check transaction V1 separately because the layout is
134 : different. We do the same checks for V1 and V0/legacy, just in
135 : a different code branch. */
136 6327 : if( version==FD_TXN_V1 ) {
137 6327 : sig_cnt = *cursor;
138 6327 : cursor++;
139 :
140 : /* There must be at least one signature. */
141 6327 : if( sig_cnt==0U ) return 0;
142 :
143 : /* Check if the signatures exceed the V1 limit */
144 6324 : if( sig_cnt>FD_TXN_SIG_MAX ) return 0;
145 :
146 : /* Skip other fields */
147 : //uint ro_signed_cnt = *cursor;
148 6324 : cursor++;
149 : //uint ro_unsigned_cnt = *cursor;
150 6324 : cursor++;
151 : //uint config_mask = fd_uint_load_4( cursor );
152 6324 : cursor += 4UL;
153 : //uchar const * blockhash = cursor;
154 6324 : cursor += FD_TXN_BLOCKHASH_SZ;
155 :
156 6324 : if( cursor + 2 > end ) return 0;
157 6324 : ulong instr_cnt = *cursor;
158 6324 : cursor++;
159 6324 : ulong addr_cnt = *cursor;
160 6324 : cursor++;
161 :
162 : /* Check if the instructions exceed the V1 limit */
163 6324 : if( instr_cnt>FD_TXN_INSTR_MAX ) return 0;
164 :
165 : /* Check if the addresses exceed the V1 limit */
166 6321 : if( addr_cnt>FD_TXN_ACCT_ADDR_MAX ) return 0;
167 :
168 6318 : if( sig_cnt>addr_cnt ) return 0;
169 :
170 6315 : return 1;
171 6318 : }
172 :
173 0 : sig_cnt = *cursor;
174 0 : cursor++;
175 54 : } else {
176 : /* Legacy message */
177 54 : sig_cnt = header_b0;
178 54 : }
179 :
180 : /* Legacy and v0 txns are at most FD_TXN_MTU_V0 bytes. */
181 54 : if( sz>FD_TXN_MTU_V0 ) return 0;
182 :
183 : /* There must be at least one signature. */
184 30 : if( sig_cnt==0U ) return 0;
185 :
186 : /* Check if signatures exceed txn size limit */
187 30 : ulong sig_sz;
188 30 : if( __builtin_umull_overflow( sig_cnt, 64UL, &sig_sz ) ) return 0;
189 30 : if( sig_sz > (FD_TXN_MTU_V0-txn_msg_min_sz) ) return 0;
190 :
191 : /* Skip other fields */
192 : //uint ro_signed_cnt = *cursor;
193 30 : cursor++;
194 : //uint ro_unsigned_cnt = *cursor;
195 30 : cursor++;
196 :
197 30 : if( cursor + 3 > end ) return 0;
198 30 : ulong addr_cnt_sz = fd_cu16_dec_sz( cursor, 3UL );
199 30 : if( !addr_cnt_sz ) return 0;
200 30 : ulong addr_cnt = fd_cu16_dec_fixed( cursor, addr_cnt_sz );
201 30 : cursor += addr_cnt_sz;
202 :
203 30 : if( sig_cnt>addr_cnt ) return 0;
204 :
205 18 : return 1;
206 30 : }
207 :
208 : FD_FN_PURE static int
209 : fd_keyguard_payload_matches_ping_msg( uchar const * data,
210 : ulong sz,
211 7092 : int sign_type ) {
212 7092 : return sign_type==FD_KEYGUARD_SIGN_TYPE_ED25519 &&
213 7092 : sz==32UL &&
214 7092 : (memcmp( data, "SOLANA_PING_PONG", 16UL ) == 0);
215 7092 : }
216 :
217 : FD_FN_PURE static int
218 : fd_keyguard_payload_matches_pong_msg( uchar const * data,
219 : ulong sz,
220 7092 : int sign_type ) {
221 7092 : return sign_type==FD_KEYGUARD_SIGN_TYPE_SHA256_ED25519 &&
222 7092 : sz==48UL &&
223 7092 : (memcmp( data, "SOLANA_PING_PONG", 16UL ) == 0);
224 7092 : }
225 :
226 : FD_FN_PURE static int
227 : fd_keyguard_payload_matches_prune_data( uchar const * data,
228 : ulong sz,
229 7092 : int sign_type ) {
230 7092 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
231 :
232 6549 : ulong const static_sz = 106UL;
233 6549 : if( sz < static_sz ) return 0;
234 6486 : if( sz > FD_GOSSIP_MTU ) return 0; /* prune messages fit in a gossip packet */
235 :
236 3210 : if( FD_LOAD( ulong, data )!=18UL ) return 0;
237 3 : if( memcmp( data+8UL, "\xffSOLANA_PRUNE_DATA", 18UL ) ) return 0;
238 :
239 3 : ulong prune_cnt = FD_LOAD( ulong, data+58UL );
240 3 : ulong expected_sz;
241 3 : if( __builtin_umull_overflow( prune_cnt, 32UL, &expected_sz ) ) return 0;
242 3 : if( __builtin_uaddl_overflow( expected_sz, static_sz, &expected_sz ) ) return 0;
243 3 : if( sz != expected_sz ) return 0;
244 :
245 3 : return 1;
246 3 : }
247 :
248 : FD_FN_PURE static int
249 : fd_keyguard_payload_matches_gossip( uchar const * data,
250 : ulong sz,
251 7092 : int sign_type ) {
252 :
253 : /* All gossip messages except pings use raw signing */
254 7092 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
255 :
256 : /* Every gossip message contains a 4 byte enum variant tag (at the
257 : beginning of the message) and a 32 byte public key (at an arbitrary
258 : location), and fits in a gossip packet. */
259 6549 : if( sz<36UL ) return 0;
260 6510 : if( sz>FD_GOSSIP_MTU ) return 0;
261 :
262 3234 : uint tag = FD_LOAD( uint, data );
263 :
264 3234 : return tag<FD_GOSSIP_VALUE_CNT;
265 6510 : }
266 :
267 : FD_FN_PURE static int
268 : fd_keyguard_payload_matches_repair( uchar const * data,
269 : ulong sz,
270 7092 : int sign_type ) {
271 :
272 : /* All repair messages except pings use raw signing */
273 7092 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
274 :
275 : /* Every repair message contains a 4 byte enum variant tag (at the
276 : beginning of the message) and a 32 byte public key (at an arbitrary
277 : location), and is at most FD_REPAIR_SIG_SER_MAX bytes. */
278 6549 : if( sz<36UL ) return 0;
279 6510 : if( sz>FD_REPAIR_SIG_SER_MAX ) return 0;
280 :
281 : /* Ensure that the kind matches a possible repair request. */
282 120 : uint kind = FD_LOAD( uint, data );
283 120 : if( (kind==FD_REPAIR_SERDE_TAG_WINDOW_INDEX)
284 120 : | (kind==FD_REPAIR_SERDE_TAG_HIGHEST_WINDOW_INDEX)
285 120 : | (kind==FD_REPAIR_SERDE_TAG_ORPHAN)
286 120 : | (kind==FD_REPAIR_SERDE_TAG_PARENT_AND_FEC_SET_COUNT)
287 120 : | (kind==FD_REPAIR_SERDE_TAG_FEC_SET_ROOT)
288 120 : | (kind==FD_REPAIR_SERDE_TAG_WINDOW_INDEX_FOR_BLOCK_ID) )
289 3 : return 1;
290 :
291 117 : return 0;
292 120 : }
293 :
294 : FD_FN_PURE int
295 : fd_keyguard_payload_matches_shred( uchar const * data,
296 : ulong sz,
297 7092 : int sign_type ) {
298 7092 : (void)data;
299 :
300 : /* Note: Legacy shreds no longer relevant (drop_legacy_shreds) */
301 :
302 : /* FIXME: Sign Merkle shreds using SIGN_TYPE_SHA256_ED25519 (!!!) */
303 7092 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
304 6549 : if( sz != 32 ) return 0;
305 :
306 33 : return 1;
307 6549 : }
308 :
309 : FD_FN_PURE int
310 : fd_keyguard_payload_matches_tls_cv( uchar const * data,
311 : ulong sz,
312 7092 : int sign_type ) {
313 :
314 7092 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
315 :
316 : /* TLS CertificateVerify signing payload one of 3 sizes
317 : depending on hash function chosen */
318 6549 : switch( sz ) {
319 0 : case 130UL: break; /* Prefix + 32 byte hash */
320 0 : case 146UL: break; /* Prefix + 48 byte hash */
321 0 : case 162UL: break; /* Prefix + 64 byte hash */
322 6549 : default:
323 6549 : return 0;
324 6549 : }
325 :
326 : /* Always prefixed with client or server pattern */
327 0 : static char const client_prefix[ 98 ] =
328 0 : " " /* 32 spaces */
329 0 : " " /* 32 spaces */
330 0 : "TLS 1.3, client CertificateVerify";
331 :
332 0 : static char const server_prefix[ 98 ] =
333 0 : " " /* 32 spaces */
334 0 : " " /* 32 spaces */
335 0 : "TLS 1.3, server CertificateVerify";
336 0 : int is_client = 0==memcmp( data, client_prefix, 98UL );
337 0 : int is_server = 0==memcmp( data, server_prefix, 98UL );
338 0 : return (is_client)|(is_server);
339 6549 : }
340 :
341 : FD_FN_PURE int
342 : fd_keyguard_payload_matches_ag_vote( uchar const * data,
343 : ulong sz,
344 7092 : int sign_type ) {
345 :
346 : /* Alpenglow vote payload produced by ag_vote_signing_ser:
347 :
348 : u8 tag (1..5, WireConsensusMessageKind vote tags)
349 : u64 slot
350 : [32 bytes block id] only for notar (1) and notar fallback (4)
351 : u16 shred_version */
352 :
353 7092 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_BLS ) return 0;
354 363 : if( sz!=11UL && sz!=43UL ) return 0;
355 357 : uchar tag = data[ 0 ];
356 357 : if( tag<1 || tag>5 ) return 0;
357 351 : int has_hash = ( tag==1 ) | ( tag==4 );
358 351 : return has_hash ? ( sz==43UL ) : ( sz==11UL );
359 357 : }
360 :
361 : FD_FN_PURE int
362 : fd_keyguard_payload_matches_bls_pubkey( uchar const * data FD_PARAM_UNUSED,
363 : ulong sz,
364 7092 : int sign_type ) {
365 :
366 : /* Alpenglow BLS public key query: u64 authority index. Its range is
367 : checked by fd_keyguard_authorize_bls_pubkey. */
368 :
369 7092 : return sign_type==FD_KEYGUARD_SIGN_TYPE_BLS_PUBKEY && sz==sizeof(ulong);
370 7092 : }
371 :
372 : FD_FN_PURE int
373 : fd_keyguard_payload_matches_bundle( uchar const * data,
374 : ulong sz,
375 7092 : int sign_type ) {
376 7092 : (void)data;
377 :
378 7092 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_PUBKEY_CONCAT_ED25519 ) return 0;
379 3 : if( sz!=9UL ) return 0;
380 :
381 0 : return 1;
382 3 : }
383 :
384 : FD_FN_PURE int
385 : fd_keyguard_payload_matches_event( uchar const * data,
386 : ulong sz,
387 7092 : int sign_type ) {
388 7092 : static char const sign_prefix[ 100 ] =
389 7092 : " " /* 32 spaces */
390 7092 : " " /* 32 spaces */
391 7092 : "Firedancer event challenge-response";
392 :
393 7092 : if( sz!=sizeof(sign_prefix)+217UL ) return 0;
394 0 : if( sign_type!=FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
395 0 : if( 0!=memcmp( data, sign_prefix, sizeof(sign_prefix) ) ) return 0;
396 0 : return 1;
397 0 : }
398 :
399 : /* Tower1_14_11: node_pubkey, threshold_depth, threshold_size, ... */
400 :
401 : FD_FN_PURE static int
402 : fd_keyguard_payload_matches_tower( uchar const * data,
403 : ulong sz,
404 7092 : int sign_type ) {
405 7092 : static uchar const zeros[ 65 ] = {0};
406 7092 : if( sign_type!=FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
407 6549 : if( sz<1807UL || sz>2522UL ) return 0; /* smallest and largest the tower tile writes */
408 1317 : if( FD_LOAD( ulong, data+32UL )!=8UL ) return 0; /* threshold_depth */
409 54 : if( FD_LOAD( ulong, data+40UL )!=0x3FE5555555555555UL ) return 0; /* threshold_size, 2/3 as f64 bits */
410 51 : if( memcmp( data+48UL, zeros, sizeof(zeros) ) ) return 0;
411 45 : ulong votes_cnt = FD_LOAD( ulong, data+113UL );
412 45 : return votes_cnt>=1UL && votes_cnt<=31UL;
413 51 : }
414 :
415 : /* VoteHistory, as the votor writes it: node_pubkey, nine empty
416 : collections, root */
417 :
418 : FD_FN_PURE static int
419 : fd_keyguard_payload_matches_vote_history( uchar const * data,
420 : ulong sz,
421 7092 : int sign_type ) {
422 7092 : if( sign_type!=FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
423 6549 : if( sz!=32UL+9UL*8UL+8UL ) return 0;
424 345 : for( ulong i=0UL; i<9UL; i++ ) if( FD_LOAD( ulong, data+32UL+i*8UL ) ) return 0;
425 21 : return 1;
426 48 : }
427 :
428 : FD_FN_PURE ulong
429 : fd_keyguard_payload_match( uchar const * data,
430 : ulong sz,
431 7092 : int sign_type ) {
432 7092 : ulong res = 0UL;
433 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_txn_msg ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_TXN, 0 );
434 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_gossip ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_GOSSIP, 0 );
435 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_repair ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_REPAIR, 0 );
436 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_prune_data ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_PRUNE, 0 );
437 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_shred ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_SHRED, 0 );
438 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_tls_cv ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_TLS_CV, 0 );
439 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_ping_msg ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_PING, 0 );
440 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_pong_msg ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_PONG, 0 );
441 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_bundle ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_BUNDLE, 0 );
442 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_event ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_EVENT, 0 );
443 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_ag_vote ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_AG_VOTE, 0 );
444 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_bls_pubkey ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_BLS_PUBKEY, 0 );
445 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_tower ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_TOWER, 0 );
446 7092 : res |= fd_ulong_if( fd_keyguard_payload_matches_vote_history( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_VOTE_HISTORY, 0 );
447 7092 : return res;
448 7092 : }
|
