# Tag Info

13

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

7

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

6

An attack would be trivial if the seed of the RNG was only 32 bits; just enumerate the seeds, and test which matches the intercepted messages. That's easy. However the default Java Random class uses a 48-bit state and seed (which would still be attackable, though $2^{16}$ times less easily), and there are safe subclasses, thus use of Random does not imply ...

6

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

5

This problem is equivalent to the decisional Diffie-Hellman problem, and hence your problem is intractable (assuming, of course, that the group is well chosen). Here's how we can use an Oracle that can solve the above problem to solve the DDH problem: In the DDH problem, we're given values $g, g^x, g^y, g^z$, and we're asked whether $xy = z$. We call the ...

4

Before we get to the questions, we need to understand what these attacks look like. An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^2 = x^3 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$. (The equations I'm writing ...

4

Computations on elliptic curves are more efficient. Roughly speaking, when the base field has size $n$ (for DH/ElGamal/DSA, the size in bits of the modulus $p$; for elliptic curves, the size of the field for point coordinates) and a "security level" $t$ (e.g. $t = 80$ for "80-bit security" as can be expected when using a 160-bit subgroup and a 160-bit hash ...

4

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

4

A quantum computer solves the discrete logarithm problem for both finite fields and elliptic curves. Being able to efficiently calculate discrete logarithms implies being able to break Diffie-Hellman, so Diffie-Hellman on either of them is not secure against an adversary who owns a large quantum computer. There might be other groups in which DL problem is ...

4

If an implementation uses a poor PRNG, there will always be vulnerabilities in that implementation. However, if you replace Random for a cryptographically secure PRNG, the method you describe for generating private exponents is fine. In such case the timings will only reveal information about: The public modulus $p$, which may be presumed to be known ...

4

How large should $p$ be if the Diffie-Hellman exchange is encrypted? Well, that rather depends on: How much do you trust the encryption key not to be recovered? Why are you doing a Diffie-Hellman in the first place? If you can trust that the encryption key will never be recovered by anyone other than the sender and the receiver, then it doesn't really ...

4

There are standard algorithms for this. See, e.g., Section 7.3 of Algorithmic Number Theory (Eric Bach, Jeffrey Shallit, MIT Press, 1996). If you want to take square roots, you can use Cipolla's algorithm, the Tonelli-Shanks algorithm, or Pocklington's algorithm. The Tonelli-Shanks algorithm apparently has a generalization to take arbitrary $n$th roots. ...

3

This is another way of expressing the decisional Diffie-Hellman problem. This problem is more typically written as 'given $g,\ g^a, g^b, g^c$, does $g^{ab} = g^c$?'. As for the difficulty of this problem, it is believed to be difficult as long as you stay within a large prime subgroup; in this case (because you specify a strong prime), you means that you ...

3

Depends what you mean by "validate". You should always validate any Public Key, as otherwise how do you know who owns it? If you are not sure of the owner, you are open to a man-in-the-middle attack. But I guess by validate you mean validate that the point is of the right order? You should certainly check that its on the curve (easy) and check that its not ...

3

There are two answers: the "engineering" answer, and the "principled" answer. The engineering answer is that, in practice, if you generate two keys using two different info strings, I suspect you'd probably get away with it without problems. If we model the hash as a random oracle (admittedly a very strong "assumption"), then I suspect it might be possible ...

3

A key derivation function is intuitively "purifying" the entropy in the group element Z into uniformly random (looking) bits that can used as a key for other purposes. It is not designed to produce "multiple keys" from the same Z, and one should definitely not call the KDF on the same Z twice (even with different salts) and expect to get two independent ...

3

The Computational Diffie-Hellman (CDH) problem is: Given some group $G$ and group element $g$, and the elements $g^a$ and $g^b$, compute the value $g^{ab}$. The Decisional Diffie-Hellman (DDH) problem is: Given some group $G$ and group elements $g$, and the elements $g^a$, $g^b$ and $g^c$, determine whether $g^c = g^{ab}$ These are obviously ...

3

If you're asking about the likely future for public key cryptography, then my opinion is that we are likely to see a transition (gradually over the next number of years) from things such as RSA and DH, and into Elliptic Curve Cryptography. This is because ECC is just more efficient; we know that we can break RSA and DH in subexponential time; that means ...

2

I believe that you are talking about one specific version of EKE, which is one of several known Password authenticated key agreement methods (which is the general category of methods that do a key agreement with the property that someone listening into the exchange can't learn anything, and an attacker that poses as one of the two sides can learn no more ...

2

Elliptic Curve Cryptography (ECC) is not known to be specifically more resistant to side channel attacks (of course the next question is more resistant than what). This paper reviews power analysis side-channel attacks against ECC and countermeasures. Given that ECC uses multiplication and many common implementations of the MUL instruction run in time ...

2

If Alice and Bob both use static DH keys, they only have to perform the DH operation once to get their shared secret. The number of messages that are safe to exchange encrypted with something derived from that shared secret is not really a function of the DH problem, except to the extent that the size of the modulus and of the private keys put a limit on the ...

2

Generating an (EC)DH key pair entails "producing" the group parameters (the curve or the modulus+generator), then the private key $x$, (a random integer modulo the group order $q$), and then applying the private key to the generator (i.e. computing $xG$ on the curve, $g^x \mod p$ for plain DH). Producing new group parameters would be the most expensive ...

2

So what you are doing here are two Diffie-Hellman key exchanges in parallel – one with the server's static Diffie-Hellman key pair $(x,y)$ and the client's ephemeral key pair $(a,A)$ to calculate $k = k'$, and one with completely ephemeral keys to calculate the actual pre_master_secret. $k$ is only used as a MAC key to authenticate the server's exchange ...

2

Finding the corresponding $m'$ using $c'$ is a chosen cipher text attack. It's possible for a scheme to be semantically secure under certain types of attacks (perhaps something weaker like chosen-plaintext attack), but be broken under heavier attacks (like the chosen ciphertext attack you talk about).

2

There is no known way to compute $(g^a)^k \mod p = g^{ak} \mod p$, given only $g^k \mod p$ and $g^a \mod p$ as per the Decisional Diffie–Hellman assumption. This is roughly equivalent to the discrete log problem. This is described in more detail in this paper.

1

$Adversary\:$ receives $C^1_{publ}$ $Adversary\:$ adaptively queries an oracle that implements: take $C^2$ as input, generate $S^1_{publ}$, set $\: k_{adv} = KDF\left(\left(C_2\right)^{S^0_{priv}},label_0\right) \:$, $\:$ output $\: AE_{k_{adv}}\left(S^1_{publ}\right)$ Note that $\:Adversary\:$ can (with, heuristically, overwhelming accuracy) test whether ...

1

By non-standard do you mean when to use custom curves? Like in crypto++ where you can specify your own parameters? Given that the standards recommend certain sets of domain parameters (and interesting enough US government departments are forbidden from using their own parameters) it's sounds like the answer is no, for reasons of avoiding the risks of self ...

1

The usual solution for the Man-in-the-Middle problem of Diffie-Hellman is to combine it with a public-key authentication solution. This could either work by including the server's public Diffie-Hellman key (which then must be a long-term key, not a short-term or even session key – this way you lose your forward-security) in the client, or including a ...

1

I am assuming you are throughly familiar with traditional Diffie-Hellman. If not, read up on it first. For our purposes here, an elliptic curve is a curve whose points satisfy the equation $y^2=x^3+ax+b$. That right there tells you what $a$ and $b$ are, they are coefficients of the curve. In elliptic curve cryptography, we need an algebraic group for a ...

1

Alice computes $A=g^a$, Bob computes $B=g^b$ and Charlie computes $C=g^c$. $A,B$ and $C$ are published. Alice computes $AC=C^a$ and $AB=B^a$ and Bob computes $BC=C^b$. $AB,AC$ and $BC$ are published. Alice computes $ABC=BC^a$, Bob computes $ABC=AC^b$ and Charlie computes $ABC=AB^c$. Everybody shares $ABC=g^{abc}$. This can be generalized for any number of ...

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