Category: cryptocurrency

Ethereum Security and the DAO Solidity Attack

The basics of Ethereum are described in the Gavin Wood paper. A list of keywords in Solidity are described in this file from its source, which includes “address”, “contract”, “event”, “mapping” and “wei” ( 1 Eth= 10^18 Wei). This list does not include “gas”, which is a mechanism described in Wood’s paper to combat abuse. Interestingly the paper says “The first example of utilising the proof-of-work as a strong economic signal to secure a currency was by Vishnumurthy et al [2003]”, aka the Karma paper.

The karma paper talks about solving a cryptographic puzzle as enabling one to join the network and be assigned a bank set: “the node certifies that it completed this computation by encrypting challenges provided by its bank-set nodes with its private key. Thus each node is assigned an id beyond its immediate control, and acquires a public-private key pair that can be used in later stages of the protocol without having to rely on a public-key infrastructure”. Crypto puzzles for diverse problems have been proposed before, a survey and comparison is at

The DAO attack had 3 components, a hacker, a malicious contract and a vulnerable contract. The malicious contract was used to withdraw funds from the vulnerable contract so that it never got to the code to decrement its balance. Oddly enough the gas mechanism which is supposed to limit (runaway) computation did not kick in to stop this repeated remittance.

A few weeks before the DAO attack someone had pointed out to me that security of solidity was a bit of an open problem. My feeling was contracts should be layered above the value exchange mechanism, not built into it. Bitcoin based protocols with the simpler OP_RETURN semantics appeared more solid. Later around October’16 at an Ethereum meetup, Fred Ehrsam made the comment that most new projects would be using Ethereum instead of bitcoin. But Bitcoin meetups had more real-world use cases being discussed. The technical limitations exist, which are being addressed by forks such as SegWit2x this November. Today saw a number of interesting proposals with Ethereum, including Dharma, DataWallet and BloomIDs. Security would be a continuing  concern with the expanding scope of such projects.

Sequence diagram of the attack, showing a double-withdraw –

More on Ethereum –

It uses the Keccac-256 hash function.

It supports the Ethereum Virtual Machine. The EVM is formally specified in section 9 of Gavin Wood paper. Some properties –

  • computation on EVM is intrinsically tied to a parameter ‘gas’ which limits the amount of computation.
  • stack based machine, with max stack depth of1024
  • 256-bit word size. 256-bit stack item size. 256-bit chosen to facilitate Keccak-256 hash and Elliptic Curve computations
  • machine halts on various exceptions including OOG (out of gas)
  • memory model is a word-addressed byte-array
  • program code is store in a ‘virtual ROM’ accessed via a specialized instruction
  • runs state transition function

The state transition function takes as input – state σ, remaining gas g, and a tuple I.
The execution agent must provide in the execution environment, certain information, that are contained in the tuple I:
Ia, the address of the account which owns the code that is executing.
Io, the sender address of the transaction that originated this execution.
Ip, the price of gas in the transaction that originated this execution.
Id, the byte array that is the input data to this execution; if the execution agent is a transaction,
this would be the transaction data.
Is, the address of the account which caused the code to be executing; if the execution agent is a
transaction, this would be the transaction sender.
Iv , the value, in Wei, passed to this account as part of the same procedure as execution; if the
execution agent is a transaction, this would be the transaction value.
Ib, the byte array that is the machine code to be executed.
IH , the block header of the present block.
Ie, the depth of the present message-call or contract-creation (i.e. the number of CALLs or
CREATEs being executed at present).
The execution model defines the function Ξ, which can compute the resultant state σ′, the remaining gas g′, the suicide list s, the log series l, the refunds r and the resul- tant output, o, given these definitions:
(115) (σ′, g′, s, l, r, o) ≡ Ξ(σ, g, I)

The official code is written in Golang (~640,000 lines). A code walkthrough is at

The table of Opcodes is at

But what is a formal notion of a contract (specifically on the EVM which aims to generalize contracts) ? Is it any function. Is it a function of a specific template, expecting certain inputs/outputs. Can these functions be composed ?

The notions of contracts are delved in

“The contractual phases of search, negotiation, commitment, performance, and adjudication constitute the realm of smart contracts.”

Example – a vending machine. The machine ‘takes in coins and dispenses change and product according to the displayed price’, it is ‘a contract with bearer: anybody with coins can participate in an exchange with the vendor’.

So one can think of a smart contract as a digital vending machine. That’s actually a useful mental model. With a digital vending machine (DVM ?), the buyer can make a choice of what product buyer wants (of possibly very many – not limited to a physical machine), and be served that product upon due payment without interaction with another person or agency.

Elliptic Curve Crypto – an algebraic introduction

A brief review of algebraic concepts leading to Elliptic Curve Cryptography (ECC):

Algebraic Group: A set G with a single binary operator (+) that maps any 2 elements of G to another element of G, where the operator supports closure, identity, inverse and associative properties. If the + operator is commutative, G is called an Abelian group or a Commutative group. [matrix multiplication and quaterion multiplication are not commutative; the symmetric group Sn for n>=3 is non abelian – because transformation order of permutations matters; S5 is not solvable . I mention these because the notion of a group became useful and well-defined when non-Abelian groups such as S5 were encountered]For ECC the groups involved are commutative or Abelian.

Algebraic Ring: A set R with a two binary operators (+) and (*) that map any 2 elements of G to another element of R. Every Ring is an Abelian group with respect to (+). If it is Abelian with respect to (*) then it is called a Commutative Ring. Note the absence of inverse or division requirement. [In Zp below, if p were not prime, then one would have a Ring instead of a Field because inverses would not always exist.]

Algebraic Field: A set F with a two binary operators (+) and (*) that map any 2 elements of F to another element of F; where (+) and (*) are both commutative; and where each element of F has a unique inverse with respect to (*), which is also in F. The set of Rationals form a Field, the set of Integers do not. The group properties are followed wrt (+) and (*) individually and the respective groups are the additive group and the multiplicative group.

Polynomial: A construct consisting of repeated applications of (+) and (*) on elements of a Field (which by definition of a Field returns another element of the Field ). The set of polynomials forms a Ring.

Closed Field: If the roots of every polynomial on a Field belong to the Field, it is a Closed Field. The set of Complex numbers form a Closed Field, the set of Reals do not. [A Field extension can be used to extend a non-Closed Field to a Closed Field].

Algebraic Finite Field: A Field with finite number of elements. It is not a Closed Field, but satisfies other properties of a Field, specifically that multiplication is invertible. The number of elements of the Finite Field is called its order. An example is the modulus field, obtained by modulo division by a prime number P. Note that exponentiation on a finite field generates a distribution of all the numbers in the sequence less than the order – for large values of an exponent it produces an highly irregular distribution. This makes the inverse operation of discrete logarithm a hard problem. The inverse of a specific element ‘a’ of a finite field of order n is a^(n-2), by Fermat’s little theorem.

Galois Field: Same as above, a finite Field. Finite fields have order pk, where p is a prime and k an integer>=1. All finite fields of a given order are isomorphic. In a field of order pk, adding p copies of any element always results in zero; that is, the characteristic of the field is p. If a finite field had a non-prime order with different factors that would imply that different elements of the field could be added to themselves a different number of times to give 0, but each element of a field must have the same characteristic . We met a  GF (28) in AES S-boxes.

Elliptic-Curve (over reals): A cubic equation, arises in calculation of arclength of an ellipse and naturally has a group property, where two elements on the curve map to a third element also on the curve. See here. The group property is used to define EC-addition (A+B), EC-doubling (A+A) and EC-scalar-multiplication (A+A+..A = kA). This is the group operation on Elliptic curves, a reasonable explanation of why it exists is here. These two operations are defined in more detail- . Lets observe that they are distinct from, but dependent on the underlying field properties. The EC operations are maps on tuples or points.  In history of elliptic curves it notes that whereas ellipses are quadratic, elliptic curves are cubic or quartic, attributing the name linkage to Wallis. It also notes the tangent-secant method of  Diophantus in using two rational solutions of a cubic to find a third rational solution (later proved to be an Abelian Algebraic Group: points A and B on a curve map to a third point C, and one defines Group addition with A+B =-C, where the – is reflection around x-axis. makes the argument using symmetry of A,B,C; important thing is this ‘addition’ is not a linear operation). For a tangent, look at Frey Elliptic curves and Tate’s review with its discussion on isogenies.

Elliptic-Curve over a Field: The set of points (tuples) belonging to a field F that satisfy an elliptic curve equation (y*y = x*x*x+a*x+b) with the (+) and (*) defined according to the field.  Again the name elliptic curve arises because this equation comes up when calculating the arclength of the ellipse; the actual plot of this over different fields does not look like a curve let alone an ellipse. What’s interesting is that the Group property noted above is retained over different Fields. This lecture discusses how consideration of whether the area of a right triangle can be 1, over a field of rationals gave rise to elliptic curves –

Elliptic-Curve over a Finite Field: Tuples drawn from a Finite Field F, that satisfy the elliptic curve equation (y^2 = x^3+ax+b).

Elliptic-Curve Crypto: Built on the hardness of solving the discrete logarithm problem: Given an elliptic curve E defined over a finite field Fq of order(=size) n, a point P ∈ E(Fq ), and a point Q ∈ E(Fq ), find the integer k ∈ [0,n −1] such that Q = k P. The integer k is called the discrete logarithm of Q to the base P, denoted by k = logP Q. This is asking for an inverse operation. Introduction to ECC by Christof Paar – .

In the Bitcoin implementation of ECDSA, the finite field is a prime modulus field Zp and the EC equation is y^2 (mod p) = x^3+7 (mod p).  Zp uses the prime modulus p=2^256 – 2^32 – 977 = 115792089237316195423570985008687907853269984665640564039457‌584007908834671663.  A 256 bit integer has (2^10)^25.6 or 3*25.6~77 digit numbers. So two 256 bit numbers are mapped to a third 256 bit number. Sounds good for encryption- but how is this inverted? It is not: one of the first numbers, the scalar multipler k, is the private key.  This 256-bit scalar private key is multiplied with a Generator Point G to arrive at a public key, with a 256bit x and y coordinates for a a 512-bit public key. From the kG, the private key k cannot be derived; the strength depends on this irreversibility. The “curve” on the finite field is highly discontinuous and an example is shown here. sepc256k1 is the name of the curve y^2=x^3+7, a list of other curves is here –

So how do we generate and verify a signature – an ECDSA ? This math is a layer on top of the preceding maps for generating keypairs. See for details and some implementation weaknesses. Openssl operations on EC based keypairs are described here – The size of the keys for EC are smaller than the size of RSA keys for equivalent security. Since the size of a signature is the same as the size of the key in bits, this means the EC signatures are shorter in size than RSA signatures. A 256 bit EC key takes 32bytes, compared to 512bytes for a (roughly) comparable 4096 bit RSA key.

An ECDSA signature of a message m is a pair of integers (r,s) where r does not depend on the message and s depends on the hash of the message, e, and on r.

The signature depends on a parameter k which should be random or deterministically generated via (say) RFC6979.

Other elliptic curves on finite fields, including on F(2^m) are described in

The cryptol verification software has been used to find bugs in the implementation of a Elliptic Curve Crypto implementations. Implementation errors can dramatically impact security properties of crypto that appears mathematically sound.

Note that a Group sounds like a simpler structure than a Field, but a Galois Group is a more complex structure than a Galois Field.