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

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 =& ... 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. ... 7 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; ... 6 This expands CodesInChaos's comment into an answer. Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and ... 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 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 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 \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 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 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 ... 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 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 What you are envisioning has basically been standardized as the integrated encryption scheme being a hybrid encryption scheme providing message authenticity (IND-CCA security). 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 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 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 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 I'm guessing whoever made the program was confused about key lengths. A 256-bit DH modulus will not give 256-bits of security. It will provide far less. If you're reading http://www.keylength.com, the value here corresponds to the "discrete logarithm group". These days you really want a minimum of 2048 bits. 3 In TLS, the key exchange step results in a key called the master secret which is then derived into as much key material as needed with a custom key derivation function, called in TLS terminology the PRF. It is not slow -- contrary to PBKDF2, the "PRF" of TLS is not for handling password and thus has no need to be slow. 3 This algorithm is vulnerable to a Man in the middle. From Wikipedia: In the original description, the Diffie–Hellman exchange by itself does not provide authentication of the communicating parties and is thus vulnerable to a man-in-the-middle attack. Mallory may establish two distinct key exchanges, one with Alice and the other with Bob, effectively ... 3 Are there any advantages to “1.”, especially when users must communicate the password/key through a separate channel in both cases? As the comments (1, 2) already indicated: the first option “1.” will be easier to communicate. When you talk about a “high-entropy key”, I assume you are generating that high-entropy with a cryptographically secure random ... 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 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 ... 2 Yes, it's secure. It is somewhat overkill, however, since you could stop replay attacks by using either: a persistent counter as IV, or a random nonce, and including a timestamp in the message. The AEAD must authenticate the IV (and GCM certainly does), so either would work without requiring any extra round-trips. You can just use the IV in the initial ... 2 Using Diffie-Hellman key agreement for generating a nonce should be safe as long as both key pairs are ephemeral, i.e. generated for each run of the key agreement protocol. Otherwise a man-in-the-middle can fool one of the parties in generating the same nonce over and over again. Ephemeral Diffie-Hellman is however overkill for generating a nonce, as the ... 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 Alice didn't know that 16\equiv 3^{24}\mod 17. The video just made it clearer that they were intrisically computing the same value. I'm guessing that the point the video was trying to make was that$$3^{54\times24}\equiv3^{24\times54}\equiv 16^{54}\equiv15^{24}\equiv1\mod 17.

2

Yes, the same keypairs can be used to derive shared secrets between multiple pairs of parties. If knowing the shared secret between Alice and Bob would help Eve find out the shared secret between Alice and Carol, Eve could just create her own random private key and calculate a "shared" secret between that key and Alice's public key to get the same ...

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