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 https://pdfs.semanticscholar.org/d8b9/a0309cef8c309541876c9c2c5ad5c16c3b7a.pdf

The DAO attack had 3 components, a hacker, a malicious contract and a vulnerable contract. The malicious contract is used to withdraw funds from the vulnerable contract so that it does not get a chance to decrement its balance. Oddly enough the gas mechanism which is supposed to limit 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, DataWaller and BloomIDs. Security would be a continuing  concern with the expanding scope of such projects.

Advertisements

Lessons from SF Muni Ransomware

On Nov 25, a hacker going by “andy saolis” infected the San Francisco Municipal Transportation Agency’s (SMFTA) network with ransomware that encrypted data on 900 office computers, spreading through the system’s Windows operating system. Saolis threatened to publish 30 gigabytes of data, including contracts, employee data, customer information.  SMFTA’s ticketing system was shut down to prevent the malware from spreading. The attacker demanded a 100 Bitcoin ransom, around $73,000, to unlock the affected files. Salted hash reported the malware is likely a variant of HDDCryptor, which uses commercial tools to encrypt hard drives and network shares.

The service was restored due to backups . However consider these systems were in an ICS scenario. An unexpected downtime would result, which would be unacceptable.

Elliptic Curve Crypto

A brief review of concepts leading to ECC:

Algebraic Group: A set G with a single binary operator (+) that maps any 2 elements of G to another element of G.  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 https://youtu.be/ebc8EdBNA-E https://youtu.be/h6JBiYeBfC4 https://m.youtube.com/watch?v=oM1LD80E7XU . 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 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.

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- http://www.coindesk.com/math-behind-bitcoin/ . 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. https://crypto.stackexchange.com/questions/53974/when-adding-two-points-on-an-elliptic-curve-why-flip-over-the-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.

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

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.

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 https://en.m.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Correctness_of_the_algorithm for details and some implementation weaknesses. Openssl operations on EC based keypairs are described here – https://wiki.openssl.org/index.php/Command_Line_Elliptic_Curve_Operations. 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.

Other elliptic curves on finite fields, including on F(2^m) are described in http://www.secg.org/sec2-v2.pdf.

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. https://www.encyclopediaofmath.org/index.php/Permutation_group https://math.stackexchange.com/questions/45893/how-to-find-the-galois-group-of-a-polynomial