LCOV - code coverage report
Current view: top level - disco/keyguard - fd_keyguard_match.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 0 121 0.0 %
Date: 2025-03-20 12:08:36 Functions: 0 10 0.0 %

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

Generated by: LCOV version 1.14