Hot answers tagged

24

Is this number specified anywhere? It was formally specified in this RFC as the 1536 bit MODP group (although its use predates that RFC). However, from what I've seen, the 2048 bit MODP group from that same document is actually more popular. Why was this particular number picked? Well, it's a safe prime; in addition, the leading 64 bits and the ...


23

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


23

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


20

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} = ((...


19

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


19

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


19

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


18

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


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


15

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 $A=g^a=\underbrace{g\...


15

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


14

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 = g^...


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

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


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

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

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

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


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

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


11

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


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


10

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


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

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

The Diffie-Hellman key exchange is a public-key technology. It is (by itself) not an encryption algorithm (or signature algorithm), though. Here is the basic function: (All calculations here happen in a discrete group of sufficient size, where the Diffie-Hellman problem is considered hard, usually the multiplicative group modulo a big prime (for classical ...



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