# Tag Info

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

10

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

8

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

7

Your problem seems to be at least as hard as the 2-weak Bilinear Diffie-Hellman Inversion Problem (2-wBDHI problem): Given $g, g^x, g^{x^2}, g^y \in \mathbb G$, and $T \in \mathbb G_T$ to determine whether or not $T = e(g,g)^{x^3 y}$. Proof: We first need to define an equivalent version of your problem, where we take some generator $h$ so $g = h^b$. ...

6

It does not; the equation holds for any element $g$. The fact that $g$ is a generator means only that every element of the group can be obtained a key. This is not at all necessary for the protocol.

5

$\mathbb{Z}^*_{13}$ is a group with 12 elements, not 13. A group is defined by a set of elements, and a "law". The law combines two elements and yields a third one within the set. You get a group if the law fulfils some properties (the law is associative, there is a neutral element, each element has an opposite in the group). $\mathbb{Z}_{13}$ is a group ...

5

It's an element of the field of all integers modulo $p$, and these are represented by the numbers $0,\ldots, p-1$. And $g$ will be one of them.

5

There are several possible ways to generate a weak DH group: The attacker can generate a $g$ with a small order; this would make deriving the shared secret from the public values easy. The attacker can generate a $g$ with a smooth order; that is, the order is large, but is composed of small prime factors; this would make deriving the shared secret from the ...

5

The answer is yes; see Chapter 21 of Galbraith's book. Suppose we have your Fixed-Inverse-DH oracle $O(\cdot)$, and given $g^a$ and $g^b$ we want to find $g^{ab}$. We do this in two steps. First, we use $O$ to compute $g^{a^2}$ from $g^{a}$—this is a related problem called the Square-DH problem. Then we use the quarter-squares identity to compute $g^{ab}$. ...

5

This is a reduction showing that if you can compute $g^{a^2}$ given $g^a$, then you can solve the computational Diffie Hellman problem. Here is the reduction. Let $A$ be an adversary that given $g^a$ for a random $a$, outputs $g^{a^2}$ with probability $\epsilon$. We construct $A'$ who receives $u=g^a$ and $v=g^b$ and works as follows. $A'$ runs $A$ three ...

4

When using a Discrete Logarithm based scheme, such as SRP, the rule of thumb is to always use private exponents with a bit length twice the desired security strength. Hence, a 128 bit exponent $a$ will at most give you 64 bits of security. If you want 128 bit security, you need (at least) a 256 bit exponent. This is because the algebraic structure of the ...

4

This has been specified by the standard, steps 4 and 5 of the protocol described in RFC 4253: S generates a random number y (0 < y < q) and computes f = g^y mod p. S receives e. It computes K = e^y mod p, H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K) (these elements are encoded according to their types; see below), ...

4

You can't encrypt a message with ECDH alone, because all it gives you is a shared secret that you can't really control. Rather, you use that secret in a symmetric scheme like AES (generally after passing it through a KBKDF to convert from an ECDH result to a proper-length and less-structured symmetric key, which you then use as the key for symmetric crypto). ...

3

A lot of modern cryptography is based on some mathematical assumptions and aims to achieve what is called Computational Security. That means that the adversary (Eve) could get some information about the plaintext with a negligible probability and the adversary is modeled as someone with bounded computational power, storage and bounded time. So all the ...

3

The twist attack is best explained in Fouque et al's paper. While the (quadratic) twist of the curve $E : y^2 = x^3 + ax + b \in \mathbb{F}_p$ is indeed of the form $E^t : y^2 = x^3 + d^2ax + d^3b \in \mathbb{F}_{p}$ for nonsquare $d$, you can also think of the twist as the set of points $(x, y)$ in $E^2 : y^2 = x^3 + ax + b \in \mathbb{F}_{p^2}$ where $x$ ...

3

DH: OpenSSL commandline has three options for creating certs, but all of them either selfsign the cert or require a selfsigned CSR, and DH can't do either of those. OpenSSL library called from a program you write can construct an X509 object (cert) containing a DH publickey, subject and other attributes as you specify, signed by an RSA key corresponding to a ...

3

This sounds like "fair exchange," the subject of many good research papers. In general you need a third party to give any security guarantees, but "optimistic fair exchange" involves the third party only when one of the parties tries to cheat (i.e., when both play honestly there is no involvement from the third party). Incidentally, Diffie-Hellman is most ...

3

Agreeing with @otus but adding more background and context than I think belongs in comments: This is an OpenSSL question though you don't say so; all other SSL/TLS software I've looked at uses the RFC spellings DHE ECDHE DH_anon ECDH_anon, but OpenSSL was written yonks ago with EDH in some places (mostly the ones dating before ECC was introduced and there ...

3

How does Diffie-Hellman prevent a man-in-the-middle attack? Answer: Diffie-Hellman does not prevent a man-in-the-middle attack. If you're using Diffie-Hellman without any sort of authentication, then Oscar can certainly change the keys. When he does that, what's effectively happen is that Alice and Bob aren't actually negotiating keys; Alice is ...

3

The problem about Man-in-the-Middle attack on Diffie-Hellman is that both sides are not confident about other side's public key (g^a and g^b). If they were sure that they have correct public key of their's friend Man-in-the-Middle attack wouldn't be possible, because MITM attack is based on the forgery of public keys by adversary! If for instance Bob and ...

3

Actually, RFC3526 does have recommendations for the random number size; see section 8, and the table listing "exponent size". Now, it gives two different recommendations (which sounds rather less useful than giving one); the summary is that if the size of the random number you pick is $x$ bits, then an attacker can recover the shared secret with no more ...

3

For a given prime $p$, there are many choices for the generator $g$, but $g$ cannot be completely arbitrary. As the name hints, $g$ is supposed to be a generator of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ (or at least a large subgroup, more on this later), that is, it must have the property that the set of its powers modulo $p$ $\{g^1 \bmod p, ... 3 The best option you have is TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA. This is likely to provide most security, as the AES keylength is maximal and ECDSA keys tend to provide more security than RSA keys, as a 128-bit security level is quite common with ECDSA (field size: 256 bit) whereas 112-bit is the standard with RSA (keylength: 2048 bit). However in practice ... 3 I haven't checked, is$p$a safe prime and/or is 4 a generator over$p$? Server has random secret$S$, known$p$and$g$a generator. I'm substituting in$V$for your$g$, with$g = 4$.$V = g^S \mod pV$is a verifier of the server, as in SRP.$V$is your$g$, so known by the client. Anyone knowing$V$can establish communications with the server. ... 2 Well, as it says in your link the problem is authentication. So somehow Alice and Bob must set up an authenticated channel. One way of implementing such a channel is by Alice and Bob holding each others public verification key for a signature scheme. A CA would probably not hold a secret key for Alice and Bob. However, using a CA to get an authentic copy ... 2 According to RFC 5246 (and older standards), DHE means ephemeral Diffie–Hellman. EDH isn't a standard way to state it, but it doesn't have another usual meaning. I.e. all but the ECDH-* ones should have perfect forward secrecy. However, the export algorithms (EXP-*) are very weak, probably using only 40-bit keys. The other *-DES-CBC-SHA algorithms with ... 2 I know how Diffie-Hellman Key Exchange works. Is this the main way of encrypting with PGP, ssh, ssl (https), DKIM, ...? As the name says Diffie-Hellman key exchange is a key exchange protocol, i.e., a protocol where two parties agree on a common secret without having exchanged any secret prior to that, in an interactive way, i.e., both parties are ... 2 Mostly. The two problems are actually more closely equivalent in a gap model than in a non-gap model. Square-DH clearly reduces to CDH either way, but CDH reduces to two calls to Square-DH (you have 3, but you can use$(u-v)^2$to make it 2). This is fine if the Square-DH adversary is always right, but maybe the adversary only solves the Square-DH problem ... 2 Does using a slow-hash on the output of an asymmetric key-exchange offer any more protection in a quantum-computing era? No.$\:$A quantum attacker would simply find seed even if you didn't use "a slow-hash on" it. Is the algorithm (greatly) diminished, or completely broken? The algorithm will still be completely broken by quantum attacks. ... 2 Fkraiem's answer is correct: this is not necessary. From your comment on his answer it seems however you don't understand why Alice and Bob retrieve the same key. This, again, doesn't rely on$g$being a generator. Recall from your high school math classes that$(g^a)^b = g^{ab} = g^{ba} = (g^b)^a\$. This is basically the trick that is being used here. Since ...

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