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


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


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

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


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


8

What does DH add? Perfect Forward Secrecy. That is, suppose you have a secure session with the server Bob, and then you close the session down. Then, someone steals the server (or serves a warrant to the owner). If you use RSA to transport the random session key, well, the server still has the RSA private key, and so they'll be able to decrypt your ...


7

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


7

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


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


7

It can be used as a key for a symmetric key algorithm. It can be used to derive a key via a standard key derivation mechanism.


7

What's missing is the authentication of the entities. If you don't authenticate the entity then you don't know who you've established the master secret with. This means an attacker can pose as a man in the middle or the attacker can simply act as one of the entities. You can use static DH key pairs, but in that case the DH public keys must be trusted and ...


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.


6

"Attacks that work on the DLP do not work on ECDLP" is a rather vague statement, as ECDLP is just a particular case of DLP, on elliptic curves. I suppose that you refer to DLP over $\mathbb{F}_q$ for some $q = p^k$, $p$ being a prime. The intuitive reason why the DLP is harder to solve over (well chosen) elliptic curves is that they are our best ...


6

In traditional DH Key exchange, users A and B derive a common secret $g^{ab}$ from their respective key pairs $(pk_A=g^a, sk_A=a)$ and $(pk_B=g^b, sk_B=b)$. Aside from active attacks, the security of the scheme depends on the Computational Diffie-Hellman (CDH) assumption, since it is difficult to compute $g^{ab}$ from public keys $g^{a}$ and $g^{b}$. If you ...


6

Can exponent be random number just like it is now or it should be a prime too? There is no particular advantage to be gained in selecting only prime exponents. Is using dynamic modulus and generator better idea? Whether it makes sense to use dynamic modulii is currently under debate. There are known algorithms that make attacking multiple discrete ...


6

Use DLIES, which is essentially Diffie-Hellman with an ephemeral sender key. Assuming you know the receiver's public key, that will cost no extra round trips. The sender does: (eph_sender_private, eph_sender_public) = Generate_Key_Pair() shared_key = SHA-512(Diffie-Hellman(receiver_public, eph_sender_private)) ciphertext = Encrypt(shared_key, message) ...


6

I purposefully did not look at the details of the change you are proposing because whatever the change is, the answer is a resounding YES. If you make any change to a cryptographic construction, then you must prove the security of the modified scheme. If you are lucky, you may be able to reduce the security of the modified scheme to the original scheme, or ...


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

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


5

I will assume for simplicity that you're talking about the full multiplicative group of $F_p$ instead of a proper subgroup, thus there are no problems with $g^a+1$ (except when $g^a=p-1$ which can be trivially ruled out by comparing to $p$). The quantity $\log_g(g^a+1)$ is sometimes referred to as the Zech logarithm (strictly speaking, it is defined for ...


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

1) In the selective unforgeability game (often also denoted universal unforgeability), the adversary is given the public key and a target message for which it needs to produce a forgery (instead of giving the adversary only the public key and letting the adversary choose the target message). 2) No, any scheme that is EUF-CMA is also SUF-CMA (this is easy ...


5

You are absolutely right! The random self-reducibility goes in the other direction, and this variant of the DDH assumption does not follow from it. I have no idea what the author was thinking when he wrote it :-). In any case, the paper has now been updated in ePrint and fixed. Thank you for catching this. I include the proof of this variant here: Consider ...


4

The source of that quote is: Hellman, M. E. (2002). An overview of public key cryptography. IEEE Communications Magazine, 40(5), 42-49. That paper is currently available here: http://www.lkn.fe.uni-lj.si/gradiva/kk/IEEE%20%C4%8Dlanki/IEEE%20Hellman%20An%20Overview%20of%20Public%20Key%20Cryptography%20-reprint.pdf Here's the complete quote: The system ...


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


4

Export ciphers date back to the time when cryptography export was regulated by governments, most notably the US government (see this answer for a good overview of the history of export restrictions). Back then, exporting cryptography with more than 56 bit strength was forbidden. For the Diffie-Hellman Key Agreement scheme, 56 bit of security meant that they ...



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