Hot answers tagged

22

In the beginning SSL handshake, the client sends a list of supported ciphersuites (among other things). The server then picks one of the ciphersuites, based on a ranking, and tells the client which one they will be using. This step is the one that determines whether or not the future connection will have perfect forward secrecy. Note that, at this point, ...


20

ECDSA is a digital signature algorithm ECIES is an Integrated Encryption scheme ECDH is a key secure key exchange algorithm First you should understand the purpose of these algorithms. Digital signature algorithms are used to authenticate a digital content. A valid digital signature gives a recipient reason to believe that the message was created by a ...


18

Both RSA and Diffie-Hellman work with modular exponentiation. But they work in a different way: In RSA, there are two exponentiations which invert each other, i.e. we have $e$ and $d$ such that $(x^e)^d \equiv x$ for all $x$. E.g. if $\square^e$ is the encryption, $\square^d$ is the corresponding decryption. To create this pair of $e$ and $d$ (or derive one ...


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


17

The security of Diffie-Hellman depends upon the group in which DH is used, but not upon which generator is used for this group. See note 3.53 (chapter 3, page 103) of the Handbook of Applied Cryptography. In more details: for DH, we use a subgroup of size $q$ of the integers modulo $p$ (a big prime) with the multiplication as group operation. $q$ should be ...


17

The really great thing about Diffie-Hellman is how light it is, network-wise: both parties send each other a single message; neither has to wait for the message from the peer before beginning to computing his own message. If you can tolerate something heavier, you can have a look at what @Paŭlo describes; with $n$ participants, it requires $n-1$ messaging ...


17

The standard Diffie-Hellman key exchange algorithm (or family of algorithms) works in an cyclic group with generator $g$, and relies on $$ {y_A}^{x_B} = (g^{x_A})^{x_B} = (g^{x_B})^{x_A} = {y_B}^{x_A}, $$ where $y_A$ and $y_B$ are publicly transmitted, while $x_A$ and $x_B$ remain private. With three parties, we still have $$((g^{x_A})^{x_B})^{x_C} = ...


16

First, we are talking about multiplications, so we work in $\mathbb{Z}_p^*$, not $\mathbb{Z}_p$. By definition, any integer $g \in \mathbb{Z}_p^*$ is the generator for... the subgroup generated by $g$, i.e. the set of $g^k \mod p$ for all integer values $k$. The order of $g$ is the smallest $k \geq 1$ such that $g^k = 1 \mod p$. For soundness (Alice and ...


15

I assume you're talking about SSL/TLS or a similar protocol. In these protocols there are two reasons to use Diffie-Hellman: Your certificate only supports signing Either it is an RSA certificate restricted to signing, or it uses an algorithm that doesn't support encryption, such as DSA or ECDSA. Forward security - What happens if the server's private key ...


15

Diffie Hellman Diffie Hellman is a key exchange protocol. It is an interactive protocol with the aim that two parties can compute a common secret which can then be used to derive a secret key typically used for some symmetric encryption scheme. I take the notation from the link above and this means we have a group $\mathbb{Z}_p^*$ for prime $p$ ...


14

As far as we know, Diffie-Hellman is secure as long as the subgroup generated by g is impervious to discrete logarithm. When working modulo a prime p, this is achieved when the following are met: p is large enough (at least 1024 bits, go to 2048 bits for a bigger safety margin) and is not a "special form" prime (a randomly generated prime will be fine with ...


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


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


13

The problems: The Discrete Logarithm problem: Given $y$, find $x$ so that $g^x = y$. The Computational Diffie-Hellman problem: Given $y_1 = g^{x_1}$ and $y_2 = g^{x_2}$ (but not $x_1$ and $x_2$), find $y = g^{x_1·x_2}$. The Decisional Diffie-Hellman problem: Given $y_1, y_2, y_3$, decide if they are of the form $y_1 = g^{x_1}$, $y_2 = g^{x_2}$ and $y_3 = ...


13

Not only does g not need to be a generator for the entire group, general practice is that it is not. As Thomas has mentioned, the order of $g$ is the smallest $k \ge 1$ such that $g^k = 1 \mod p$. Let $q$ be the order of the value $g$ we use. If $g$ is a generator for the entire group, then $q = p-1$, if not, it is some proper divisor of $p-1$. Now, if ...


13

Well, the advantages of static-ephemeral ECDH (and, they apply to DH as well): You get one-way authentication for free. That is, if Bob has Alice's public ECDH key, and uses it to talk to someone, Bob knows that that someone is Alice, without doing any further checks. Now, Alice has no idea who she's talking to; on the other hand, for some scenarios, ...


13

Actually, there is no major difference between $p \equiv 23\ (\bmod\ 24)$ vs $p \equiv 11\ (\bmod\ 24)$; any minor difference boils down to "do you prefer the DH shared secret to be limited to half the possible values; or do you prefer to leak a bit of the secret exponents?". OpenSSL prefers to leak one bit; the RFC 3526 designers decided they preferred ...


13

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

The difference is subtle. DH is used to generate a shared secret in public for later symmetric ("private-key") encryption: Diffie-Hellman: Creates a shared secret between two (or more) parties, for subsequent symmetric encryption Key identity: (gens1)s2 = (gens2)s1 = shared secret   (mod prime) Where: gen is an integer whose ...


11

On a general basis, you want to keep encryption and signature keys disjoint, because they tend to have distinct life cycles. In broad terms, an encryption key should be escrowed, because loss of the private key implies loss of the data which is encrypted relatively to the public key. However, a signature key must not be escrowed, since the proof value of a ...


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

Yes, you are correct. The simplest way without stepping outside NaCl would be to have both create an ephemeral, random crypto_box_keypair, then exchange public keys using their long term keys. Further communication would use that new keypair for crypto_box during that session. After they are done with the session, delete those ephemeral keys from memory. ...


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

Oh, and while you did not specifically ask about this, there is another point I believe that is important to highlight; DH and SRP are different protocols, and have different requirements on the generator they use. In particular, taking a generator that is designed to be used securely within DH can void the security properties of SRP. Here's what's going ...


10

Well, yes, that is generally good advice about DH. Here is some background on this: support you were given a value $g^x \bmod p$, and you were also told that $1 \le x \le A$ for some value $A$. If so, then there are several known attacks (such as Big Step/Little Step and Pollard's Rho) that can recover $x$ in about $\sqrt A$ steps. If we have as our ...


10

Well, to answer your questions in order: How big should $p$ be? Well, it should be large enough to defend against the known attacks against it. The most efficient attack is NFS; that has been used against numbers on the order of $2^{768}$ (a 232 digit number). It would appear wise to pick a $p$ that's considerably bigger than that; around 1024 bits at a ...


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

$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x$ of them] $\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.03 in}y$ of them] $\ldots \cdot g\cdot g\cdot g)$ $= \;\;\; g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$ of them] ...


9

Diffie-Hellman and RSA are distinct and do not use the same "trick". In Diffie-Hellman, commutativity is used: $(g^a)^b = (g^b)^a$. Both Alice and Bob do two modular exponentiations each (Alice chooses $a$, computes $g^a$ and sends it to Bob, receives $g^b$ from Bob, and finally computes $(g^b)^a$). Security relies on the difficulty of discrete logarithm: ...


9

The paper "On the Joint Security of Encryption and Signature in EMV" shows that ECIES and EC-Schnorr signatures can be used together without compromising security: In the random oracle model ECIES-KEM and EC-Schnorr are jointly secure if the gap-DLP problem and gap-DH problem are both hard Ed25519 is extremely similar to EC-Schnorr, and both ECIES ...



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