From 9e694994681b0b2861553d0a50bca6623b546dd2 Mon Sep 17 00:00:00 2001
From: Gian Demarmels <gian@demarmels.org>
Date: Mon, 14 Feb 2022 00:03:06 +0100
Subject: CS thesis

---
 doc/cs/content/4_3_implementation.tex | 333 ++++++++++++++++++++++++++++++++++
 1 file changed, 333 insertions(+)
 create mode 100644 doc/cs/content/4_3_implementation.tex

(limited to 'doc/cs/content/4_3_implementation.tex')

diff --git a/doc/cs/content/4_3_implementation.tex b/doc/cs/content/4_3_implementation.tex
new file mode 100644
index 00000000..07423e4e
--- /dev/null
+++ b/doc/cs/content/4_3_implementation.tex
@@ -0,0 +1,333 @@
+\chapter{Implementation}
+\label{chap:implement}
+This chapter gives an overview on the implementation challenges and discusses special parts in the implementation.
+
+
+\section{Signature Scheme Operations}
+The signature scheme operations are implemented in the GNUnet core repository \cite{gnunet-git} (and have been merged into the master branch).
+This would allow other GNUnet projects to use our implementation of the Clause Blind Schnorr Signature Scheme.
+
+The implementation is done in multiple locations:
+\begin{itemize}
+  \item \texttt{src/include/gnunet\_crypto\_lib.h}:
+        This header file is included when using GNUnet's cryptography implementation.
+  \item \texttt{src/util/crypto\_cs.c}:
+        The functions specified in \texttt{gnunet\_crypto\_lib.h} will be implemented here.
+  \item \texttt{src/util/test\_crypto\_cs.c}:
+        The test cases for the signature scheme will be implemented here.
+  \item \texttt{src/util/perf\_crypto\_cs.c}:
+        This file houses the implementation of a small program that will be used to compare the performance against the blind RSA Signature Scheme.
+\end{itemize}
+
+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.
+
+The \texttt{map\_to\_scalar\_subgroup} function clamps scalars, which is necessary for values that are derived using a \gls{hkdf}.
+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.
+This process is further described in \cite{rfc7748} and \cite{madden:curve25519-clamping}.
+
+\begin{lstlisting}[style=bfh-c, language=C, caption={Function map\_to\_scalar\_subgroup - Crypto API}, label={lst:map-to-scalar}]
+static void
+map_to_scalar_subgroup (struct GNUNET_CRYPTO_Cs25519Scalar *scalar)
+{
+    scalar->d[0] &= 248;
+    scalar->d[31] &= 127;
+    scalar->d[31] |= 64;
+}
+\end{lstlisting}
+
+Another important function is the \gls{fdh} (see \ref{sec:schnorr-sig}) used to map the message to a scalar.
+GNUnet provides a \gls{fdh} function, which expects libgcrypt's multi precision format.
+A conversion function is provided by GNUnet, which requires the data to be in big endian format.
+Since libsodium uses a little endian representation, the conversion process must include endianness conversion.
+The complete \gls{fdh} including the required conversions is implemented in the function described in listing \ref{lst:cs-fdh}.
+\begin{lstlisting}[style=bfh-c, language=C, caption={Function cs\_full\_domain\_hash - Crypto API}, label={lst:cs-fdh}]
+static void
+cs_full_domain_hash (const struct GNUNET_CRYPTO_CsRPublic *r_dash,
+                     const void *msg,
+                     size_t msg_len,
+                     const struct GNUNET_CRYPTO_CsPublicKey *pub,
+                     struct GNUNET_CRYPTO_CsC *c)
+{
+    ...
+\end{lstlisting}
+
+Last but not least, the implementation has one notable performance improvement not mentioned in the redesigned protocols.
+In various steps \gls{hkdf} is used multiple times in a row.
+For example to derive the four blinding secrets $\alpha_0, \alpha_1, \beta_0, \beta_1$.
+The derivation can be done in one \gls{hkdf} call with bigger output size, 128 bit in this case.
+The output then can be split in four parts and then mapped to the ed25519 subgroup.
+This can be done secure, because as explained in \autoref{sec:kdf} a \gls{hkdf} output is truly random.
+
+
+\section{Taler Cryptographic Utilities}
+\begin{bfhNoteBox}
+    Implementation is done in Taler's exchange.
+    From here on the implementation can be found in the exchange git repository \cite{taler-git:exchange}.
+\end{bfhNoteBox}
+The cryptographic utilities of Taler can be found in \texttt{src/util}.
+
+
+The implementation is done in various locations:
+\begin{itemize}
+    \item \texttt{src/include/taler\_crypto\_lib.h}: This header file is included when using Taler's cryptography implementation.
+    The different data structures and functionality are defined here.
+    \item \texttt{src/util/denom.c}: Implement denomination utility functions for \gls{CSBS} cases
+    \item \texttt{src/util/crypto.c}: Adjust all utility functions to support \gls{CSBS}.
+    crypto.c contains many cryptographic utility functions, for example to create planchets or blinding factors.
+    \item \texttt{src/util/test\_crypto.c}: Functionality tests for crypto.c and denom.c
+    \item \texttt{src/include/taler\_signatures.h}: In this header file message formats and signature constants are defined (not modified)
+    \item \texttt{src/util/secmod\_signatures.c}: Utility functions for Taler security module signatures
+\end{itemize}
+
+The security module \texttt{taler-secmod-cs} is implemented here:
+\begin{itemize}
+    \item \texttt{src/util/taler-exchange-secmod-cs.c}: Standalone process to perform private key Clause Blind Schnorr signature operations.
+    \item \texttt{src/util/taler-exchange-secmod-cs.h}: Specification of \ac{IPC} messages for the CS secmod process
+    \item \texttt{src/util/taler-exchange-secmod-cs.conf}: Configuration file for the secmod process
+    \item \texttt{src/util/secmod\_common.c} and \texttt{src/util/secmod\_common.h}: Common functions for the exchange's security modules (not modified)
+\end{itemize}
+
+The corresponding crypto helper, that talks with the security module, and its tests \& benchmarks are implemented here:
+\begin{itemize}
+    \item \texttt{src/util/crypto\_helper\_cs.c}: Utility functions to communicate with the security module
+    \item \texttt{src/util/crypto\_helper\_common.c}: and \texttt{crypto\_helper\_common.h}: Common functions for the exchange security modules (not modified)
+    \item \texttt{src/util/test\_helper\_cs.c}: Tests and benchmarks for the \gls{CSBS} crypto helper
+\end{itemize}
+% Crypto API offene Punkte:
+%Input-Validierung von Punkten und Skalar
+% Clamping beschreiben: https://neilmadden.blog/2020/05/28/whats-the-curve25519-clamping-all-about/
+% Testing: inverse operations, blinded signature test
+
+
+\section{Denomination Key Management}
+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:
+\begin{itemize}
+    \item \url{src/exchange/taler-exchange-httpd_keys.h} and \\
+    \url{src/exchange/taler-exchange-httpd_keys.c}: Integrate \gls{CSBS} secmod and denomination key management
+    \item \url{src/exchange-tools/taler-exchange-offline.c}: Implement \gls{CSBS} case for offline signing of denomination keys
+    \item \url{src/include/taler_exchange_service.h}: \\
+    Add \gls{CSBS} secmod public key to struct\\TALER\_EXCHANGE\_FutureKeys
+    \item \url{src/json/json_helper.c}: Implement CS case in function parse\_denom\_pub (used in taler-exchange-offline.c)
+    \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)
+    \item \url{src/pq/pq_query_helper.c}: Implement \gls{CSBS} case in function qconv\_denom\_pub
+    \item \url{src/pq/pq_result_helper.c}: Implement \gls{CSBS} case in function extract\_denom\_pub
+\end{itemize}
+
+In order for the tests to pass, the following changes had to be implemented:
+\begin{itemize}
+    \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
+    \item \url{src/testing/.gitignore}: Add paths where \gls{CSBS} keys are stored (secmod-helper)
+    \item \url{src/testing/test_auditor_api.conf}: Add section taler-exchange-secmod-cs
+    \item \url{src/testing/test_exchange_api_keys_cherry_picking.conf}: Add section taler-exchange-secmod-cs
+    \item \url{src/testing/testing_api_helpers_exchange.c}: Add \gls{CSBS} secmod start and stop logic
+\end{itemize}
+
+
+\section{New Endpoint for $R$}
+The new endpoint is available in the exchange's HTTP server under \url{/csr}.
+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.
+The implementation can be found in:
+\begin{itemize}
+    \item \url{src/exchange/taler-exchange-httpd.c}:
+    Definition for the new endpoint, calls the function that handles \url{/csr} requests
+    \item \url{src/exchange/taler-exchange-httpd_responses.h} and \\
+    \url{src/exchange/taler-exchange-httpd_responses.c}: \\
+    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
+    \item \url{src/exchange/taler-exchange-httpd_csr.h} and \\
+    \url{src/exchange/taler-exchange-httpd_csr.c}: \\
+    Implementation of the request handler for the new endpoint
+    \item \url{src/exchange/taler-exchange-httpd_keys.h} and \\
+    \url{src/exchange/taler-exchange-httpd_keys.c}: \\
+    Additional function TEH\_keys\_denomination\_cs\_r\_pub that passes down the request to derive the $ R $ to the taler-exchange-secmod-cs helper
+\end{itemize}
+
+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/}).
+Since the new endpoint is used during withdrawing coins, testing for the \url{/csr} endpoint is integrated in these protocol tests.
+Therefore, a call to the endpoint was implemented and later integrated into the calls to the withdraw-\ac{API}.
+Code for calling the endpoint is located in these files:
+\begin{itemize}
+    \item \url{src/include/taler_exchange_service.h}: \\
+    Header describing functions and data structures used in withdraw and refresh testing:
+    \begin{itemize}
+        \item struct TALER\_EXCHANGE\_CsRHandle: Handle containing request information
+        \item struct TALER\_EXCHANGE\_CsRResponse: Response details
+        \item function TALER\_EXCHANGE\_CsRCallback: Callback function to deliver the results (used in withdraw and refresh)
+        \item function TALER\_EXCHANGE\_csr: Used to call endpoint
+        \item function TALER\_EXCHANGE\_csr\_cancel: Used to free dynamically allocated resources
+    \end{itemize}
+    \item \url{src/lib/exchange_api_csr.c}: Implementation of \url{/csr} request
+\end{itemize}
+
+
+\section{Withdraw Protocol}
+\label{sec:withdraw-protocol-impl}
+Since this is an existing endpoint, it was adjusted to support \gls{CSBS}.
+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.
+\\\\
+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)$).
+This step ensures that the same signature will always be returned for a certain nonce.
+Using the same nonce for the same denomination twice without this check would lead to the same random value $r$.
+This is due to derivation of $r := \text{HKDF}(256,n_w || d_s, \text{"r"})$.
+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}.
+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}.
+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}.\\
+The designed Taler protocols using \gls{CSBS} are preventing this attack by checking the nonce and return the previously generated signature.
+Additionally the denomination's public key is included in this check to prevent another issue explained in section \ref{sec:taler-vuln}.\\
+The check is implemented by persisting a hash value over $n_w$ and $D_p$.
+On every withdrawal \texttt{check\_request\_idempotent()} is called, which checks whether the persisted hash matches with the current $n_w, D_p$ pair.
+
+
+\begin{itemize}
+    \item \url{src/exchange/taler-exchange-httpd_withdraw.c}: Implementation of \gls{CSBS} case for withdraw endpoint
+    \item \url{src/exchange/taler-exchange-httpd_keys.c}: Implement \gls{CSBS} case in function \\
+    TEH\_keys\_denomination\_sign (passes the signature creation down to the crypto helpers)
+    \item \url{src/include/taler_json_lib.h} and \url{src/json/json_helper.c}: \\
+    Add function TALER\_JSON\_spec\_blinded\_planchet
+    \item \url{src/json/json_pack.c}: \\
+    Implement \gls{CSBS} case in function\\ TALER\_JSON\_pack\_blinded\_denom\_sig
+    \item \url{src/pq/pq_query_helper.c}: implement \gls{CSBS} case in functions qconv\_denom\_sig and qconv\_blinded\_denom\_sig
+    \item \url{src/pq/pq_result_helper.c}: Implement \gls{CSBS} case in function extract\_blinded\_denom\_sig
+\end{itemize}
+
+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:
+\begin{itemize}
+    \item \url{src/testing/test_exchange_api.c}: Add additional tests for \gls{CSBS} withdraw
+    \item \url{src/include/taler_testing_lib.h}: Specification for functions \\
+    TALER\_TESTING\_cmd\_withdraw\_cs\_amount and \\
+    TALER\_TESTING\_cmd\_withdraw\_cs\_amount\_reuse\_key, add denomination cipher parameter to function TALER\_TESTING\_find\_pk
+    \item \url{src/testing/testing_api_cmd_withdraw.c}: add functions \\
+    TALER\_TESTING\_cmd\_withdraw\_cs\_amount and \\
+    TALER\_TESTING\_cmd\_withdraw\_cs\_amount\_reuse\_key, implement \gls{CSBS}-specific logic for withdraw
+    \item \url{src/testing/testing_api_helpers_exchange.c}:
+    add cipher parameter to function TALER\_TESTING\_find\_pk
+    \item \url{src/lib/exchange_api_withdraw.c}: Implement \gls{CSBS}-specific withdraw logic, integrate \url{/csr} request
+    \item \url{src/lib/exchange_api_withdraw2.c}: implement \gls{CSBS} case
+    \item \url{src/include/taler_json_lib.h} and \url{src/json/json_pack.c}: \\
+    Add function TALER\_JSON\_pack\_blinded\_planchet
+    \item \url{src/json/json_helper.c} implement \gls{CSBS} case in function parse\_blinded\_denom\_sig
+\end{itemize}
+
+\section{Deposit Protocol}
+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.
+\begin{itemize}
+    \item \url{/src/exchange/taler-exchange-httpd_deposit.c}: Add check whether denomination cipher and denomination signature cipher are equal
+    \item \url{/src/json/json_helper.c}: Implement \gls{CSBS} case in function parse\_denom\_sig
+    \item \url{/src/pq/pq_result_helper.c}: Implement \gls{CSBS} case in function extract\_denom\_sig
+\end{itemize}
+
+Tests for deposit are implemented here:
+\begin{itemize}
+    \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
+    \item \url{/src/json/json_pack.c}: Implement \gls{CSBS} case in function TALER\_JSON\_pack\_denom\_sig
+\end{itemize} 
+
+\section{Fixing a Minor Security Issue in Taler's RSA Blind Signature Protocols}
+\label{sec:taler-vuln}
+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.
+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.
+
+\subsection{Security Issue}
+\label{sec:taler-vuln-desc}
+
+The redesigned \gls{CSBS} protocols already include the denomination key in the nonce check, which fixes this issue (see \ref{sec:withdraw-protocol-schnorr}).
+In the case of \gls{RSABS}, the current protocol includes an \gls{idempotence} check by persisting the hash value of the blinded coin $m'$. 
+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.
+This could lead to the following scenario:
+
+\begin{enumerate}
+    \item A broken wallet withdraws a coin with denomination $D_{p_{(1)}}$.
+    \item The wallet sends a request to withdraw the same coin for denomination $D_{p_{(2)}}$.
+    \item The exchange returns the signature for the denomination $D_{p_{(1)}}$ due to the \gls{idempotence} check.
+    \item Since the exchange returned an invalid signature, the customer can file a complaint at the auditor.
+    \item The auditor then has to investigate why the exchange returned invalid signatures.
+    \item The auditor can disprove the complaint by querying the persisted hash used for the \gls{idempotence} check.
+    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.
+\end{enumerate}
+
+Including the denomination public key into the persisted hash for the \gls{idempotence} check solves this issue.
+If a broken wallet now sends the same coin for more than one denomination, the exchange returns valid signatures in both cases.\\
+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.
+
+\subsection{Impact}
+The impact of this security vulnerability is considered as very low.
+An auditor investigating such an issue can simply retrace what happened by checking the persisted hash and associated denomination.
+The impact of the issue is, that an auditor needs to investigate an issue, which can be prevented inside the protocol.
+\\
+In the previous section the client was considered a broken wallet.
+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.
+
+
+\subsection{Fix}
+Listing \ref{lst:rsa-idempotence} shows the code of calculating the hash for the idempotency check in the RSA case before it was fixed.
+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.
+After discussing this issue with Christian Grothoff, the conclusion was to include the denomination public key to prevent the discussed issue.
+
+\begin{lstlisting}[style=bfh-c,language=C, caption={Idempotency check on RSA}, label={lst:rsa-idempotence}]
+    enum GNUNET_GenericReturnValue
+    TALER_coin_ev_hash (const struct TALER_BlindedPlanchet *blinded_planchet,
+                        struct TALER_BlindedCoinHash *bch)
+    {
+      switch (blinded_planchet->cipher)
+      {
+      case TALER_DENOMINATION_RSA:
+        GNUNET_CRYPTO_hash (
+          blinded_planchet->details.rsa_blinded_planchet.blinded_msg,
+          blinded_planchet->details.rsa_blinded_planchet.blinded_msg_size,
+          &bch->hash);
+        return GNUNET_OK;
+      case TALER_DENOMINATION_CS:
+      ...
+    
+\end{lstlisting}
+
+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.
+The applied fix can be seen in listing \ref{lst:fixed-idempotence}.
+
+\begin{lstlisting}[style=bfh-c,language=C, caption={Fixed idempotency check}, label={lst:fixed-idempotence}]
+    enum GNUNET_GenericReturnValue
+    TALER_coin_ev_hash (const struct TALER_BlindedPlanchet *blinded_planchet,
+                        const struct TALER_DenominationHash *denom_hash,
+                        struct TALER_BlindedCoinHash *bch)
+    {
+      switch (blinded_planchet->cipher)
+      {
+      case TALER_DENOMINATION_RSA:
+        {
+          struct GNUNET_HashContext *hash_context;
+          hash_context = GNUNET_CRYPTO_hash_context_start ();
+    
+          GNUNET_CRYPTO_hash_context_read (hash_context,
+                                           &denom_hash->hash,
+                                           sizeof(denom_hash->hash));
+          GNUNET_CRYPTO_hash_context_read (hash_context,
+                                           blinded_planchet->details.
+                                           rsa_blinded_planchet.blinded_msg,
+                                           blinded_planchet->details.
+                                           rsa_blinded_planchet.blinded_msg_size);
+          GNUNET_CRYPTO_hash_context_finish (hash_context,
+                                             &bch->hash);
+          return GNUNET_OK;
+        }
+      case TALER_DENOMINATION_CS:
+        {
+          struct GNUNET_HashContext *hash_context;
+          hash_context = GNUNET_CRYPTO_hash_context_start ();
+    
+          GNUNET_CRYPTO_hash_context_read (hash_context,
+                                           &denom_hash->hash,
+                                           sizeof(denom_hash->hash));
+          GNUNET_CRYPTO_hash_context_read (hash_context,
+                                           &blinded_planchet->details.
+                                           cs_blinded_planchet.nonce,
+                                           sizeof (blinded_planchet->details.
+                                                   cs_blinded_planchet.nonce));
+          GNUNET_CRYPTO_hash_context_finish (hash_context,
+                                             &bch->hash);
+          return GNUNET_OK;
+        }
+      default:
+        GNUNET_break (0);
+        return GNUNET_SYSERR;
+      }
+    }
+\end{lstlisting}
-- 
cgit v1.2.3

