Security

You are currently browsing articles tagged Security.

Bitcoin – ECDSA signature

December 24, 2018 in Bitcoin | No comments

Download pdf here: Bitcoin ECDSA

1. Introduction

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 $10^{-8}.$ 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.

Read the rest of this entry »

Tags: dsa, ecdsa, malleability, Schnorr, Security

MLSAG Signature Scheme

May 7, 2018 in Monero | No comments

Download pdf here: MLSAG Signature Scheme

1. Introduction

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 $[(pk_1,sk_1),.,(pk_n,sk_n)]$ instead of only one pair $(pk,sk).$
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 ${\Sigma}$ associated with a given ring member can produce a valid signature (i.e., verified by $\mathcal{V}$ ). Any other procedure that bypasses ${\Sigma}$ will result in a failed attempt of forgery with overwhelming probability. We note the following about the verification process of $\mathcal{V}$ :

In a “non-ring” setting, the verification is done using a particular public key $pk_{\pi}$ . The validation of a given signature proves that the signer of the message (in this case user $\pi$ ) knows the secret key $sk_{\pi}$ associated with $pk_{\pi}$ . Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair ( $pk_{\pi},sk_{\pi}$ ) signed the message.
In a ring setting, the verification is conducted using a public key vector $L \equiv [pk_1,...,pk_{\pi},...,pk_n]$ 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 $\pi$ ) knows the secret key associated with one of the public keys in $L$ . Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair ( $pk_{\pi},sk_{\pi}$ ) signed the message, for some index $1 \leq \pi \leq n$ that no one other then the actual signer knows.
The ring setting can be generalized further by allowing each ring member $i, 1 \leq i \leq n$ to have a key-pair vector of length $m$ , given by $[(pk_{i}^1, sk_{i}^1),...,(pk_{i}^m, sk_{i}^m)]$ , as opposed to a unique key pair $(pk_i, sk_i)$ . In this setting, the verification is conducted using a public key matrix

$PK= \begin{bmatrix} pk_1^1 & ... & pk_{\pi}^1 & ... & pk_n^1 \\ ... & ... & ... & ... & ...\\ pk_1^m & ... & pk_{\pi}^m & ... & pk_n^m \\ \end{bmatrix}$

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 $PK$ (say column $1 \leq \pi \leq n$ ) 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 $[(pk_{\pi}^1,sk_{\pi}^1),...,(pk_{\pi}^m,sk_{\pi}^m)]$ signed the message, for some index $1 \leq \pi \leq n$ (that no one other then the actual signer knows).

Read the rest of this entry »

Tags: LSAG, MLSAG, Monero, multilayered, ring signature, Security

Pointcheval and Stern Generic Signature

April 8, 2018 in Monero | No comments

Download pdf here: Pointcheval and Stern Generic Signature

1. Introduction

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 $(sk,pk)$ 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 $m$ , our generic scheme creates a signature $\sigma(m) \equiv (r,h,\alpha)$ where $r$ is a random element chosen from a pre-defined set, $h = \mathcal{H}(m,r)$ (i.e., RO output on query $(m,r)$ ), and $\alpha$ is fully determined by $m, r,$ and $h$ . By design, we require that the probability of selecting any particular $r$ be upper-bounded by $\frac{1}{2^{k-1}}$ for a given security parameter $k$ .

Schnorr’s signature scheme is an example that fits this generic model. To see why, recall that $\Sigma_{Schnorr}$ chooses a random commitment $k \in \mathbb{Z}^{*}_{q}$ where $q$ is a pre-defined prime number. It then assigns $r \equiv g^{k}$ where $g$ denotes a chosen generator of $\mathbb{Z}^{*}_{q}$ . Afterwards, $h$ is set to $\mathcal{H}(m,r)$ . Finally, $\alpha$ is calculated as $k-hx$ where $x$ denotes the signer’s private key. Note that $r$ can be any element of $\mathbb{Z}^{*}_{q}$ and so the probability that it takes on a specific value is equal to $\frac{1}{q-1}$ . By design, we choose the security parameter $k \leq log_{2}(q)$ . This choice of $k$ guarantees that the aforementioned probability is upper-bounded by $\frac{1}{2^{k}-1} \leq \frac{1}{2^{k-1}}$ .

Read the rest of this entry »

Tags: Correctness, Privacy, Schnorr, Security, Signature, Unforgeability

Digital Signature and Other Prerequisites

April 5, 2018 in Bitcoin, Monero, Prerequisites | No comments

Download pdf here: Digital Signature and Other Prerequisites

1. Introduction

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].

Read the rest of this entry »

Tags: Crypto, Hash function, Math, Monero, Privacy, Probabilistic Turing Machine, Random Oracle, Reduction model, Security, Signature, Splitting lemma

Delfr

Security

Bitcoin – ECDSA signature

1. Introduction

MLSAG Signature Scheme

1. Introduction

Pointcheval and Stern Generic Signature

1. Introduction

2. Pointcheval and Stern generic signature scheme

Digital Signature and Other Prerequisites

1. Introduction

Recent Posts

Categories

Meta

Delfr

Security

Bitcoin – ECDSA signature

1. Introduction

MLSAG Signature Scheme

1. Introduction

Pointcheval and Stern Generic Signature

1. Introduction

2. Pointcheval and Stern generic signature scheme

Digital Signature and Other Prerequisites

1. Introduction

Stay in touch

Recent Posts

Categories

Meta