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