# Tag Info

11

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

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

9

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

8

Shared secret resulting from the Diffie-Hellman step is a mathematical object; namely, the X coordinate of a curve point. It is a value in a non-binary range; moreover, it is indistinguishable from randomness only up to the security against discrete logarithm, i.e. about 128 bits. Thus, it is at least debatable that parts of the key might be guessable from ...

7

How long are parameters used for? Usually $g$ and $p$ are kept static for a very long time indeed. In fact, the values to use are actually written in to standards. See here for an example. Those were values standardised ten years ago. So the answer is basically decades. The impossibility of brute force Let's suppose that I as an attacker decide I'm going ...

7

There is nothing related to passwords in AES. AES uses 128-bit keys, i.e. sequences of 128 bits. How you come up with such a key is out of scope of AES. In some contexts, you want to generate these 128 bits in a deterministic way from a password (and possibly some publicly known contextual data, like a "salt"); this is a job for password hashing. In other ...

7

ElGamal appears to be used instead of Diffie-Hellman (or IES) in OpenPGP mostly because when that format was put together, there were some unresolved intellectual property issues surrounding both RSA and Diffie-Hellman, while ElGamal was unproblematic. This trend for ElGamal seems to stick around, mostly by force of habit, e.g. when switching to ...

7

Rather risk vulnerabilities of third party library than implement your own. If you feel novice on this field, only implement cryptography yourself as an learning exercise. Why: Mistakes, lack of know-how and maintenance. It is very easy to make novice mistakes in custom implementation of cryptography. Even battle scarred veterans of the field do mistakes ...

7

If the DDH is hard in a group $G$ with generator $g$, then it is hard to decide given $(g,g^a,g^b,g^c)$ whether $ab\equiv c\pmod{ord(G)}$. If you take as $G$ the group $Z_p^*$ of order $p-1$ with $p$ being prime, then you will have $(p-1)/2$ elements being quadratic residues ($QR$) and the other half being non-quadratic residues ($QNR$). Now, we know that ...

7

A generator of a finite group is a value $g$ such that all elements of the group can be represented as $g^k$ for some integer $k$. Another key of looking at it is that if we consider the sequence $g,\ \ g \cdot g,\ \ g \cdot g \cdot g, ...$, saying $g$ is a generator means that all values in the group will appear somewhere in the sequence. Now, when it ...

7

There are actually only 5 unique $x$-coordinates one needs to be concerned about: $(0, \ldots)$ $(1, \ldots)$ $(-1, \ldots)$ $(x_1, \ldots)$ $(x_2, \ldots)$, where $$\begin{eqnarray} x_1 =& 393823572354896145817230607815530211125 \\ & 29911719440698176882885853963445705823 \end{eqnarray}$$ and $$\begin{eqnarray} x_2 =& ... 6 It is equivalent to the computational Diffie-Hellman problem; if you can one of the two problems, you can solve the other (with a polynomial number of queries to the oracle which solves the other). If you can solve the Diffie-Hellman problem, you can solve your problem: this can be seen by first noting that, with a Diffie-Hellman solver, given g^b, you ... 6 For what it's worth, the OpenSSL developers have committed changes that improve this. I assume they will be in OpenSSL 1.0.2, but I don't know for sure. In any case, if you clone the git repo and compile the OpenSSL_1_0_2-stable branch (or master, I suppose), s_client will display the curve name:  OPENSSL_CONF=apps/openssl.cnf apps/openssl s_client -CApath ... 5 One way to address this question is to notice that if there was such a vulnerability in reusing g and P multiple times, then that vulnerability can be used to attack a specific exchange, even if they use g and P only that one time. That is, changing g and P cannot help matters. Here is how this observation works; suppose we have a black box ... 5 You can make OpenSSL print out the handshake messages with the -msg parameter: openssl s_client -msg -connect myserver.net:443 Then look for the ServerKeyExchange message. Here is an example: <<< TLS 1.2 Handshake [length 014d], ServerKeyExchange 0c 00 01 49 03 00 17 41 04 6b d8 6e 14 1c 9b 12 4d 58 29 20 e8 e2 1a 24 0d da 8f 38 1a 5d 85 ... 5 There are a bunch of issues involved with this question; the bottom line is that it while it wouldn't be a bad approach from a cryptographical standpoint, it appears to be more costly than the standard approach. Let us first examine the number theory issues: the first question to ask is "does g generate a large prime subgroup of Z/p?". That is, does ... 5 With addition and \mathbb{Z}_n, each party chooses a secret x and sends xg \pmod n over the wire, for an agreed upon generator g. Division by g modulo n is easily computable, and reveals x. In other words, a prerequisite for DH to be secure is that the equivalent to discrete logarithm is hard in the chosen group. With \mathbb{Z}_n and ... 5 This is due to the Extended Euclidean algorithm, which allows us to compute inverses modulo any number. If the modulus is prime, things are even more easier to explain. For prime p, we know that g^{p-1} \equiv 1 \pmod{p}. Therefore, y = g^{p-2} \equiv 1/g \pmod {p}. Therefore, (xg).y \equiv x \pmod{p}, revealing the secret key. If modulus is not ... 5 The problem doesn't lie with curves in Weierstrass form necessarily, but with naive implementations of elliptic curve arithmetic on such curves. Basically, if you implement an ECC scheme (ECDH, ECDSA or whatever) on a smart card using a curve in Weierstrass form in the most straightforward way possible (by writing a simple double-and-add loop for ... 5 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. ... 4 Given a EC public key, can a different, but plausible and functional private key be derived to match the public key? No, a public key will correspond to only one private key (with one minor exception, which I will explain below). With Elliptic Curve systems, the private key is an integer d between 1 and q (the order the generator point G), and ... 4 Even if you were doing that you would only ensure that the communication between you and "some" router is secure. It's still possible to MITM using arpspoof for instance such that in: [you] <--- A ---> [hacker] <--- B ---> [router] Communications A & B are encrypted, yet you're not talking to the real router. 4 The simplest index-calculus attack on discrete logarithms is the following. You have a generator g, a target y and a bunch of small primes \ell_1, \dots, \ell_k. The computation proceeds in three phases. First generate lots of relations of the form$$g^{r_i} = \prod_j \ell_j^{s_{ij}}. These relations give you a set of linear equations in $r_i$, ...

4

To decrypt with this system, the decryptor first computes $g^{ab}$ (which he can do because he knows one of the two private exponents); then, he computes the modular inverse of $g^{ab}$; that is written as $(g^{ab})^{-1}$. The modular inverse is defined the same way that the regular multiplicative inverse is defined in the reals (although there it is ...

4

The risks are much higher that there will be mistakes in a novice (or even advanced) implementation. Look at the history of OpenSSL. It was long thought secure, until someone discovered a timing side channel attack. How would you know your code is secure against all the vulnerabilities you don't know about?

4

$\pi$ is the transcendental number 3.1415926... It's there in the formula to show this specific number was not chosen with a specific cryptographical backdoor in mind; it seems unlikely that anyone was able to select the value of $\pi$ (unless Carl Sagan was correct, of course :-)

4

What we have to show for random self reducibility is that we can reduce an efficient algorithm for solving an arbitrary (worst-case) instance to an algorithm that solves a random instance efficiently. Consequently, an efficient algorithm for the average case implies an efficient algorithm for the worst case. You already have outlined how this is ...

4

The encryption of the signatures $\;$ keeps the identity of the initiator (Alice) confidential, even against active attackers $\;\;\;\;$ and $\;$ keeps the identity of the responder (Bob) confidential against passive eavesdroppers $\;\;\;\;$ and $\;$ provides some protection against identity misbinding attacks, $\;$ although not as much as a good protocol ...

4

What you are envisioning has basically been standardized as the integrated encryption scheme being a hybrid encryption scheme providing message authenticity (IND-CCA security).

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