Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Joy of Cryptography

joyofcryptography.com

Post reply on HN
Print view View original

91–100 of 105 posts

Re: The Joy of Cryptography

#91

Post by upofadown »

garmaine wrote: post #86
upofadown wrote: post #82

Earlier quoted context omitted.

RSA is faster for signature generation. RSA is faster by more than an order of magnitude for signature verification[1] and encryption[2]. All these libraries listed here are bad in some way for RSA? * https://en.wikipedia.org/wiki/Comparison_of_cryptography_lib... [1] https://www.ijser.org/researchpaper/Performance-Based-Compar... [2] https://hal.archives-ouvertes.fr/hal-02926106/document

Your own link [2] shows RSA being 10-50x slower than the EC algo they used, which itself is many factors slower than state of the art. Are you reading the table right?

Table 3 (decryption) from link [2] shows that it took 1.265 seconds for 233 bit ECC and 0.031 seconds for 2240 bit RSA to encrypt something. The associated comment was:

>We noted that the encryption by the RSA algorithm is faster than the one with ECC algorithm.

While we are here, I will point out that the performance was almost the same for the same key lengths in the encryption case.

So ECC seems to be faster for key generation but overall slower for everything else.

Re: The Joy of Cryptography

#92

Post by marcan_42 »

tptacek wrote: post #73
marcan_42 wrote: post #46

Earlier quoted context omitted.

No magic numbers is certainly one of the advantages of curve25519 and its siblings. The NSA already gave us one backdoored elliptic curve algorithm (Dual EC DRBG); there is no reason to trust them with magic numbers. They may be backdoored or they may not be, but every serious cryptography engineer knows there's no good reason for algorithm constants not to be generated according to public criteria if you aren't hidi…

Curves in the Web PKI are overwhelmingly NIST P-curves, which, again, are only deeply mistrusted on message boards, and when needed to get the BADA55 paper accepted. New designs shouldn't use the P-curves, because it's too easy to implement them vulnerably (for all intents and purposes any random string is a workable Curve25519 point, and that's not the case for the P-curves --- you have to do fussy input validation)…

That the NSA picked the magic DES S-boxes in order to defend against differential cryptanalysis (which they'd discovered first), and that the NSA picked the Dual EC DRBG constants to backdoor it in a NOBUS type operation are both established facts.

Yes, curves in the Web PKI are largely P curves right now, but ed25519 is also standardized.

You're certainly free to trust the NIST curves, but my point still stands: there is no good reason not to pick such constants using a nothing up my sleeve algorithm, and the fact they didn't do that means they either know something we don't, they backdoored it, they wanted people to suspect they backdoored it, or they're idiots and decided to ignore established best practice for no reason. It's entirely possible the answer is the latter, of course :)

Re: The Joy of Cryptography

#93

Post by marcan_42 »

upofadown wrote: post #91
garmaine wrote: post #86

Earlier quoted context omitted.

Your own link [2] shows RSA being 10-50x slower than the EC algo they used, which itself is many factors slower than state of the art. Are you reading the table right?

Table 3 (decryption) from link [2] shows that it took 1.265 seconds for 233 bit ECC and 0.031 seconds for 2240 bit RSA to encrypt something. The associated comment was: >We noted that the encryption by the RSA algorithm is faster than the one with ECC algorithm. While we are here, I will point out that the performance was almost the same for the same key lengths in the encryption case. So ECC seems to be faster for k…

Those numbers are clearly nonsense; notice how the smaller ones don't even scale with key size, while they obviously should to some extent. That paper is flawed. They obviously made a mistake.

Look at the ed25519 benchmarks:

https://ed25519.cr.yp.to/

71000 signature verifications per second and 109000 signature generations per second on a quad-core machine. That is much, much faster than RSA.

It's well established that ECC is much faster than RSA in general. I suspect I know what happened. DSA signature schemes require randomness to generate signatures, unlike RSA. They probably were using an entropy-constrained random number generator. That bottlenecked ECDSA through no fault of the algorithm. Ed25519 does not suffer from this issue, since it is constructed in a way that requires no external source of randomness (the random part is substituted with a deterministic hash of the key and input).

Re: The Joy of Cryptography

#94

Post by __MatrixMan__ »

smus wrote: post #88
__MatrixMan__ wrote: post #85

Earlier quoted context omitted.

Yeah, I think you're right. There's something about real analysis that makes me uncomfortable. I've been struggling for years to put my finger on it. Whatever it is, topology doesn't have it. I had mistakenly decided that it was an overappreciation of continuity, but I think it must be something else.

Maybe it's the differential structure itself? Or an (over?)emphasis on the study of functions from space to space instead of the study of the space itself? Or the specificity of calculus (the study of one specific space) instead of the generality of topology (thinking about a lot of spaces and comparing them to each other)

Hmm, I'll have to ponder those. Specificity seems closest. Whatever it is, it's not a rational critique. Despite the discomfort, I'm also fascinated by it because one should not have an emotional response to specific types of math, but I very much do.

Something about the homework in Real Analysis left me feeling angry. Not because it was difficult or presented poorly, but because it was somehow... untrustworthy? As if my betters had decided which ideas were the good ones and the only thing left for me to do was optimize along the one dimension that they had assigned me. I realize that this is nonsense, but I can't seem to shake it.

Re: The Joy of Cryptography

#95

Post by smus »

__MatrixMan__ wrote: post #94
smus wrote: post #88

Earlier quoted context omitted.

Maybe it's the differential structure itself? Or an (over?)emphasis on the study of functions from space to space instead of the study of the space itself? Or the specificity of calculus (the study of one specific space) instead of the generality of topology (thinking about a lot of spaces and comparing them to each other)

Hmm, I'll have to ponder those. Specificity seems closest. Whatever it is, it's not a rational critique. Despite the discomfort, I'm also fascinated by it because one should not have an emotional response to specific types of math, but I very much do. Something about the homework in Real Analysis left me feeling angry. Not because it was difficult or presented poorly, but because it was somehow... untrustworthy? As i…

I think it's totally good and human to have preferences for one sort of math over another :)

Re: The Joy of Cryptography

#96

Post by tptacek »

marcan_42 wrote: post #92
tptacek wrote: post #73

Earlier quoted context omitted.

Curves in the Web PKI are overwhelmingly NIST P-curves, which, again, are only deeply mistrusted on message boards, and when needed to get the BADA55 paper accepted. New designs shouldn't use the P-curves, because it's too easy to implement them vulnerably (for all intents and purposes any random string is a workable Curve25519 point, and that's not the case for the P-curves --- you have to do fussy input validation)…

That the NSA picked the magic DES S-boxes in order to defend against differential cryptanalysis (which they'd discovered first), and that the NSA picked the Dual EC DRBG constants to backdoor it in a NOBUS type operation are both established facts. Yes, curves in the Web PKI are largely P curves right now, but ed25519 is also standardized. You're certainly free to trust the NIST curves, but my point still stands: the…

No, the logic in your last paragraph doesn't hold at all. You should read the Menezes paper rather than trying to derive this stuff from faulty axioms.

Re: The Joy of Cryptography

#97

Post by upofadown »

marcan_42 wrote: post #93
upofadown wrote: post #91

Earlier quoted context omitted.

Table 3 (decryption) from link [2] shows that it took 1.265 seconds for 233 bit ECC and 0.031 seconds for 2240 bit RSA to encrypt something. The associated comment was: >We noted that the encryption by the RSA algorithm is faster than the one with ECC algorithm. While we are here, I will point out that the performance was almost the same for the same key lengths in the encryption case. So ECC seems to be faster for k…

Those numbers are clearly nonsense; notice how the smaller ones don't even scale with key size, while they obviously should to some extent. That paper is flawed. They obviously made a mistake. Look at the ed25519 benchmarks: https://ed25519.cr.yp.to/ 71000 signature verifications per second and 109000 signature generations per second on a quad-core machine. That is much, much faster than RSA. It's well established th…

If you want to prove that ed25519 is generally faster than RSA for signatures I think you would have to find a benchmark that supports your contention.

Re: The Joy of Cryptography

#98

Post by marcan_42 »

upofadown wrote: post #97
marcan_42 wrote: post #93

Earlier quoted context omitted.

Those numbers are clearly nonsense; notice how the smaller ones don't even scale with key size, while they obviously should to some extent. That paper is flawed. They obviously made a mistake. Look at the ed25519 benchmarks: https://ed25519.cr.yp.to/ 71000 signature verifications per second and 109000 signature generations per second on a quad-core machine. That is much, much faster than RSA. It's well established th…

If you want to prove that ed25519 is generally faster than RSA for signatures I think you would have to find a benchmark that supports your contention.

https://blog.cloudflare.com/ecdsa-the-digital-signature-algo...

RSA 2048 bits: 1001 signatures per second ECDSA P-256: 9516 signatures per second

Note that 256-bit RSA provides a higher security level than 2048-bit RSA, so this is biased in RSA's favor.

https://connect2id.com/blog/nimbus-jose-jwt-6

That one has ed25519 signing 60x faster than RSA-2048. Verification is a bit slower with ed25519 (RSA is very asymmetric there due to the low hamming weight public exponents), but considering the difference in security level, it basically works out to about the same.

So signature verification is about the same for EC vs RSA, while EC is much faster than RSA for signature generation, and ridiculously faster for key generation. EC certainly isn't significantly slower than RSA for any equivalent operation, and definitely not by 40x like the paper you linked claims. That is just wrong.

Re: The Joy of Cryptography

#99

Post by upofadown »

marcan_42 wrote: post #98
upofadown wrote: post #97

Earlier quoted context omitted.

If you want to prove that ed25519 is generally faster than RSA for signatures I think you would have to find a benchmark that supports your contention.

https://blog.cloudflare.com/ecdsa-the-digital-signature-algo... RSA 2048 bits: 1001 signatures per second ECDSA P-256: 9516 signatures per second Note that 256-bit RSA provides a higher security level than 2048-bit RSA, so this is biased in RSA's favor. https://connect2id.com/blog/nimbus-jose-jwt-6 That one has ed25519 signing 60x faster than RSA-2048. Verification is a bit slower with ed25519 (RSA is very asymmetric…

It is fairly well accepted that RSA is faster than most curve based things for signature verification and your sources support that?

This is all in response to another user who said:

> There is a massive performance difference—not just size, but computation as well.

... and we don't know exactly what they meant by that, but I was pointing out that it was not that simple...

Asymmetrical performance is normally not very important in most systems due to the use of symmetric stuff to do all the heavy lifting. The exception would be if you were doing some sort of forward secrecy scheme that involved forgetting the private key for each and every message. There the speed of ECDHE is helpful vs the slow key generation of RSA. However, the Signal Protocol shows us we can use a hash ratchet for such short cycle forward secrecy schemes so that key generation speed does not have to be a significant issue.

Re: The Joy of Cryptography

#100

Post by Terry_Roll »

bdamm wrote: post #87
Terry_Roll wrote: post #76

Earlier quoted context omitted.

So in a replay attack all the communication is recorded including the session keys, and whilst primes are infinite dont dispute this, where the theory (human) and the practical (cpu's) differs is the limitations in the machine hardware, in much the same way Spectre and Meltdown exploited the hardware to obtain secrets. The point about the webserver was using methods to work out what the underlying webserver and versi…

Cryptanalysis is a pretty robust area of research. There are in fact a lot of cryptanalysts that know CPUs quite deeply. Certain organizations spend a great deal of money to make it so. If vulnerabilities are found we learn from them and advance the understanding of cryptography design. It has been that way for 76 years now, at least.

Not disputing what you say, but mistakes do happen to the best of us.

http://sunnyday.mit.edu/accidents/Ariane5accidentreport.html and yet again another OpenSSL bug , another flaw in the open source fallacy of many eyes to spot bugs... https://nakedsecurity.sophos.com/2021/03/28/serious-security...

plus when considering in maths there are ways to rearrange formulas including new discoveries like this one (a new way to do quadratic equations) https://news.ycombinator.com/item?id=29342161 https://www.sciencealert.com/math-genius-finally-discovers-e...

I wonder if discovering a new way to do things could be done to cryptographic algorithms.

Post reply on HN