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

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. Data^fs refers to False Start application data that some TLS clients send before receiving the server’s Finished message.

imperfect forward secrecy

Advertisement

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

 

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 f_i : V_i → W_i is injective (respectively surjective, an isomorphism) precisely if each of the linear maps f_i is.

There is a collection of simple objects in Rep(Q). Indeed, each vertex i ∈ Q₀ determines a simple object S_i of Rep(Q), the unique representation of Q up to isomorphism for which dim(V_j) = δ_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 E₁ ⊂ E to be the kernel of f and repeat the argument with E₁. In this way we get a filtration

… ⊂ E₃ ⊂ E₂ ⊂ E₁ ⊂ E

with each quotient object Eⁱ⁻¹/Eⁱ simple. Once again, this filtration cannot continue indefinitely, so after a finite number of steps we get E_n = 0. Renumbering by setting E_i := Eⁿ⁻ⁱ 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 = {r_i} of elements of its path algebra, where each r_i is contained in the subspace A(Q)_aibi of A(Q) spanned by all paths p starting at vertex aiand finishing at vertex b_i. Elements of R are called relations. A representation of (Q, R) is a representation of Q, where additionally each relation r_i is satisfied in the sense that the corresponding linear combination of homomorphisms from V_ai to V_bi 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 a_na_n−1 · · · a₁ of Q, formed by composable arrows a_i of Q with h(a_n) = t(a₁), 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

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 a_m…a₀ such that h_(ai−1) = t_(ai) for i = 1,…, m:

The path is p = a_m…a₀. Writing t(p) = t(a₀) and saying that p starts at t(a₀) and, similarly, writing h(p) = h(a_m) and saying that p finishes at h(a_m). For each vertex i ∈ Q₀, we denote by e_i 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 A_l ⊂ A to be the subspace spanned by paths of length l. Then A = ⊕_l≥0A_l is a graded C-algebra. The subring A₀ ⊂ A spanned by the trivial paths e_i is a semisimple ring in which the elements e_i are orthogonal idempotents, in other words e_ie_j = e_i 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 V_i

and the A-module structure is extended linearly from

e_iv = v, v ∈ M_i

= 0, v ∈ M_j for j ≠ i

for i ∈ Q₀ and

av = φ_a(v_t(a)), v ∈ V_t(a)

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

for a ∈ Q₁. This construction can be inverted as follows: given a left A-module V, we set V_i = e_iV for i ∈ Q₀ and define the map φ_a: V_t(a) → V_h(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 Q₀, a set of arrows Q₁, and head and tail maps

h, t : Q₁ → Q₀

We always assume that Q is finite, i.e., the sets Q₀ and Q₁ are finite.

A (complex) representation of a quiver Q consists of complex vector spaces V_i for i ∈ Q₀ and linear maps

φ_a : V_t(a) → V_h(a)

for a ∈ Q₁. A morphism between such representations (V, φ) and (W, ψ) is a collection of linear maps f_i : V_i → W_i for i ∈ Q₀ such that the diagram

commutes ∀ a ∈ Q₁. A representation of Q is finite-dimensional if each vector space V_i is. The dimension vector of such a representation is just the tuple of non-negative integers (dim V_i)_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 f_i, the trivial representation in which each V_i = 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: V₁ → V₂. If W = im(f) is a nonzero proper subspace of V₂, then the splitting V₂ = U ⊕ W, and the corresponding object of Rep(Q) splits as a direct sum of the two representations

V₁ →^ƒ W and 0 → W

Thus if an object f: V₁ → V₂ 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^μ; yⁱ). Let us consider the pull-back of the tangent bundle  τ_B: T_B → B along the map π^k₀: J^kB → B:

A generalized vector field of order k over B is a section Ξ of the fibre bundle π^* : π^k₀ : ^*T_B → J^kB, i.e.

for each section σ: M → B, one can define Ξ_σ = i ○ Ξ ○ j^kσ: 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^μ, yⁱ, …, yⁱ_μ1,…μk) is given the form:

Ξ = ξ^μ(x^μ, yⁱ, …, yⁱ_μ1,…μk)∂_μ + ξⁱ(x^μ, yⁱ, …, yⁱ_μ1,…μk)∂_i

which, for k ≠ 0, is not an ordinary vector field on B due to the dependence of the components (ξ^μ, ξⁱ) 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^μ)∂_μ + ξⁱ(x^μ, yⁱ, …, yⁱ_μ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:

Ξ = ξⁱ(x^μ, yⁱ, …, yⁱ_μ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:

Ξ_σ = ξⁱ(x^μ, σⁱ(x),…, ∂_{μ1,…, μk}σⁱ(x))∂_i

If Ξ = ξ^μ∂_μ + ξⁱ∂_i is a generalized projectable vector field, then Ξ_(v) = (ξⁱ – yⁱ_μξ^μ)∂_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 σ = σ₀. 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.