Hot answers tagged

18

A couple things: This article is two years old, so take its predictions with a grain of salt. In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon. The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those ...


14

These are completely different things: Man-in-the-middle is an active attack to a cryptographic protocol, where the attacker is, effectively, in between the communications of two users, and is capable of intercepting, relying, and (possibly) altering messages. In this case, the meaning of "in the middle" is direct: the attacker is in the middle of two ...


12

How could this allow for a backdoor? Well, if you do DH modulo a composite, an attacker can recover the shared secret if they can solve the DH problem (or the DLog problem) modulo each of the primes that make up the composite. There are a couple of ways that could be used by someone who knows the factorization to solve the DLog problem easier than ...


11

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


11

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


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


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

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.


7

Alice could just generate a random number (to be their shared key), sign it, encrypt it with Bob's public key, and send it to Bob. I, as an eavesdropper, can capture this exchange. In fact, I can capture many of these as I want with other people communicating with Bob. Then, fast forward to some point in the future, if I can compromise Bob's private ...


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

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


6

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


6

I just want to highlight: The new advancement need to be realized and validated. ECC and DH are quite similar although ECC discrete logarithm problem is harder. In other words, whatever effects the security of DH might not affect ECC with the same magnitude.


5

Ephemerality does not refer to "a new session key being made each time a new session is set up", it refers to both parties' key pairs (and group elements) being freshly chosen. ​These Diffie-Hellman key pairs are should be ephemeral for forward secrecy; the session key is always ephemeral, even if static-static Diffie-Hellman is applied. Any nonces are used ...


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

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

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

Because (I assume) $g$ is a generator, it is not a square (prove this), so its Legendre symbol is $-1$. And hence, the Legendre symbols of $g^a$ and $g^b$ leak the parities or $a$ and $b$. Hence they leak the parity of $ab$, which leaks the Legendre symbol of $g^{ab}$.


5

Counting number of points on elliptic curve over $\mathbb F_2$ is very easy.For extension of fields we can use of this theorem: Theorem : Let $E$ be an elliptic curve defined over $F_q$, and let $\#E(F_q ) = q +1−t$. Then $\#E(F_{q^n} ) = q^n + 1 − V_n$ for all $n ≥ 2$, where $\{V_n\}$ is the sequence defined recursively by $V_0 = 2, V_1 = t$, and $V_n = ...


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


4

The difference is purely conceptual. That is, when Diffie-Hellman published their paper, they equated between public-key encryption and trapdoor functions. Thus, they did not think that they had constructed a public-key encryption scheme, and this invention came only a year later with RSA. In fact, Diffie and Hellman even explicitly talk about publishing one ...


3

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


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

No. First, you've exposed a padding oracle by using unauthenticated AES. Secondly, you've not authenticated the devices: it's easy to mount a man in the middle attack. Thirdly, I don't understand the role of changing parameters all the time in your protocol.



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