# 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

NO, we can't apply an hill-climbing algorithm to Diffie–Hellman. In order to break Diffie-Hellman key exchange, it is enough for Eve to reverse exponentiation modulo the public prime $p$; that is, given $g^x\bmod p$, find $x$. That's the Discrete Logarithm Problem. We do not know that hill-climbing can help for that (or the slightly less general DH ...

10

I recommend avoiding Diffie-Hellman parameter generation. Instead, use a standardized DH group with a sufficiently large modulus (2048-bit or larger). For example, group #14 or #15 from RFC3526 (see sections 3 and 4) would be a good choice. Alternatively, switch to the elliptic curve variant of Diffie-Hellman and use Curve25519. The article you linked to ...

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$; ...

9

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

7

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

6

Yes, there are a few reasons to prefer ECDH over RSA: ECDH will perform much better; ECDH can provide forward security when used with ephemeral key pairs without a large performance overhead for creating those key pairs; ECDH should be impervious to most oracle attacks, i.e. timing based padding oracle attacks on OAEP. For the forward secrecy you require ...

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

You might want to checkout Wikipedia page of elliptic curves to get a basic overview. The difference between DH and ECDH is mainly the group which is being chosen to compute the secret key(s). While DH uses a multiplicative group of integers modulo a prime $p$, ECDH uses a multiplicative group of points on an elliptic curve: Alice and Bob agree on an ...

5

It is possible to find the desired values in an acceptable amount of time. TL;DR: Find the curve order, factor it, select a (random) point until you have one with the desired order and calculate the cofactor as quotient of curve and point order. First, you can use yyyyyyy's answer to find the order $n$ of the described curve using Schoof's algorithm. ...

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

5

Short key fingerprints are indeed vulnerable. But those are different from the short-authentication-string (SAS) used by ZRTP. A simple SAS based protocol using one-time keys could look like this: Alice sends a (collision resistant) hash of her public key to Bob. Bob sends his public key to Alice Alice sends her public key to Bob The short ...

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

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

4

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

In the introduction of the Logjam paper, it is stated that After a week-long precomputation for a specified 512-bit group, we can compute arbitrary discrete logs in that group in about a minute. So it seems that what it actually does is attack the discrete logarithm problem, so any discrete-logarithm-based system which uses a common prime should ...

3

The "obvious" (it really isn't that obvious) thing you are missing is: The same reasoning could be applied to literally any other private key! There is nothing special about $a=\lvert(\mathbb Z/p\mathbb Z)^\times\rvert=p-1$ (which would, by the way, more commonly be represented as $0$ modulo itself), except that checking for it is particularly easy. For ...

3

Sounds like a description of ECIES to me. ECIES is a hybrid cryptosystem that builds upon ECDH. Basically: the static public key of the receiver is used together with an ephemeral key pair generated at the sender. The public key of the receiver and ephemeral private key of the sender are used to generate a "shared secret" using ECDH. This shared secret is ...

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 First, a bit of background. If we refer to the size of an elliptic curve group as$n$, we select an elliptic curve with$n = hq$, where$q$is a large prime, and$h$is a small integer called the cofactor; it is typically either 1, 4 or 8. The values of$q$and$h$will be part of the curve definition. As you know, with straight DH, we agree on a point ... 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 ... 3 I see you use the same generator on both sides (this need not work for any$n_1, n_2$of course...). But even if this holds (trying a small example): Let 1 use$n_1 = 11, M=2$, and 2 uses$n_2 = 13, M= 2$. Check that$2$is a generator for both of the multiplicative groups. If$d_1 = 7, d_2 = 9$, then$A = 2^7 \bmod 11 = 7$, while$B = 2^9 \bmod 13 = 5\$. ...

2

After this step every sent packet is encrypted over simple XOR block cipher by secure key's bytes, in this case 256bit long block. Does this mean "divide the message into 256-bit blocks, and XOR each block with the key"? If so, this is very insecure. If any part of the message is predictable, the attacker can recover part or all of the key, and ...

2

The protocol seems secure. Some comments below. Bob computes the DH shared secret X using his private key and Alice's static public key, and then K(X), the result of applying an appropriate key derivation function (KDF) to the combination of A, B, and X. The DH secret X already depends on both key-pairs. Including the public keys in key ...

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