Computation of a 30750-Bit Binary Field Discrete Logarithm • Hacker News Board

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#11

Post by fractionalhare » Tue, Oct 06, 2020, 2:26 PM UTC

rocqua wrote: post #7

Is all the research for asymmetric cryptographic primitives that do not depend on discrete logarithms currently focused on post-quantum-crypto research? Personally, I am not aware of any alternative systems outside of the post-quantum-crypto world.

Yes and no.

Yes, in the sense that any system which is not based on an intractability assumption that reduces to the discrete logarithm problem is of research interest for post-quantum cryptography.

No, in the sense that some of the systems under consideration predate serious research in quantum cryptanalysis (including Shor's and Grover's attacks).

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#12

Post by fractionalhare » Tue, Oct 06, 2020, 2:29 PM UTC

blame_lewis wrote: post #10

fractionalhare wrote: post #9

Earlier quoted context omitted.

I would be shocked if SHA-256 is fundamentally broken in the next 20 years. I also think AES will remain substantially as strong as it currently is in that timeframe, with cryptanalytic weaknesses dominated by particular block cipher modes rather than the substitution-permutation network itself.

AES is one of the few that has a pretty good shot at it, yeah. SHA-2 has had its margin eroded significantly over the last 10 years. I'd feel nervous about using it in security-critical applications now , never mind 20 years down the line. ECB is insecure regardless of which cipher you use. There's no excuse for using it in production applications. http://valerieaurora.org/hash.html

No, SHA-2 has not had its margins eroded "significantly", and you should not feel nervous about using it whatsoever. It's fundamentally different from MD5 in structure, so you shouldn't extrapolate a few years' worth of minor weaknesses to forecast major weaknesses in the near future.

The website you've linked is citing legitimate cryptanalytic papers, but it loses credibility by interpreting systems with minor weaknesses as "not considered strong." Minor weaknesses are exhibited in all cryptosystems older than a few years. Can you find me a professional cryptographer who will say SHA-2 is not strong? Because I can't think of any. The authors of these cryptanalytic papers would probably choose it for new projects without being nervous.

It's an attractive idea that cryptographic algorithms will trend towards insecurity over time. But that's a very oversimplified look at how they work, and it's not a reliable prediction over a period several deep research breakthroughs away from a meaningful break in SHA-2.

But I'm just some guy on the internet. If you don't trust my opinion on this, here is the opinion of one of the BLAKE authors, a finalist in the SHA-3 competition: https://twitter.com/veorq/status/834872988445065218

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#13

Post by BlackFingolfin » Tue, Oct 06, 2020, 3:55 PM UTC

MrXOR wrote: post #2

TIL: “The best theory is inspired by practice. The best practice is inspired by theory.” (by Don aka "Yoda") An unpopular opinion: time until the end of ECC = 20 years Good links: [1] https://en.wikipedia.org/wiki/Discrete_logarithm_records [2] https://dldb.loria.fr [3] http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf

The article is about discrete logarithms in binary finite fields, though, not in elliptic curves; so are the references you give (other than Wikipedia). Perhaps elaborate how you draw conclusions about ECC from this? (I am not saying I disagree, but I feel your comment is oddly disconnected from TFA)

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#14

Post by MrXOR » Tue, Oct 06, 2020, 4:22 PM UTC

BlackFingolfin wrote: post #13

MrXOR wrote: post #2

TIL: “The best theory is inspired by practice. The best practice is inspired by theory.” (by Don aka "Yoda") An unpopular opinion: time until the end of ECC = 20 years Good links: [1] https://en.wikipedia.org/wiki/Discrete_logarithm_records [2] https://dldb.loria.fr [3] http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf

The article is about discrete logarithms in binary finite fields, though, not in elliptic curves; so are the references you give (other than Wikipedia). Perhaps elaborate how you draw conclusions about ECC from this? (I am not saying I disagree, but I feel your comment is oddly disconnected from TFA)

The end of DLP (over any field) is the end of ECC.

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#15

Post by vbezhenar » Tue, Oct 06, 2020, 4:32 PM UTC

blame_lewis wrote: post #8

MrXOR wrote: post #6

Earlier quoted context omitted.

EDIT: there isn't any unpopular opinion :-) Qs: What about AES? RSA first or ECC?

AES is one of the few that I'm pretty confident will be around for a while. RSA already has a lot of caveats to its use and they will undoubtedly grow. In my completely uneducated opinion, it's even odds on RSA vs ECC first.

As long as you’re using it correctly RSA should work, right? We’re not going to factor big numbers anytime soon and RSA is pretty much about factoring.

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#16

Post by MrXOR » Tue, Oct 06, 2020, 4:39 PM UTC

blame_lewis wrote: post #8

MrXOR wrote: post #6

Earlier quoted context omitted.

EDIT: there isn't any unpopular opinion :-) Qs: What about AES? RSA first or ECC?

AES is one of the few that I'm pretty confident will be around for a while. RSA already has a lot of caveats to its use and they will undoubtedly grow. In my completely uneducated opinion, it's even odds on RSA vs ECC first.

I completely agree.

My real unpopular opinion: designing a secure asymmetric cipher is much harder than symmetric.

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#17

Post by BlackFingolfin » Tue, Oct 06, 2020, 6:42 PM UTC

MrXOR wrote: post #14

BlackFingolfin wrote: post #13

Earlier quoted context omitted.

The article is about discrete logarithms in binary finite fields, though, not in elliptic curves; so are the references you give (other than Wikipedia). Perhaps elaborate how you draw conclusions about ECC from this? (I am not saying I disagree, but I feel your comment is oddly disconnected from TFA)

The end of DLP (over any field) is the end of ECC.

Why? Is there a reduction from EC DLP to FF DLP?

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#18

Post by blame_lewis » Wed, Oct 07, 2020, 1:46 AM UTC

vbezhenar wrote: post #15

blame_lewis wrote: post #8

Earlier quoted context omitted.

AES is one of the few that I'm pretty confident will be around for a while. RSA already has a lot of caveats to its use and they will undoubtedly grow. In my completely uneducated opinion, it's even odds on RSA vs ECC first.

As long as you’re using it correctly RSA should work, right? We’re not going to factor big numbers anytime soon and RSA is pretty much about factoring.

Yes, but in the real world there are a lot of opportunities for implementation failure.

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#19

Post by thu2111 » Wed, Oct 07, 2020, 8:19 AM UTC

MrXOR wrote: post #14

BlackFingolfin wrote: post #13

Earlier quoted context omitted.

The article is about discrete logarithms in binary finite fields, though, not in elliptic curves; so are the references you give (other than Wikipedia). Perhaps elaborate how you draw conclusions about ECC from this? (I am not saying I disagree, but I feel your comment is oddly disconnected from TFA)

The end of DLP (over any field) is the end of ECC.

No it isn't. The curves used in all real systems are based on prime fields. The results against binary fields don't seem to generalise to curves deployed in the wild.

Re: Computation of a 30750-Bit Binary Field Discrete Logarithm

#20

Post by thu2111 » Wed, Oct 07, 2020, 8:21 AM UTC

vbezhenar wrote: post #15

blame_lewis wrote: post #8

Earlier quoted context omitted.

AES is one of the few that I'm pretty confident will be around for a while. RSA already has a lot of caveats to its use and they will undoubtedly grow. In my completely uneducated opinion, it's even odds on RSA vs ECC first.

As long as you’re using it correctly RSA should work, right? We’re not going to factor big numbers anytime soon and RSA is pretty much about factoring.

RSA key sizes have gone up constantly over the years exactly because we did factor ever bigger numbers. ECC key sizes are the same as when the schemes were new, that's one reason ECC is better.