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 "../../discof/repair/fd_repair.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 : - Legacy shred signed payloads
15 : - Merkle shred roots
16 : - TLS CertificateVerify challenges
17 : - Gossip message signed payloads (CrdsData)
18 :
19 : ### Fake Signing Attacks
20 :
21 : The main goal of fd_keyguard_match is to defeat "fake signing"
22 : attacks. These are attacks in which the keyguard signs a request for
23 : which the client is not authorized. Such attacks use a combination
24 : of vulnerabilities: Key reuse, and type confusion.
25 :
26 : Key reuse is particularly prevalent with the validator identity key,
27 : the hot Ed25519 key that a validator uses in almost all protocols
28 : that it actively participates in.
29 :
30 : Type confusion occurs when the message payload being signed can be
31 : interpreted as multiple different message types. Usually, this is
32 : categorically prevented by using "signing domains".
33 :
34 : Such attacks are particularly dangerous to validators because their
35 : validator identity key holds an amount of native tokens to
36 : participate in Tower BFT voting. In the worst case, an attacker
37 : could trick a validator into signing an innocuous message (e.g. a
38 : gossip message) that can also be interpreted as a transaction
39 : withdrawing these tokens.
40 :
41 : ### Code Verification
42 :
43 : The safety of this module can be verified using a number of CBMC
44 : proofs composed via deductive reasoning.
45 :
46 : - fd_txn_minsz_proof verifies the constant FD_TXN_MIN_SERIALIZED_SZ.
47 : - fd_txn_ambiguity_gossip_proof verifies that gossip messages cannot
48 : be parsed as transactions.
49 : - fd_keyguard_match_txn_harness verifies that the txn fingerprinting
50 : logic is free of false negatives.
51 : - fd_keyguard_ambiguity_proof verifies that any input up to 2048 byte
52 : size are unambiguous, i.e. either detected by one or none of the
53 : fingerprinting functions.
54 :
55 : Under the hood, CBMC executes the keyguard logic with all possible
56 : inputs (>=2^16384 unique inputs) via symbolic execution. The CBMC
57 : machine model also verifies that the code is free of common
58 : vulnerability classes (memory unsoundness, undefined behavior, …).
59 :
60 : As a result, we know with a high degree of certainty that type
61 : detection logic is free of false negatives. For example, when
62 : fd_keyguard_match sees a transaction, it will always reliably detect
63 : it as one. (fd_keyguard_match might also wrongly fingerprint
64 : arbitrary other inputs as, e.g. transactions. But this is not a
65 : problem, as strict checks follow later on in fd_keyguard_authorize.)
66 :
67 : ### Deployment Context
68 :
69 : fd_keyguard_match is exposed to untrusted "signing request" inputs
70 : and implements the first line of authorization checks in the
71 : keyguard. It is thus a critical component for securing the identity
72 : key.
73 :
74 : ### Implementation Approach
75 :
76 : This code looks awful and scary, but is carefully crafted to meet the
77 : aforementioned high assurance and formal verification requirements.
78 :
79 : Although parsers for the supported message types are available
80 : elsewhere in the codebase, they were not used here due to their time
81 : complexity exceeding the capabilities of CBMC. The time complexity
82 : of all parsers in this compile unit is O(1), which allowed for
83 : complete CBMC coverage.
84 :
85 : TLDR: The following code implements the least possible logic
86 : required to reliably detect types of identity key signing
87 : payloads without false negatives. */
88 :
89 : FD_FN_PURE static int
90 : fd_keyguard_payload_matches_txn_msg( uchar const * data,
91 : ulong sz,
92 0 : int sign_type ) {
93 :
94 0 : uchar const * end = data + sz;
95 :
96 0 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
97 :
98 : /* txn_msg_min_sz is the smallest valid size of a transaction msg. A
99 : transaction is the concatenation of (signature count, signatures,
100 : msg). The smallest size of a txn is FD_TXN_MIN_SERIALIZED_SZ
101 : (formally proven with CBMC in fd_txn_minsz_proof.c). We know the
102 : smallest sizes of "signature count" and "signatures", thus we can
103 : derive the smallest size of "msg". */
104 :
105 0 : ulong const txn_msg_min_sz =
106 0 : FD_TXN_MIN_SERIALIZED_SZ
107 0 : - 1UL /* min sz of signature count (compact_u16 encoding) */
108 0 : - 64UL; /* min sz of signature list (array of Ed25519 sigs) */
109 0 : if( sz<txn_msg_min_sz ) return 0;
110 :
111 : /* Message type check.
112 :
113 : Bit patterns of first bytes are as follows
114 :
115 : - 0aaaaaaa bbbbbbbb cccccccc (Legacy txns)
116 : - 10000000 aaaaaaaa bbbbbbbb cccccccc (v0 txns)
117 :
118 : Where 'a' are the bits that make up the 'required signature count'
119 : ... 'b' .... 'readonly signed count'
120 : ... 'c' .... 'readonly unsigned count' */
121 :
122 0 : uchar const * cursor = data;
123 0 : uint header_b0 = *cursor;
124 0 : cursor++;
125 0 : uint sig_cnt; /* sig count (ignoring compact_u16 encoding) */
126 0 : if( header_b0 & 0x80UL ) {
127 : /* Versioned message, only v0 recognized so far */
128 0 : if( (header_b0&0x7F)!=FD_TXN_V0 ) return 0;
129 0 : sig_cnt = *cursor;
130 0 : cursor++;
131 0 : } else {
132 : /* Legacy message */
133 0 : sig_cnt = header_b0;
134 0 : }
135 :
136 : /* There must be at least one signature. */
137 0 : if( sig_cnt==0U ) return 0;
138 :
139 : /* Check if signatures exceed txn size limit */
140 0 : ulong sig_sz;
141 0 : if( __builtin_umull_overflow( sig_cnt, 64UL, &sig_sz ) ) return 0;
142 0 : if( sig_sz > (FD_TXN_MTU-txn_msg_min_sz) ) return 0;
143 :
144 : /* Skip other fields */
145 : //uint ro_signed_cnt = *cursor;
146 0 : cursor++;
147 : //uint ro_unsigned_cnt = *cursor;
148 0 : cursor++;
149 :
150 0 : if( cursor + 3 > end ) return 0;
151 0 : ulong addr_cnt_sz = fd_cu16_dec_sz( cursor, 3UL );
152 0 : if( !addr_cnt_sz ) return 0;
153 0 : ulong addr_cnt = fd_cu16_dec_fixed( cursor, addr_cnt_sz );
154 0 : cursor += addr_cnt_sz;
155 :
156 0 : if( sig_cnt>addr_cnt ) return 0;
157 :
158 0 : return 1;
159 0 : }
160 :
161 : FD_FN_PURE static int
162 : fd_keyguard_payload_matches_ping_msg( uchar const * data,
163 : ulong sz,
164 0 : int sign_type ) {
165 0 : return sign_type==FD_KEYGUARD_SIGN_TYPE_ED25519 &&
166 0 : sz==32UL &&
167 0 : (memcmp( data, "SOLANA_PING_PONG", 16UL ) == 0);
168 0 : }
169 :
170 : FD_FN_PURE static int
171 : fd_keyguard_payload_matches_pong_msg( uchar const * data,
172 : ulong sz,
173 0 : int sign_type ) {
174 0 : return sign_type==FD_KEYGUARD_SIGN_TYPE_SHA256_ED25519 &&
175 0 : sz==48UL &&
176 0 : (memcmp( data, "SOLANA_PING_PONG", 16UL ) == 0);
177 0 : }
178 :
179 : FD_FN_PURE static int
180 : fd_keyguard_payload_matches_prune_data( uchar const * data,
181 : ulong sz,
182 0 : int sign_type ) {
183 0 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
184 :
185 0 : ulong const static_sz = 106UL;
186 0 : if( sz < static_sz ) return 0;
187 :
188 0 : if( FD_LOAD( ulong, data )!=18UL ) return 0;
189 0 : if( memcmp( data+8UL, "\xffSOLANA_PRUNE_DATA", 18UL ) ) return 0;
190 :
191 0 : ulong prune_cnt = FD_LOAD( ulong, data+58UL );
192 0 : ulong expected_sz;
193 0 : if( __builtin_umull_overflow( prune_cnt, 32UL, &expected_sz ) ) return 0;
194 0 : if( __builtin_uaddl_overflow( expected_sz, static_sz, &expected_sz ) ) return 0;
195 0 : if( sz != expected_sz ) return 0;
196 :
197 0 : return 1;
198 0 : }
199 :
200 : FD_FN_PURE static int
201 : fd_keyguard_payload_matches_gossip( uchar const * data,
202 : ulong sz,
203 0 : int sign_type ) {
204 :
205 : /* All gossip messages except pings use raw signing */
206 0 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
207 :
208 : /* Every gossip message contains a 4 byte enum variant tag (at the
209 : beginning of the message) and a 32 byte public key (at an arbitrary
210 : location). */
211 0 : if( sz<36UL ) return 0;
212 :
213 0 : uint tag = FD_LOAD( uint, data );
214 :
215 0 : return tag<FD_GOSSIP_VALUE_CNT;
216 0 : }
217 :
218 : FD_FN_PURE static int
219 : fd_keyguard_payload_matches_repair( uchar const * data,
220 : ulong sz,
221 0 : int sign_type ) {
222 :
223 : /* All repair messages except pings use raw signing */
224 0 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
225 :
226 : /* Every repair message contains a 4 byte enum variant tag (at the
227 : beginning of the message) and a 32 byte public key (at an arbitrary
228 : location). */
229 0 : if( sz<36UL ) return 0;
230 :
231 : /* Ensure that the kind matches a possible repair request. */
232 0 : uint kind = FD_LOAD( uint, data );
233 0 : if( (kind==FD_REPAIR_KIND_SHRED)
234 0 : | (kind==FD_REPAIR_KIND_HIGHEST_SHRED)
235 0 : | (kind==FD_REPAIR_KIND_ORPHAN) )
236 0 : return 1;
237 :
238 0 : return 0;
239 0 : }
240 :
241 : FD_FN_PURE int
242 : fd_keyguard_payload_matches_shred( uchar const * data,
243 : ulong sz,
244 0 : int sign_type ) {
245 0 : (void)data;
246 :
247 : /* Note: Legacy shreds no longer relevant (drop_legacy_shreds) */
248 :
249 : /* FIXME: Sign Merkle shreds using SIGN_TYPE_SHA256_ED25519 (!!!) */
250 0 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
251 0 : if( sz != 32 ) return 0;
252 :
253 0 : return 1;
254 0 : }
255 :
256 : FD_FN_PURE int
257 : fd_keyguard_payload_matches_tls_cv( uchar const * data,
258 : ulong sz,
259 0 : int sign_type ) {
260 :
261 0 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_ED25519 ) return 0;
262 :
263 : /* TLS CertificateVerify signing payload one of 3 sizes
264 : depending on hash function chosen */
265 0 : switch( sz ) {
266 0 : case 130UL: break; /* Prefix + 32 byte hash */
267 0 : case 146UL: break; /* Prefix + 48 byte hash */
268 0 : case 162UL: break; /* Prefix + 64 byte hash */
269 0 : default:
270 0 : return 0;
271 0 : }
272 :
273 : /* Always prefixed with client or server pattern */
274 0 : static char const client_prefix[ 98 ] =
275 0 : " " /* 32 spaces */
276 0 : " " /* 32 spaces */
277 0 : "TLS 1.3, client CertificateVerify";
278 :
279 0 : static char const server_prefix[ 98 ] =
280 0 : " " /* 32 spaces */
281 0 : " " /* 32 spaces */
282 0 : "TLS 1.3, server CertificateVerify";
283 0 : int is_client = 0==memcmp( data, client_prefix, 98UL );
284 0 : int is_server = 0==memcmp( data, server_prefix, 98UL );
285 0 : return (is_client)|(is_server);
286 0 : }
287 :
288 : FD_FN_PURE int
289 : fd_keyguard_payload_matches_bundle( uchar const * data,
290 : ulong sz,
291 0 : int sign_type ) {
292 0 : (void)data;
293 :
294 0 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_PUBKEY_CONCAT_ED25519 ) return 0;
295 0 : if( sz!=9UL ) return 0;
296 :
297 0 : return 1;
298 0 : }
299 :
300 : FD_FN_PURE int
301 : fd_keyguard_payload_matches_event( uchar const * data,
302 : ulong sz,
303 0 : int sign_type ) {
304 0 : (void)data;
305 :
306 0 : if( sign_type != FD_KEYGUARD_SIGN_TYPE_FD_EVENTS_AUTH_CONCAT_ED25519 ) return 0;
307 0 : if( sz!=32UL ) return 0;
308 :
309 0 : return 1;
310 0 : }
311 :
312 : FD_FN_PURE ulong
313 : fd_keyguard_payload_match( uchar const * data,
314 : ulong sz,
315 0 : int sign_type ) {
316 0 : ulong res = 0UL;
317 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_txn_msg ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_TXN, 0 );
318 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_gossip ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_GOSSIP, 0 );
319 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_repair ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_REPAIR, 0 );
320 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_prune_data( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_PRUNE, 0 );
321 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_shred ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_SHRED, 0 );
322 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_tls_cv ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_TLS_CV, 0 );
323 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_ping_msg ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_PING, 0 );
324 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_pong_msg ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_PONG, 0 );
325 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_bundle ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_BUNDLE, 0 );
326 0 : res |= fd_ulong_if( fd_keyguard_payload_matches_event ( data, sz, sign_type ), FD_KEYGUARD_PAYLOAD_EVENT, 0 );
327 0 : return res;
328 0 : }
|
