diff options
| -rw-r--r-- | configure.ac | 10 | ||||
| -rw-r--r-- | doc/paper/postquantum_melt.tex | 306 | ||||
| -rw-r--r-- | src/Makefile.am | 4 | ||||
| -rw-r--r-- | src/bank-lib/bank_api_admin.c | 1 | ||||
| -rw-r--r-- | src/exchange-lib/test_exchange_api.conf | 4 | ||||
| -rw-r--r-- | src/exchange/exchange.conf | 2 | ||||
| -rw-r--r-- | src/exchange/taler-exchange-aggregator.c | 4 | ||||
| -rw-r--r-- | src/exchange/taler-exchange-httpd.c | 4 | ||||
| -rw-r--r-- | src/exchange/test_taler_exchange_httpd.conf | 6 | ||||
| -rw-r--r-- | src/include/taler_amount_lib.h | 2 | ||||
| -rw-r--r-- | src/taler.conf | 2 | ||||
| -rw-r--r-- | src/wire/plugin_wire_sepa.c | 4 | ||||
| -rw-r--r-- | src/wire/plugin_wire_template.c | 4 | ||||
| -rw-r--r-- | src/wire/plugin_wire_test.c | 6 | ||||
| -rw-r--r-- | src/wire/test_wire_plugin.conf | 2 |
15 files changed, 342 insertions, 19 deletions
diff --git a/configure.ac b/configure.ac index 7b92fd7b7..52af3e4c5 100644 --- a/configure.ac +++ b/configure.ac @@ -241,6 +241,16 @@ else AC_DEFINE([HAVE_LIBCURL],[1],[Have CURL]) fi + +# Check for curl/curl.h and gnurl/curl.h so we can use #ifdef +# HAVE_CURL_CURL_H later (the above LIBCURL_CHECK_CONFIG accepted +# *either* header set). +AC_CHECK_HEADERS([curl/curl.h],, + curl=false + AC_CHECK_HEADERS([gnurl/curl.h],, + gnurl=false)) + + # libgnurl if test "x$gnurl" = "x0" then diff --git a/doc/paper/postquantum_melt.tex b/doc/paper/postquantum_melt.tex new file mode 100644 index 000000000..2dfefeeed --- /dev/null +++ b/doc/paper/postquantum_melt.tex @@ -0,0 +1,306 @@ +\documentclass{llncs} +%\usepackage[margin=1in,a4paper]{geometry} +\usepackage[T1]{fontenc} +\usepackage{palatino} +\usepackage{xspace} +\usepackage{microtype} +\usepackage{tikz,eurosym} +\usepackage{amsmath,amssymb} +\usepackage{enumitem} +\usetikzlibrary{shapes,arrows} +\usetikzlibrary{positioning} +\usetikzlibrary{calc} + +% Relate to: +% http://fc14.ifca.ai/papers/fc14_submission_124.pdf + +% Terminology: +% - SEPA-transfer -- avoid 'SEPA transaction' as we use +% 'transaction' already when we talk about taxable +% transfers of Taler coins and database 'transactions'. +% - wallet = coins at customer +% - reserve = currency entrusted to exchange waiting for withdrawal +% - deposit = SEPA to exchange +% - withdrawal = exchange to customer +% - spending = customer to merchant +% - redeeming = merchant to exchange (and then exchange SEPA to merchant) +% - refreshing = customer-exchange-customer +% - dirty coin = coin with exposed public key +% - fresh coin = coin that was refreshed or is new +% - coin signing key = exchange's online key used to (blindly) sign coin +% - message signing key = exchange's online key to sign exchange messages +% - exchange master key = exchange's key used to sign other exchange keys +% - owner = entity that knows coin private key +% - transaction = coin ownership transfer that should be taxed +% - sharing = coin copying that should not be taxed + + +\title{Post-quantum anonymity in Taler} + +\begin{document} +\mainmatter + +\author{Jeffrey Burdges} +\institute{Intria / GNUnet / Taler} + + +\maketitle + +\begin{abstract} +David Chaum's original RSA blind sgnatures provide information theoretic +anonymity for customers' purchases. In practice, there are many schemes +that weaken this to provide properties. We describe a refresh protocol +for Taler that provides customers with post-quantum anonymity. +It replaces an elliptic curve Diffe-Hellman operation with a unique +hash-based encryption scheme for the proof-of-trust via key knoledge +property that Taler requires to distinguish untaxable operations from +taxable purchases. +\end{abstract} + + +\section{Introduction} + +David Chaum's RSA blind sgnatures \cite{} can provide financial +security for the exchange, or traditionally mint, + assuming RSA-CTI \cite{,}. + +A typical exchange deployment must record all spent coins to prevent +double spending. It would therefore rotate ``denomination'' signing +keys every few weeks or months to keep this database from expanding +indefinitely \cite{Taler??}. As a consequence, our exchange has +ample time to respond to advances in cryptgraphy by increasing their +key sizes, updating wallet software with new algorithms, or +even shutting down. + +In particular, there is no chance that quantum computers will emerge +and become inexpensive within the lifetime of a demonination key. +Indeed, even a quantum computer that existed only in secret posses +little threat because the risk of exposing that secret probably exceeds +the exchange's value. + +\smallskip + +We cannot make the same bold pronouncement for the customers' anonymity +however. We must additionally ask if customers' transactions can be +deanonymized in the future by the nvention of quantum computes, or +mathematical advances. + +David Chaum's original RSA blind sgnatures provide even information +theoretic anonymity for customers, giving the desired negative answer. +There are however many related schemes that add desirable properties +at the expense of customers' anonymity. In particular, any scheme +that supports offline merchants must add a deanonymization attack +when coins are double spent \cite{B??}. + +Importantly, there are reasons why exchanges must replace coins that +do not involve actual financial transactons, like to reissue a coin +before the exchange rotates the denomination key that signed it, or +protect users' anonymity after a merchant recieves a coin, but fails +to process it or deliver good. + +In Taler, coins can be partially spent by signing with the coin's key +for only a portion of the value determined by the coin's denomination +key. This allows precise payments but taints the coin with a +transaction, which frequently entail user data like a shipng address. +To correct this, a customer does a second transaction with the exchange +where they sign over the partially spent coin's risidual balance +in exchange for new freshly anonymized coins. +Taler employs this {\em refresh} or {\em melt protocol} for +both for coins tainted through partial spending or merchant failures, +as well as for coin replacement due to denomination key roration. + +If this protocol were simply a second transaction, then customers +would retain information theoreticaly secure anonymity. +In Taler however, we require that the exchange learns acurate income +information for merchants. If we use a regular transaction, then +a customer could conspire to help the merchant hide their income +\cite[]{Taler??}. +To prevent this, the refresh protocol requires that a customer prove +that they could learn the private key of the resulting new coins. + +At this point, Taler employs an elliptic curve Diffie-Hellman key +exchange between the coin's signing key and a new linking key +\cite[??]{Taler??}. As the public linking key is exposed, +an adversary with a quantum computer could trace any coins involved +in either partial spending operations or aborted transactions. +A refresh prompted by denomination key rotation incurs no anonymity +risks regardless. + +\smallskip + +We could add an existing post-quantum key exchange, but these all +incur significantly larger key sizes, requiring more badwidth and +storage space for the exchange, and take longer to run. +In addition, the established post-quantum key exchanges based on +Ring-LWE, like New Hope \cite{}, require that both keys be +ephemeral. +Super-singular isogenies \cite{,} would work ``out of the box'', +if it were already packeged in said box. + +Instead, we observe that + + + + + + + +In this paper, we describe a post-quantum + +It replaces an elliptic curve Diffe-Hellman operation with a unique +hash-based encryption scheme for the proof-of-trust via key knoledge +property that Taler requires to distinguish untaxable operations from +taxable purchases. + +... + +\smallskip + +We observe that several elliptic curve blind signature schemes provide +information theoreticly secure blinding as well, but + Schnorr sgnatures require an extra round trip \cite{??}, and + pairing based schemes offer no advnatages over RSA \cite{??}. + +There are several schemes like Anonize \cite{} in Brave \cite{}, +or Zcash \cite{} used in similar situations to blind signatures. +% https://github.com/brave/ledger/blob/master/documentation/Ledger-Principles.md +In these systems, anonymity is not post-quantum due to the zero-knowledge +proofs they employ. + + + + +\section{Background} + + +\section{Refresh} + + +Let $\kappa$ and $\theta$ denote + the exchange's security parameter and + the maximum number of coins returned by a refresh, respectively. + +We define a Merkle tree/sequence function + $\mlink(m,i,j) = H(m || "YeyCoins!" || i || j)$ + Actual linking key for jth cut of ith target coin + $\mhide(m,i,j) = H( \mlink(m,i,j) )$ + Linking key hidden for Merkle + $\mcoin(m,i) = H( \mhide(m,i,1) || \ldots || \mhide(m,i,\kappa) )$ + Merkle root for refresh into the ith coin + $\mroot(m) = M( \m_coin(m,1), \ldots, \mcoin(m,\theta) )$ + Merkle root for refresh of the entire coin + $mpath(m,i)$ is the nodes adjacent to Merkle path to $\mcoin(m,i)$ +If $\theta$ is small then $M(x[1],\ldots,x[\theta])$ could be simply be +the concatenate and hash function $H( x[1] || ... || x[\theta] )$ like +in $\mcoin$, giving $O(n)$ time. If $\theta$ is large, then $M$ should +be a hash tree to give $O(\log n)$ time. We could use $M$ in $\mcoin$ +too if $\kappa$ were large, but concatenate and hash wins for $\kappa=3$. +All these hash functions should have a purpose string. + + +A coin now consists of + a Ed25519 public key $C = c G$, + a Merkle root $M = \mroot(m)$, and + an RSA signature $S = S_d(C || M)$ by a denomination key $d$. +There was a blinding factor $b$ used in the creation of the coin's signature $S$. +In addition, there was a value $s$ such that + $c = H(\textr{"Ed25519"} || s)$, + $m = H(\textr{"Merkle"} || s)$, and + $b = H(\textr{"Blind"} || s)$, +but we try not to retain $s$ if possible. + + +We have a tainted coin $(C,M,S)$ that we wish to + refresh into $n \le \theta$ untained coins. +For simplicity, we allow $x'$ to stand for the component + normally denoted $x$ of the $i$th new coin being created. +So $C' = c' G$, $M' = \mroot(m')$, and $b'$ must be derived from $s'$. +For $j=1\cdots\kappa$, + we allow $x^j$ to denote the $j$th cut of the $i$th coin. +So again + $C^j = c^j G$, $M^j = \mroot(m^j)$, and $b^j$ must be derived from $s^j$. + +Wallet phase 1. + For $j=1 \cdots \kappa$: + Create random $s^j$ and $l^j$. + Compute $c^j$, $m^j$, and $b^j$ from $s^j$ as above. + Compute $C^j = c^j G$ and $L^j = l^j G$ too. + Compute $B^j = B_{b^j}(C^j || \mroot(m^j))$. + Set $k = H(\mlink(m,i,j) || l^j C)$ + Encrypt $E^j = E_k(s^j,l^j)$. + Send commitment $S' = S_C( (L^j,E^1,B^1), \ldots, (E^\kappa,B^\kappa) )$ +% Note : If $\mlink$ were a stream cypher then $E()$ could just be xor. + +Exchange phase 1. + Pick random $\gamma \in \{1 \cdots \kappa\}$. + Mark $C$ as spent by saving $(C,gamma,S')$. + Send gamma and $S(C,gamma,...)$ + +Wallet phase 2. + Save ... + Set $\Beta_gamma = \mhide(m,i,gamma) = H( \mlink(m,i,gamma) )$ and + $\beta_i = \mlink(m,i,j)$ for $j=1\cdots\kappa$ not $\gamma$ + Prepare a responce tuple $R^j$ consisting of + $Beta_gamma$, $(beta_j,l^j)$ for $j=1\cdots\kappa$ not $\gamma$, + and $\mpath(m,i)$, including $\mcoin(m,i)$, + Send $S_C(R^j)$. + +Exchange phase 2. + Set $Beta_j = H(beta_j)$ for $j=1\ldots\kappa$ except $\gamma$, + keep $Beta_gamma$ untouched. + Verify $M$ with $\mpath(m,i)$ including $\mcoin(m,i)$. + Verify $\mcoin(m,i) = H( Beta_1 || .. || Beta_kappa )$. + For $j=1 \cdots \kappa$ except $\gamma$: + Decrypt $s^j$ from $E^i$ using $k = H(beta_j || l^j C)$ + Compute $c^j$, $m^j$, and $b^j$ from $s^j$. + Compute $C^j = c^j G$ too. + Verify $B^i = B_{b^j}(C^j || \mroot(m^j))$. + If verifications pass then send $S_{d_i}(B^\gamma)$. + + +\section{Withdrawal} + + +\bibliographystyle{alpha} +\bibliography{taler,rfc} + +% \newpage +% \appendix + +% \section{} + + + +\end{document} + + + +$l$ denotes Merkle tree levels +yields $2^l$ leaves +costs $2^{l+1}$ hashing operations + +$a$ denotes number of leaves used +yields $2^{a l}$ outcomes + + + + + + +commit H(h) and h l C and E_{l C)(..) +reveal h and l + + + +x_n ... x_1 c G + + + + + + +waiting period of 10 min + + + + diff --git a/src/Makefile.am b/src/Makefile.am index 6e0fb2049..ee66bb39b 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -15,6 +15,10 @@ if WALLET_ONLY SUBDIRS = include util else +pkgcfgdir = $(prefix)/share/taler/config.d/ +pkgcfg_DATA = \ + taler.conf + SUBDIRS = include util json $(PQ_DIR) $(BANK_LIB) wire exchangedb exchange exchange-tools if HAVE_LIBCURL SUBDIRS += exchange-lib diff --git a/src/bank-lib/bank_api_admin.c b/src/bank-lib/bank_api_admin.c index a334d4629..df3525185 100644 --- a/src/bank-lib/bank_api_admin.c +++ b/src/bank-lib/bank_api_admin.c @@ -20,7 +20,6 @@ * @author Christian Grothoff */ #include "platform.h" -#include <curl/curl.h> #include <jansson.h> #include <microhttpd.h> /* just for HTTP status codes */ #include <gnunet/gnunet_util_lib.h> diff --git a/src/exchange-lib/test_exchange_api.conf b/src/exchange-lib/test_exchange_api.conf index e7d849bc3..5fcc36552 100644 --- a/src/exchange-lib/test_exchange_api.conf +++ b/src/exchange-lib/test_exchange_api.conf @@ -4,10 +4,12 @@ # Persistant data storage for the testcase TALER_TEST_HOME = test_exchange_api_home/ -[exchange] +[taler] # Currency supported by the exchange (can only be one) CURRENCY = EUR +[exchange] + # Wire format supported by the exchange # We use 'test' for testing of the actual # coin operations, and 'sepa' to test SEPA-specific routines. diff --git a/src/exchange/exchange.conf b/src/exchange/exchange.conf index eab476ccd..96322d6a2 100644 --- a/src/exchange/exchange.conf +++ b/src/exchange/exchange.conf @@ -1,8 +1,6 @@ # This file is in the public domain. # [exchange] -# Currency supported by the exchange (can only be one) -# CURRENCY = EUR # Where do we store the private keys the exchange needs at # runtime? (Denomination and signing keys are then stored diff --git a/src/exchange/taler-exchange-aggregator.c b/src/exchange/taler-exchange-aggregator.c index e4ba975a2..0cb47667f 100644 --- a/src/exchange/taler-exchange-aggregator.c +++ b/src/exchange/taler-exchange-aggregator.c @@ -249,12 +249,12 @@ exchange_serve_process_config () { if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_string (cfg, - "exchange", + "taler", "currency", &exchange_currency_string)) { GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, - "exchange", + "taler", "currency"); return GNUNET_SYSERR; } diff --git a/src/exchange/taler-exchange-httpd.c b/src/exchange/taler-exchange-httpd.c index c99535382..6efb1492e 100644 --- a/src/exchange/taler-exchange-httpd.c +++ b/src/exchange/taler-exchange-httpd.c @@ -387,12 +387,12 @@ exchange_serve_process_config () } if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_string (cfg, - "exchange", + "taler", "currency", &TMH_exchange_currency_string)) { GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, - "exchange", + "taler", "currency"); return GNUNET_SYSERR; } diff --git a/src/exchange/test_taler_exchange_httpd.conf b/src/exchange/test_taler_exchange_httpd.conf index 612d9f4d4..642bbf668 100644 --- a/src/exchange/test_taler_exchange_httpd.conf +++ b/src/exchange/test_taler_exchange_httpd.conf @@ -2,11 +2,13 @@ # Persistant data storage for the testcase TALER_TEST_HOME = test_taler_exchange_httpd_home/ - -[exchange] +[taler] # Currency supported by the exchange (can only be one) CURRENCY = EUR + +[exchange] + # Wire format supported by the exchange # We use 'test' for testing of the actual # coin operations. diff --git a/src/include/taler_amount_lib.h b/src/include/taler_amount_lib.h index 2fd547196..8c613e020 100644 --- a/src/include/taler_amount_lib.h +++ b/src/include/taler_amount_lib.h @@ -29,7 +29,7 @@ extern "C" #endif #endif -#include <gnunet/platform.h> +#include <gnunet/gnunet_util_lib.h> /** diff --git a/src/taler.conf b/src/taler.conf new file mode 100644 index 000000000..d05b656c6 --- /dev/null +++ b/src/taler.conf @@ -0,0 +1,2 @@ +[taler] +CURRENCY = KUDOS diff --git a/src/wire/plugin_wire_sepa.c b/src/wire/plugin_wire_sepa.c index 6f01167d9..7a3d0d17b 100644 --- a/src/wire/plugin_wire_sepa.c +++ b/src/wire/plugin_wire_sepa.c @@ -737,12 +737,12 @@ libtaler_plugin_wire_sepa_init (void *cls) { if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_string (cfg, - "exchange", + "taler", "CURRENCY", &sc->currency)) { GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, - "exchange", + "taler", "CURRENCY"); GNUNET_free (sc); return NULL; diff --git a/src/wire/plugin_wire_template.c b/src/wire/plugin_wire_template.c index 46908c297..826d93185 100644 --- a/src/wire/plugin_wire_template.c +++ b/src/wire/plugin_wire_template.c @@ -242,12 +242,12 @@ libtaler_plugin_wire_template_init (void *cls) } if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_string (cfg, - "exchange", + "taler", "CURRENCY", &tc->currency)) { GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, - "exchange", + "taler", "CURRENCY"); GNUNET_free (tc->bank_uri); GNUNET_free (tc); diff --git a/src/wire/plugin_wire_test.c b/src/wire/plugin_wire_test.c index c11adbaed..55d698172 100644 --- a/src/wire/plugin_wire_test.c +++ b/src/wire/plugin_wire_test.c @@ -224,7 +224,7 @@ test_amount_round (void *cls, if (NULL == tc->currency) { GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, - "exchange", + "taler", "CURRENCY"); return GNUNET_SYSERR; /* not configured with currency */ } @@ -820,12 +820,12 @@ libtaler_plugin_wire_test_init (void *cls) } if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_string (cfg, - "exchange", + "taler", "CURRENCY", &tc->currency)) { GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, - "exchange", + "taler", "CURRENCY"); GNUNET_free (tc->bank_uri); GNUNET_free (tc); diff --git a/src/wire/test_wire_plugin.conf b/src/wire/test_wire_plugin.conf index ece816954..b9aebdba7 100644 --- a/src/wire/test_wire_plugin.conf +++ b/src/wire/test_wire_plugin.conf @@ -17,5 +17,5 @@ SEPA_RESPONSE_FILE = test_wire_plugin_sepa.json # is avaialble). BANK_URI = http://localhost/ -[exchange] +[taler] CURRENCY = "EUR" |