RistrettoWith Curve 25519, we have an order which has a cofactor of eight. This can lead to a range of weaknesses, such as for octal spending. Sometimes this can be overcome with some bit twiddling, but the best way is to create a light-weight group that integrates on top of Curve 25519. In this case we will use Ristretto255, and which has an order which is a prime number. The core usage is with Ed25519, and which provides digital signatures using Curve 25519. The order of Ristretto255 is \(2^{252}+27742317777372353535851937790883648493\), and which is the same as the subgroup prime order for Curve 25519. The security of Ristretto255 is thus the same as Curve 25519. Ristretto255
TheoryIn the Python Cryptography library, the module which contains most of the functions is given the name of “Hazmat”, which is short for “Hazardous Materials”. For this, it is defined that: You should ONLY use it if you’re 100% absolutely sure that you know what you’re doing because this module is full of land mines, dragons, and dinosaurs with laser guns. The warning is highly significant, and proper cryptography is often a difficult subject which needs a good deal of experience in both theory and practice. And, so, I spend a good deal of time in the guts of programs and finding problems which weaken the system. Just last week, I said to a developer, “Did you know I can add a point to your signature and still produce a valid signature?” “Sorry, what?” I then showed how I could easily octal-spend on a transaction and produce another seven valid Ed25519 signatures from a single valid one. So what’s the problem? Well, in a highly secure environment, developers need to fully understand the methods they are using and in the same way that a bridge architecture needs to understand the law of mechanics. So, let’s dive into the wonderful Curve 25519 and find out its weaknesses. What is an order?In cryptographic systems, we typically implement within a group with a prime order of ℓ. But what does this mean? Well, let’s say we have a simple cipher and where we modular multiply by \(h\), and then to decipher, we modulo divide by \(h\). The cipher would then be: \(c=h.x \pmod p\) If we select \(p\) as 7 and \(h\) as 2, we then map: x=0 -> c=0 x=1 -> c=3 x=2 -> c=6 x=3 -> c=2 x=4 -> c=5 x=5 -> c=1 x=6 -> c=4 And now we repeat: x=7 -> c=0 x=8 -> c=3 and so on. This is a ring which has outputs from 0 ... 6, and thus the number of valid outputs is 7. This is known as the order of the group, and in this case is a prime number. In this case number of possible outputs is equal to the prime number, but the order can differ from this as not all the outputs might be valid. If we now have \(h^x \pmod p\), and with \(h=3\) and \(p=11\), we get: x=0 -> c=1 x=1 -> c=3 x=2 -> c=2 x=3 -> c=6 x=4 -> c=4 x=5 -> c=5 And now we repeat: x=6 -> c=1 x=7 -> c=3 and so on. The order is 6. In discrete log problems the order is \(p-1\) and which will not be a prime number. For elliptic curve cryptography, the order of the curve is not not equal the prime number used. This is because not all the (x,y) points have a solution of the elliptic curve equation, such as for: \(y^2 = x^3 + ax+b \pmod p\) For example, if we pick a=5 and p=53 [here], we have: \(y^2 = x^3 + 5x + 7 \pmod {53}\) From this we get valid points of [here]: [(1, 15), (1, 38), (2, 48), (2, 5), (3, 46), (3, 7), (4, 41), (4, 12), (8, 33), (8, 20), (11, 42), (11, 11), (12, 24), (12, 29), (13, 19), (13, 34), (16, 46), (16, 7), (18, 24), (18, 29), (22, 18), (22, 35), (23, 24), (23, 29), (25, 49), (25, 4), (26, 8), (26, 45), (33, 49), (33, 4), (34, 46), (34, 7), (36, 16), (36, 37), (40, 36), (40, 17), (42, 23), (42, 30), (43, 21), (43, 32), (44, 44), (44, 9), (45, 41), (45, 12), (46, 0), (48, 49), (48, 4), (49, 33), (49, 20), (51, 28), (51, 25), (52, 1), (52, 52)] We can see there are no valid points at x=5, x=6 and x=7. This reduces the number of points we can have, as we are not using the full range of points. In this case, the order is 29, as there are 29 possible x values. The order is then a prime number. The problemThe problem we have, is that many of our existing elliptic curves do not have a prime number order, and there is typically a cofactor. This means that the order is h⋅ℓ, and where h is typically 4 or 8. Overall, this can cause vulnerabilities, and which are fixed within the implementation of the method. This means that we cannot formally prove the methods. Unfortunately, though, prime-order curves provide a correct proof, but they are slower than the ones with cofactors. The solution to this was proposed by Mike Hamburg in his Decaf proposal [1]. With this, we can convert from a curve with a small co-factor into one which has a prime order — and with no loss of performance. One such curve is Curve 25519, and which has a co-factor of 8. This means that the total number of points is 8⋅𝑝′ and where 𝑝′ is a prime of \(2^{252}+27742317777372353535851937790883648493\). Overall, we use a prime number of \(2^{255}-19\) (and which has 255 bits), and but the prime order value has 252 bits — due to the bits of the co-factor (as the value of eight has three bits). Ristretto255Within key exchange (X25519), we overcome a security weakess by clearing the three least significant bits of scalar values — this is known as clamping, and does a similar operation to just multiply by the co-factor. The least signifcant bits of a scalar value for key exchange with Curve 25519 are thus always zeros. This reduces the security of the curve, but makes it more secure against attacks. While the paper focuses on co-factors of 4, we can extend to co-factors of 8 with Ristretto255. This matches well to Curve 25519, and especially to Ed25519. Overall, Ed25519 is often used with zero-knowledge proofs, and where weaknesses can be introduced if there is no modifications. One of these is the double-spend vulnerability (or defined more precisely as “octal-spend”). This is where it is possible to add a low-order point to an existing transaction and end up with a valid transaction. We also see the vulnerability in the Tor network which uses Ed25519 for siggnatures. With this, each Tor node has eight addresses, which represent each of the combinations of the three least significant bits. While the fix for X25519 works, we cannot do this with Ed25519. With Ristretto, we do not clear the three least significant bits but add in a lightweight layer which fixes the order and gives us a prime-order group. ClampingI has a problem to solve recently. In ECDH (Elliptic Curve Diffie-Hellman) with X25519 — and which uses Curve 25519 rather than NIST P256. With this, Alice generates a and Bob generates b. Next, Alice computes aG (and which is the point G added a times), and Bob computes bG. They pass these values, and then Alice computes a(bG), and Bob computes b(aG), and they end up with abG and have a shared key. Here is an example [here]:I has a problem to solve recently. In ECDH (Elliptic Curve Diffie-Hellman) with X25519 — and which uses Curve 25519 rather than NIST P256. With this, Alice generates a and Bob generates b. Next, Alice computes aG (and which is the point G added a times), and Bob computes bG. They pass these values, and then Alice computes a(bG), and Bob computes b(aG), and they end up with abG and have a shared key. Here is an example [here]: Bob private (b): 10 Alice private (a): 9 Bob public (bG): b'c288c2bc5d7953c290c2a25433c39e41c3a7c29e4a0368c2822b4e3cc383c3b13709c2a554c391005dc2ab467e' Alice public (aG): b'c3900b0269c3b66758c3b27ac2afc3833b33c28e0ac3ac21c39bc3be73c38128c2ba75c29fc2b4c3a043c2a10b2b54' Bob shared (b)aG: b'564521c2b742c3934b36c3adc3b4127b2bc29ec38dc2890fc39b510b53083bc3a004174860c39ec3ab5d1f' Alice shared (a)bG: b'564521c2b742c3934b36c3adc3b4127b2bc29ec38dc2890fc39b510b53083bc3a004174860c39ec3ab5d1f' And so, I tried to compute (ab) G, and where we multiply a by b, and then perform the multiplication: print (“\n\nJust checking …”) res=(bytes_to_int(a)*bytes_to_int(b)) k = base_point_mult(int_to_bytes(res,32)) print (“\n\nChecking shared (ab)G:\t”,binascii.hexlify(k.encode())) And the answer is not the same as a(bG) and b(aG): Just checking … Checking shared (ab)G: b’2fc3a57dc2a347c38d62431528c39ac2ac5fc2bb290730c3bfc3b6c284c2afc384c38fc382c3adc290c2995f58c38b3b74' So what’s the problem? Well, it took me a while to realise, but it’s all to do with clamping, and where the least significant bits are masked, so that the three least significant bits are set to zero: def clamp(n): n &= ~7 n &= ~(128 << 8 * 31) n |= 64 << 8 * 31 return n Thus, the value of 9 (1001) will be 8 (1000), and the value of 10 (1010) will also be 8 (1010). Thus we actually have 8 times 8, which is 64. Bob private (b): 8 Alice private (a): 8Bob public (bG): b’0bc386c28f6872172fc29dc2a9c3835bc3a0c28276c2a636c2a804c29d4426c39cc2b5067c56c2b81138504d6a’ Alice public (aG): b’0bc386c28f6872172fc29dc2a9c3835bc3a0c28276c2a636c2a804c29d4426c39cc2b5067c56c2b81138504d6a’ Bob shared (b)aG: b’c2ac54c3b0546711c2956fc2b2035ac2a4c2a531c2b1c293731d65c2916ac2b4c3aac287c2961714024fc392c2a17b’ Alice shared (a)bG: b’c2ac54c3b0546711c2956fc2b2035ac2a4c2a531c2b1c293731d65c2916ac2b4c3aac287c2961714024fc392c2a17b’ Just checking …Checking shared (ab)G: b’c2af6c6bc3a037c38c0622c3a8c28a735ac298c3b77ac3806f372bc2adc28542c2bc0f65c380c385c280c2b0c295c2ae4e’ Bob private (b): 10 Alice private (a): 9 Bob public (bG): b'c288c2bc5d7953c290c2a25433c39e41c3a7c29e4a0368c2822b4e3cc383c3b13709c2a554c391005dc2ab467e' Alice public (aG): b'c3900b0269c3b66758c3b27ac2afc3833b33c28e0ac3ac21c39bc3be73c38128c2ba75c29fc2b4c3a043c2a10b2b54' Bob shared (b)aG: b'564521c2b742c3934b36c3adc3b4127b2bc29ec38dc2890fc39b510b53083bc3a004174860c39ec3ab5d1f' Alice shared (a)bG: b'564521c2b742c3934b36c3adc3b4127b2bc29ec38dc2890fc39b510b53083bc3a004174860c39ec3ab5d1f' The code is here: And so, I tried to compute (ab) G, and where we multiply a by b, and then perform the multiplication: print (“\n\nJust checking …”)res=(bytes_to_int(a)*bytes_to_int(b))k = base_point_mult(int_to_bytes(res,32))print (“\n\nChecking shared (ab)G:\t”,binascii.hexlify(k.encode())) And the answer is not the same as a(bG) and b(aG): Just checking …Checking shared (ab)G: b’2fc3a57dc2a347c38d62431528c39ac2ac5fc2bb290730c3bfc3b6c284c2afc384c38fc382c3adc290c2995f58c38b3b74' So what’s the problem? Well, it took me a while to realise, but it’s all to do with clamping, and where the least significant bits are masked, so that the three least significant bits are set to zero: def clamp(n): n &= ~7 n &= ~(128 << 8 * 31) n |= 64 << 8 * 31 return n Thus, the value of 9 (1001) will be 8 (1000), and the value of 10 (1010) will also be 8 (1010). Thus we actually have 8 times 8, which is 64. Bob private (b): 8 Alice private (a): 8 Bob public (bG): b’0bc386c28f6872172fc29dc2a9c3835bc3a0c28276c2a636c2a804c29d4426c39cc2b5067c56c2b81138504d6a’ Alice public (aG): b’0bc386c28f6872172fc29dc2a9c3835bc3a0c28276c2a636c2a804c29d4426c39cc2b5067c56c2b81138504d6a’ Bob shared (b)aG: b’c2ac54c3b0546711c2956fc2b2035ac2a4c2a531c2b1c293731d65c2916ac2b4c3aac287c2961714024fc392c2a17b’ Alice shared (a)bG: b’c2ac54c3b0546711c2956fc2b2035ac2a4c2a531c2b1c293731d65c2916ac2b4c3aac287c2961714024fc392c2a17b’ Just checking … Checking shared (ab)G: b’c2af6c6bc3a037c38c0622c3a8c28a735ac298c3b77ac3806f372bc2adc28542c2bc0f65c380c385c280c2b0c295c2ae4e’ References[1] Hamburg, M. (2015). Decaf: Eliminating cofactors through point compression. In Advances in Cryptology — CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2015, Proceedings, Part I 35 (pp. 705–723). Springer Berlin Heidelberg. https://eprint.iacr.org/2015/673.pdf |