Nytro Posted April 15, 2020 Report Posted April 15, 2020 April 2020 Cofactor Explained: Clearing Elliptic Curves' dirty little secret Much of public key cryptography uses the notion of prime-order groups. We first relied on the difficulty of the Discrete Logarithm Problem. Problem was, Index Calculus makes DLP less difficult than it first seems. So we used longer and longer keys – up to 4096 bits (512 bytes) in 2020 – to keep up with increasingly efficient attacks. Elliptic curves solved that. A well chosen, safe curve can only be broken by brute force. In practice, elliptic curve keys can be as small as 32 bytes. On the other hand, elliptic curves were not exactly fast, and the maths involved many edge cases and subtle death traps. Most of those problems were addressed by Edwards curves, which have a complete addition law with no edge cases, and Montgomery curves, with a simple and fast scalar multiplication method. Those last curves however did introduced a tiny little problem: their order is not prime. (Before we dive in, be advised: this is a dense article. Don't hesitate to take the time you need to digest what you've just read and develop an intuitive understanding. Prior experience with elliptic curve scalar multiplication helps too.) Prime-order groups primer First things first: what's so great about prime-order groups? What's a group anyway? What does "order" even mean? A group is the combination of a set of elements "G", and an operation "+". The operation follows what we call the group laws. For all a and b in G, a+b is also in G (closure). For all a, b, and c in G, (a+b)+c = a+(b+c) (associativity). There's an element "0" such that for all a, 0+a = a+0 = a (identity element). For all a in G, there's an element -a such that a + -a = 0 (inverse element). Basically what you'd expect from good old addition. The order of a group is simply the number of elements in that group. To give you an example, let's take G = [0..15], and define + as binary exclusive or. All laws above can be checked. It's order is 16 (there are 16 elements). Note some weird properties. For instance, each element is its own inverse (a xor a is zero). More interesting are cyclic groups, which have a generator: an element that repeatedly added to itself can walk through the entire group (and back to itself, so it can repeat the cycle all over again). Cyclic groups are all isomorphic to the group of non-negative integers modulo the same order. Let's take for instance [0..9], with addition modulo 10. The number 1 is a generator of the group: 1 = 1 2 = 1+1 3 = 1+1+1 4 = 1+1+1+1 5 = 1+1+1+1+1 6 = 1+1+1+1+1+1 7 = 1+1+1+1+1+1+1 8 = 1+1+1+1+1+1+1+1 9 = 1+1+1+1+1+1+1+1+1 0 = 1+1+1+1+1+1+1+1+1+1 1 = 1+1+1+1+1+1+1+1+1+1+1 (next cycle starts) 2 = 1+1+1+1+1+1+1+1+1+1+1+1 etc. Not all numbers are generators of the entire group. 5 for instance can generate only 2 elements: 5, and itself. 5 = 5 0 = 5+5 5 = 5+5+5 (next cycle starts) 0 = 5+5+5+5 etc. Note: we also use the word "order" to speak of how many elements are generated by a given element. In the group [0..9], 5 "has order 2", because it can generate 2 elements. 1, 3, 7, and 9 have order 10. 2, 4, 6, and 8 have order 5. 0 has order 1. Finally, prime-order groups are groups with a prime number of elements. They are all cyclic. What's great about them is their uniform structure: every element (except zero) can generate the whole group. Take for instance the group [0..10] (which has order 11). Every element except 0 is a generator: (Note: from now on, I will use the notation A.4 to denote A+A+A+A. This is called "scalar multiplication" (in this example, the group element is A and the scalar is 4). Since addition is associative, various tricks can speed up this scalar multiplication. I use a dot instead of "×" so we don't confuse it with ordinary multiplication, and to remind that the group element on the left of the dot is not necessarily a number.) 1.1 = 1 2.1 = 2 3.1 = 3 4.1 = 4 1.2 = 2 2.2 = 4 3.2 = 6 4.2 = 8 1.3 = 3 2.3 = 6 3.3 = 9 4.3 = 1 1.4 = 4 2.4 = 8 3.4 = 1 4.4 = 5 1.5 = 5 2.5 = 10 3.5 = 4 4.5 = 9 1.6 = 6 2.6 = 1 3.6 = 7 4.6 = 2 etc. 1.7 = 7 2.7 = 3 3.7 = 10 4.7 = 6 1.8 = 8 2.8 = 5 3.8 = 2 4.8 = 10 1.9 = 9 2.9 = 7 3.9 = 5 4.9 = 3 1.10 = 10 2.10 = 9 3.10 = 8 4.10 = 7 1.11 = 0 2.11 = 0 3.11 = 0 4.11 = 0 You get the idea. In practice, we can't distinguish group elements from each other: apart from zero, they all have the same properties. That's why discrete logarithm is so difficult: there is no structure to latch on to, so an attacker would mostly have to resort to brute force. (Okay, I lied. Natural numbers do have some structure to latch on to, which is why RSA keys need to be so damn huge. Elliptic curves – besides treacherous exceptions – don't have a known exploitable structure.) The cofactor So what we want is a group of order P, where P is a big honking prime. Unfortunately, the simplest and most efficient elliptic curves out there – those that can be expressed in Montgomery and Edwards form – don't give us that. Instead, they have order P×H, where P is suitably large, and H is a small number (often 4 or 8): the cofactor. Let's illustrate this with the cyclic group [0..43], of order 44. How much structure can we latch on to? 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 Since 44 is not prime, not all elements will have order 44. For instance: 1 has order 44 2 has order 22 3 has order 44 4 has order 11 … You get the idea. When we go over all numbers, we notice that the order of each element is not arbitrary. It is either 1, 2, 4, 11, 22, or 44. Note that 44 = 11 × 2 × 2. We can see were the various orders come from: 1, 2, 2×2, 11, 11×2, 11×2×2. The order of an element is easy to test: just multiply by the order to test, see if it yields zero. For instance (remember A.4 is a short hand for A+A+A+A, and we're working modulo 44 – the order of the group): 8 . 11 = 0 -- prime order 24 . 11 = 0 -- prime order 25 . 11 = 33 -- not prime order 11 . 4 = 0 -- low order 33 . 4 = 0 -- low order 25 . 4 = 12 -- not low order ("Low order" means orders below 11: 1, 2, 4. Not much lower than 11, but if we replace 11 by a large prime P, the term "low order" makes more sense.) Understandably, there are only few elements of low order: 0, 11, 22, and 33. 0 has order 1, 22 has order 2, 11 and 33 have order 4. Like the column on the left, they form a proper subgroup. It's easier to see by swapping and rotating the columns a bit: 0 11 22 33 4 15 26 37 8 19 30 41 12 23 34 1 16 27 38 5 20 31 42 9 24 35 2 13 28 39 6 17 32 43 10 21 36 3 14 25 40 7 18 29 The low order subgroup is shown on the first line. And now we can finally see the structure of this group: a narrow rectangle, with 11 lines and 4 columns, where each element in this rectangle is the sum of an element of prime order, and an element of low order. For instance: 30 = 8 + 22 = 4.2 + 11.2 35 = 24 + 11 = 4.6 + 11.1 1 = 12 + 33 = 4.3 + 11.3 You just have to look left and up to know which elements to sum. To do this algebraically, you need to multiply by the right scalar. You need to clear the (co)factor. Let's first look left. How do we clear the cofactor? We start by an element that can be expressed thus: E = 4.a + 11.b What we want to find is the scalar s such that E.s = 4.a Note that E.s = (4.a + 11.b).s E.s = 4.a.s + 11.b.s E.s = 4.(a×s) + 11.(b×s) E.s = 4.(a×1) + 11.(b×0) Recall that 4 has order 11, and 11 has order 4. So s must follow these equations: s = 1 mod 11 -- preserve a s = 0 mod 4 -- absorb b There's only one such scalar between 0 and 44: 12. So, multiplying by 12 clears the cofactor, and preserves the prime factor. For instance: 13.12 = 24 27.12 = 16 42.12 = 20 Now we know how to look left. To look up, we follow the same reasoning, except this time, our scalar s must follow these equations: s = 0 mod 11 -- absorb a s = 1 mod 4 -- preserve b That's 33. For instance: 13.33 = 33 27.33 = 11 42.33 = 22 Now we can look up as well. (Note: This "looking up" and "looking left" terminology isn't established mathematical terminology, but rather a hopefully helpful illustration. Do not ask established mathematicians or cryptographers about "looking up" and "looking left" without expecting them to be at least somewhat confused.) Torsion safe representatives We now have an easy way to project elements in the prime-order subgroup. Just look left by multiplying the element by the appropriate scalar (in the case of our [0..43] group, that's 12). That lets us treat each line of the rectangle as an equivalence class, with one canonical representative: the leftmost element – the one that is on the prime-order subgroup. This effectively gets us what we want: a prime-order group. Let's say we have a scalar s and an element E, which are not guaranteed to be on the prime-order subgroup. We want to know in which line their scalar multiplication will land, and we want to represent that line by its leftmost element. To do so, we just need to perform the scalar multiplication, then look left. For instance: s = 7 -- some random scalar E = 31 -- some random point E.s = 41 result = (E.s).12 = 8 Or we could first project E to the left, then perform the scalar multiplication. It will stay on the left column, and give us the same result: E = 31 E . 12 = 20 result = (E.12).s = 8 The problem with this approach is that it is slow. We're performing two scalar multiplications instead of just one. That kind of defeats the purpose of choosing a fast curve to begin with. We need something better. Let us look at our result one more time: result = (E.s).12 = 8 result = (E.12).s = 8 It would seem the order in which we do the scalar multiplications does not matter. Indeed, the associativity of group addition means we can rely on the following: (E.s).t = E.(s×t) = E.(t×s) = (E.t).s Now you can see that we can avoid performing two scalar multiplications, and multiply the two scalars instead. To go back to our example: s = 7 -- our random scalar E = 31 -- our random point result = E.(7×12) -- scalarmult and look left result = E.(84) result = E.(40) -- because 84 % 44 = 40 result = 8 Remember we are working with a cyclic group of order 44: adding an element to itself 84 times is like adding it to itself 44 times (the result is zero), and again 40 times. So better reduce the scalar modulo the group order so we can have a cheaper scalar multiplication. Let's recap: s = 7 -- our random scalar E = 31 -- our random point E.s = 41 E.(s×12) = 8 41 and 8 are on the same line, and 8 is in the prime-order subgroup. Multiplying by s×12 instead of s preserved the main factor, and cleared the cofactor. Because of this, we call s×12 the torsion safe representative of s. Now computing (s×12) % 44 may be simple, but it doesn't look very cheap. Thankfully, we're not out of performance tricks: (s×12) % 44 = (s×(11+1)) % 44 = (s×(11+1)) % 44 = (s + (s × 11)) % 44 = s + (s × 11) % 44 -- we assume s < 11 = s + (s%4 × 11) -- we can remove %44 We only need to add s and and a multiple of 11 (0, 11, 2×11, or 3×11). The result is guaranteed to be under the group order (44). The total cost is: Multiplying the prime order by a small number. Adding two scalars together. Compared to the scalar multiplication, that's practically free. Decoupling main factor and cofactor We just found the torsion safe representative of a scalar, that after scalar multiplication preserves the line, and only chooses the left column. In some cases, we may want to reverse roles: preserve the column, and and only chose the top line. In other words, we want to do the equivalent of performing the scalar multiplication, then looking up. The reasoning is the same as for torsion safe representatives, only flipped on its head. Instead of multiplying our scalar by 12 (which is a multiple of the low order, equals 1 modulo the prime order), we want to multiply it by 33: a multiple of the prime order, which equals 1 modulo the low order. Again, modular multiplication by 33 is not cheap, so we repeat our performance trick: (s×33) % 44 = (s×11×3) % (11×4) = ((s×3) % 4) × 11 In this case, we just have to compute (s×3) % 4 and multiply the prime order by that small number. The total cost is just the multiplication of the order by a very small number. Now we can do the decoupling: s = 7 -- some random scalar E = 31 -- some random point E.s = 41 -- normal result E.(s×12) = 8 E.(s×33) = 33 E.s = 8 + 33 = 41 -- decoupled result Cofactor and discrete logarithm Time to start applying our knowledge. Let's say I have elements A and B, and a scalar s such that B = A.s. The discrete logarithm problem is about finding s when you already know A and B. If we're working in a prime-order group with a sufficiently big prime, that problem is intractable. But we're not working with a prime-order group. We have a cofactor to deal with. Let's go back to our group of order 44: 0 11 22 33 4 15 26 37 8 19 30 41 12 23 34 1 16 27 38 5 20 31 42 9 24 35 2 13 28 39 6 17 32 43 10 21 36 3 14 25 40 7 18 29 We can easily recover the line and the column of A and B, so let's do that. Take for instance A = 27 and B = 15. Now let's find s. A = 27 A = 16 + 11 A = 4.4 + 11.1 B = 15 B = 4 + 11 B = 4.1 + 11.1 B = A . s 4.1 + 11.1 = (4.4 + 11.1) . s 4.1 + 11.1 = (4.4).s + (11.1).s 4 .1 = (4 .4).s 11.1 = (11.1).s Now look at that last line. Since 11 has only order 4, there are only 4 possible solutions, which are easy to brute force. We can try them all and easily see that: 11 . 1 = (11.1).1 (mod 44) s mod 4 = 1 The other equation however is more of a problem. There are 11 possible solutions, and trying them all is more expensive: 4 . 1 ≠ (4.4).1 4 . 1 ≠ (4.4).2 4 . 1 = (4.4).3 s mod 11 = 3 Now that we know both moduli, we can deduce that s = 25: A . s = B 27.25 = 15 What we just did here is reducing the discrete logarithm into two, easier discrete logarithms. Such divide and conquer is the reason why we want prime-order groups, where the difficulty of the discrete logarithm is the square root of the prime order (square root because there are cleverer brute force methods than just trying all possibilities). Here however, the difficulty wasn't the square root of 44. It was sqrt(11) + sqrt(2) + sqrt(2), which is significantly lower. The elliptic curves we are interested in however have much bigger orders. Curve25519 for instance has order 8 × L where L is 2²⁵² + something (and the cofactor is 8). So the difficulty of solving discrete logarithm for Curve25519 is sqrt(2)×3 + sqrt(2²⁵²), or approximately 2¹²⁶. Still lower than sqrt(8×L) (about 2¹²⁷), but not low enough to be worrying: discrete logarithm is still intractable. Cofactor and X25519 Elliptic curves can have a small cofactor, and still guarantee we can't solve discrete logarithm. There's still a problem however: the attacker can still solve the easy half of discrete logarithm, and deduce the value of s, modulo the cofactor. In the case of Curve25519, that means 3 bits of information, that could be read, or even controlled by the attacker. That's not ideal, so DJB rolled two tricks up his sleeve: The chosen base point of the curve has order L, not 8×L. Multiplying that point by our secret scalar, can then only generate points on the prime-order subgroup (the leftmost column). The three bits of information the attacker could have had are just absorbed by that base point. The scalar is clamped. Bit 255 is cleared and bit 254 is set to prevent timing leaks in poor implementations, and put a lower bound on standard attacks. More importantly, bits 0, 1, and 2 are cleared, to make sure the scalar is a multiple of 8. This guarantees that the low order component of the point, if any, will be absorbed by the scalar multiplication, such that the resulting point will be on the prime-order subgroup. The second trick is especially important: it guarantees that the scalar multiplication between your secret key and an attacker controlled point on the curve can only yield two kinds of results: A point on the curve, that has prime order. The attacker don't learn anything about your private key (at least not without solving discrete logarithm first), and they can't control which point on the curve you are computing. We're good. Zero. Okay, the attacker did manage to force this output, but this only (and always) happens when they gave you a low order point. So again, they learned nothing about your private key. And if you needed to check for low order output (some protocols, like CPace, require this check), you only need to make sure it's not zero (use a constant-time comparison, please). (I'm ignoring what happens if the point you're multiplying is not on the curve. Failing to account for that has broken systems in the past. X25519 however only transmits the x-coordinate of the point, so the worst you can have is a point on the "twist". Since the twist of Curve25519 also has a big prime order (2²⁵³ minus something) and a small cofactor (4), the results will be similar, and the attacker will learn nothing. Curve25519 is thus "twist secure".) Cofactor and Elligator Elligator was developed to help with censorship circumvention. It encodes points on the curve so that if the point is selected at random, its encoding will be indistinguishable from random. With that tool, the entire cryptographic communication is fully random, including initial ephemeral keys. This enables the construction of fully random formats, and facilitates steganography. Communication protocols often require ephemeral keys to initiate communications. In practice, they need to generate a random key pair, and send the public half over the network. Public keys however will not necessarily look random, even though the private half was indeed random. Curve25519 for instance have a number of biases: Curve25519 points are encoded in 255 bits (we only encode the x-coordinate). Since all communication happens at the byte level, there is one unused bit, which is usually cleared. This is easily remedied by simply randomising the unused bit. The x-coordinate of Curve25519 points does not span all values from 0 to 2²⁵⁵-1. Values 2²⁵⁵-19 and above never occur. In practice though, this bias is small enough to be utterly undetectable. Curve25519 points satisfy the equation y² = x³ + 486662 x² + x. All the attacker has to do is take the suspected x-coordinate, compute the right hand side of the equation, and check whether this is a square in the finite field GF(2²⁵⁵-19). For random strings, it will be about half the time. if it is a Curve25519 x-coordinate, it will be all the time. The remedy is Elligator mappings, which can decode all numbers from 0 to 2²⁵⁵-20 into a point on the curve. Encoding fails about half the time, but we can try generating key pair until we find one that can be turned into a random looking encoding. X25519 keys aren't selected at random to begin with: because of cofactor clearing, they are taken from the prime-order subgroup. Even with Elligator mappings, an attacker can decode the point, and check whether it belongs to the prime-order subgroup. Again, with X25519, this would happen all the time, unlike random representatives. When I first discovered this problem, I didn't know what to do. The remedy is fairly simple once I understood the cofactor. The real problem was reaching that understanding. So, our problem is to generate a key pair, where the public half is a random point on the whole curve, not just the prime-order subgroup. Let's again illustrate it with the [0..43] group: 0 11 22 33 4 15 26 37 8 19 30 41 12 23 34 1 16 27 38 5 20 31 42 9 24 35 2 13 28 39 6 17 32 43 10 21 36 3 14 25 40 7 18 29 Recall that the prime-order subgroup is the column on the left, and the low order subgroup is the first line. X25519 is designed in such a way that: The chosen generator of the curve has prime order. The private key is a multiple of the cofactor. For us here, this means our generator is 4, and our private key is a multiple of 4. You can check that multiplying 4 by a multiple of 4 will always yield a multiple of… 4. An element on the left column. (Remember, we're working modulo 44). But that's no good. I want to select a random element on the whole rectangle, not just the left column. If we recall our cofactor lessons, the solution is simple: add a random low order element. The random prime-order element selects the line, and the random low order element selects the column. Adding them together gives us a random element over the whole group. To add icing on the cake, this method is compatible X25519. Let's take an example. Let's first have a regular key exchange: B = 4 -- Generator of the prime-order group sa = 20 -- Alice's private key sb = 28 -- Bob's private key SA = B.sa = 4.20 = 36 -- Alice's public key SB = B.sb = 4.28 = 24 -- Bob's public key ssa = SB.sa = 24.20 = 40 -- Shared secret (computed by Alice) ssb = SA.sb = 36.28 = 40 -- Shared secret (computed by Bob) As expected of Diffie–Hellman, Alice and Bob compute the same shared secret. Now, what happens if Alice adds a low order element to properly hide her key? Let's say she adds 11 (an element of order 4). LO = 11 -- random low order point HA = SA+LO = 36+11 = 3 -- Alice's "hidden" key ssb = HA.sb = 3.28 = 40 Bob still computes the same shared secret! Which by now should not be a big surprise: scalars that are a multiple of the cofactor absorb the low order component, effectively projecting the result back in the prime order subgroup. Applying this to Curve25519 is straightforward: Select a random number, then clamp it as usual. It is now a multiple of the cofactor of the curve (8). Multiply the Curve25519 base point by that scalar. Add a low order point at random. There's a little complication, though. X25519 works on Montgomery curves, which are optimised for an x-coordinate only ladder. That ladder takes advantage of differential addition. Adding a low order point requires arbitrary addition, whose code is neither trivial nor available. We can work around that problem by starting from Edwards25519 instead: Select a random number, then clamp it as usual. It is now a multiple of the cofactor of the curve (8). Multiply the Edwards25519 base point by that scalar. Add a low order point at random. (By the way, be sure the selection of the low order point happens in constant time. Avoid naive array lookup tables.) Convert the result to Curve25519 (clamping guarantees we do not hit the treacherous exceptions of the birational map). The main advantage here is speed: Edwards25519 scalar multiplication by the base point often takes advantage of pre-computed tables, making it much faster than the Montgomery ladder in practice. (Note: pre-computed tables don't really apply to key exchange, which is why X22519 uses the Montgomery ladder instead.) This has a price however: we now depend on EdDSA code, which is not ideal if we don't compute signatures as well. Moreover, some libraries, like TweetNaCl avoid pre-computed tables to simplify the code. This makes Edwards scalar multiplication slower than the Montgomery ladder. Alternatively, there is a way to stay in Montgomery space: change the base point. Let's try it with the [0..43] group. Instead of using 4 as the base point, we'll add 11, a point whose order is the same as the cofactor (4). Our "dirty" base point is 15 (4+11). Now let's multiply that by Alice's public key: O = 11 -- low order point (order 4) B = 4 -- base point (prime order) D = B+LO = 11+4 = 15 -- "dirty" base point sa = 20 -- Alice's private key SA = B.sa = 4.20 = 36 -- Alice's public key HA = D.sa = 15.20 = 36 -- ??? Okay we have a problem: even with the dirty base point, we get the same result. That's because Alice's private key is still a multiple of the cofactor, and absorbs the low order component. But we don't want to absorb it, we want to use it, to select a column at random. Here's the trick: Use a multiple of the cofactor (4) to select the line. Use a multiple of the prime order (11) to select the column. Add those two numbers. Multiply the dirty base point by it. Note the parallel with EdDSA: we were adding points, now we add scalars. But the result is the same: d = 33 -- random multiple of the prime order da = sa+d = 20+33 = 9 -- Alice's "dirty" secret key HA = D.da = 15. 9 = 3 -- Alice's hidden key Note that we can ensure both methods yield the same results by properly decoupling the main factor and the cofactor. Now we can apply the method to Curve25519: Add a low order point of order 8 to the base point. That's our new, "dirty" base point. That can be done offline, and the result hard coded. (I personally added the Edwards25519 to a low order Edwards point, then converted the result to Montgomery.) Select a random number, then clamp it as usual. It is now a multiple of the cofactor of the curve (8). Note that if we multiply the dirty base point by that scalar, we'd absorb the low order point all over again. Select a random multiple of the prime order. For Curve25519, that means, 0, L, 2L… up to 7L. Add that multiple of L to the clamped random number above. Multiply the resulting scalar by the dirty base point. That way we no longer need EdDSA code. (Note: you can look at actual code in the implementation of the crypto_x25519_dirty_*() functions in my Monocypher cryptographic library.) Cofactor and scalar inversion Scalar inversion is useful for exponential blinding to implement Oblivious Pseudo-Random Functions (OPRF). (It will make sense soon, promise). Let's say Alice wants to connect to Bob's server, with her password. To maximise security, they use the latest and greatest in authentication technology (augmented PAKE). One important difference between that and your run of the mill password based authentication, is that Alice doesn't want to transmit her password. And Bob certainly doesn't want to transmit the salt to anyone but Alice, that would be the moral equivalent of publishing his password database. Yet we must end up somehow with Alice knowing something she can use as the salt: a blind salt, which must be a function of the password and the salt only: Blind_salt = f(password, salt) One way to do this is with exponential blinding. We start by having Alice compute a random point on the curve, which is a function of the password: P = Hash_to_point(Hash(password)) That will act as a kind of secret, hidden base point. The Hash_to_point() function can use the Elligator mappings. Note that even though P is the base point multiplied by some scalar, we cannot recover the value of that scalar (if we could, it would mean Elligator mappings could be used to solve discrete logarithm). Now Alice computes an ephemeral key pair with that base point: r = random() R = P . r She sends R to Bob. Note that as far as Bob (or any attacker) is concerned, that point R is completely random, and has no correlation with the password, or its hash. The difficulty of discrete logarithm prevents them to recover P from R alone. Now Bob uses R to transmit the blind salt: S = R . salt He sends S back to Alice, who then computes the blind salt: Blind_salt = S . (1/r) -- assuming r × (1/r) = 1 Let's go over the whole protocol: P = Hash_to_point(Hash(password)) r = random() R = P . r S = R . salt Blind_salt = S . (1/r) Blind_salt = R . salt . (1/r) Blind_salt = P . r . salt . (1/r) Blind_salt = P . (r × salt × (1/r)) Blind_salt = P . salt Blind_salt = Hash_to_point(Hash(password)) . salt And voila, our blind salt depends solely on the password and salt. You need to know the password to compute it from the salt, and if Mallory tries to connect to Bob, guessing the wrong password will give her a totally different, unexploitable blind salt. Offline dictionary attack is not possible without having hacked the database first. Now this is all very well, if we are working on a prime-order subgroup. Scalars do have an inverse modulo the order of the curve, hash to point will give us what we want… except nope, our group does not have prime order. We need to deal with the cofactor, somehow. The first problem with the cofactor comes from Hash_to_point(). When Elligator decodes a representative into a point on the curve, that point is not guaranteed to belong to the prime-order subgroup. There's the potential to leak up to 3 bits of information about the password (the cofactor of Curve25519 is 8). Fortunately, the point P is not transmitted over the network. Only R is. And this gives us the opportunity to clear the cofactor: R = P . r If the random scalar r is a multiple of 8, then R will be guaranteed to be on the prime-order subgroup, and we won't leak anything. X25519 has us covered: after clamping, r is a multiple of 8. This guarantee however goes out the window as soon as R is transmitted across the network: Mallory could instead send a bogus key that is not on the prime-order subgroup. (They could also send a point on the twist, but Curve25519 is twist secure, so let's ignore that.) Again though, X25519 takes care of this: S = R . salt Just clamp salt, and we again have a multiple of 8, and S will be guaranteed to be on the prime-order subgroup. Of course, Alice might receive some malicious S instead, so she can't assume it's the correct one. And this time, X25519 does not have us covered: Blind_salt = S . (1/r) See, X25519 clamping has a problem: while it clears the cofactor all right, it does not preserve the main factor. Which means clamping neither survives nor preserves algebraic transformations. Inverting r then clamping does not work. Clamping then inverting r does not clear the cofactor. The solution is torsion safe representatives: c = clamp(r) i = 1/c -- modulo L s = i × t -- t%L == 1 and t%8 == 0 Where L is the prime order of the curve. For Curve25519, t = 3×L + 1. The performance trick explained in the torsion safe representatives section apply as expected. (Note: you can look at actual code in the implementation of the crypto_x25519_inverse() function in Monocypher.) Conclusion Phew, done. I confess didn't think I'd need such a long post. But you get the idea: properly dealing with a cofactor these days is delicate. It's doable, but the cleaner solution these days is to use the Ristretto Group: you get modern curves and a prime order group. (Discuss on Hacker News, Reddit, Lobsters) Sursa: http://loup-vaillant.fr/tutorials/cofactor Quote
