4_3_implementation.tex (21745B)
1 \chapter{Implementation} 2 \label{chap:implement} 3 This chapter gives an overview on the implementation challenges and discusses special parts in the implementation. 4 5 6 \section{Signature Scheme Operations} 7 The signature scheme operations are implemented in the GNUnet core repository \cite{gnunet-git} (and have been merged into the master branch). 8 This would allow other GNUnet projects to use our implementation of the Clause Blind Schnorr Signature Scheme. 9 10 The implementation is done in multiple locations: 11 \begin{itemize} 12 \item \texttt{src/include/gnunet\_crypto\_lib.h}: 13 This header file is included when using GNUnet's cryptography implementation. 14 \item \texttt{src/util/crypto\_cs.c}: 15 The functions specified in \texttt{gnunet\_crypto\_lib.h} will be implemented here. 16 \item \texttt{src/util/test\_crypto\_cs.c}: 17 The test cases for the signature scheme will be implemented here. 18 \item \texttt{src/util/perf\_crypto\_cs.c}: 19 This file houses the implementation of a small program that will be used to compare the performance against the blind RSA Signature Scheme. 20 \end{itemize} 21 22 The specification explaining the \ac{API} can be found in section \ref{sec:specification-signature-scheme}. There are two internal functions that have to be explained further in this section. 23 24 The \texttt{map\_to\_scalar\_subgroup} function clamps scalars, which is necessary for values that are derived using a \gls{hkdf}. 25 It sets the three least significant bits to zero (making the scalar a multiple of 8), sets the most significant bit to zero and the second-most significant bit to one. 26 This process is further described in \cite{rfc7748} and \cite{madden:curve25519-clamping}. 27 28 \begin{lstlisting}[style=bfh-c, language=C, caption={Function map\_to\_scalar\_subgroup - Crypto API}, label={lst:map-to-scalar}] 29 static void 30 map_to_scalar_subgroup (struct GNUNET_CRYPTO_Cs25519Scalar *scalar) 31 { 32 scalar->d[0] &= 248; 33 scalar->d[31] &= 127; 34 scalar->d[31] |= 64; 35 } 36 \end{lstlisting} 37 38 Another important function is the \gls{fdh} (see \ref{sec:schnorr-sig}) used to map the message to a scalar. 39 GNUnet provides a \gls{fdh} function, which expects libgcrypt's multi precision format. 40 A conversion function is provided by GNUnet, which requires the data to be in big endian format. 41 Since libsodium uses a little endian representation, the conversion process must include endianness conversion. 42 The complete \gls{fdh} including the required conversions is implemented in the function described in listing \ref{lst:cs-fdh}. 43 \begin{lstlisting}[style=bfh-c, language=C, caption={Function cs\_full\_domain\_hash - Crypto API}, label={lst:cs-fdh}] 44 static void 45 cs_full_domain_hash (const struct GNUNET_CRYPTO_CsRPublic *r_dash, 46 const void *msg, 47 size_t msg_len, 48 const struct GNUNET_CRYPTO_CsPublicKey *pub, 49 struct GNUNET_CRYPTO_CsC *c) 50 { 51 ... 52 \end{lstlisting} 53 54 Last but not least, the implementation has one notable performance improvement not mentioned in the redesigned protocols. 55 In various steps \gls{hkdf} is used multiple times in a row. 56 For example to derive the four blinding secrets $\alpha_0, \alpha_1, \beta_0, \beta_1$. 57 The derivation can be done in one \gls{hkdf} call with bigger output size, 128 bit in this case. 58 The output then can be split in four parts and then mapped to the ed25519 subgroup. 59 This can be done secure, because as explained in \autoref{sec:kdf} a \gls{hkdf} output is truly random. 60 61 62 \section{Taler Cryptographic Utilities} 63 \begin{bfhNoteBox} 64 Implementation is done in Taler's exchange. 65 From here on the implementation can be found in the exchange git repository \cite{taler-git:exchange}. 66 \end{bfhNoteBox} 67 The cryptographic utilities of Taler can be found in \texttt{src/util}. 68 69 70 The implementation is done in various locations: 71 \begin{itemize} 72 \item \texttt{src/include/taler\_crypto\_lib.h}: This header file is included when using Taler's cryptography implementation. 73 The different data structures and functionality are defined here. 74 \item \texttt{src/util/denom.c}: Implement denomination utility functions for \gls{CSBS} cases 75 \item \texttt{src/util/crypto.c}: Adjust all utility functions to support \gls{CSBS}. 76 crypto.c contains many cryptographic utility functions, for example to create planchets or blinding factors. 77 \item \texttt{src/util/test\_crypto.c}: Functionality tests for crypto.c and denom.c 78 \item \texttt{src/include/taler\_signatures.h}: In this header file message formats and signature constants are defined (not modified) 79 \item \texttt{src/util/secmod\_signatures.c}: Utility functions for Taler security module signatures 80 \end{itemize} 81 82 The security module \texttt{taler-secmod-cs} is implemented here: 83 \begin{itemize} 84 \item \texttt{src/util/taler-exchange-secmod-cs.c}: Standalone process to perform private key Clause Blind Schnorr signature operations. 85 \item \texttt{src/util/taler-exchange-secmod-cs.h}: Specification of \ac{IPC} messages for the CS secmod process 86 \item \texttt{src/util/taler-exchange-secmod-cs.conf}: Configuration file for the secmod process 87 \item \texttt{src/util/secmod\_common.c} and \texttt{src/util/secmod\_common.h}: Common functions for the exchange's security modules (not modified) 88 \end{itemize} 89 90 The corresponding crypto helper, that talks with the security module, and its tests \& benchmarks are implemented here: 91 \begin{itemize} 92 \item \texttt{src/util/crypto\_helper\_cs.c}: Utility functions to communicate with the security module 93 \item \texttt{src/util/crypto\_helper\_common.c}: and \texttt{crypto\_helper\_common.h}: Common functions for the exchange security modules (not modified) 94 \item \texttt{src/util/test\_helper\_cs.c}: Tests and benchmarks for the \gls{CSBS} crypto helper 95 \end{itemize} 96 % Crypto API offene Punkte: 97 %Input-validation of points and scalars: 98 % describe clamping: https://neilmadden.blog/2020/05/28/whats-the-curve25519-clamping-all-about/ 99 % Testing: inverse operations, blinded signature test 100 101 102 \section{Denomination Key Management} 103 For the implementation, the \gls{CSBS} security module had to be connected to the key handling and the \gls{CSBS} denominations had to be integrated: 104 \begin{itemize} 105 \item \url{src/exchange/taler-exchange-httpd_keys.h} and \\ 106 \url{src/exchange/taler-exchange-httpd_keys.c}: Integrate \gls{CSBS} secmod and denomination key management 107 \item \url{src/exchange-tools/taler-exchange-offline.c}: Implement \gls{CSBS} case for offline signing of denomination keys 108 \item \url{src/include/taler_exchange_service.h}: \\ 109 Add \gls{CSBS} secmod public key to struct\\TALER\_EXCHANGE\_FutureKeys 110 \item \url{src/json/json_helper.c}: Implement CS case in function parse\_denom\_pub (used in taler-exchange-offline.c) 111 \item \url{src/json/json_pack.c}: Implement \gls{CSBS} case in function TALER\_JSON\_pack\_denom\_pub (used in taler-exchange-httpd\_keys.c) 112 \item \url{src/pq/pq_query_helper.c}: Implement \gls{CSBS} case in function qconv\_denom\_pub 113 \item \url{src/pq/pq_result_helper.c}: Implement \gls{CSBS} case in function extract\_denom\_pub 114 \end{itemize} 115 116 In order for the tests to pass, the following changes had to be implemented: 117 \begin{itemize} 118 \item \url{src/lib/exchange_api_management_get_keys.c}: Add denom\_secmod\_cs\_public\_key JSON parsing, implement \gls{CSBS} case \\in function TALER\_EXCHANGE\_ManagementGetKeysHandle 119 \item \url{src/testing/.gitignore}: Add paths where \gls{CSBS} keys are stored (secmod-helper) 120 \item \url{src/testing/test_auditor_api.conf}: Add section taler-exchange-secmod-cs 121 \item \url{src/testing/test_exchange_api_keys_cherry_picking.conf}: Add section taler-exchange-secmod-cs 122 \item \url{src/testing/testing_api_helpers_exchange.c}: Add \gls{CSBS} secmod start and stop logic 123 \end{itemize} 124 125 126 \section{New Endpoint for $R$} 127 The new endpoint is available in the exchange's HTTP server under \url{/csr}. 128 It parses and checks the input, passes the request for derivation of the two $ R $'s down to the \gls{CSBS} security module and returns them to the requestor. 129 The implementation can be found in: 130 \begin{itemize} 131 \item \url{src/exchange/taler-exchange-httpd.c}: 132 Definition for the new endpoint, calls the function that handles \url{/csr} requests 133 \item \url{src/exchange/taler-exchange-httpd_responses.h} and \\ 134 \url{src/exchange/taler-exchange-httpd_responses.c}: \\ 135 Added function TEH\_RESPONSE\_reply\_invalid\_denom\_cipher\_for\_operation that indicates a failure when the endpoint is called for a non-\gls{CSBS} denomination 136 \item \url{src/exchange/taler-exchange-httpd_csr.h} and \\ 137 \url{src/exchange/taler-exchange-httpd_csr.c}: \\ 138 Implementation of the request handler for the new endpoint 139 \item \url{src/exchange/taler-exchange-httpd_keys.h} and \\ 140 \url{src/exchange/taler-exchange-httpd_keys.c}: \\ 141 Additional function TEH\_keys\_denomination\_cs\_r\_pub that passes down the request to derive the $ R $ to the taler-exchange-secmod-cs helper 142 \end{itemize} 143 144 The tests that check the functionality of the procotols are defined in \url{src/testing/} and use code that calls the \ac{API} (located in \url{src/lib/}). 145 Since the new endpoint is used during withdrawing coins, testing for the \url{/csr} endpoint is integrated in these protocol tests. 146 Therefore, a call to the endpoint was implemented and later integrated into the calls to the withdraw-\ac{API}. 147 Code for calling the endpoint is located in these files: 148 \begin{itemize} 149 \item \url{src/include/taler_exchange_service.h}: \\ 150 Header describing functions and data structures used in withdraw and refresh testing: 151 \begin{itemize} 152 \item struct TALER\_EXCHANGE\_CsRHandle: Handle containing request information 153 \item struct TALER\_EXCHANGE\_CsRResponse: Response details 154 \item function TALER\_EXCHANGE\_CsRCallback: Callback function to deliver the results (used in withdraw and refresh) 155 \item function TALER\_EXCHANGE\_csr: Used to call endpoint 156 \item function TALER\_EXCHANGE\_csr\_cancel: Used to free dynamically allocated resources 157 \end{itemize} 158 \item \url{src/lib/exchange_api_csr.c}: Implementation of \url{/csr} request 159 \end{itemize} 160 161 162 \section{Withdraw Protocol} 163 \label{sec:withdraw-protocol-impl} 164 Since this is an existing endpoint, it was adjusted to support \gls{CSBS}. 165 Mainly, the in- and output-handling had to be adjusted as described in section \ref{sec:specification-withdraw-public-api}, additional cipher checks for the denomination were added and the \gls{CSBS} for persisting the request in the database was implemented. 166 \\\\ 167 An interesting part of the implementation is the check whether a nonce was already used for this denomination or not (step: $s \leftarrow \text{GetWithdraw}(n_w, D_p)$). 168 This step ensures that the same signature will always be returned for a certain nonce. 169 Using the same nonce for the same denomination twice without this check would lead to the same random value $r$. 170 This is due to derivation of $r := \text{HKDF}(256,n_w || d_s, \text{"r"})$. 171 An attacker could then immediately recover the secret key by the following equation: $(h' - h) * x \mod q = s -s' \mod q$ \cite{tibouchi:attacks-schnorr-nonce}. 172 There are popular examples of this vulnerability in Sony Playstation 3's or Bitcoins ECDSA implementation \cite{buchanan:ps3-ecdsa-vuln} \cite{wang:bitcoin-ecdsa-vuln}. 173 More details on how such a vulnerability can be exploited can be found in one of the author's blog posts \cite{gian:nonce-sense}.\\ 174 The designed Taler protocols using \gls{CSBS} are preventing this attack by checking the nonce and return the previously generated signature. 175 Additionally the denomination's public key is included in this check to prevent another issue explained in section \ref{sec:taler-vuln}.\\ 176 The check is implemented by persisting a hash value over $n_w$ and $D_p$. 177 On every withdrawal \texttt{check\_request\_idempotent()} is called, which checks whether the persisted hash matches with the current $n_w, D_p$ pair. 178 179 180 \begin{itemize} 181 \item \url{src/exchange/taler-exchange-httpd_withdraw.c}: Implementation of \gls{CSBS} case for withdraw endpoint 182 \item \url{src/exchange/taler-exchange-httpd_keys.c}: Implement \gls{CSBS} case in function \\ 183 TEH\_keys\_denomination\_sign (passes the signature creation down to the crypto helpers) 184 \item \url{src/include/taler_json_lib.h} and \url{src/json/json_helper.c}: \\ 185 Add function TALER\_JSON\_spec\_blinded\_planchet 186 \item \url{src/json/json_pack.c}: \\ 187 Implement \gls{CSBS} case in function\\ TALER\_JSON\_pack\_blinded\_denom\_sig 188 \item \url{src/pq/pq_query_helper.c}: implement \gls{CSBS} case in functions qconv\_denom\_sig and qconv\_blinded\_denom\_sig 189 \item \url{src/pq/pq_result_helper.c}: Implement \gls{CSBS} case in function extract\_blinded\_denom\_sig 190 \end{itemize} 191 192 For testing, the \gls{CSBS}-related data structures and procedures as well as the request to the additional endpoint \url{/csr} (before performing the actual withdrawal) were integrated: 193 \begin{itemize} 194 \item \url{src/testing/test_exchange_api.c}: Add additional tests for \gls{CSBS} withdraw 195 \item \url{src/include/taler_testing_lib.h}: Specification for functions \\ 196 TALER\_TESTING\_cmd\_withdraw\_cs\_amount and \\ 197 TALER\_TESTING\_cmd\_withdraw\_cs\_amount\_reuse\_key, add denomination cipher parameter to function TALER\_TESTING\_find\_pk 198 \item \url{src/testing/testing_api_cmd_withdraw.c}: add functions \\ 199 TALER\_TESTING\_cmd\_withdraw\_cs\_amount and \\ 200 TALER\_TESTING\_cmd\_withdraw\_cs\_amount\_reuse\_key, implement \gls{CSBS}-specific logic for withdraw 201 \item \url{src/testing/testing_api_helpers_exchange.c}: 202 add cipher parameter to function TALER\_TESTING\_find\_pk 203 \item \url{src/lib/exchange_api_withdraw.c}: Implement \gls{CSBS}-specific withdraw logic, integrate \url{/csr} request 204 \item \url{src/lib/exchange_api_withdraw2.c}: implement \gls{CSBS} case 205 \item \url{src/include/taler_json_lib.h} and \url{src/json/json_pack.c}: \\ 206 Add function TALER\_JSON\_pack\_blinded\_planchet 207 \item \url{src/json/json_helper.c} implement \gls{CSBS} case in function parse\_blinded\_denom\_sig 208 \end{itemize} 209 210 \section{Deposit Protocol} 211 For deposit, only few changes were necessary because some of the required functionality has already been added for the previously implemented protocols, and only the coin signature verification is \gls{CSBS}-specific in this protocol. 212 \begin{itemize} 213 \item \url{/src/exchange/taler-exchange-httpd_deposit.c}: Add check whether denomination cipher and denomination signature cipher are equal 214 \item \url{/src/json/json_helper.c}: Implement \gls{CSBS} case in function parse\_denom\_sig 215 \item \url{/src/pq/pq_result_helper.c}: Implement \gls{CSBS} case in function extract\_denom\_sig 216 \end{itemize} 217 218 Tests for deposit are implemented here: 219 \begin{itemize} 220 \item \url{/src/testing/test_exchange_api.c}: Add tests (see "struct TALER\_TESTING\_Command\ spend\_cs[]") that spend \gls{CSBS} coins withdrawn in tests added for withdrawal 221 \item \url{/src/json/json_pack.c}: Implement \gls{CSBS} case in function TALER\_JSON\_pack\_denom\_sig 222 \end{itemize} 223 224 \section{Fixing a Minor Security Issue in Taler's RSA Blind Signature Protocols} 225 \label{sec:taler-vuln} 226 While implementing the nonce check in the \gls{CSBS} protocol (see section \ref{sec:withdraw-protocol-impl}), a minor security issue in Taler's current RSA Blind Signature implementation was detected and fixed. 227 The issue was only in the implementation of the current RSA Blind Signature protocols, the fix for this scenario was already implemented in \gls{CSBS} since the beginning. 228 229 \subsection{Security Issue} 230 \label{sec:taler-vuln-desc} 231 232 The redesigned \gls{CSBS} protocols already include the denomination key in the nonce check, which fixes this issue (see \ref{sec:withdraw-protocol-schnorr}). 233 In the case of \gls{RSABS}, the current protocol includes an \gls{idempotence} check by persisting the hash value of the blinded coin $m'$. 234 On a withdrawal/refresh the \gls{idempotence} check compares if the hash value of $m'$ was seen in the past and returns the 'old' signature on a match. 235 This could lead to the following scenario: 236 237 \begin{enumerate} 238 \item A broken wallet withdraws a coin with denomination $D_{p_{(1)}}$. 239 \item The wallet sends a request to withdraw the same coin for denomination $D_{p_{(2)}}$. 240 \item The exchange returns the signature for the denomination $D_{p_{(1)}}$ due to the \gls{idempotence} check. 241 \item Since the exchange returned an invalid signature, the customer can file a complaint at the auditor. 242 \item The auditor then has to investigate why the exchange returned invalid signatures. 243 \item The auditor can disprove the complaint by querying the persisted hash used for the \gls{idempotence} check. 244 With the associated denomination public key that is also persisted, the auditor can successfully verify the signature and thus prove that the exchange operated honestly. 245 \end{enumerate} 246 247 Including the denomination public key into the persisted hash for the \gls{idempotence} check solves this issue. 248 If a broken wallet now sends the same coin for more than one denomination, the exchange returns valid signatures in both cases.\\ 249 While this is still an issue, this case is already handled nicely in Taler since this situation could also occur if a broken value tries to withdraw the same coin with two different blinding factors. 250 251 \subsection{Impact} 252 The impact of this security vulnerability is considered as very low. 253 An auditor investigating such an issue can simply retrace what happened by checking the persisted hash and associated denomination. 254 The impact of the issue is, that an auditor needs to investigate an issue, which can be prevented inside the protocol. 255 \\ 256 In the previous section the client was considered a broken wallet. 257 While this could be done on purpose by malicious a customer, there is no real motivation for abusing this issue due the easy detection of an auditor. 258 259 260 \subsection{Fix} 261 Listing \ref{lst:rsa-idempotence} shows the code of calculating the hash for the idempotency check in the RSA case before it was fixed. 262 By trying to implement the \gls{CSBS} case, the question came up why the RSA case has not included the denomination key into the check. 263 After discussing this issue with Christian Grothoff, the conclusion was to include the denomination public key to prevent the discussed issue. 264 265 \begin{lstlisting}[style=bfh-c,language=C, caption={Idempotency check on RSA}, label={lst:rsa-idempotence}] 266 enum GNUNET_GenericReturnValue 267 TALER_coin_ev_hash (const struct TALER_BlindedPlanchet *blinded_planchet, 268 struct TALER_BlindedCoinHash *bch) 269 { 270 switch (blinded_planchet->cipher) 271 { 272 case TALER_DENOMINATION_RSA: 273 GNUNET_CRYPTO_hash ( 274 blinded_planchet->details.rsa_blinded_planchet.blinded_msg, 275 blinded_planchet->details.rsa_blinded_planchet.blinded_msg_size, 276 &bch->hash); 277 return GNUNET_OK; 278 case TALER_DENOMINATION_CS: 279 ... 280 281 \end{lstlisting} 282 283 The issue is fixed by adding a hash of the current denomination key into the calculation of the hash used in the \gls{idempotence} check. 284 The applied fix can be seen in listing \ref{lst:fixed-idempotence}. 285 286 \begin{lstlisting}[style=bfh-c,language=C, caption={Fixed idempotency check}, label={lst:fixed-idempotence}] 287 enum GNUNET_GenericReturnValue 288 TALER_coin_ev_hash (const struct TALER_BlindedPlanchet *blinded_planchet, 289 const struct TALER_DenominationHash *denom_hash, 290 struct TALER_BlindedCoinHash *bch) 291 { 292 switch (blinded_planchet->cipher) 293 { 294 case TALER_DENOMINATION_RSA: 295 { 296 struct GNUNET_HashContext *hash_context; 297 hash_context = GNUNET_CRYPTO_hash_context_start (); 298 299 GNUNET_CRYPTO_hash_context_read (hash_context, 300 &denom_hash->hash, 301 sizeof(denom_hash->hash)); 302 GNUNET_CRYPTO_hash_context_read (hash_context, 303 blinded_planchet->details. 304 rsa_blinded_planchet.blinded_msg, 305 blinded_planchet->details. 306 rsa_blinded_planchet.blinded_msg_size); 307 GNUNET_CRYPTO_hash_context_finish (hash_context, 308 &bch->hash); 309 return GNUNET_OK; 310 } 311 case TALER_DENOMINATION_CS: 312 { 313 struct GNUNET_HashContext *hash_context; 314 hash_context = GNUNET_CRYPTO_hash_context_start (); 315 316 GNUNET_CRYPTO_hash_context_read (hash_context, 317 &denom_hash->hash, 318 sizeof(denom_hash->hash)); 319 GNUNET_CRYPTO_hash_context_read (hash_context, 320 &blinded_planchet->details. 321 cs_blinded_planchet.nonce, 322 sizeof (blinded_planchet->details. 323 cs_blinded_planchet.nonce)); 324 GNUNET_CRYPTO_hash_context_finish (hash_context, 325 &bch->hash); 326 return GNUNET_OK; 327 } 328 default: 329 GNUNET_break (0); 330 return GNUNET_SYSERR; 331 } 332 } 333 \end{lstlisting}