You are currently browsing articles tagged Security.
December 24, 2018 in Bitcoin | No comments
Download pdf here: Bitcoin ECDSA
Simply stated, a bitcoin transaction is a transfer of spending control between different parties over a pre-specified amount of satoshis. A satoshi is the smallest fraction of a bitcoin and is equivalent to BTC In order to successfuly complete said transfer, the sender must demonstrate that she is the rightful owner of the satoshis she wishes to spend. Such a proof is imperative as it allows the different nodes on the network to reach an agreement regarding the validity of the transaction and as a result, facilitate its inclusion in the blockchain.
At the time of writing, bitcoin's proof of ownership is encapsulated in a particular type of digital signature known as the Elliptic Curve Digital Signature Algorithm (ECDSA). It is a variant of the Digital Signature Algorithm (DSA) that relies on Elliptic Curve Cryptography (ECC).
In the first section, we introduce the DSA scheme, prove its correctness, and discuss some of its security properties. In particular, we point out that as of the time of writing, and despite its prevalence in various cryptographic settings, we do not know of any valid security proof of DSA in the random oracle (RO) model. However, we highlight that slight variations of it can be proven to be secure.
In the second section, we introduce the ECDSA scheme and prove its correctness. Later on, we present a python-based implementation to further elucidate its building blocks. We also describe how an ECDSA signature gets typically encoded within a bitcoin transaction. Finally, we highlight some of the scheme's potential shortcomings including the absence to-date of a security proof in the RO model, its susceptibility to being malleable, and its non-linear design that hinders an efficient implementation of multisignature transactions.
Tags: dsa, ecdsa, malleability, Schnorr, Security
May 7, 2018 in Monero | No comments
Download pdf here: MLSAG Signature Scheme
Monero stands out from other cryptocurrencies in its ability to hide the signer, conceal the transaction amount, and protect the identity of the recepient. Parts 1, 2, 3, 4, 5, and 6 helped us build the foundation to better understand and appreciate the security properties of ring signatures (albeit in the RO model). This part (introduction to MLSAG), as well as part 8 and part 9 will focus on Monero's privacy in so far as the signer's identity and the transaction amount are concerned. Part 10 will introduce stealth addresses as a mechanism to protect the identity of the fund's recipient.
In order to describe how a Monero transaction hides both the signer's identity and the amount of the transaction, we introduce 2 additional concepts:
A generalization of the LSAG signature (introduced in part 6) to allow each member of the ring to have a key-pair vector instead of only one pair
A particular map known as the Pedersen Commitment that will be used to hide transaction amounts while allowing the network to check that input and output amounts always balance out.
Recall that by proving that a digital signature scheme was unforgeable, one gets the assurance that only the signing algorithm associated with a given ring member can produce a valid signature (i.e., verified by ). Any other procedure that bypasses will result in a failed attempt of forgery with overwhelming probability. We note the following about the verification process of :
In a "non-ring" setting, the verification is done using a particular public key . The validation of a given signature proves that the signer of the message (in this case user ) knows the secret key associated with . Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair ( ) signed the message.
In a ring setting, the verification is conducted using a public key vector known as a ring. This vector is used to conceal the identity of the signer. The validation of a given signature proves that the the signer of the message (in this case user ) knows the secret key associated with one of the public keys in . Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair ( ) signed the message, for some index that no one other then the actual signer knows.
The ring setting can be generalized further by allowing each ring member to have a key-pair vector of length , given by , as opposed to a unique key pair . In this setting, the verification is conducted using a public key matrix
The validation of the signature proves that the signer knows the secret key associated with each one of its public keys. In other terms, there exists a column in (say column ) such that the signer knows the secret key associated with each public key appearing in that column. Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair vector signed the message, for some index (that no one other then the actual signer knows).
Tags: LSAG, MLSAG, Monero, multilayered, ring signature, Security
April 8, 2018 in Monero | No comments
Download pdf here: Pointcheval and Stern Generic Signature
In the next few parts of this series, we look at various signature schemes and prove their security in the RO model. This part is dedicated to the analysis of Pointcheval and Stern Generic Signature Scheme of which the Schnorr scheme is an example. The generic scheme is built around a single pair. Later parts of this series will focus on ring signature schemes. Ring signatures embed the actual signer in a ring of other possible signers to hide her identity. We will discuss them in parts 3, 4, 5, 6, and 7.
2. Pointcheval and Stern generic signature scheme
For a given message , our generic scheme creates a signature where is a random element chosen from a pre-defined set, (i.e., RO output on query ), and is fully determined by and . By design, we require that the probability of selecting any particular be upper-bounded by for a given security parameter .
Schnorr's signature scheme is an example that fits this generic model. To see why, recall that chooses a random commitment where is a pre-defined prime number. It then assigns where denotes a chosen generator of . Afterwards, is set to . Finally, is calculated as where denotes the signer's private key. Note that can be any element of and so the probability that it takes on a specific value is equal to . By design, we choose the security parameter . This choice of guarantees that the aforementioned probability is upper-bounded by .
Tags: Correctness, Privacy, Schnorr, Security, Signature, Unforgeability
April 5, 2018 in Bitcoin, Monero, Prerequisites | No comments
Download pdf here: Digital Signature and Other Prerequisites
We divide this post into 6 sections. Section 2 is a qualitative description of digital signature schemes. Section 3 motivates the introduction of hash functions along with some of their desired properties. Section 4 describes a hypothetical ideal random function known as a Random Oracle. Section 5 briefly introduces the notion of Probabilistic Turing Machines that will be needed when studying the security of digital signature schemes. Sections 6 and 7 describe 2 pillars introduced by Poitncheval & Stern to prove the resilience of some digital signature schemes against a forgery attack in the Random Oracle model. In particular, Setion 6 describes a reduction model to facilitate the security analysis of signature schemes. Section 7 states and proves an important lemma known as the splitting lemma.
There is one caveat: I assume that the reader is familiar with basic probability theory, modulo arithmetic, as well as some group theoretic concepts including the notions of cyclic groups and finite fields. A concise introduction to group and field theory can be found in this post. For a more detailed treatment, the reader can refer to e.g., [3].
Tags: Crypto, Hash function, Math, Monero, Privacy, Probabilistic Turing Machine, Random Oracle, Reduction model, Security, Signature, Splitting lemma