Month: April 2016

Reactive Microservices

· Leave a comment ·

I came across CQRS and attended a talk by James Roper on Lagom for micro services called “Rethinking REST” this week. The idea put forth in the talk was that REST services being synchronous are not ideal for microservices. Microservices should not be blocking , so something that emphasizes this async aspect would be preferable to REST.

How is this notion of async services different from a pub-sub model ? One way it goes beyond that is by proposing polyglot persistence. Different microservices should use their own persistence layer that is optimal – relational, nosql, timeseries, event log.

Lagom architecture is based on the book Reactive Services Architecture and that also suggests CQRS. The book proposes service isolation and that composition of systems with microservices should be done asynchronously via message passing.

A quote from the book on why bulkheads failed to save the Titanic:

“The Titanic did use bulkheads, but the walls that were supposed to isolate the compartments did not reach all the way up to the ceiling. So when 6 out of its 16 compartments were ripped open by the iceberg, the ship started to tilt and water spilled over from one compartment to the next, until all of the compartments were filled with water and the Titanic sank, killing 1500 people.”

The suggestion is that for higher availability there should be stricter isolation. The individual (micro)services may fail but the overall system should not be affected. Looking at it this way I think requires one to examine more closely the system design and its invariants.

Take CQRS as an example. In a query system, data is being read and not being modified; a query is a search operation on accumulated data – potentially a very large set with speed (availability) demands. Whereas in a command system, there is more real-time,  perhaps collaborative aspect which leaves most of the data untouched, but creates some new data which needs to be recorded (upload this image, send this message). Why should these two very different operations be served by the same backend ?

One of the systems that has done separation of concerns remarkably well is  AWS. Let’s take the separation of S3 and the database (say Dynamodb). Neither filesystem vendors nor database vendors came up with simple services to solve the problem of an app trying to upload an object and update a database that the object has been uploaded. The failure modes of each service are exposed to the client and the client is not forced to upload files to S3 via a server (bottleneck). S3 offers a read-write consistency for new uploads and eventually consistency for updates. Here the storage object, its universally addressable name, and its properties (backup, encryption, access, versioning, retention policies) are an invariant -a client does not need to fiddle with them apart from being assured of a certain level of service. One can call it an ingestion system.  More on that here.

The takeaway is that microservices should do one thing and do it very well, in a highly available, non-blocking manner. REST services can certainly be non-blocking, but they can also be blocking as described here, which is a problem.

A cornerstone of asynchronous services is messaging. Here’s a talk on Riak, a masterless database and messaging system, running on CloudFoundry, at GE – https://youtu.be/aYaz17qf7cE?t=2161 . It is followed by talks on microservices.

Nvidia nvGraph and Tesla P100 GPU

· 1 Comment ·

“The latest version of NVIDIA’s parallel computing platform gives developers direct access to powerful new Pascal features, including unified memory and NVLink. Also included in this release is a new graph analytics library — nvGRAPH — which can be used for robotic path planning, cyber security and logistics analysis, expanding the application of GPU acceleration into the realm of big data analytics.”

nvGRAPH supports three widely-used algorithms:

Page Rank is most famously used in search engines, and also used in social network analysis, recommendation systems, and for novel uses in natural science when studying the relationship between proteins and in ecological networks.

Single Source Shortest Path is used to identify the fastest path from A to B through a road network, and can also be used for a optimizing a wide range of other logistics problems.

Single Source Widest Path is used in domains like IP traffic routing and traffic-sensitive path planning.

In addition, the nvGRAPH semiring Sparse Matrix Vector Multiplication (SPMV) operations can be used to build a wide range of innovative graph traversal algorithms.

A paper on how to represent cyber attacks as graphs – http://csis.gmu.edu/noel/pubs/2015_IEEE_HST.pdf references the CAPEC, which is a collection of vulnerabilities for such a graph study.

A graphdb represents data using nodes, edges and properties.

graphdatabase_propertygraph

It allows querying with a graph traversal language such as Gremlin. Blazegraph offers a GPU accelerated graphdb. Here’s a graph of machine learning papers from Research Front Maps.

rfmap1

MapD, a GPU accelerated db recently got funding from Nvidia and others.

Elliptic Curve Crypto – an algebraic introduction

· 2 Comments ·

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 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 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- 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. 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 – https://www.youtube.com/watch?v=6eZQu120A80.

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 – https://www.youtube.com/watch?v=vnpZXJL6QCQ .

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 – https://neuromancer.sk/std/secg/

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.

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

S-boxes

· 1 Comment ·

In several crypto systems, there are P-boxes and S-boxes. P-boxes are permutations of input to outputs. What are S-boxes ? I’ve known that they are static maps, used for “confusion” of input to output, have something to do with Galois fields, and that small changes in them affect the crypto properties of a cryptosystem; so they are analyzed by cryptographers in great detail.  Their design is a bit of a black box. Even in cryptol documentation, they are described as a kind of gift from above.

S-box stands for a substitution box.  The goal of the S-box is that for a small change of input there should be a large change in the output – an avalanche.  This property is clearly not true of pure transposition, substitution, vignere pad ciphers  – where a change of an input letter changes exactly one output letter. Because this property is not true, the simple crypto systems can be broken easily by analyzing output/input pairs.

A P-box can be described by a multiplication of the input (symbols, not sequence) with a matrix which is the identity matrix  with its rows transposed (scrambled) according to the permutation order.  So the P-box transform is an invertible linear transform. Can the S-box be another linear transform ? Suppose it were linear. One could give it unit input vectors and determine the rows of the transform, or use Gauss elimination with known input/output pairs.

So one would want this to be non-linear.  In fact, the AES S-box is a sophisticated permutation map – for each byte another unique byte is mapped in a lookup table . Isn’t a permutation linear ?  The key is that the bits of an output byte are not linearly related to the bits of the input byte. Looking at the Substitution-Permutation Network design makes it clear that this property will break Gauss elimination techniques on input/output pairs .

With that, here’s a reference which discusses the finite field math and the transform f_affine( g_finite_field_inverse( input_x ) ) which comprises the S-box design of AES – http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf . The design goal is explicitly to maximize the non-linearity and beat differential attacks which analyze differences of output with input.

The design considers bits as coefficients of a polynomial (1111 = x^3+x^2+x^1+x^0), bytes as degree 7 polynomials and defines an invertible multiplication of two bytes as a map to another byte. Irreducible polynomials over a field are not factorizable over the field. A polynomial presupposes multiplication and addition of elements (multiplication is distinct from addition, and specifically is not repeated addition – adding a number to itself gives zero). For a modulo(prime) finite group, multiplication can be defined using the same modulo operator that defines the group (In G7, 3*5 = 15%7 = 1). A polynomial representation of a byte is a polynomial of (max) degree 7 with coefficients 0 or 1. The multiplication that maps (byte * byte -> byte) can be defined by taking the product polynomial (a polynomial of max degree 14)  then taking modulus via a irreducible byte polynomial of degree 7 or higher (in analogy with modulo group above) to give back a polynomial of max degree less than 7, i.e. a byte. Note the modulus used in AES is a specific polynomial of degree 8, m(x), which is not itself a byte. The division is done with polynomial long division. For more on GF(28) see http://www.cs.utsa.edu/~wagner/laws/FFM.html.

The irreducibility of m(x) of degree 8 implies that the GCD of the product of any two bytes p(x)=a(x).b(x) and m(x) is 1, so m(x) does not cleanly divide any p(x), so the division p(x)/m(x) always has a non-zero remainder for non-zero p(x), hence a non-zero product according to above definition of multiplication. If m(x) were degree 7, then x*m(x)%m(x) = x, so x would map to itself, which is not good. The GCD=1 also implies that each element has a multiplicative inverse. The m(x) chosen is a pentanomial with non-zero terms (8,4,3,1,0) or 100011011 or 0x11B. This design yields modulus math on bytes. So you can raise a byte to the power of n and get back another (well-scrambled) byte.

What a cool secret language. Raising to a power is non-linear. But why choose n=-1 ?

The choice of n=-1 is described in the Rijndael paper here with the reference to Nyberg’94 paper here which carries the line “The author’s attention to the mapping x ->x^-1 was drawn by C. Carlet. He observed that the high nonlinearity property (i) was actually proven in the work of Carlitz and Uchiyama.” The non-linearity  is aimed at defeating linear cryptanalysis where a few input-output pairs can be used to guess the key. The design of the scheme in Nyberg paper is aimed at defeating differential cryptanalysis, by flattening out the variation in the output, so it is close to noise.

Yet, if the letter “s” is common, the corresponding S-box letter (from the lookup table) will also be common. This S-box must be only part of an encryption scheme.

The Nyberg paper has the following line: “However,the high nonlinear order of the inversion mapping and .. comes into effect if these mappings are combined with appropriately chosen linear or affine permutations which may vary from round to round and depend on the secret key.”  A counter paper is here –On Exact Algebraic [Non-]Immunity of S-boxes Based on Power Function

A clear explanation of nonlinearity of a function F as the minimum hamming distance between bytes reachable by linear functions and bytes reachable by the non-linear function F is found in The Design Of S-Boxes by Jennifer Miuling Cheung (2010) p.13.  For two input bits, there are 8 linear functions (1, x1, x2, x1+1, x2+1, x1+x2, x1+x2+1) and 4 input sequences of 00,01,10,11; the output of each of the 8 functions on the 4 input sequences gives 8 output vectors of length 4. But there are 16 vectors of length 4; of these the linear functions reach only 8, the remaining 8 unreachable by linear functions are are termed nonlinear.

This paper, discusses constant time implementations of AES S-Boxes. Instead of a lookup table, they rely on doing the actual multiplication in the finite field: “During the offline phase, we precompute values H,X ·H,X2 ·H,…,X127 ·H. Based on this precomputation, multiplication of an element D with H can be computed using a series of xors conditioned on the bits of D”