Imperfect Forward Secrecy – The Failure of Diffie-Hellman Key Exchange

Diffie-Hellman key exchange, also called exponential key exchange, is a method of digital encryption that uses numbers raised to specific powers to produce decryption keys on the basis of components that are never directly transmitted, making the task of a would-be code breaker mathematically overwhelming.

Let’s say Alice and Bob want to communicate with each other without John knowing what they’re saying or sending. Anything Alice sends to Bob, John will receive, likewise, anything Bob sends to Alice, John will also receive. So how do Alice and Bob send anything to each other without John understanding? Well that’s where Diffie-Hellman comes in.

To start, Alice and Bob decide publicly (John will also get a copy) on two prime numbers, g and n. Generally g is a small prime number and n is quite large, usually 2000 or more commonly 4000 bits long. So now Alice, Bob and John all know these numbers.

Now Alice decides secretly on another number, a. and Bob decides secretly on a number, b. Neither Alice nor Bob send these numbers, they are kept to themselves. Alice performs a calculation, g ^ a mod n, we’ll call this A, since it comes from a. Bob then performs g ^ b mod n which we’ll call B.

Alice sends Bob, A, and Bob sends Alice, B. Note John now has 4 numbers, A, B, g and n but not a or b. Finally, for the heart of the trick. Alice takes Bob’s and performs B ^ a mod n. Similarly, Bob takes Alice’s A and performs A ^ b mod n. This results in the same number i.e. B ^ a mod n = A ^ b mod n. They now have a shared number. Notice how John can’t figure out what these numbers are from the numbers he’s got.

Actually he can and its given a name called solving the discrete log problem. If we make n very large this becomes an extremely computationally heavy problem to solve and simply isn’t worth the time to figure out. John would have to figure out a or b from A or B which is simply far too time consuming.

So what can Alice and Bob do with this key they’ve just created together? Well they can use it to start encrypting messages they send to each other. A very simple example that should not be used anywhere as it’s extremely insecure is in encrypting their messages with a shift cipher (Caesar cipher) where the shift value is determined by the newly generated key. Both Alice and Bob can encrypt and decrypt the messages as they know the shift value but John can’t as he doesn’t have the key.

Diffie-Hellman key exchange is a cornerstone of applied cryptography, but it is often less secure than widely believed. The problems stem from the fact that the number field sieve for discrete log allows an attacker to perform a single precomputation that depends only on the group, after which computing individual logs in that group has a far lower cost. Although this fact is well known to cryptographers, it apparently has not been widely understood by system builders. Likewise, many cryptographers did not appreciate that the security of a large fraction of Internet communication depends on Diffie-Hellman key exchanges that use a few small, widely shared groups.

A key lesson from this state of affairs is that cryptographers and creators of practical systems need to work together more effectively. System builders should take responsibility for being aware of applicable cryptanalytic attacks. Cryptographers, for their part, should involve themselves in how crypto is actually being applied, such as through engagement with standards efforts and software review. Bridging the perilous gap that separates these communities will be essential for keeping future systems secure.

Untitled

The Logjam attack: A man-in-the-middle can force TLS clients to use export-strength DH with any server that allows DHE_EXPORT. Then, by finding the 512-bit discrete log, the attacker can learn the session key and arbitrarily read or modify the contents. Datafs refers to False Start application data that some TLS clients send before receiving the server’s Finished message.

imperfect forward secrecy

Why Can’t There Be Infinite Descending Chain Of Quotient Representations? – Part 3

 

8cmbD

For a quiver Q, the category Rep(Q) of finite-dimensional representations of Q is abelian. A morphism f : V → W in the category Rep(Q) defined by a collection of morphisms fi : Vi → Wi is injective (respectively surjective, an isomorphism) precisely if each of the linear maps fi is.

There is a collection of simple objects in Rep(Q). Indeed, each vertex i ∈ Q0 determines a simple object Si of Rep(Q), the unique representation of Q up to isomorphism for which dim(Vj) = δij. If Q has no directed cycles, then these so-called vertex simples are the only simple objects of Rep(Q), but this is not the case in general.

If Q is a quiver, then the category Rep(Q) has finite length.

Given a representation E of a quiver Q, then either E is simple, or there is a nontrivial short exact sequence

0 → A → E → B → 0

Now if B is not simple, then we can break it up into pieces. This process must halt, as every representation of Q consists of finite-dimensional vector spaces. In the end, we will have found a simple object S and a surjection f : E → S. Take E1 ⊂ E to be the kernel of f and repeat the argument with E1. In this way we get a filtration

… ⊂ E3 ⊂ E2 ⊂ E1 ⊂ E

with each quotient object Ei−1/Ei simple. Once again, this filtration cannot continue indefinitely, so after a finite number of steps we get En = 0. Renumbering by setting Ei := En−i for 1 ≤ i ≤ n gives a Jordan-Hölder filtration for E. The basic reason for finiteness is the assumption that all representations of Q are finite-dimensional. This means that there can be no infinite descending chains of subrepresentations or quotient representations, since a proper subrepresentation or quotient representation has strictly smaller dimension.

In many geometric and algebraic contexts, what is of interest in representations of a quiver Q are morphisms associated to the arrows that satisfy certain relations. Formally, a quiver with relations (Q, R) is a quiver Q together with a set R = {ri} of elements of its path algebra, where each ri is contained in the subspace A(Q)aibi of A(Q) spanned by all paths p starting at vertex aiand finishing at vertex bi. Elements of R are called relations. A representation of (Q, R) is a representation of Q, where additionally each relation ri is satisfied in the sense that the corresponding linear combination of homomorphisms from Vai to Vbi is zero. Representations of (Q, R) form an abelian category Rep(Q, R).

A special class of relations on quivers comes from the following construction, inspired by the physics of supersymmetric gauge theories. Given a quiver Q, the path algebra A(Q) is non-commutative in all but the simplest examples, and hence the sub-vector space [A(Q), A(Q)] generated by all commutators is non-trivial. The vector space quotientA(Q)/[A(Q), A(Q)] is seen to have a basis consisting of the cyclic paths anan−1 · · · a1 of Q, formed by composable arrows ai of Q with h(an) = t(a1), up to cyclic permutation of such paths. By definition, a superpotential for the quiver Q is an element W ∈ A(Q)/[A(Q), A(Q)] of this vector space, a linear combination of cyclic paths up to cyclic permutation.

The Case of Morphisms of Representation Corresponding to A-Module Holomorphisms. Part 2

1-s2.0-S0001870811003495-fx003

Representations of a quiver can be interpreted as modules over a non-commutative algebra A(Q) whose elements are linear combinations of paths in Q.

Let Q be a quiver. A non-trivial path in Q is a sequence of arrows am…a0 such that h(ai−1) = t(ai) for i = 1,…, m:

Untitled

The path is p = am…a0. Writing t(p) = t(a0) and saying that p starts at t(a0) and, similarly, writing h(p) = h(am) and saying that p finishes at h(am). For each vertex i ∈ Q0, we denote by ei the trivial path which starts and finishes at i. Two paths p and q are compatible if t(p) = h(q) and, in this case, the composition pq can defined by juxtaposition of p and q. The length l(p) of a path is the number of arrows it contains; in particular, a trivial path has length zero.

The path algebra A(Q) of a quiver Q is the complex vector space with basis consisting of all paths in Q, equipped with the multiplication in which the product pq of paths p and q is defined to be the composition pq if t(p) = h(q), and 0 otherwise. Composition of paths is non-commutative; in most cases, if p and q can be composed one way, then they cannot be composed the other way, and even if they can, usually pq ≠ qp. Hence the path algebra is indeed non-commutative.

Let us define Al ⊂ A to be the subspace spanned by paths of length l. Then A = ⊕l≥0Al is a graded C-algebra. The subring A0 ⊂ A spanned by the trivial paths ei is a semisimple ring in which the elements ei are orthogonal idempotents, in other words eiej = ei when i = j, and 0 otherwise. The algebra A is finite-dimensional precisely if Q has no directed cycles.

The category of finite-dimensional representations of a quiver Q is isomorphic to the category of finitely generated left A(Q)-modules. Let (V, φ) be a representation of Q. We can then define a left module V over the algebra A = A(Q) as follows: as a vector space it is

V = ⊕i∈Q0 Vi

and the A-module structure is extended linearly from

eiv = v, v ∈ Mi

= 0, v ∈ Mj for j ≠ i

for i ∈ Qand

av = φa(vt(a)), v ∈ Vt(a)

= 0, v ∈ Vj for j ≠ t(a)

for a ∈ Q1. This construction can be inverted as follows: given a left A-module V, we set Vi = eiV for i ∈ Q0 and define the map φa: Vt(a) → Vh(a) by v ↦ a(v). Morphisms of representations of (Q, V) correspond to A-module homomorphisms.

Indecomposable Objects – Part 1

An object X in a category C with an initial object is called indecomposable if X is not the initial object and X is not isomorphic to a coproduct of two noninitial objects. A group G is called indecomposable if it cannot be expressed as the internal direct product of two proper normal subgroups of G. This is equivalent to saying that G is not isomorphic to the direct product of two nontrivial groups.

A quiver Q is a directed graph, specified by a set of vertices Q0, a set of arrows Q1, and head and tail maps

h, t : Q1 → Q0

We always assume that Q is finite, i.e., the sets Q0 and Q1 are finite.

Untitled

A (complex) representation of a quiver Q consists of complex vector spaces Vi for i ∈ Qand linear maps

φa : Vt(a) → Vh(a)

for a ∈ Q1. A morphism between such representations (V, φ) and (W, ψ) is a collection of linear maps fi : Vi → Wi for i ∈ Q0 such that the diagram

Untitled

commutes ∀ a ∈ Q1. A representation of Q is finite-dimensional if each vector space Vi is. The dimension vector of such a representation is just the tuple of non-negative integers (dim Vi)i∈Q0.

Rep(Q) is the category of finite-dimensional representations of Q. This category is additive; we can add morphisms by adding the corresponding linear maps fi, the trivial representation in which each Vi = 0 is a zero object, and the direct sum of two representations is obtained by taking the direct sums of the vector spaces associated to each vertex. If Q is the one-arrow quiver, • → •, then the classification of indecomposable objects of Rep(Q), yields the objects E ∈ Rep(Q) which do not have a non-trivial direct sum decomposition E = A ⊕ B. An object of Rep(Q) is just a linear map of finite-dimensional vector spaces f: V1 → V2. If W = im(f) is a nonzero proper subspace of V2, then the splitting V2 = U ⊕ W, and the corresponding object of Rep(Q) splits as a direct sum of the two representations

V1 →ƒ W and 0 → W

Thus if an object f: V1 → V2 of Rep(Q) is indecomposable, the map f must be surjective. Similarly, if ƒ is nonzero, then it must also be injective. Continuing in this way, one sees that Rep(Q) has exactly three indecomposable objects up to isomorphism:

C → 0, 0 → C, C →id C

Every other object of Rep(Q) is a direct sum of copies of these basic representations.

Lie-Dragging Sections Vectorially. Thought of the Day 149.0

Generalized vector fields over a bundle are not vector fields on the bundle in the standard sense; nevertheless, one can drag sections along them and thence define their Lie derivative. The formal Lie derivative on a bundle may be seen as a generalized vector field. Furthermore, generalized vector fields are objects suitable to describe generalized symmetries.

Let B = (B, M, π; F) be a bundle, with local fibered coordinates (xμ; yi). Let us consider the pull-back of the tangent bundle  τB: TB → B along the map πk0: JkB → B:

Untitled

A generalized vector field of order k over B is a section Ξ of the fibre bundle π: πk*TB → JkB, i.e.

Untitled

for each section σ: M → B, one can define Ξσ = i ○ Ξ ○ jkσ: M → TB, which is a vector field over the section σ. Generalized vector fields of order k = 0 are ordinary vector fields over B. Locally, Ξ(xμ, yi, …, yiμ1,…μk) is given the form:

Ξ = ξμ(xμ, yi, …, yiμ1,…μk)∂μ + ξi(xμ, yi, …, yiμ1,…μk)∂i

which, for k ≠ 0, is not an ordinary vector field on B due to the dependence of the components (ξμ, ξi) on the derivative of fields. Once one computes it on a section σ, then the pulled-back components depend just on the basic coordinates (xμ) so that Ξσ is a vector field over the section σ, in the standard sense. Thus, generalized vector fields over B do not preserve the fiber structure of B.

A generalized projectable vector field of order k over the bundle B is a generalized vector field Ξ over B which projects on to an ordinary vector field ξ = ξμ(x)∂μ on the base. Locally, a generalized projectable vector field over B is in the form:

Ξ = ξμ(xμ)∂μ + ξi(xμ, yi, …, yiμ1,…μk)∂i

As a particular case, one can define generalized vertical vector fields (of order k) over B, which are locally of the form:

Ξ = ξi(xμ, yi, …, yiμ1,…μk)∂i

In particular, for any section σ of B and any generalized vertical vector field Ξ over B, one can define a vertical vector field over σ given by:

Ξσ = ξi(xμ, σi(x),…, ∂μ1,…, μkσi(x))∂i

If Ξ = ξμμ + ξii is a generalized projectable vector field, then Ξ(v) = (ξi – yiμξμ)∂i = ξi(v)i is a generalized vertical vector field, where Ξ(v) is called the vertical part of Ξ.

If σ’: ℜ x M → B is a smooth map such that for any fixed s ∈ ℜ σs(x) = σ'(s, x): M → B is a global section of B. The map σ’ as well as the family {σs}, is then called a 1-parameter family of sections. In other words, a suitable restriction of the family σs, is a homotopic deformation with s ∈ ℜ of the central section σ = σ0. Often one restricts it to a finite (open) interval, conventionally (- 1, 1) (or (-ε, ε) if “small” deformations are considered). Analogous definitions are given for the homotopic families of sections over a fixed open subset U ⊆ M or on some domain D ⊂ M (possibly with values fixed at the boundary ∂D, together with any number of their derivatives).

A 1-parameter family of sections σs is Lie-dragged along a generalized projectable vector field Ξ iff

(v))σs = d/ds σs

thus dragging the section.