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”

AES Pipeline

· Leave a comment ·

AES divides the input into chunks of 128 bits. 128 bits is 16 bytes. 16 bytes can be arranged in a 4×4 matrix and are represented in this two dimensional form by AES. This matrix is called the “state”.

Using cryptol, the AES algorithm is described with the following functions

AESRound : (RoundKey, State) -> State

AESRound (rk, s) = AddRoundKey (rk, MixColumns (ShiftRows (SubBytes s)))

The final round leaves out the MixColumns transform.

AESFinalRound : (RoundKey, State) -> State
AESFinalRound (rk, s) = AddRoundKey (rk, ShiftRows (SubBytes s))

The inverse transform is as follows

AESInvRound : (RoundKey, State) -> State

AESInvRound (rk, s) =
InvMixColumns (AddRoundKey (rk, InvSubBytes (InvShiftRows s)))

AESFinalInvRound : (RoundKey, State) -> State

AESFinalInvRound (rk, s) = AddRoundKey (rk, InvSubBytes (InvShiftRows s))

ASN1 Types

· Leave a comment ·

ASN1 is a data interoperability format that is widely used in directory, security and network management systems. Data is stored in triplets of TLV – type, length, value (in BER, DER encoding rules). TLV allows a format that is efficient, recursive and self-describing.

The type system is the interesting aspect. A “type” is a descriptor for the data, that the TLV triplet holds. The “type” is stored as a sequence of one or more bytes. This sequence can be as small  as a single byte or be as large as needed (unlimited length). In case of a single byte “type”, the bits 7,8 represent the class of the type (4 classes exist), bit 6 represents whether type is single atomic data element or nested, and bits 5-1 encode the tag of the type.  This single byte type can hold tags from 0 to 30. If the type is outside this range 0-30, the 5 to 1 bits are set to 1, and the actual tag starts in the following bytes of the now multi-byte type. In case of multi-byte “types”, the most significant bit of each byte must be 1, except for the last byte, which must be 0.

There are atomic types and component types.

Atomic types include OBJECT IDENTIFIER types and various strings (bits, ascii, octet), integers, null .

Component types include the ordered SEQUENCE and the unordered SET, both of which types can contain one or more occurrences of different types of data. SEQUENCE OF and SET OF are component types which contain zero or more occurrences of the same types of data.

There is potential for ambiguity as to whether an Object Identifier (OID) in the tagged notation is described as a multi-byte type since the OID is itself multi-byte. It is not, it is described as a single byte ASN1 type with tag = 06 as described in the tag table here and clarified by this Microsoft example of an OID encoding. So the OID value sits in the value field of the TLV triplet, not in the type.

An example of the encoding for RSA private key in PKCS#1 is here.

oid-info.com allows lookup of Object Identifiers. Here is a tree display for RSA private key which has OID 1.2.840.113549.1.1.1 – http://oid-info.com/cgi-bin/display?oid=1.2.840.113549.1.1.1+&submit2=Tree+display

What are examples of multi-byte ASN1 types ?  The EMV format used in payments and smartcards use two-byte types.

The “abstract” in the name came from a contrast to “transfer syntax notation” which is the on-wire format. The “abstract syntax” maps to “transfer syntax” via encoding rules.

For comparison, consider the XDR scheme used in SunRPC. Here the types (metadata) are not included within the protocol as tags, but defined externally in a .x file which is an input to an rpcgen compiler. Protobuf and capnproto also use external medata in a .proto file. ASN1 now supports Packed Encoding Rules (PER) which remove the tag information for greater compactness and efficiency.  Finally, while ASN1 continues to be used for highly structured information, the rapid growth of JSON/REST protocols in the identity space has been interesting.

The ‘DROWN’ attack on SSL and its extension to QUIC

· Leave a comment ·

The DROWN attack was recently shown to cause HTTPS sites supporting SSLv2 to be vulnerable to MITM attacks. An attack extension to QUIC is discussed in section 7 of their paper, along the same lines referenced earlier, which makes it relevant to current discussions of TLS.

Some background. Consider a simple encryption scheme that encrypts a message M to a ciphertext C. Should it always encrypt M to C ? One might think yes. But if yes, then an attacker could create his own extensive tables of encryptions of messages (Mi->Ci) , and then lookup the encrypted (intercepted) message Ci and infer what Mi was. Second, even if there is not a lookup hit, then the maps so collected could be used to deterministically modify Ci, to match another valid Mi.  This latter property is called malleability of encryption. Malleability may be desirable in some cases (homomorphic encryption), but in general it weakens encryption.

So determinism is bad and we want to make the encryption non-deterministic. We can do so by adding some random bytes to beginning of the message every time we encrypt. After decryption, we remove those random bytes and get back our message. These random bytes are called an initialization vector, or also called ‘padding‘.

The way padding is added, is important. If the attacker is able to infer that certain messages do not decrypt to the expected padding format (via error messages returned from the server), then he can narrow the range of valid messages. A ‘padding oracle’ is a server that freely answers whether an encrypted message is correctly padded or not. This is the basis of the Bleichenbacher attack.

The SSLv2 servers are using an old form of the RSA which is unpadded, deterministic and malleable. This property is the basis of many attacks, that involve a protocol downgrade (e.g. a PFS cipher to RSA cipher, or TLS to SSL) , or attack a known weak protocol. The Breach attack used the fact that compression changed the size of a message in a predictable way to infer bytes of a key. Compression is disabled in TLS1.2.

But why should this attack be possible with newer protocols like QUIC ? QUIC does not even support PKCS#1 v1.5 encryption.

QUIC achieves low latency by caching TLS state on the client. If any part of the protocol is using a deterministic behaviour it can be exploited. The Jager paper makes the following observations. 1. The server authentication is performed only in the connect phase, not in the repeat phase.  and 2. The signed SCFG message is made independent of the client request, which makes it possible for the server or an attacker to precompute it. So, there is exploitable determinism.

Certain fixes have been proposed in QUIC v31, to switch the server signature from a static signature of the server config to a signature of the server config with a hash of the client hello message. This is claimed to eliminate the DROWN vulnerability.

Erlang ‘for’ and ‘if’

· Leave a comment ·

When thinking of immutable state, I imagine a large

input->[processingbox]->output

box being broken into a chain of multiple smaller mini-boxes,

input0->[pbox0]->output0 -> [pbox1]->output1 ->[pbox2]->output3

with each individual box accomplishing a change in its input to its output, without keeping any internal mutable state.

Which reminds me of Linear-Time-Invariant systems. As long as each part of the system is linear and time-invariant, a large system can be composed of simpler parts and still be analyzed by deriving a composite transfer function. The composite system can be studied for its stability and loss/gain characteristics and adjustments made in the system design.

I suspect a similar payoff occurs with functional programming. But it is not so clearly stated or visible in the ability to analyze large programs. Erlang is essentially a version of event driven programming. The conciseness of expression is encouraging, but I hope to arrive at good examples of program composition.

Meanwhile the ‘if’ statement in erlang is a curveball. In addition to the odd syntax, and statements like true->false, one finds one cannot place a log statement anywhere inside a set of statements to see what’s going on. Punctuation rules. The trick is to place the log a comma before the last expression before the semicolon.

if
   Val >= Left andalso Val =< Right ->
   io:format("==> ok~p<~p<~p\n\n",[Left,Val,Right]),
   true;

   true ->
   io:format("==>not ok ~p<~p<~p\n\n",[Left,Val,Right]),
   false
end.

The semicolons indicate different phrases which are pattern-matching options. The commas are continued statements within the same phrase. The last statement in the phrase is the return value. The last phrase is typically a catch-all, in this case returning a value of false. The case statement is more commonly used than the if. The -> denotes  ‘lhs condition is mapped to rhs’ .

The ‘for’ statement does not exist at all and below are alternatives.

foreach(Fun, List)->ok, %% just applies a function Fun to each element of a list
foldl(Fun, Accumulator, List)-> Acc1,  %% fold list left to right into an accumulator
foldl(Fun, Accumulator, List)-> Acc1 %% fold list right to left into an accumulator
map(Fun, List1) -> List2  %% maps a list to a new list

The = sign in erlang is used for (a) immutable assignment of a term to a value and (b) for comparing if a previously assigned term or expression of terms is the same as another term or value – this is called pattern matching. One cannot reassign a term to a new value, so the math notion of equality always holds. The = used in C/Java could be called mutable assignment, every variable is hiding within it mutable state. A term in erlang does have an internal state of bound or unbound. On a successful pattern match any unbound variable becomes bound.

1> [H|T] = [1,2,3].

2> io:write(H) .

To generate a list of numbers, like range(n) in python, there is lists:seq(1,n). io:fwrite(“~p”, [lists:seq(1,20)]).

The philosophy behind some of these decisions is discussed here https://news.ycombinator.com/item?id=13499377. An objective is to make it impossible to write runaway loops – to make the runtime system always be able to recover and reallocate its cycles. A related aspect is to let-it-fail and not write a lot of exception handling, defensive code.

My erlang work was done while modifying RabbitMQ (written in erlang) to support features for certificate based authentication for MQTT, while consulting at GE Predix.

Erlang OTP (for Open Telecom Platform) is a layer on top of erlang language and proposes design principles for organizing code including ideas around failure handling with supervision trees. These form the basis of the actor model, where code is structured as isolated processes that communicate by sending and receiving messages. The actor can crash but is supervised by another actor. More in https://www.brianstorti.com/the-actor-model/ .

Tail recursion in erlang with an accumulator, is used as a replacement for loops – https://learnyousomeerlang.com/recursion

‘Tail recursion is a way to transform a linear process (it grows as much as there are elements) to an iterative one (there is not really any growth).’

Whatsapp talk on Engineering for Scale mentions Erlang allows hot-swapping and loose coupling because of message queues everywhere, and after fixing a bug looking for places where contagion spread, meaning there was not enough loose coupling there – https://developers.facebook.com/videos/f8-2016/a-look-at-whatsapp-engineering-for-success-at-scale

Bytecode VMs

· Leave a comment ·

I came to be looking at different language VMs recently- Erlang BEAM and the Smalltalk VM. Smalltalk VM was a bytecode based stack VM (just like Java VM), and likely influenced the VM of Erlang. 

Java bytecode verification checks (and their vulnerabilities in bytecode loaders) are well known, but the security characteristics of other VMs and even languages running on JVM is less well known (clojure/scala ?).

BEAM is the Erlang VM (Bogdan/Björn’s Erlang Abstract Machine). It is the successor of JAM (Joe’s Abstract Machine) which was inspired by Prolog WAM. Details on it are found in the Hitchhiker’s Tour of BEAM, with ways to crash the BEAM VM such as creating too many atoms (which never get deleted). BEAM can run on bare-metal on XEN – http://erlangonxen.org . The format is described as based on EA IFF 85 – Standard for Interchange Format Files with a FOR1 starting 4 bytes. Here’s the full 6k lines of beam_load.c .

The code-to-BEAM-bytecode processing pipeline is described here as including a preprocessing step (see -E, -S, -P options to erlc). An interesting problem of peeking and pattern-matching inflight messages is discussed here. I find it interesting to think what would happen if one froze an erlang VM to see all inflight messages – like putting a breakpoint in the kernel. The way to get a stacktrace is erlang:get_stacktrace()

The hot-swapping capability is worrying, coming from the objective-c world that had code-signing to lock down changes. Erlang does have a strong process isolation model.

This article on Dart makes the case for non-bytecode VMs with the following  line “When your VM’s input is program source code, it can rely on the grammar of the language itself to enforce important invariants”. Sounds relevant to byte-code VMs as well.

Brief history of cloud time

· Leave a comment ·

Amazon Web Services (AWS) started with elastic and scalable compute and storage offerings – an elastic compute cloud (EC2) and a simple storage service (S3). EC2 was based on virtual machines. S3 was a simple key value store with an object store backend.

Heroku came up with a deploy an app with a single command line model – heroku deploy. It would allow automation of deployment of rails apps. It was an early example of a platform as a service (PAAS). The app ran in a virtualized linux container called a dyno.

NASA engineers wanted to store and process big data and tasked an internal team and Rackspace to build a web application framework for it. When they tried to use the existing aws offerings, they found the time to upload the data to AWS would take too long. They came up with their own implementation to manage virtual machines and handle storage, with openstack. It provided EC2 and S3 like apis and worked with certain hypervisors.

Greenplum which is a big data company acquired by EMC, wanted a framework to make use of big data easily. EMC had brought VMware which brought Cloudfoundry. Greenplum worked with VWware and a dev company pivotal labs to build up Cloudfoundry as a mechanism to deploy apps so they could be scaled up easily. Pivotal got acquired by VMware and later spun out as Pivotal Cloudfoundry to provide enterprise level support to the open source cloudfoundry offering.  This had participation from EMC, VMWare (both were one already), and a third participant – GE with an interest to build an industrial cloud.   Cloudfoundry forms the basis of the GE predix cloud.

Cloudfoundy is now a 3rd gen PAAS which works on top of an IAAS layer such as openstack or vmware vsphere or even docker containers running locally via a Cloud Provider Interface (CPI).

Another interesting project is Apache Geode, an in-memory database along the lines of Hana.

Meanwhile Amazon and Azure increase the number of webservices  available rapidly as well as reducing their costs.

There was a meetup on Ranger recently at Pivotal labs which discussed authorization for various components in the Hadoop ecosystem, including Kafka.

OAuth Threat Model, Mobile and Oracle Mobile Security Suite

· Leave a comment ·

Researchers in Germany recently found two previously unknown vulnerabilities in OAuth2.0, in the publication A Comprehensive Formal Security Analysis of OAuth 2.0.

An extensive OAuth thread model RFC 6819 exists. A SAML threat model by OWASP is discussed in – On Breaking SAML: Be whoever you want to be. OAuth and SAML protocols serve as prototypes for OpenId Connect protocol – which implements an authentication layer as an extension of authorization layer of OAuth2 and has a similar threat model. The above two vulnerabilities occur in both OAuth2 and OpenID Connect.

In the Microsoft paper, OAuth demystified for Mobile Application Developers, the authors discussed why OAuth is so easy to get wrong for mobile apps – it was originally designed for websites, not mobile. The browser redirection step that OAuth heavily relies on, cannot be performed securely on iOS in the general case. Moreover the complexity of the protocol means that out of 149 apps tested, 60% were faulty and vulnerable.

This is interesting because in the Oracle Mobile Security Suite we developed at BitzerMobile, these problems were addressed in a bulletproof manner for enterprise applications, by wrapping web access protocols into a simpler challenge response protocol that was injected securely into mobile apps. The app and the device are authenticated independently of the user. This reduces the attack surface considerably, for a common use.

A useful summary of attacks and countermeasures from OAuth and OpenID Connect Risks and Vulnerabilities follows:

Attack Category Countermeasures
Extracting credentials or tokens in captured traffic TLS encryption
Impersonating authorization server or resource server TLS server authentication
Manufacturing or modifying tokens Issue tokens as signed JWTs
Redirect manipulation Require clients to declare redirect URIs during registration
Guessing or interception of client credentials Use signed JWTs for client authentication
Client session hijacking or fixation Use the State parameter to ensure continuity of client session throughout the OAuth flow

The Relying Party (RP), aka Client (in unfortunately overloaded OAuth parlance), aka ‘Relying’ Service Provider (in Kerberos parlance), is a third party service which needs access. It may not have an incentive to follow the protocol intent (e.g. enforce adequate controls). Or it may willing to accept more data than the protocol intended.

The latter is the case in the first attack, where the IDP sends a 307 temporary redirect resulting in password form data being sent to the RP. The RP receives the user creds. The fix is to use a 302 Found.

The second attack has to do with HTTPS not being used in the path between the user and the RP, which allows a MITM to manipulate the request and send it to an Attacker IDP instead of the Honest IDP. The fix is for the RP to use HTTPS instead which is immune to MITM (but who enforces this ? the redirect is too quick for the user to inspect the site certs).

Note: OAuth terminology becomes clearer to an enterprise mindset by expanding the terms auth server, resource owner, resource server, client. The “client” is an untrusted service w.r.t. user creds but needs temporary access to HTTP resources. Instead of using the “resource owners” username/password, it  must acquire an access_token for this access.  In correspondence with Kerberos/SAML, the functional roles are

1. Identity Provider (=IDP =auth server = KDC. e.g. twitter, fb as a pure login service),

2. Trusted Server (=resource server, that is in same trust zone as IDP. e.g. twitter tweets/profile, fb photos/profile),

3. Relying Service ( a delegate service that wants to provide additional functionality using data from Trusted Service and user identity from IDP, e.g. filter tweets, mash photos, partner HR app; called client in OAuth). The client_id/client_secret are created for this entity – a bit like an independent KDC principal name. The client is a Relying Service which is in a different trust domain from the IDP/Trusted Service and needs an access token. This Relying Service may need to authenticate itself to the Trusted Service – which is done using a client_secret, in cases where the RS can keep a secret (i.e. in web apps, not mobile and browser based apps). One would need as many clients_ids as the number of clients that lie in independently revocable auth domains.

4. the User (=resource owner, a person or organization who has credentials/data stored in the IDP/TS and desires use of the Relying Service with existing IDP credentials).  The “authorization grant” is a  credential that identifies the user and correspond to the Kerberos Ticket Granting Ticket aka TGT.

There are four oauth authorization grant types: authorization_code, implicit, resource owner, client_credentials. Authorization_code authenticates both user and client. Implicit authenticates only the user, not the client (no client_secret, no authorization grant). In Resource_owner the client does authenticate itself, but gets the access token directly. Client credentials (RS-TS) is the simplest one and is used for M2M communications, here the client is acting on its own behalf, not the user. The type depends on the method used by the client to request authorization and the types supported by the authorization server.

The difference from the NFS/KDC case is that in the NFS case the additional (server) principals is created for the NFS server, not the NFS client. The focus in NFS is on not sending the password over the wire. In OAuth the focus is on not giving the password to the client.

Let’s Encrypt. Less Green ?

· Leave a comment ·

Letsencrypt.com is a service conceived to reduce the friction in enabling HTTPS on a website, by automating SSL certificate creation, validation, signing, installation and renewal. The server certificate setup which used to take hours can be done in a minute. Encryption will reduce the incidence of man-in-the-middle (MITM) attacks, which can easily insert or modify the javascript in transit.

Some of this is driven by Mozilla and its large public backers with perhaps an interest in showing the green bar and lock for more websites. A self-signed cert would also provide free encryption, prevent MITM attacks and be easy to setup but would throw an untrusted connection alert to the user.

So is LetsEncrypt encryption enough to show a green bar for a website ? Because regular certification schemes require a purchase, one has to go through a credit card verification step before being issued their cert. Certs with Extended Validation have more steps to go through. There are three types of certs based on level of validation – DV, OV, EV. Doman Validation (DV) does not try to check identity of the user and is what LetsEncrypt automates using a challenge-response scheme. Clicking on websites which use LetsEncrypt DV confirms that they display a green lock/bar (using firefox).

The problem with a widely accepted CA which has a zero cost barrier for setting up HTTPS is similar to that with the free precursor to OpenDNS.  A number of less than trustworthy websites can set themselves up as mirror images of trustworthy websites and send phishing attacks by email or sms, and an end-user has no way of telling the difference. Here’s a link on how to do just such a phishing attack with LetsEncrypt. So is LetsEncrypt making the web less secure ?

It’s true that the large number of CAs with their diverse validation mechanisms makes the existing scheme not so great – especially when CAs are compromised and/or issue bad certs (e.g Superfish, Comodo, NIC). However one could inspect the CA trusted authority and if there was reason to believe it is not trustworthy – e.g. see this pic (Chris Palmer), one could avoid clicking the link.

I think the average user should receive a better visual indication on the level of trust provided by a LetsEncrypt cert that has undergone a lower level of validation by design. Use a less green color ?

End users should be more aware of the certification process and get into the habit of explicitly checking Cert chains for HTTPS by clicking on the green lock displayed next to the URL.

Update: The owner field is not defined in a Domain Validated cert like ones issued by LetsEncrypt. https://superuser.com/questions/1042383/how-to-set-the-owner-of-certificate-generated-by-lets-encrypt

Cloud Access Security Brokers

· Leave a comment ·

Skyhigh Networks which was mentioned in my previous post  is one example of a Cloud Access Security Broker. There are several other companies in this field – NetSkope, Bitglass, Palerra, CipherCloud, Elastica, Adallom, Zscaler, some more familiar than others.

Gartner says the penetration will be 25% in the enterprise in 2016. Here’s a comparison table.

There is considerable scope for innovation in this space based on different user requirements – for instance the amount and type of sharing of the data affects the architecture. Homomorphic encryption while theoretically possible is not yet practical. I expect to see more differentiation before consolidation of different technologies in the domain.

Real World Crypto 2016

· 2 Comments ·

SSL/TLS dominated the conference with talks on its use at FB, Google, Amazon and modifications in the direction of TLS 1.3, with presentations on  QUIC, OPTLS, S2N and more, covering things like lower latency, forward secrecy, better ciphers. Some of the optimizations can have an impact on data center operations efficiency.

The timing attack on S2N protocol was interesting – the KL divergence measures the difference between two probability distributions and can be used to leak information from an SSL stream.

Privacy preserving operations on encrypted data (Skyhigh) talk was also interesting. Paul Grubbs discussed searchable symmetric encryption tradeoffs and open questions around a stateless SSE. In case of an encryption proxy, who maintains it ? The client would find it cumbersome. So an encrypted index is maintained by Skyhigh. This is not easy to manage. Also if one wants *both* security and privacy the search times and/or the number of roundtrips goes up.

Cryptol is a software from Galois to simulate ciphers and is useful to model, verify and even implement them. It is written in Haskell and is open source. It comes with several examples including the Enigma cipher. I tried this and will blog about it later.

I expected some presentations on DNS security – e.g. DNSSEC and DANE; talked to attendees from Verisign on their offerings (ddos monitoring, threat intelligence graph). DNS operates over IP (vs an out-of-band method for updates/insertions); with DNSSEC the DNS server needs to trust the same CA as the origin server which feeds it the DNS record. The general feeling I think is the trust problem has to be solved at the application layer and attacks like the Kaminsky attack have been mitigated against.

Here’s a diagram of the QUIC protocol. The claim is zero RTT for a repeat (secure) connection to the server (75% of the time), by combining TCP and SSL handshakes into one and caching state on the client. A practical attack on QUIC is discussed in this paper, a type of adaptive chosen ciphertext attack, which references this paper by Zhang, Reiter et al, discussing more general PAAS attacks including an SAML SSO attack.

Perfect forward secrecy definition: A public-key system has the property of forward secrecy if it generates one random secret key per session to complete a key agreement, without using a deterministic algorithm  .

If the attacker starts recording SSL sessions and later gets a compromised server private key, he can decrypt the sessions, without forward secrecy. With TLS 1.2 forward secrecy is optional and with session resumption optimization it is effectively disabled. TLS1.3 mandates forward secrecy with DH key exchanges.

Spark and Scala

· Leave a comment ·

Spark is a general-purpose distributed data processing engine that is used for for variety of big data use cases – e.g. analysis of logs and event data for security, fraud detection and intrusion detection. It has the notion of Resilient Distributed Datasets. The “resilience” has to do with lineage of a datastructure, not to replication. Lineage means the set of operators applied to the original datastructure. Lineage and metadata are used to recover lost data, in case of node failures, using recomputation.

Spark word count example discussed in today’s meetup.

val textfile = sc.textFile("obama.txt")
val counts = textFile.flatMap(line=>line.split(" ")).filter(_.length>4).map(word=>(word,1)).reduceByKey(_+_)
val sortedCounts = counts.map(_.swap).sortByKey(false)
sortedCounts.take(10)

Scala is a functional programming language which is used in Spark. It prefers immutable datastructures. Sounds great! How are state changes done then ? Through function calls. Recursion has a bigger role to play because it is a way for state changes to happen via function calls. The stack is utilized for the writes, rather than the heap. I recalled seeing a spiral scala program earlier and found one here on the web. Modified it to find the reverse spiral. Here’s the resulting code. The takeaway is that functional programs are structured differently – one could do some things more naturally. It feels closer to how the mind works. As long as one get the base cases right, one can build large amount of complexity trivially. On the other hand, if one has to start top down and must debug a large call stack, it could be challenging.

// rt annotated spiral program.
// source http://www.kaiyin.co.vu/2015/10/draw-plain-text-spiral-in-scala.html
// reference: http://www.cis.upenn.edu/~matuszek/Concise%20Guides/Concise%20Scala.html
// syntax highlight: http://bsnyderblog.blogspot.com/2012/12/vim-syntax-highlighting-for-scala-bash.html
import java.io.{File, PrintWriter}
import scala.io.Source

object SpiralObj {   // object keyword => a singleton object of a class defined implicitly by the same name
  object Element {   // subclass. how is element a singleton ? there are several elements. has 3 subclasses which are not singetons
    private class ArrayElement(  // subsubclass, not a singleton
                                val contents: Array[String]  // "primary constructor" is defined in class declaration, must be called
                                ) extends Element
    private class LineElement(s: String) extends Element {
      val contents = Array(s)
    }
    private class UniformElement(  // height and width of a line segment. what if we raise width to 2. works.
                                  ch: Char,
                                  override val width: Int,   // override keyword is required to override an inherited method
                                  override val height: Int
                                  ) extends Element {
      private val line = ch.toString * width  // fills the characters in a line
      def contents = Array.fill(height)(line) // duplicates line n(=height) times, to create a width*height rectangle
    }
    // three constructor like methods
    def elem(contents: Array[String]): Element = {
      new ArrayElement(contents)
    }
    def elem(s: String): Element = {
      new ArrayElement(Array(s))
    }
    def elem(chr: Char, width: Int, height: Int): Element = {
      new UniformElement(chr, width, height)
    }
  }


  abstract class Element {
    import Element.elem
    // contents to be implemented
    def contents: Array[String]

    def width: Int = contents(0).length

    def height: Int = contents.length

    // prepend this to that, so it appears above
    def above(that: Element): Element = {      // above uses widen
      val this1 = this widen that.width
      val that1 = that widen this.width
      elem(this1.contents ++ that1.contents)
    }

    // prefix new bar line by line
    def beside(that: Element): Element = {     // beside uses heighten
      val this1 = this heighten that.height
      val that1 = that heighten this.height
      elem(
        for ((line1, line2) <- this1.contents zip that1.contents)
          yield line1 + line2
      )
    }

    // add padding above and below
    def heighten(h: Int): Element = {          // heighten uses above
      if (h <= height) this
      else {
        val top = elem(' ', width, (h - height) / 2)
        val bottom = elem(' ', width, h - height - top.height)
        top above this above bottom
      }
    }

    // add padding left and right
    def widen(w: Int): Element = {             // widen uses beside
      if (w <= width) this
      else {
        val left = elem(' ', (w - width) / 2, height)
        val right = elem(' ', w - width - left.width, height)
        left beside this beside right
      }
    }

    override def toString = contents mkString "\n"
  }


  object Spiral {
    import Element._
    val space = elem("*")
    val corner1 = elem("/")
    val corner2 = elem("\\")
    def spiral(nEdges: Int, direction: Int): Element = { // clockwise spiral
      if(nEdges == 0) elem("+")
      else {
        //val sp = spiral(nEdges - 1, (direction + 1) % 4) // or (direction - 1) % 4, but we don't want negative numbers
        val sp = spiral(nEdges - 1, (direction + 3) % 4) // or (direction - 1) % 4, but we don't want negative numbers
        var verticalBar = elem('|', 1, sp.height)        // vertBar and horizBar have last two params order switched
        var horizontalBar = elem('-', sp.width, 1)
    val thick = 1
        // at this stage, assume the n-1th spiral exists and you are adding another "line" to it (not a whole round)
        // use "above" and "beside" operators to attach the line to the spiral
        if(direction == 0) {
          horizontalBar = elem('r', sp.width, thick)
          (corner1 beside horizontalBar) above (sp beside space) //  order is left to right
        }else if(direction == 1) {
          verticalBar = elem('d',thick, sp.height)
          (sp above space) beside (corner2 above verticalBar)
        } else if(direction == 2) {
          horizontalBar = elem('l', sp.width, thick)
          (space beside sp) above (horizontalBar beside corner1)
        } else {
          verticalBar = elem('u',thick, sp.height)
          (verticalBar above corner2) beside (space above sp)
        }
      }
    }

    def revspiral(nEdges: Int, direction: Int): Element = { // try counterclockwise
      if(nEdges == 0) elem("+")
      else {
        //val sp = spiral(nEdges - 1, (direction + 1) % 4) // or (direction - 1) % 4, but we don't want negative numbers
        val sp = revspiral(nEdges - 1, (direction + 3) % 4) // or (direction - 1) % 4, but we don't want negative numbers
        var verticalBar = elem('|', 1, sp.height)        // vertBar and horizBar have last two params order switched
        var horizontalBar = elem('-', sp.width, 1)
    val thick = 1
        // at this stage, assume the n-1th spiral exists and you are adding another "line" to it (not a whole round)
        if(direction == 0) { // right
          horizontalBar = elem('r', sp.width, thick)
          (sp beside space) above (corner2 beside horizontalBar)
        }else if(direction == 1) { // up
          verticalBar = elem('u',thick, sp.height)
          (space above sp) beside (verticalBar above corner1)
        } else if(direction == 2) { // left
          horizontalBar = elem('l', sp.width, thick)
          (horizontalBar beside corner2 ) above (space beside sp) 
        } else { // down
          verticalBar = elem('d',thick, sp.height)
          (corner1 above verticalBar) beside (sp above space)
        }
      }
    }
    def draw(n: Int): Unit = {
      println()
      println(spiral(n, n % 4))  // %4 returns 0,1,2,3 .    right, down, left, up
      println()
      println(revspiral(n, n % 4))  // %4 returns 0,1,2,3   
    }
  }
}

object Main {
  def usage() {
      print("usage: scala Main szInt");
  }

  def main(args: Array[String]) {
    
    import SpiralObj._
    if(args.length > 0) {
        val spsize = args(0)
        Spiral.draw(spsize.toInt)
    } else {
    usage()
        println()
    }
  }
}


A note on tail-call recursion. If the last statement of function is a call to another function, then the return position of the called function is the same as that of the calling function. The current stack position is valid for the called function. Such a function is tail recursive and the effect is that of a loop – a series of function calls can be made without consuming stack space.