7 ms·

Please elaborate the downvotes. While not actually testing Curve25519 is perfectly valid for the authors, comepletly ignoring its existence is a bit far-fetched

by ge0rg 11y ago

Please elaborate the downvotes. While not actually testing Curve25519 is perfectly valid for the authors, comepletly ignoring its existence is a bit far-fetched, as it is clearly in scope. To quote the first sentence of the paper: "We show that elliptic-curve cryptography implementations on mobile devices are vulnerable to electromagnetic and power side-channel attacks." At least they should have said "some implementations" or "widely-used implementations".

cjbprime 11y ago
Upvoted, you're totally correct. Each of these attacks is providing support to DJB's focus on constant time implementations of everything.
- mikeash 11y ago
  Does constant time mean constant power usage and constant EM emission? It seems like those would be separate problems.
  - marcosdumay 11y ago
    They are highly correlated. The best way to achieve constant time is making your code paths data independent, that is, it always execute the same instructions, whatever the data. This code will also use constant power and have constant EM emission. (Except for low level optimizations in hardware, that may break any of those characteristics.)
    - mikeash 11y ago
      That parenthetical sounds extremely important! Won't executing the same instructions on different data use different amounts of power and emit different amounts of EM? For example, I would think (naively, I'm only familiar with the most basic of hardware whatnot) that multiplying 0 and 0 would not use the same amount of power and emit the same EM as multiplying 0xffffffff by 0xffffffff.
      - powerbutton65 11y ago
        Yes, this exactly the basis of differential power analysis. This was first demonstrated back in 1999 by Kocher et al [0] [0]: https://www.cis.upenn.edu/~nadiah/courses/cis800-02-f13/readings/kocher-jaffe-jun.pdf https://www.cis.upenn.edu/~nadiah/courses/cis800-02-f13/read...
        baby 11y ago
        and in a video: https://www.youtube.com/watch?v=gbqNCgVcXsM https://www.youtube.com/watch?v=gbqNCgVcXsM
      - deleted 11y ago
        [deleted]
      - marcosdumay 11y ago
        That depends on the specifics. The fastest implementation of most integer instructions use constant time. Constant power and EM depend on some extra factors, but when there is variance, it is normally very small (a transistor or two not switching for each bit of difference).
  - powerbutton65 11y ago
    Constant time only reduces the chance of 'simple power analysis' (SPA) which is predominantly what the authors perform ('simple' is misleading but it's just the name for it). There are a number of works that perform 'differential power analysis' (DPA) attacks on mobile devices that target symmetric crypto. These are generally both constant time and constant execution path. In this instance, attackers can attack the data dependancy in the EM emanations. Simple example! a program that XORs two registers: r1 = r1 XOR r2 If r2 has all the bits set to 1, then this will completely invert the contents of r1. This in turn consumes more energy (and hence emit more EM) in comparison to if r2 was all 0's. Hope that clarifies.
- nullc 11y ago
  Your comment is demonstrating the material misunderstandings created by the overused of marketing for subtle technical matters. The implementations of ed25519 that you can find, including the ones worked on by DJB, are not "constant time everything"-- they're constant time for secret key operations. Other operations, like signature verification, are variable time... because that is usually fine and important for performance. It isn't always fine, however, -- you don't want an voting system anonymizer leaking information about which order it is validating which ballots, for example. Of course, 25519 implementations are by far not the only cryptographic code which achieves basic side-channel resistance-- and there are other things which go further and try to achieve stronger resistance to other kinds of sidechannels by also implementing blinding... If people go around incorrectly thinking these implementations are "constant time everything", eventually someone will get burned -- because the real culprit isn't constant time or not, it's the mismatch between requirements and provided properties. Since speed is also a frequently required (security!) property there is no such thing as a strictly more conservative choice, and no replacement for understanding and imagination.
powerbutton65 11y ago
The paper serves to demonstrate that electromagnetic side-channel attacks on mobile devices (even almighty Apple stuff) are feasible. ECDSA is just an example they chose. Also, Curve25519 is only side-channel resistant to timing side-channels, this does NOT protect it in any way against the EM side-channels exploited in this paper. You can't expect the authors to go over every possible curve out there.
- ge0rg 11y ago
  I was not questioning the impact of their demonstration, which is really impressive. However, being responsible academics, they should have done their related work research. And when doing related work research on side-channel attacks against elliptic curves, it is hardly possible to miss Curve25519 and the fact that it was designed with side-channel attacks in mind. The authors at least reference earlier work by DJB on attacking AES. Also, Curve25519 is only side-channel resistant to timing side-channels, this does NOT protect it in any way against the EM side-channels exploited in this paper. This only reinforces the point that performing an EM side-channel attack on Curve25519/NaCl/Sodium would have been a good contribution to the state of the art, with mentioning Curve25519 in the "Future work" section a viable second.
tptacek 11y ago
This is academic crypto research involving one of the most important names in this part of the field (Eran Tromer is one of the people who invented microarchitectural side channel attacks). I don't know that it's typical for research like this to comprehensively evaluate targets that aren't relevant to the research. Regardless, here we have an attack on the ECDSA k-nonce. People who use Curve25519 don't even use ECDSA; they use Ed25519's deterministic Schnorr-style signatures. It's not even the same signature construction. So what you're asking of the authors seems a bit like the authors of the DROWN paper explaining that their RSA padding oracle attack doesn't work if you instead use DH key agreement.
- ge0rg 11y ago
  I'm only a crypto hobbyist, so I haven't followed the field (side-channel attacks on ECC) too closely. Still, the authors themselves address ECC and not jus ECDSA in the related work section, and I considered Curve/Ed-25519 to be a sufficiently important contribution to the field to at least mention it. One way or the other, this is really impressive work and it shows yet another reason to avoid ECDSA, unless you are a crypto rocket surgeon.
  - tptacek 11y ago
    Again: Ed25519 isn't ECDSA. Not just different curves, but different signature constructions. Curve25519 and ECDSA are orthogonal. I'd have disagreed with your comment even if you had said "Ed25519" instead of "Curve25519", but I especially disagree with the comment you actually wrote.
    - ge0rg 11y ago
      Thanks for the clarification. While I am aware that Curve25519 is not Ed25519 is not ECDSA, they all at least belong into the field of Elliptic Curve Cryptography. It is hard for an outsider to tell how wide a certain sub-field is, and how far the related work research should go. I merely took the hints from the paper, which addressed ECC in some places, and wrongfully concluded that DJB's research would be still on topic.
software_radio 11y ago
The paper clearly says what was vulnerable. Don't extrapolate from the summary, that most likely wasn't even written by "them."

by ge0rg 11y ago

cjbprime 11y ago

Upvoted, you're totally correct. Each of these attacks is providing support to DJB's focus on constant time implementations of everything.

mikeash 11y ago
Does constant time mean constant power usage and constant EM emission? It seems like those would be separate problems.
- marcosdumay 11y ago
  They are highly correlated. The best way to achieve constant time is making your code paths data independent, that is, it always execute the same instructions, whatever the data. This code will also use constant power and have constant EM emission. (Except for low level optimizations in hardware, that may break any of those characteristics.)
  - mikeash 11y ago
    That parenthetical sounds extremely important! Won't executing the same instructions on different data use different amounts of power and emit different amounts of EM? For example, I would think (naively, I'm only familiar with the most basic of hardware whatnot) that multiplying 0 and 0 would not use the same amount of power and emit the same EM as multiplying 0xffffffff by 0xffffffff.
    - powerbutton65 11y ago
      Yes, this exactly the basis of differential power analysis. This was first demonstrated back in 1999 by Kocher et al [0] [0]: https://www.cis.upenn.edu/~nadiah/courses/cis800-02-f13/readings/kocher-jaffe-jun.pdf https://www.cis.upenn.edu/~nadiah/courses/cis800-02-f13/read...
      - baby 11y ago
        and in a video: https://www.youtube.com/watch?v=gbqNCgVcXsM https://www.youtube.com/watch?v=gbqNCgVcXsM
    - deleted 11y ago
      [deleted]
    - marcosdumay 11y ago
      That depends on the specifics. The fastest implementation of most integer instructions use constant time. Constant power and EM depend on some extra factors, but when there is variance, it is normally very small (a transistor or two not switching for each bit of difference).
- powerbutton65 11y ago
  Constant time only reduces the chance of 'simple power analysis' (SPA) which is predominantly what the authors perform ('simple' is misleading but it's just the name for it). There are a number of works that perform 'differential power analysis' (DPA) attacks on mobile devices that target symmetric crypto. These are generally both constant time and constant execution path. In this instance, attackers can attack the data dependancy in the EM emanations. Simple example! a program that XORs two registers: r1 = r1 XOR r2 If r2 has all the bits set to 1, then this will completely invert the contents of r1. This in turn consumes more energy (and hence emit more EM) in comparison to if r2 was all 0's. Hope that clarifies.
nullc 11y ago
Your comment is demonstrating the material misunderstandings created by the overused of marketing for subtle technical matters. The implementations of ed25519 that you can find, including the ones worked on by DJB, are not "constant time everything"-- they're constant time for secret key operations. Other operations, like signature verification, are variable time... because that is usually fine and important for performance. It isn't always fine, however, -- you don't want an voting system anonymizer leaking information about which order it is validating which ballots, for example. Of course, 25519 implementations are by far not the only cryptographic code which achieves basic side-channel resistance-- and there are other things which go further and try to achieve stronger resistance to other kinds of sidechannels by also implementing blinding... If people go around incorrectly thinking these implementations are "constant time everything", eventually someone will get burned -- because the real culprit isn't constant time or not, it's the mismatch between requirements and provided properties. Since speed is also a frequently required (security!) property there is no such thing as a strictly more conservative choice, and no replacement for understanding and imagination.

powerbutton65 11y ago

The paper serves to demonstrate that electromagnetic side-channel attacks on mobile devices (even almighty Apple stuff) are feasible. ECDSA is just an example they chose. Also, Curve25519 is only side-channel resistant to timing side-channels, this does NOT protect it in any way against the EM side-channels exploited in this paper. You can't expect the authors to go over every possible curve out there.

ge0rg 11y ago
I was not questioning the impact of their demonstration, which is really impressive. However, being responsible academics, they should have done their related work research. And when doing related work research on side-channel attacks against elliptic curves, it is hardly possible to miss Curve25519 and the fact that it was designed with side-channel attacks in mind. The authors at least reference earlier work by DJB on attacking AES. Also, Curve25519 is only side-channel resistant to timing side-channels, this does NOT protect it in any way against the EM side-channels exploited in this paper. This only reinforces the point that performing an EM side-channel attack on Curve25519/NaCl/Sodium would have been a good contribution to the state of the art, with mentioning Curve25519 in the "Future work" section a viable second.

tptacek 11y ago

This is academic crypto research involving one of the most important names in this part of the field (Eran Tromer is one of the people who invented microarchitectural side channel attacks). I don't know that it's typical for research like this to comprehensively evaluate targets that aren't relevant to the research. Regardless, here we have an attack on the ECDSA k-nonce. People who use Curve25519 don't even use ECDSA; they use Ed25519's deterministic Schnorr-style signatures. It's not even the same signature construction. So what you're asking of the authors seems a bit like the authors of the DROWN paper explaining that their RSA padding oracle attack doesn't work if you instead use DH key agreement.

ge0rg 11y ago
I'm only a crypto hobbyist, so I haven't followed the field (side-channel attacks on ECC) too closely. Still, the authors themselves address ECC and not jus ECDSA in the related work section, and I considered Curve/Ed-25519 to be a sufficiently important contribution to the field to at least mention it. One way or the other, this is really impressive work and it shows yet another reason to avoid ECDSA, unless you are a crypto rocket surgeon.
- tptacek 11y ago
  Again: Ed25519 isn't ECDSA. Not just different curves, but different signature constructions. Curve25519 and ECDSA are orthogonal. I'd have disagreed with your comment even if you had said "Ed25519" instead of "Curve25519", but I especially disagree with the comment you actually wrote.
  - ge0rg 11y ago
    Thanks for the clarification. While I am aware that Curve25519 is not Ed25519 is not ECDSA, they all at least belong into the field of Elliptic Curve Cryptography. It is hard for an outsider to tell how wide a certain sub-field is, and how far the related work research should go. I merely took the hints from the paper, which addressed ECC in some places, and wrongfully concluded that DJB's research would be still on topic.

software_radio 11y ago

The paper clearly says what was vulnerable. Don't extrapolate from the summary, that most likely wasn't even written by "them."