8 ms·

Building a Curve25519 Hardware Accelerator

223 points by picture 5y ago

sowbug 5y ago
This work is associated with Precursor (https://www.bunniestudios.com/blog/?p=5921 https://www.bunniestudios.com/blog/?p=5921), which is Bunnie's project to build a mobile hardware platform from the ground up.
jazzyjackson 5y ago
TIL 255 is divisible by 17 Edit: thanks to my replies I know several more things now lol big day for me
- pavpanchekha 5y ago
  256 = 16 * 16 255 = 256 - 1 = 16 * 16 - 1 = 15 * 17
- pfortuny 5y ago
  (a^2-1)=(a+1)(a-1).
- jandrese 5y ago
  It is also divisible by 5.
- Sesse__ 5y ago
  2^p - 1 can only be prime (a so-called Mersenne prime) if p is prime. 2^8 - 1 thus cannot be a prime, since 8 is composite. (Note that is it not _sufficient_ that p is prime, but it is necessary.)
upofadown 5y ago
>The “double ratchet” algorithm is integral to modern end-to-end-encrypted chat apps, such as Signal, WhatsApp, and Matrix. Signal protocol uses a hash ratchet for the message to message forward secrecy. So you don't need to do the expensive key agreement stuff unless that hash ratchet falls out of synchronization. It isn't really clear if any messaging application really needs message to message forward secrecy in the first place. You really only need to do that expensive key agreement operation when you want to get rid of some old messages that someone has captured off the wire. That can be reasonably done at the end of a session or even weekly. Very few people need messages that have not even scrolled off the screen to be forward secret, assuming they need it at all.
- admax88q 5y ago
  I'm not sure you gain much by moving the forward secrecy to a weekly or session based level, and I think you lose a lot in terms of simplicity. It is simpler to design and analyze if it applies at every message. It's a design for the best case. No longer need to make judgement calls on if 1 week is enough, or maybe 2, or maybe some middle ground.
- tptacek 5y ago
  You really only need to do that expensive key agreement operation when you want to get rid of some old messages that someone has captured off the wire. Could you perhaps share more of your analysis here? I'd like to be able to better follow what you are trying to say.
  - upofadown 5y ago
    If you are using a temporary shared secret then after you forget that shared secret you will need a new secret which you will have to generate. I mean nothing more than that.
    - tptacek 5y ago
      Right, why would anyone ever be better off holding that temporary secret over many messages and many days?
      - upofadown 5y ago
        My entire point is that it is not really necessary to do shared secret generation at any but a very slow rate. Even if you don't so it the Signal protocol way it is still perfectly reasonable to only do it once in a while. That might be a short while but it could reasonably be quite long.
        tptacek 5y ago
        Why is it reasonable to only do shared secret generation once in awhile? What's the win to doing that? The win to not doing it is that it narrows the blast radius of a single key compromise to a small number of messages (or, in full ratchets, to a single message). Why would I ever, ever want to increase the blast radius of a key?
OJFord 5y ago
> It’s a weird thing about academics — they like to write papers and “share ideas”, but it’s very hard to get source code from them. I suppose at least part of the reason, especially for things like crypto and statistics, is that they don't want to get bogged down in plausibly-correct claims of fatal flaws, and be perhaps repeatedly (over years hence) put in a defensive position of having to prove the criticism incorrect or have everyone assume the work was wrong? I can sort of understand that. The same's true for the papers themselves of course, but I can see it being more annoying for code. ('But it's never going to actually be in that state', etc.)
- gww 5y ago
  In the biological sciences there is a huge push for the code to be released alongside the paper. Many publications (but not enough yet) include a complete pipeline in a workflow language that downloads, processes the data and generates the figures used in the paper.
  - toomuchtodo 5y ago
    What’s the language de jour typically leveraged to declare these workflows?
    - semi-extrinsic 5y ago
      Since GP mentions biology, I would guess R is the first choice.
    - gww 5y ago
      Nextflow and Snakemake are quite common. I prefer the later as I have a lot of Python experience.
- staticassertion 5y ago
  Are you saying this based on experience? My assumption was that it was a number of factors. 1. Researchers are often weak coders, and they may be self conscious about their code. 2. My own experience is that researcher code is totally undocument, or broken. I've repeatedly found that the code linked to from a paper has no straightforward way to be built, or appears to have compiler errors etc. 3. It's more work, and researchers have the incentive to put out a compelling paper, not to put out code (because we don't hold them to that standard). My own experiences have led to me to mostly dismiss papers where I can't find the code or can't get it to build.
IfOnlyYouKnew 5y ago
Excellent deep dive on this beast that had me similarly question my intelligence in the past. As a former academic: the reason sharing source code is/was rare is that it tends to be extremely ugly, and that you don’t get any credit for publishing it where it matters (I. e. tenure committees). To go from something that works to something that you would allow people to see takes about as much time as the original work. (As a side note: I feared for the worst when I saw, among tags like “hacking” and “open source”, the tag “feminism” in the side bar. I enjoyed being wrong.)
- vlovich123 5y ago
  I don’t think that’s a good reason. Production code is also ugly.
staticassertion 5y ago
> Wait, what? So many articles and journals I read on the topic just talk about prime fields, modular reduction and blah blah blah like it’s asking someone to buy milk and eggs at the grocery store. No kidding, it's so frustrating! I have to read some articles/ papers like 20x and open a bunch of wikipedia tabs to understand wtf they're talking about. If they gave a simple, high level explanation it would save tons of time - while a wikipedia article is going to be very in depth, it's not tailored to the context of what I'm reading, so I often have to look at a whole bunch of things to start to build a good model in my head for wtf they're trying to convey. This post, on the other hand, is perfect for me. Thank you so much for writing it I'm learning a ton.
- bunnie 5y ago
  Thanks! It's good to know I'm not alone in feeling this way. This is actually an abridged version, if you click into the link for the "datasheet" (https://ci.betrusted.io/betrusted-soc/doc/engine.html https://ci.betrusted.io/betrusted-soc/doc/engine.html) you can find all the gory details down to the register level...
  - amirhirsch 5y ago
    I liked your struggle with the corner-case :)
  - staticassertion 5y ago
    Awesome, much appreciated, I'll dig into it. I was actually just using the dalek crate myself quite heavily this week, so this is great timing.
- dragontamer 5y ago
  https://www.youtube.com/watch?v=xE4jEKx9fTM https://www.youtube.com/watch?v=xE4jEKx9fTM GF5 is the 3rd smallest finite field (GF2 and GF3 are smaller), but GF2 and GF3 are too small to really see where the beauty of all this math lies. ------ GF5 (which is simply "arithmetic modulo 5") has all the properties of Real-numbers "we care about", and none of the hassles of decimals or partial numbers. GF5 is simply arithmetic modulo 5. Its really easy to do. 4 + 2 == 1. (Aka: 4 + 2 mod 5 == 6 mod 5 == 1). Addition and multiplication are easily proven to be the same. The fun starts when you start doing roots, exponents and logarithms (!!!). Take the definition of addition / multiplication above (aka: addition / multiplication modulo 5) and redefine square-root, exponents, and logarithms to be consistent with it. That is to say: 2 * 3 == 1. Which means that 3 == (1/2) (yes, "one half" is now 3 in GF5). Which means 3 is 2^(-1). * 2^2 == 4. * 2^2 * (2^-1) == 4 * 3 == 12 mod 5 == 2. Which means 2^2 * 2^-1 == 2^(2-1) and look, exponents work as expected. Feel free to play around with all the numbers: you'll find that exponents work once you match this new "definition" of exponents. --------- Because exponents work, logarithms work. Because everything works, we can have complicated ellipical curves defined over the numbers {0, 1, 2, 3, 4} (aka: the numbers mod 5) and have everything work out mathematically. -------- The hard part is proving that all of this works in GF(5^2) aka GF25. It turns out that you can't just "mod 25" the stuff, you need to do an extension field (and basically make a complex number out of things). Once you understand GF25 extension fields and its relationship with GF5, then it becomes easy to generalize that to GF2 and its extension fields GF(2^8) (aka: binary numbers of 8 bits) or GF(2^32) (aka: 32-bit numbers). Turns out for extension fields (like GF(5^2) aka GF25) you need to redefine multiplication and addition as well and then rebuild all the math from the ground up off of this new definition of addition and new definition of multiplication. And again, this is most important for GF(2^32), aka the 32-bit number field that's common on today's computers. Bonus points: GF(2^32)'s new addition operator is just an xor. Only multiplication is difficult. But once you do that, it all __JUST WORKS__ and is amazing. ---------- Galois Fields are a way to "cheat" a definition of logarithm, exponents, square roots, multiplication, division, and addition (by redefining these operations). It turns out that these operations continue to work "as expected" in the Galois Field... as long as you're cool with the new definitions of them. ------ EDIT: I'm slightly wrong. Seems like Curve25519 is a prime field and not an extension field. So this is more similar to GF5 than it is to GF(2^32). Still, other elliptical curves are in GF(2^32) or other extension fields, so the study of extension fields is useful for other curves. Curve25519 can be understood with just the GF(5) description I gave earlier in this post. Prime fields are really simple: just mod(the prime number) and you're set. There's some weird properties that can accelerate speed (Any division by Foo is equivalent to multiplying by (1/Foo), which might be faster).
ChuckMcM 5y ago
This is an excellent read[1]. It reminded me of the process I went through putting together an FFT engine in an FPGA although I think the small execution engine is just stellar, and not something I had considered. [1] To be fair I find most of the stuff Bunnie writes about to be worth reading! :-)
jlrubin 5y ago
Hi Bunnie! Curious if you also have a power usage comparison, which I'm guessing is also relevant in the mobile context.
- bunnie 5y ago
  Hi Jeremy! So far only some anecdotal characterizations. Running the crypto core full-out on our wiggle-everything-to-see-that-it-works test vector suite adds 247mW +/- 5mW of power over the baseline idle condition. This is fairly comparable to the power delta of loading our RISC-V core fully with a software task versus idling it (around 200mW). So compared to the alternative of running the math on a RISC-V CPU core, we consume about 20% more power, but we complete the operation in 1/15th the time -- overall, it's a significant net savings of energy out of the battery pack. Also, we do have the ability to completely gate the clock to the crypto blocks when they are not in use, so they don't contribute to any dynamic power during normal run time. Static leakage then becomes the main concern. In the case of an FPGA, I suspect we're paying the static leakage penalty whether we use the logic or not, as they don't do VDD switching of configured domains on this chip. If this were to go to silicon, you'd either have to include circuitry to power off the block, bias the back side to reduce leakage, or just be willing to pay the static leakage penalty for the extra logic.
korethr 5y ago
This is neat. The ever-present admonition against rolling one's own crypto lurks in the back of my mind, though. It is not my intent here to impugn Bunnie's competence, though I do wonder if he's run the design or implementation past any cryptographers to try to verify that the design or implementation are sound, and don't subtly break critical assumptions vital to the security of the algorithm.
- pinewurst 5y ago
  But he’s not rolling his own crypto - in an algorithm sense - purely trying to speed the execution of an existing algorithm which can be easily validated against other existing implementations
  - korethr 5y ago
    Sure, but is it not possible that a hardware acceleration, if not also proven correct, could subtly undermine an otherwise valid software implementation? I do not assert that this is the case generally, nor particularly here -- I would be quite happy to be wrong about this. But if there's one thing I've taken from my admittedly minor study of crypto is that the most trivial of details can be critically important, and failure to get a detail exactly correct can compromise an entire algorithm and anything built thereupon. I would love to see hardware acceleration for ed25519, just like there's been hardware acceleration for AES. It could help drive adoption of an algorithm that is less fiddly and easy to get wrong than RSA, and maybe in another 15 years, I'd be able to purchase IT equipment that supports ed25519 and not just hardware accelerated RSA and AES.
    - not2b 5y ago
      Correctness alone is not sufficient. A crypto implementation also has to avoid introducing side channels. He describes how he avoids introducing a timing side channel (can't have any conditional branches that depend on the data) so it seems he took care to get that part right.
- bunnie 5y ago
dreamcompiler 5y ago
I learned Montgomery multiplication from the Handbook of Applied Cryptography (Menezes, Oorschot and Vanstone), and coded it directly from the pseudocode therein. Not to mention lots of other crypto algorithms. This book is a gold mine.

223 points by picture 5y ago

This work is associated with Precursor (https://www.bunniestudios.com/blog/?p=5921 https://www.bunniestudios.com/blog/?p=5921), which is Bunnie's project to build a mobile hardware platform from the ground up.

jazzyjackson 5y ago

TIL 255 is divisible by 17 Edit: thanks to my replies I know several more things now lol big day for me

pavpanchekha 5y ago
256 = 16 * 16 255 = 256 - 1 = 16 * 16 - 1 = 15 * 17
pfortuny 5y ago
(a^2-1)=(a+1)(a-1).
jandrese 5y ago
It is also divisible by 5.
Sesse__ 5y ago
2^p - 1 can only be prime (a so-called Mersenne prime) if p is prime. 2^8 - 1 thus cannot be a prime, since 8 is composite. (Note that is it not _sufficient_ that p is prime, but it is necessary.)

upofadown 5y ago

>The “double ratchet” algorithm is integral to modern end-to-end-encrypted chat apps, such as Signal, WhatsApp, and Matrix. Signal protocol uses a hash ratchet for the message to message forward secrecy. So you don't need to do the expensive key agreement stuff unless that hash ratchet falls out of synchronization. It isn't really clear if any messaging application really needs message to message forward secrecy in the first place. You really only need to do that expensive key agreement operation when you want to get rid of some old messages that someone has captured off the wire. That can be reasonably done at the end of a session or even weekly. Very few people need messages that have not even scrolled off the screen to be forward secret, assuming they need it at all.

admax88q 5y ago
I'm not sure you gain much by moving the forward secrecy to a weekly or session based level, and I think you lose a lot in terms of simplicity. It is simpler to design and analyze if it applies at every message. It's a design for the best case. No longer need to make judgement calls on if 1 week is enough, or maybe 2, or maybe some middle ground.
tptacek 5y ago
You really only need to do that expensive key agreement operation when you want to get rid of some old messages that someone has captured off the wire. Could you perhaps share more of your analysis here? I'd like to be able to better follow what you are trying to say.
- upofadown 5y ago
  If you are using a temporary shared secret then after you forget that shared secret you will need a new secret which you will have to generate. I mean nothing more than that.
  - tptacek 5y ago
    Right, why would anyone ever be better off holding that temporary secret over many messages and many days?
    - upofadown 5y ago
      My entire point is that it is not really necessary to do shared secret generation at any but a very slow rate. Even if you don't so it the Signal protocol way it is still perfectly reasonable to only do it once in a while. That might be a short while but it could reasonably be quite long.
      - tptacek 5y ago
        Why is it reasonable to only do shared secret generation once in awhile? What's the win to doing that? The win to not doing it is that it narrows the blast radius of a single key compromise to a small number of messages (or, in full ratchets, to a single message). Why would I ever, ever want to increase the blast radius of a key?

OJFord 5y ago

> It’s a weird thing about academics — they like to write papers and “share ideas”, but it’s very hard to get source code from them. I suppose at least part of the reason, especially for things like crypto and statistics, is that they don't want to get bogged down in plausibly-correct claims of fatal flaws, and be perhaps repeatedly (over years hence) put in a defensive position of having to prove the criticism incorrect or have everyone assume the work was wrong? I can sort of understand that. The same's true for the papers themselves of course, but I can see it being more annoying for code. ('But it's never going to actually be in that state', etc.)

gww 5y ago
In the biological sciences there is a huge push for the code to be released alongside the paper. Many publications (but not enough yet) include a complete pipeline in a workflow language that downloads, processes the data and generates the figures used in the paper.
- toomuchtodo 5y ago
  What’s the language de jour typically leveraged to declare these workflows?
  - semi-extrinsic 5y ago
    Since GP mentions biology, I would guess R is the first choice.
  - gww 5y ago
    Nextflow and Snakemake are quite common. I prefer the later as I have a lot of Python experience.
staticassertion 5y ago
Are you saying this based on experience? My assumption was that it was a number of factors. 1. Researchers are often weak coders, and they may be self conscious about their code. 2. My own experience is that researcher code is totally undocument, or broken. I've repeatedly found that the code linked to from a paper has no straightforward way to be built, or appears to have compiler errors etc. 3. It's more work, and researchers have the incentive to put out a compelling paper, not to put out code (because we don't hold them to that standard). My own experiences have led to me to mostly dismiss papers where I can't find the code or can't get it to build.

IfOnlyYouKnew 5y ago

Excellent deep dive on this beast that had me similarly question my intelligence in the past. As a former academic: the reason sharing source code is/was rare is that it tends to be extremely ugly, and that you don’t get any credit for publishing it where it matters (I. e. tenure committees). To go from something that works to something that you would allow people to see takes about as much time as the original work. (As a side note: I feared for the worst when I saw, among tags like “hacking” and “open source”, the tag “feminism” in the side bar. I enjoyed being wrong.)

vlovich123 5y ago
I don’t think that’s a good reason. Production code is also ugly.

staticassertion 5y ago

> Wait, what? So many articles and journals I read on the topic just talk about prime fields, modular reduction and blah blah blah like it’s asking someone to buy milk and eggs at the grocery store. No kidding, it's so frustrating! I have to read some articles/ papers like 20x and open a bunch of wikipedia tabs to understand wtf they're talking about. If they gave a simple, high level explanation it would save tons of time - while a wikipedia article is going to be very in depth, it's not tailored to the context of what I'm reading, so I often have to look at a whole bunch of things to start to build a good model in my head for wtf they're trying to convey. This post, on the other hand, is perfect for me. Thank you so much for writing it I'm learning a ton.

bunnie 5y ago
Thanks! It's good to know I'm not alone in feeling this way. This is actually an abridged version, if you click into the link for the "datasheet" (https://ci.betrusted.io/betrusted-soc/doc/engine.html https://ci.betrusted.io/betrusted-soc/doc/engine.html) you can find all the gory details down to the register level...
- amirhirsch 5y ago
  I liked your struggle with the corner-case :)
- staticassertion 5y ago
  Awesome, much appreciated, I'll dig into it. I was actually just using the dalek crate myself quite heavily this week, so this is great timing.
dragontamer 5y ago
https://www.youtube.com/watch?v=xE4jEKx9fTM https://www.youtube.com/watch?v=xE4jEKx9fTM GF5 is the 3rd smallest finite field (GF2 and GF3 are smaller), but GF2 and GF3 are too small to really see where the beauty of all this math lies. ------ GF5 (which is simply "arithmetic modulo 5") has all the properties of Real-numbers "we care about", and none of the hassles of decimals or partial numbers. GF5 is simply arithmetic modulo 5. Its really easy to do. 4 + 2 == 1. (Aka: 4 + 2 mod 5 == 6 mod 5 == 1). Addition and multiplication are easily proven to be the same. The fun starts when you start doing roots, exponents and logarithms (!!!). Take the definition of addition / multiplication above (aka: addition / multiplication modulo 5) and redefine square-root, exponents, and logarithms to be consistent with it. That is to say: 2 * 3 == 1. Which means that 3 == (1/2) (yes, "one half" is now 3 in GF5). Which means 3 is 2^(-1). * 2^2 == 4. * 2^2 * (2^-1) == 4 * 3 == 12 mod 5 == 2. Which means 2^2 * 2^-1 == 2^(2-1) and look, exponents work as expected. Feel free to play around with all the numbers: you'll find that exponents work once you match this new "definition" of exponents. --------- Because exponents work, logarithms work. Because everything works, we can have complicated ellipical curves defined over the numbers {0, 1, 2, 3, 4} (aka: the numbers mod 5) and have everything work out mathematically. -------- The hard part is proving that all of this works in GF(5^2) aka GF25. It turns out that you can't just "mod 25" the stuff, you need to do an extension field (and basically make a complex number out of things). Once you understand GF25 extension fields and its relationship with GF5, then it becomes easy to generalize that to GF2 and its extension fields GF(2^8) (aka: binary numbers of 8 bits) or GF(2^32) (aka: 32-bit numbers). Turns out for extension fields (like GF(5^2) aka GF25) you need to redefine multiplication and addition as well and then rebuild all the math from the ground up off of this new definition of addition and new definition of multiplication. And again, this is most important for GF(2^32), aka the 32-bit number field that's common on today's computers. Bonus points: GF(2^32)'s new addition operator is just an xor. Only multiplication is difficult. But once you do that, it all __JUST WORKS__ and is amazing. ---------- Galois Fields are a way to "cheat" a definition of logarithm, exponents, square roots, multiplication, division, and addition (by redefining these operations). It turns out that these operations continue to work "as expected" in the Galois Field... as long as you're cool with the new definitions of them. ------ EDIT: I'm slightly wrong. Seems like Curve25519 is a prime field and not an extension field. So this is more similar to GF5 than it is to GF(2^32). Still, other elliptical curves are in GF(2^32) or other extension fields, so the study of extension fields is useful for other curves. Curve25519 can be understood with just the GF(5) description I gave earlier in this post. Prime fields are really simple: just mod(the prime number) and you're set. There's some weird properties that can accelerate speed (Any division by Foo is equivalent to multiplying by (1/Foo), which might be faster).

ChuckMcM 5y ago

This is an excellent read[1]. It reminded me of the process I went through putting together an FFT engine in an FPGA although I think the small execution engine is just stellar, and not something I had considered. [1] To be fair I find most of the stuff Bunnie writes about to be worth reading! :-)

jlrubin 5y ago

Hi Bunnie! Curious if you also have a power usage comparison, which I'm guessing is also relevant in the mobile context.

bunnie 5y ago
Hi Jeremy! So far only some anecdotal characterizations. Running the crypto core full-out on our wiggle-everything-to-see-that-it-works test vector suite adds 247mW +/- 5mW of power over the baseline idle condition. This is fairly comparable to the power delta of loading our RISC-V core fully with a software task versus idling it (around 200mW). So compared to the alternative of running the math on a RISC-V CPU core, we consume about 20% more power, but we complete the operation in 1/15th the time -- overall, it's a significant net savings of energy out of the battery pack. Also, we do have the ability to completely gate the clock to the crypto blocks when they are not in use, so they don't contribute to any dynamic power during normal run time. Static leakage then becomes the main concern. In the case of an FPGA, I suspect we're paying the static leakage penalty whether we use the logic or not, as they don't do VDD switching of configured domains on this chip. If this were to go to silicon, you'd either have to include circuitry to power off the block, bias the back side to reduce leakage, or just be willing to pay the static leakage penalty for the extra logic.

korethr 5y ago

This is neat. The ever-present admonition against rolling one's own crypto lurks in the back of my mind, though. It is not my intent here to impugn Bunnie's competence, though I do wonder if he's run the design or implementation past any cryptographers to try to verify that the design or implementation are sound, and don't subtly break critical assumptions vital to the security of the algorithm.

pinewurst 5y ago
But he’s not rolling his own crypto - in an algorithm sense - purely trying to speed the execution of an existing algorithm which can be easily validated against other existing implementations
- korethr 5y ago
  Sure, but is it not possible that a hardware acceleration, if not also proven correct, could subtly undermine an otherwise valid software implementation? I do not assert that this is the case generally, nor particularly here -- I would be quite happy to be wrong about this. But if there's one thing I've taken from my admittedly minor study of crypto is that the most trivial of details can be critically important, and failure to get a detail exactly correct can compromise an entire algorithm and anything built thereupon. I would love to see hardware acceleration for ed25519, just like there's been hardware acceleration for AES. It could help drive adoption of an algorithm that is less fiddly and easy to get wrong than RSA, and maybe in another 15 years, I'd be able to purchase IT equipment that supports ed25519 and not just hardware accelerated RSA and AES.
  - not2b 5y ago
    Correctness alone is not sufficient. A crypto implementation also has to avoid introducing side channels. He describes how he avoids introducing a timing side channel (can't have any conditional branches that depend on the data) so it seems he took care to get that part right.
bunnie 5y ago

dreamcompiler 5y ago

I learned Montgomery multiplication from the Handbook of Applied Cryptography (Menezes, Oorschot and Vanstone), and coded it directly from the pseudocode therein. Not to mention lots of other crypto algorithms. This book is a gold mine.