4 ms·

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.

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.