# Tag Info

14

Let's assume that everyone agreed on some elliptic curve and a public base point $g$ somewhere on the curve. When two parties Alice and Bob want to agree on a shared secret, they proceed as follows: Alice chooses some random number $a$ and applies the curve operation to $g$, the public base point, $a$ times. She obtains some result ...

10

A safe prime is a prime number $p$ for which $(p-1)/2$ is also prime. The order of an element $g$ of the group $\mathbf{Z}^*_p$ (the integers modulo $p$, excluding 0) is the smallest integer $n$ such that $g^n\equiv 1\pmod{p}$; this is always a factor of $p-1$. The orders of the subgroups of the group generated by $g$ are the factors of the order of $g$; ...

8

Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a ...

7

Your problem seems to be at least as hard as the 2-weak Bilinear Diffie-Hellman Inversion Problem (2-wBDHI problem): Given $g, g^x, g^{x^2}, g^y \in \mathbb G$, and $T \in \mathbb G_T$ to determine whether or not $T = e(g,g)^{x^3 y}$. Proof: We first need to define an equivalent version of your problem, where we take some generator $h$ so $g = h^b$. ...

6

It does not; the equation holds for any element $g$. The fact that $g$ is a generator means only that every element of the group can be obtained a key. This is not at all necessary for the protocol.

6

SHA-1 is still thought to be secure whenever collision resistance isn't required. The hash is both used for signing certificates and ECDHE public keys. There's however a difference with regard to collision attacks. It is possible for an attacker to attack the collision resistance with certificates by getting their own certificate signed by a CA. In ECDHE ...

5

It's an element of the field of all integers modulo $p$, and these are represented by the numbers $0,\ldots, p-1$. And $g$ will be one of them.

5

$\mathbb{Z}^*_{13}$ is a group with 12 elements, not 13. A group is defined by a set of elements, and a "law". The law combines two elements and yields a third one within the set. You get a group if the law fulfils some properties (the law is associative, there is a neutral element, each element has an opposite in the group). $\mathbb{Z}_{13}$ is a group ...

5

There are several possible ways to generate a weak DH group: The attacker can generate a $g$ with a small order; this would make deriving the shared secret from the public values easy. The attacker can generate a $g$ with a smooth order; that is, the order is large, but is composed of small prime factors; this would make deriving the shared secret from the ...

5

The answer is yes; see Chapter 21 of Galbraith's book. Suppose we have your Fixed-Inverse-DH oracle $O(\cdot)$, and given $g^a$ and $g^b$ we want to find $g^{ab}$. We do this in two steps. First, we use $O$ to compute $g^{a^2}$ from $g^{a}$—this is a related problem called the Square-DH problem. Then we use the quarter-squares identity to compute $g^{ab}$. ...

5

This is a reduction showing that if you can compute $g^{a^2}$ given $g^a$, then you can solve the computational Diffie Hellman problem. Here is the reduction. Let $A$ be an adversary that given $g^a$ for a random $a$, outputs $g^{a^2}$ with probability $\epsilon$. We construct $A'$ who receives $u=g^a$ and $v=g^b$ and works as follows. $A'$ runs $A$ three ...

4

This has been specified by the standard, steps 4 and 5 of the protocol described in RFC 4253: S generates a random number y (0 < y < q) and computes f = g^y mod p. S receives e. It computes K = e^y mod p, H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K) (these elements are encoded according to their types; see below), ...

4

The twist attack is best explained in Fouque et al's paper. While the (quadratic) twist of the curve $E : y^2 = x^3 + ax + b \in \mathbb{F}_p$ is indeed of the form $E^t : y^2 = x^3 + d^2ax + d^3b \in \mathbb{F}_{p}$ for nonsquare $d$, you can also think of the twist as the set of points $(x, y)$ in $E^2 : y^2 = x^3 + ax + b \in \mathbb{F}_{p^2}$ where $x$ ...

4

You can't encrypt a message with ECDH alone, because all it gives you is a shared secret that you can't really control. Rather, you use that secret in a symmetric scheme like AES (generally after passing it through a KBKDF to convert from an ECDH result to a proper-length and less-structured symmetric key, which you then use as the key for symmetric crypto). ...

3

A lot of modern cryptography is based on some mathematical assumptions and aims to achieve what is called Computational Security. That means that the adversary (Eve) could get some information about the plaintext with a negligible probability and the adversary is modeled as someone with bounded computational power, storage and bounded time. So all the ...

3

DH: OpenSSL commandline has three options for creating certs, but all of them either selfsign the cert or require a selfsigned CSR, and DH can't do either of those. OpenSSL library called from a program you write can construct an X509 object (cert) containing a DH publickey, subject and other attributes as you specify, signed by an RSA key corresponding to a ...

3

The problem about Man-in-the-Middle attack on Diffie-Hellman is that both sides are not confident about other side's public key (g^a and g^b). If they were sure that they have correct public key of their's friend Man-in-the-Middle attack wouldn't be possible, because MITM attack is based on the forgery of public keys by adversary! If for instance Bob and ...

3

Actually, RFC3526 does have recommendations for the random number size; see section 8, and the table listing "exponent size". Now, it gives two different recommendations (which sounds rather less useful than giving one); the summary is that if the size of the random number you pick is $x$ bits, then an attacker can recover the shared secret with no more ...

3

For a given prime $p$, there are many choices for the generator $g$, but $g$ cannot be completely arbitrary. As the name hints, $g$ is supposed to be a generator of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ (or at least a large subgroup, more on this later), that is, it must have the property that the set of its powers modulo $p$ $\{g^1 \bmod p, ... 3 The best option you have is TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA. This is likely to provide most security, as the AES keylength is maximal and ECDSA keys tend to provide more security than RSA keys, as a 128-bit security level is quite common with ECDSA (field size: 256 bit) whereas 112-bit is the standard with RSA (keylength: 2048 bit). However in practice ... 3 I haven't checked, is$p$a safe prime and/or is 4 a generator over$p$? Server has random secret$S$, known$p$and$g$a generator. I'm substituting in$V$for your$g$, with$g = 4$.$V = g^S \mod pV$is a verifier of the server, as in SRP.$V$is your$g$, so known by the client. Anyone knowing$V$can establish communications with the server. ... 3 I have never heard of this reason, and I don't quite understand it. In general, the security of Diffie-Hellman key exchange is reduced to the DDH assumption. According to this assumption, the result of the key exchange is a group element that is computationally indistinguishable from a random/uniformly distributed element in the group. However, what is ... 3 Basically yes, you can do that. Public keys are meant to be shared. The devil is in the details however: public keys without trust are pretty useless as you don't know who you are performing the key agreement with; two static keys will always generate the same key for the same partners if you use a naive DH implementation, something you probably don't ... 2 Well, as it says in your link the problem is authentication. So somehow Alice and Bob must set up an authenticated channel. One way of implementing such a channel is by Alice and Bob holding each others public verification key for a signature scheme. A CA would probably not hold a secret key for Alice and Bob. However, using a CA to get an authentic copy ... 2 Mostly. The two problems are actually more closely equivalent in a gap model than in a non-gap model. Square-DH clearly reduces to CDH either way, but CDH reduces to two calls to Square-DH (you have 3, but you can use$(u-v)^2$to make it 2). This is fine if the Square-DH adversary is always right, but maybe the adversary only solves the Square-DH problem ... 2 Does using a slow-hash on the output of an asymmetric key-exchange offer any more protection in a quantum-computing era? No.$\:$A quantum attacker would simply find seed even if you didn't use "a slow-hash on" it. Is the algorithm (greatly) diminished, or completely broken? The algorithm will still be completely broken by quantum attacks. ... 2 It sounds like you are thinking of performing static-static Diffie-Hellman. If that is performed naively then it will indeed derive the same secret time and time again. At least one of the key pairs needs to be non-static or ephemeral, or an additional variable (nonce) should be introduced. For instance in NIST SP 800-56A there is section 6.2.1: "Initiator ... 2 Fkraiem's answer is correct: this is not necessary. From your comment on his answer it seems however you don't understand why Alice and Bob retrieve the same key. This, again, doesn't rely on$g$being a generator. Recall from your high school math classes that$(g^a)^b = g^{ab} = g^{ba} = (g^b)^a$. This is basically the trick that is being used here. Since ... 2 SRP with the user's key = 0 is identical to DH. SRP with a publicly known key is identical to DH with a constant multiplier. For private key$x$, user ephemeral value$a$, server ephemeral value$b$, and$u$derived from shared values, SRP ends up calculating the value$g^{ab + uxa}$(which is then typically hashed to get the shared key). If$x$is zero, ... 2 Diffie-Hellman operates in a cyclic group by definition: the elements$g, g^a, g^b, g^{ab}$are in the cyclic group generated by$g$. Technically, a monoid is sufficient, but since cryptography mostly operates in finite structures, you get a group anyway. In your example, you operate in the cyclic group$c\mathbf{Z}\$, and as you were told in the comments, ...

Only top voted, non community-wiki answers of a minimum length are eligible