Re: [cryptography] A question about public keys
Well I think there are two issues: 1. if the public key is derived from a password (like a bitcoin brainwallet), or as in EC based PAKE systems) then if the point derived from your password isnt on the curve, then you know that is not a candidate password, hence you can for free narrow the password search. (Which particularly for PAKE systems weakens their security). 2. if the software doesnt properly validate that the point is on the curve, and tries to do an operation involving a private key or secret, anyway, it may leak some of the secret. DJB has some slides saying he found some software does not check. This is what elligator is about, a more deterministic way to hash keys to curves. Which is an improvement with a more friendly curve to the approach used by eg http://tools.ietf.org/html/draft-harkins-tls-pwd-03 where the way you do it is x = hash2curve( password, counter ), test (x,y) on curve, start counter at 0, and repeat until the point is on the curve. Thats bad because you have to do it lots of times, to be fairly sure it'll work its timing dependent so that leaks password entropy etc. Its much easier to aim for constant time with elligator technique and curves. Adam On Thu, Oct 03, 2013 at 02:41:30PM +0100, Michael Rogers wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 29/09/13 20:24, Nico Williams wrote: Just because curve25519 accepts every 32-byte value as a public key doesn't mean that every 32-byte value is a valid public key (one resulting from applying the curve25519 operation). The Elligator paper discusses several methods for distinguishing valid public keys from random. On 30/09/13 05:55, Trevor Perrin wrote: Phrasing this better: check that x^3 + 486662x^2 + x is a square modulo 2^255-19 Thanks Nico and Trevor for your replies. If I understand right, you're both pointing to the most severe distinguisher in section 1.1 of the Elligator 2 paper. I'm afraid I still don't understand what it means for curve25519 to accept a string as a public key if that string isn't a valid public key. Does it just mean that the function has a defined output for that input, even though that output isn't cryptographically useful? Silently accepting invalid input and producing useless output seems like a bug rather than a feature, so I feel like I must still be misunderstanding the real meaning of accepts. Cheers, Michael -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJSTXQKAAoJEBEET9GfxSfMIJkH/jmClrIJ6kD3D/h5MMf7cvIp BVLMmGROGwIFhIrfFZwfqEFGQzBZNpMP06BYJsyPbMRf1uLxFixIYHhSYXCcA+IJ ZvcLMkMptNVb2xPr9jkdC3tXd47udo23Pxo8pP3uo0i265TMkdNOyY4WwJlrnCGQ B7FDXeNXRAtNxdbfrFR2hpCd6yyVk+rqDl3AxNCQ01Slf8HmfOKtcZu7WHHwxQFZ 4ECVtlQmdcAaO8JiNdhWzyzbFW7GEEzvCdzYl3hZTqyXfXM+asGFw90K4qXKAoZS l3S7Q5Pl7tg0KxDL6iHz0XVUMpxH31Mac09DM+dZWT9hp7PEFWiF79XzD0AGi+4= =qqWu -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
On Thu, Oct 3, 2013 at 6:41 AM, Michael Rogers mich...@briarproject.orgwrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 29/09/13 20:24, Nico Williams wrote: Just because curve25519 accepts every 32-byte value as a public key doesn't mean that every 32-byte value is a valid public key (one resulting from applying the curve25519 operation). The Elligator paper discusses several methods for distinguishing valid public keys from random. On 30/09/13 05:55, Trevor Perrin wrote: Phrasing this better: check that x^3 + 486662x^2 + x is a square modulo 2^255-19 Thanks Nico and Trevor for your replies. If I understand right, you're both pointing to the most severe distinguisher in section 1.1 of the Elligator 2 paper. Yes. I'm afraid I still don't understand what it means for curve25519 to accept a string as a public key if that string isn't a valid public key. Suppose you are a good guy with a static curve25519 key, and a bad guy is sending you 32-byte strings, claiming them to be ephemeral curve25519 public keys for use in an ephemeral-static Diffie-Hellman. You repeatedly perform your side of the ephemeral-static DH. I.e., you perform a curve25519 operation betweeen the bad guy's alleged ephemeral public key and your private key. After each DH, you give the bad guy, say, some MAC based on the Diffie-Hellman result. At issue is whether this is safe without checking that the bad guy's strings correspond to possible public keys. And it is, with curve25519! But with some other curves, it isn't. In particular, if the bad guy's public key can have small order (eg generates a group with, say, 7 elements), then the resulting DH shared-secret will be confined to 7 values. The bad guy can easily test all 7 values for the MAC key, thus learning the value of your private key modulo 7. By repeating this with other public keys of small order, and using the Chinese Remainder Theorem, the bad guy could solve for your private key. Curve25519 prevents this without requiring an explicit check. See discussion of twist and small-subgroup attacks in the Curve25519 paper for more: http://cr.yp.to/ecdh/curve25519-20060209.pdf Trevor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 03/10/13 15:14, Adam Back wrote: Well I think there are two issues: 1. if the public key is derived from a password (like a bitcoin brainwallet), or as in EC based PAKE systems) then if the point derived from your password isnt on the curve, then you know that is not a candidate password, hence you can for free narrow the password search. (Which particularly for PAKE systems weakens their security). Presumably if you ensure that the private key is valid, the public key derived from it must be a point on the curve. So it's a matter of validating private rather than public keys. I understand what you're saying about a timing side-channel in the draft-harkins-tls-pwd approach, but here I'm not concerned with validating a public key after generating it, but rather with the puzzling statement that there's no need to validate a public key after receiving it: How do I validate Curve25519 public keys? Don't. The Curve25519 function was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys. http://cr.yp.to/ecdh.html#validate 2. if the software doesnt properly validate that the point is on the curve, and tries to do an operation involving a private key or secret, anyway, it may leak some of the secret. DJB has some slides saying he found some software does not check. Hmm, so perhaps the statement quoted above simply means Curve25519 contains its own key validation code, and will complain if the string you give it isn't a valid public key? Cheers, Michael -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJSTZLlAAoJEBEET9GfxSfM4dMH/jo83Jse5V6DqnZwaIkNesLY AufH8+amkMALbO8Db7r/sG+cGXMy8sSRWqPTJ0jXd3z4ZAgKbx3aW2eBEmIU9i3Y K0jkABVJty3XyvPAspoCUwZ+Fh7brUSCRHQJt0MWMQADPdoXJUY+iobmCGgO4Qbk +npDlo3pTNeEofsvkEM3uSPofR88JXvMC1sYhGr4+GMsBt330vG2Zd278AlVTlOb fVpwEtlad5Fb58RfGidMb4n7BUKKmkPI3KJewpJEXfc8CMP1ITsmX8hTzIz0wakz ubjwDu7ENUMkZhfkt4qNpTLeWQBOFrrfUDe9qrlTY5GpbNfy295K/aWMvi65c6g= =sxPV -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 03/10/13 16:45, Trevor Perrin wrote: Suppose you are a good guy with a static curve25519 key, and a bad guy is sending you 32-byte strings, claiming them to be ephemeral curve25519 public keys for use in an ephemeral-static Diffie-Hellman. You repeatedly perform your side of the ephemeral-static DH. I.e., you perform a curve25519 operation betweeen the bad guy's alleged ephemeral public key and your private key. After each DH, you give the bad guy, say, some MAC based on the Diffie-Hellman result. At issue is whether this is safe without checking that the bad guy's strings correspond to possible public keys. And it is, with curve25519! Thanks! I think I finally understand what it means to say that all 32-byte values are allowed as public keys but not all are valid public keys. Sorry for taking so many round-trips. :-) Cheers, Michael -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJSTZXwAAoJEBEET9GfxSfMUQ4H/R+89hfxD8Wy8wjPt8Bj7gsx rLLquJlvVqlvWqAGXzZcW/zkiqqb8nR5fCU+J5d8dAdB9M1J6AAJC10sDMoj+5/z vIQMBIO+9W28bhaQbb3cWLsaG+tI4Uo/rkZrEPVkBvELXq33fBNjFd4VZFcNUX63 0ZZQwYZ08JzoDtOAIKLHjHq3xEkwi2a5TDGwQMy2p5KUmSf1kIRdyQIMMGoGmKua KWtnfbeledr65+iqFIYyZlntMeMxSrgIJ0CRnjk09sqbkkjz8Pzau4/JEcuLBYhd uJb7y73L2OdKjzWVdYWjLhThKDPnVOf3FVX6CHP121YxBa7zmEYxhhOmpBNOPqc= =PH7z -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
On Thu, Oct 03, 2013 at 04:53:09PM +0100, Michael Rogers wrote: Presumably if you ensure that the private key is valid, the public key derived from it must be a point on the curve. So it's a matter of validating private rather than public keys. I understand what you're saying about a timing side-channel in the draft-harkins-tls-pwd approach, but here I'm not concerned with validating a public key after generating it, but rather with the puzzling statement that there's no need to validate a public key after receiving it: How do I validate Curve25519 public keys? Don't. The Curve25519 function was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys. http://cr.yp.to/ecdh.html#validate Well consider an EC point is an x,y coordinate both coordinates modulo p, some 256-bit prime. There are a number of points on the curve l and for a given base point a number of points generated by that point n. For prime order curves typically the co-factor h = 1 so l=n. (This is analogous to the difference between p = 2q+1 in normal diffie hellman over prime fields. Ther are p values but the group generated by g will hold q possible values before wrapping around where q divides p-1.) So now back to EC to note that n and p are almost the same size (both 256-bit but np, however clearly the number of potential points is in fact 2p (because X=(x,y) and -X=(x,-y) are both points on the curve). But 2pn nearly 2p is nearly 2x n (n the number of points on the curve). So therefore around half of the points you could start from are not on the curve, there is no solution when you try to solve for y from the curve equation. As you see in the harkin draft in that type of curve it is because x^3+ax+b has no square root. So you know about point compression? Basically you can almost recover a point from the x-coord only because each point is (x,f(x)) but with one caveat that because its a symmetric curve about the x-axis you also need to say whether thats f(x) or -f(x). So people would send the x-coord and one bit for the sign. Its getting kind of complicated but it seems to me DJB ensures all 32 byte encoded points are points by a kind of definitional trick that a point is not the x-coord and sign bit, but the number x multiplied by a base point (9,f(9)) which of course is a valid point because (9,f(9)) is a generator. Its an equally valid encoding method and is probably faster. However if you call (9,f(9))=G, you cant use DJB point encoding when you're doing PAKE because well if password attempt pwd1 you get pwd1.G and then you do some DH thing with it, send to the otherside they do Y=x.pwd1.G and send back, thats bad because you can revise pwd1 to pwd2 by division: pwd2.pwd1^-1.Y = pwd2.pwd1^-1.x.G=x.pwd2.G and then you can offline grind the PAKE key exchange which is bad. So for that you really need to start from x = H(password) and point G=(x,f(x)) and that was what the hunt and peck algorithm in Harkins is about. DJB has a solution for that too in his Elligator paper which is constant time (as I recall worst case two tries) because he can use a different method relating to the more flexible and and more efficient curves he chose. Is it just me or could we better replace NIST by DJB ? ;) He can do that EC crypto, and do constant time coding (nacl), and non-hackable mail servers (qmail), and worst-time databases (cdb). Most people in the world look like rank amateurs or no-real-programming understanding niche-bound math geeks compared to DJB! Adam -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 03/10/13 15:14, Adam Back wrote: Well I think there are two issues: 1. if the public key is derived from a password (like a bitcoin brainwallet), or as in EC based PAKE systems) then if the point derived from your password isnt on the curve, then you know that is not a candidate password, hence you can for free narrow the password search. (Which particularly for PAKE systems weakens their security). 2. if the software doesnt properly validate that the point is on the curve, and tries to do an operation involving a private key or secret, anyway, it may leak some of the secret. DJB has some slides saying he found some software does not check. Hmm, so perhaps the statement quoted above simply means Curve25519 contains its own key validation code, and will complain if the string you give it isn't a valid public key? Cheers, Michael -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJSTZLlAAoJEBEET9GfxSfM4dMH/jo83Jse5V6DqnZwaIkNesLY AufH8+amkMALbO8Db7r/sG+cGXMy8sSRWqPTJ0jXd3z4ZAgKbx3aW2eBEmIU9i3Y K0jkABVJty3XyvPAspoCUwZ+Fh7brUSCRHQJt0MWMQADPdoXJUY+iobmCGgO4Qbk +npDlo3pTNeEofsvkEM3uSPofR88JXvMC1sYhGr4+GMsBt330vG2Zd278AlVTlOb fVpwEtlad5Fb58RfGidMb4n7BUKKmkPI3KJewpJEXfc8CMP1ITsmX8hTzIz0wakz ubjwDu7ENUMkZhfkt4qNpTLeWQBOFrrfUDe9qrlTY5GpbNfy295K/aWMvi65c6g= =sxPV -END PGP SIGNATURE- ___ cryptography mailing
Re: [cryptography] A question about public keys
On 2013-10-04 03:45, Adam Back wrote: Is it just me or could we better replace NIST by DJB ? ;) He can do that EC crypto, and do constant time coding (nacl), and non-hackable mail servers (qmail), and worst-time databases (cdb). Most people in the world look like rank amateurs or no-real-programming understanding niche-bound math geeks compared to DJB! Committees are at best inherently more stupid than their most stupid member, and are at worst also inclined to evil and madness. Linux was success because Linus is unelected president for life. Let us have Jon Callas as unelected president for life of symmetric cryptography, Bernstein as God King of public key cryptography. Recall the long succession of Wifi debacles. Has any committee ever done anything good in cryptography? IEEE 802.11 was stupid. If NIST was not stupid, it was because evil was calling the shots behind the scenes, overruling the stupid. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] A question about public keys
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Sorry for making so much noise on the list today. I have a quick question about public keys. The Curve25519 paper says that every 32-byte string is accepted as a Curve25519 public key. Yet Elligator doesn't use Curve25519. So I guess there must be a way to distinguish a bunch of Curve25519 public keys from a bunch of random 32-byte strings. What is it? Cheers, Michael -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJSSFT6AAoJEBEET9GfxSfMHLIH/1W98ezG12sqVPAmjcRBauoP EbChv+BzACaOz62I0Jxhc8quGHK3eqYOB0pDtFp2nGWuJpAw7OEKSAVNCABcTO/n OKTk0v24pNCf82RKF2UfAVr43s+cC2N8ApwYobC12Dp1C8DqxiBX+ERS/XleM12b LrPcVW0W6WYcnsK2CgOlENg70XaLDn1bn1M/O+DAsb8ue8nBoXN5UXGMaLRGEkuc jAOBljsiLdPc+gS6waseBuYTWnLk2plnHfrSXOR/1P+rM9rcQgZJsYsPJALzXXeH +ZbSW0+T0NbUMN8kmEhuNOSqGH5CBBpPYzm3dJEXVT1zdBGIyLPQUf475IFZHso= =H7Qj -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
I should add that the ability to distinguish public DH keys from random is a big deal in some cases. For example, for EKE: there's a passive off-line dictionary attack that can reject a large fraction of possible passwords with each EKE iteration -- if that fraction is 1/2 then after about 20 rounds of EKE you'll have a very high likelihood of having recovered the user's password. This example is hinted at in the Elligator paper (the paper's focus being on privacy protocols). With Elligator (and randomly setting the one bit that is always zero in curve25519 public keys), the passive attacker would have to observe a very large number of EKE rounds before having enough evidence to reject enough possible passwords (that yield public keys larger than 2^256 - 19) to have a good chance of recovering the actual password. Elligator will be a great advance indeed, when it is available. Nico -- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
On Sun, Sep 29, 2013 at 9:27 AM, Michael Rogers mich...@briarproject.org wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Sorry for making so much noise on the list today. I have a quick question about public keys. The Curve25519 paper says that every 32-byte string is accepted as a Curve25519 public key. Yet Elligator doesn't use Curve25519. So I guess there must be a way to distinguish a bunch of Curve25519 public keys from a bunch of random 32-byte strings. What is it? Elligator 2 works for Curve25519, see Section 4 of the Elligator paper: http://eprint.iacr.org/2013/325.pdf To your question: Interpreting the 32-byte value as x, check that x^3 + 486662x^2 + x mod 2^255-19 has a square root. This is similar to the distinguisher in Section 1.1, bullet 3 of the paper. Trevor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] A question about public keys
On Sun, Sep 29, 2013 at 9:29 PM, Trevor Perrin tr...@trevp.net wrote: On Sun, Sep 29, 2013 at 9:27 AM, Michael Rogers mich...@briarproject.org wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Sorry for making so much noise on the list today. I have a quick question about public keys. The Curve25519 paper says that every 32-byte string is accepted as a Curve25519 public key. Yet Elligator doesn't use Curve25519. So I guess there must be a way to distinguish a bunch of Curve25519 public keys from a bunch of random 32-byte strings. What is it? Elligator 2 works for Curve25519, see Section 4 of the Elligator paper: Argh, I meant Section 5. http://eprint.iacr.org/2013/325.pdf To your question: Interpreting the 32-byte value as x, check that x^3 + 486662x^2 + x mod 2^255-19 has a square root. Phrasing this better: check that x^3 + 486662x^2 + x is a square modulo 2^255-19 Trevor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
