5 ms·

Hi HN, I'm one of the authors of this paper. Very cool to see it being discussed here! I'm happy to answer questions about private airdrops, with two caveats:

Hi HN, I'm one of the authors of this paper. Very cool to see it being discussed here! I'm happy to answer questions about private airdrops, with two caveats: first, I'm not associated with Handshake, so I probably don't know the answer to Handshake-specific questions. Second, I'm juggling some other things today, so apologies in advance if my answers are delayed.

rvnx 7y ago
I see (on your own repo) an intriguing mention: "The design of GooSig requires a public RSA modulus whose prime factorization is unknown." I see one of the key is http://certificate.fyicenter.com/356_Root_CA_America_Online_Root_Certification_Authority_1_Ameri.html http://certificate.fyicenter.com/356_Root_CA_America_Online_... Did you choose this key because you consider it to have been lost ?
- kwantam 7y ago
  Great question! The very short answer is "yes." In slightly more detail: We wanted to be able to test with a 4096-bit RSA modulus whose factorization was plausibly unknown, but this is a tough thing to find! (We certainly didn't want to include a modulus that we generated in the codebase, because from the outside there would be no way to know that we hadn't kept a trapdoor.) There are the famous RSA challenge numbers [1], but those only go up to 2048 bits; we include both of the 2048-bit challenge numbers in the repo. Root certificate moduli are almost what we want, since their factorization is a very closely guarded secret. (In fact, in all cases we're aware of, root cert secrets are kept only in hardware security modules, which by design do not allow anyone to extract the factorization---though of course HSMs can be buggy, so this is no silver bullet.) The problem is, the owner of the cert might in principle know the factorization, so we didn't want to pick an active root cert. We settled on the AOL root cert because it's the oldest 4096-bit root cert we could find that (1) that saw widespread use, (2) was plausibly uncompromised, but (3) is no longer actively used. To us, this was the best candidate for a 4096-bit modulus for which the factorization is lost---exactly as you say. This is only a heuristic---someone might know the factorization, in which case they could generate false proofs. We think it's exceedingly unlikely, but each person must assess that risk for themselves. This is related to other issues with trusted setup, "toxic waste," etc. (see, e.g., [2] for a discussion of this in the ZCash context). Another way to generate an RSA modulus whose factorization is plausibly unknown is to use a multi-party computation ceremony. In cases like this, you can believe that the factorization is unknown if you trust some fraction of the parties in the computation (details vary). I've heard that Ethereum is planning to do this at some point in the future, but I do not know any other details. As a final point, if one does not want to trust an RSA modulus, an alternative is to work in an imaginary quadratic class group. It's widely believed that there is no efficient way of computing the order of such a (which is what we require for security), and unlike an RSA group there's no trusted setup---you just pick a random prime and that defines your group. The downside is that group operations are about 10x slower. We discuss this a bit more in the paper, and our Python implementation [3] supports both RSA groups and class groups. Please let me know if the above isn't clear! [1] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge [2] https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/ https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/ [3] https://github.com/kwantam/GooSig https://github.com/kwantam/GooSig
  - rvnx 7y ago
    Very interesting feedback. I appreciate your time detailing the answer. I really like what you have done, it's a beautiful project from a mathematical perspective and the crypto code your team has wrote with GooSig is impressive. I enjoyed reading what you wrote and this made me think a lot about integer factorization, prime numbers discovery, etc, and even found cute comments in the past commits (that one made me smile: https://github.com/kwantam/GooSig/blob/dc9a197c3574127aa37e8a58afdb570a6fb219f7/libGooPy/rsa.py#L31 https://github.com/kwantam/GooSig/blob/dc9a197c3574127aa37e8... fortunately it's not there anymore). Thanks for sharing zkSNARKs too!

rvnx 7y ago

I see (on your own repo) an intriguing mention: "The design of GooSig requires a public RSA modulus whose prime factorization is unknown." I see one of the key is http://certificate.fyicenter.com/356_Root_CA_America_Online_Root_Certification_Authority_1_Ameri.html http://certificate.fyicenter.com/356_Root_CA_America_Online_... Did you choose this key because you consider it to have been lost ?

kwantam 7y ago
Great question! The very short answer is "yes." In slightly more detail: We wanted to be able to test with a 4096-bit RSA modulus whose factorization was plausibly unknown, but this is a tough thing to find! (We certainly didn't want to include a modulus that we generated in the codebase, because from the outside there would be no way to know that we hadn't kept a trapdoor.) There are the famous RSA challenge numbers [1], but those only go up to 2048 bits; we include both of the 2048-bit challenge numbers in the repo. Root certificate moduli are almost what we want, since their factorization is a very closely guarded secret. (In fact, in all cases we're aware of, root cert secrets are kept only in hardware security modules, which by design do not allow anyone to extract the factorization---though of course HSMs can be buggy, so this is no silver bullet.) The problem is, the owner of the cert might in principle know the factorization, so we didn't want to pick an active root cert. We settled on the AOL root cert because it's the oldest 4096-bit root cert we could find that (1) that saw widespread use, (2) was plausibly uncompromised, but (3) is no longer actively used. To us, this was the best candidate for a 4096-bit modulus for which the factorization is lost---exactly as you say. This is only a heuristic---someone might know the factorization, in which case they could generate false proofs. We think it's exceedingly unlikely, but each person must assess that risk for themselves. This is related to other issues with trusted setup, "toxic waste," etc. (see, e.g., [2] for a discussion of this in the ZCash context). Another way to generate an RSA modulus whose factorization is plausibly unknown is to use a multi-party computation ceremony. In cases like this, you can believe that the factorization is unknown if you trust some fraction of the parties in the computation (details vary). I've heard that Ethereum is planning to do this at some point in the future, but I do not know any other details. As a final point, if one does not want to trust an RSA modulus, an alternative is to work in an imaginary quadratic class group. It's widely believed that there is no efficient way of computing the order of such a (which is what we require for security), and unlike an RSA group there's no trusted setup---you just pick a random prime and that defines your group. The downside is that group operations are about 10x slower. We discuss this a bit more in the paper, and our Python implementation [3] supports both RSA groups and class groups. Please let me know if the above isn't clear! [1] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge [2] https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/ https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/ [3] https://github.com/kwantam/GooSig https://github.com/kwantam/GooSig
- rvnx 7y ago
  Very interesting feedback. I appreciate your time detailing the answer. I really like what you have done, it's a beautiful project from a mathematical perspective and the crypto code your team has wrote with GooSig is impressive. I enjoyed reading what you wrote and this made me think a lot about integer factorization, prime numbers discovery, etc, and even found cute comments in the past commits (that one made me smile: https://github.com/kwantam/GooSig/blob/dc9a197c3574127aa37e8a58afdb570a6fb219f7/libGooPy/rsa.py#L31 https://github.com/kwantam/GooSig/blob/dc9a197c3574127aa37e8... fortunately it's not there anymore). Thanks for sharing zkSNARKs too!