8 ms·

Rolling your own crypto: Everything you need to build AES from scratch

231 points by lxm 4y ago

nullc 4y ago
It's much more interesting to implement AES without the table lookups-- as doing so requires constructing a boolean circuit that computes the same result as the tables, more useful too since the table lookups result in security killing side channels. :) The author might be surprised at how often someone's random "learn 2 crypto" ends up in use in production. Kudos for the warnings, though I doubt that actually accomplish much: People copying and pasting code usually have tremendous tunnel vision.
- charlieyu1 4y ago
  Isn't table lookup constant time?
  - deleted 4y ago
    [deleted]
  - dchest 4y ago
    These are called "cache-timing attacks". In presence of caches, no memory lookup can be guaranteed to be constant time. Any memory lookups that use secret indices are thus not timing-safe, however non-secret indices are OK. See https://cr.yp.to/antiforgery/cachetiming-20050414.pdf https://cr.yp.to/antiforgery/cachetiming-20050414.pdf Here's an implementation that doesn't use tables: https://github.com/openbsd/src/blob/master/sys/crypto/aes.c https://github.com/openbsd/src/blob/master/sys/crypto/aes.c
    - mananaysiempre 4y ago
      (That implementation comes from BearSSL, whose website also has a discussion of the issue and a performance comparison[1].) [1] https://www.bearssl.org/constanttime.html https://www.bearssl.org/constanttime.html
  - zgs 4y ago
    No. At least not with modern caching (or very old page boundary crossings). A constant time implementation has to avoid tables & compute the values directly (and slowly) or take special care to ensure that all of the table is hit/cached on each access.
    - nullc 4y ago
      > or take special care to ensure that all of the table is hit/cached on each access. For example, by using an oblivious read: Access each row, AND it with a mask that is either all 1s or all 0s depending on if its the row you want (which you must set without branching) and OR all the results together. Very slow.
- fstokesman 4y ago
  If someone copy-pastes this code in spite of the warnings, I consider them to be very much in own-risk territory. Sucks if they end up getting burned, but I don't consider myself responsible.
- Retr0id 4y ago
  Further, you can compute the whole block transform as a giant boolean circuit (aka bitslicing). This has various advantages, sidechannel resistence being one, but surprisingly it outperforms a more traditional implementation in many circumstances (e.g. in pure-python implementations: https://github.com/DavidBuchanan314/python-bitsliced-aes https://github.com/DavidBuchanan314/python-bitsliced-aes )
henearkr 4y ago
Very interesting! Thanks. I'd be interested in doing the same with some post-quantum ciphers, especially since two of them have been officially adopted by the NIST.
rob74 4y ago
Refreshing to see "crypto" meaning cryptography, not cryptocurrencies... And also good that they mention right from the start that you shouldn't use your (or their) self-made cryptography in production (although they could have emphasized it a bit more).
- Mordisquitos 4y ago
  > you shouldn't use your (or their) self-made cryptography in production Absolutely, and that was the very first thing I thought when I saw the title. For some reason I've got the "don't roll your own crypto" commandment heavily ingrained into my brain (even though I've never been in any context where I might have tried), together with "don't let the frying pan handle stick out over the edge of the cooker in case a kid grabs it" (even though I have no kids, nor nephews etc), as well as trigger discipline and "every gun is loaded" (even though I've never touched a gun in my life and have never lived in the USA).
  - bowsamic 4y ago
    Those other mantras work but the crypto one is dangerous because it actually implicitly discourages people from playing with it and learning about it
    - bramblerose 4y ago
      The fundamental problem with cryptography (that doesn't apply as much to other areas) is that it's not a subject you can learn by playing with it. That's a result of the complexity of building a correct solution, the ease of building a solution that _looks_ correct at first glance but isn't, and the extreme adversarial nature of the problem. In most of software a "looks correct at first glance" solution is fine -- the 1% that is broken will not have significant consequences. In cryptography, your adversary will find that 1% and abuse it.
      - jonathanstrange 4y ago
        You mostly learn cryptography by doing cryptanalysis, and that certainly is a form of playing with ciphers. To be fair, modern cryptanalysis also involves a bit of math and reading some papers. None of this is something that hobby cryptographers can't do. In fact, there is no real difference between "professional" and hobby cryptographers. Many of the professional ones started as hobby cryptographers, and there are plenty of allegedly professional "cryptographers" who do not have sufficient experience in cryptanalysis. Moreover, anybody can make a fairly secure Feistel cipher, for example, it's just hard to create an efficient one. Note that proofs of security either don't exist or are based on unreasonable assumptions. Cryptography is still mostly a black art, not a science. In a nutshell, you really shouldn't reinforce the "don't roll your own crypto" mantra. It just means you'll get less skilled cryptographers in the end. Bear in mind that nearly all debacles in cryptography were caused by professional cryptographers.
laszlojamf 4y ago
"I know just enough to be dangerous" I'm stealing that!
defrost 4y ago
My own introduction to AES and developing further variations was via the print version of the algorithm in 1981 edition of Computer Networks by Andrew S. Tanenbaum & David J. Wetherall, talking about combinatorics and groups at length with people good in that field, and then tinkering with extending early versions of Cayley [-1] If you are going to dabble in cryptography it might be wise to approach it via the theory, work in the domain symbolically, and generate code that provably "works as designed" so that you can focus on attacks on the design in a symbolic domain. You then have a secure element in a security eco-system ... which leaves the issue of wether the end-points of that element are insecure or indeed whether the entire security locale can be avoided [pi] [-1] https://en.wikipedia.org/wiki/Magma_(computer_algebra_system) https://en.wikipedia.org/wiki/Magma_(computer_algebra_system... [pi] insert picture of padlocked gate with no fence in otherwise open field.
- Beldin 4y ago
  You probably meant DES instead of AES. AES is from 2001, DES from mid-70s. (First published in '75, official standard in '77, according to Wikipedia).
pca006132 4y ago
Just know that GitHub now supports mathjax in markdown.
baby 4y ago
Oh this is pretty! I built my own cute course on how to implement AES as well: https://davidwong.fr/blockbreakers/ https://davidwong.fr/blockbreakers/
emacs28 4y ago
One interesting thing is that modern processors have an AES instruction set [1] integrated into them so that primitive AES operations can be individually called and accelerated in hardware. You can run these instructions from C and it significantly speeds up the AES algorithm compared to writing out the algorithm explicitly in C. [1] https://en.m.wikipedia.org/wiki/AES_instruction_set https://en.m.wikipedia.org/wiki/AES_instruction_set
MarekKnapek 4y ago
Implementing AES from scratch is easy and fun, just read the spec and implement it 1:1, until ... you encounter GCM mode and its Galois Field "weird" math. Very. Not. Fun.
- dchest 4y ago
  Here's a (not so fast) implementation of multiplication in GF(2^128) in 32 lines of code! :) http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/sys/crypto/gmac.c?rev=1.10&content-type=text/x-cvsweb-markup http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/sys/crypto/gmac...
- zgs 4y ago
  Most cryptographic operations are easy to implement. The best part is when you make a mistake, you'll most likely get random nonsense out the end. Floating point code is much more difficult, often you'll get an answer that's almost correct or worse one that's correct most places...
  - fstokesman 4y ago
    Heard about a great floating point implementation bug just today. When nintendo released Super Mario 64 for the Wii virtual console, they essentially just made their own emulator that plays a single ROM. The emulator is pretty accurate, though they made a mistake when implementing floating point operation rounding: All operations end up rounding upwards to the next floating point number (as opposed to alternating, depending on the result). A consequence of this was that some of the moving platforms in the game that had a periodic up/down pattern would slowly (over the course of literal days) creep upwards. Ended up being exploited in a speedrun category where the player attempts to press the A button as little as possible.
    - sireat 4y ago
      Shades of the floating point truncation bug in Vancouver Stock Exchange Index in the early 1980s: https://en.wikipedia.org/wiki/Vancouver_Stock_Exchange#Rounding_errors_on_its_Index_price https://en.wikipedia.org/wiki/Vancouver_Stock_Exchange#Round... The bug caused the index to creep up to twice the real index.
Grimburger 4y ago
If you want to roll your own you should be using AES intrinsics (accessible in most [all?] languages) to replicate how the actual crypto code you use every day works. The article and code is more about understanding the math, which is great and fundamental, but it is not really about the implementation side of things. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#othertechs=AES https://www.intel.com/content/www/us/en/docs/intrinsics-guid... https://developer.arm.com/documentation/ddi0596/2020-12/SIMD-FP-Instructions/AESD--AES-single-round-decryption- https://developer.arm.com/documentation/ddi0596/2020-12/SIMD... https://en.wikipedia.org/wiki/AES_instruction_set https://en.wikipedia.org/wiki/AES_instruction_set
bjornsing 4y ago
And now for the countdown: 3, 2, 1, "You should never roll your own crypto!"
implements 4y ago
Can other people’s crypto binaries ever be fully trusted? - and there’s the other issue of ‘software rot’ making those binaries and associated data potentially unusable in the future. Home risk is mainly theft of hardware by burglars looking for cash resale rather than cryptanalyst hackers - so for purely personal use, and to guarantee future readability, perhaps rolling your own AES from source isn’t so misguided if it’s just to protect the odd spreadsheet or personal letter from prying eyes?
- fstokesman 4y ago
  If you code to a standard, this is less of a problem. If you implement AES in a way that produces a different output to someone elses implementation, then you by definition haven't implemented AES. From a binary trust perspective, this is maybe a good way of ensuring that you're running the code you really think you are - but really you just kick the can down the road. You didn't build the hardware, and thus you don't know it's doing with your data once the instructions start executing. Is it storing them off to a side-buffer? Is the CPU detecting AES-like behaviour and triggering some surreptitious path? Who knows. This is where projects like precursor (https://player.vimeo.com/video/677854277?h=8ad58eece9 https://player.vimeo.com/video/677854277?h=8ad58eece9) are really interesting. To be really, super sure that your code is running as expected, you have to build the world from the ground up.
_8j50 4y ago
I would be interested in alternative s-box implementations for Rijndael. Also, "Software AES bad"
nayuki 4y ago
Other AES learning resources: https://www.nayuki.io/page/aes-cipher-internals-in-excel https://www.nayuki.io/page/aes-cipher-internals-in-excel , https://www.nayuki.io/res/cryptographic-primitives-in-plain-python/aescipher.py https://www.nayuki.io/res/cryptographic-primitives-in-plain-... , https://en.wikipedia.org/wiki/Advanced_Encryption_Standard https://en.wikipedia.org/wiki/Advanced_Encryption_Standard , https://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html https://www.moserware.com/2009/09/stick-figure-guide-to-adva... , https://www.youtube.com/watch?v=mlzxpkdXP58 https://www.youtube.com/watch?v=mlzxpkdXP58
bjoli 4y ago
After having implemented AES I tried to implement GCM, but failed at doing it from some papers. Then I failed translating it from a reference C implementation to scheme. Then I gave up and implemented OCB(3) mode. And I was happy to see that it is now free for all. The parents are lapsed.

231 points by lxm 4y ago

It's much more interesting to implement AES without the table lookups-- as doing so requires constructing a boolean circuit that computes the same result as the tables, more useful too since the table lookups result in security killing side channels. :) The author might be surprised at how often someone's random "learn 2 crypto" ends up in use in production. Kudos for the warnings, though I doubt that actually accomplish much: People copying and pasting code usually have tremendous tunnel vision.

charlieyu1 4y ago
Isn't table lookup constant time?
- deleted 4y ago
  [deleted]
- dchest 4y ago
  These are called "cache-timing attacks". In presence of caches, no memory lookup can be guaranteed to be constant time. Any memory lookups that use secret indices are thus not timing-safe, however non-secret indices are OK. See https://cr.yp.to/antiforgery/cachetiming-20050414.pdf https://cr.yp.to/antiforgery/cachetiming-20050414.pdf Here's an implementation that doesn't use tables: https://github.com/openbsd/src/blob/master/sys/crypto/aes.c https://github.com/openbsd/src/blob/master/sys/crypto/aes.c
  - mananaysiempre 4y ago
    (That implementation comes from BearSSL, whose website also has a discussion of the issue and a performance comparison[1].) [1] https://www.bearssl.org/constanttime.html https://www.bearssl.org/constanttime.html
- zgs 4y ago
  No. At least not with modern caching (or very old page boundary crossings). A constant time implementation has to avoid tables & compute the values directly (and slowly) or take special care to ensure that all of the table is hit/cached on each access.
  - nullc 4y ago
    > or take special care to ensure that all of the table is hit/cached on each access. For example, by using an oblivious read: Access each row, AND it with a mask that is either all 1s or all 0s depending on if its the row you want (which you must set without branching) and OR all the results together. Very slow.
fstokesman 4y ago
If someone copy-pastes this code in spite of the warnings, I consider them to be very much in own-risk territory. Sucks if they end up getting burned, but I don't consider myself responsible.
Retr0id 4y ago
Further, you can compute the whole block transform as a giant boolean circuit (aka bitslicing). This has various advantages, sidechannel resistence being one, but surprisingly it outperforms a more traditional implementation in many circumstances (e.g. in pure-python implementations: https://github.com/DavidBuchanan314/python-bitsliced-aes https://github.com/DavidBuchanan314/python-bitsliced-aes )

henearkr 4y ago

Very interesting! Thanks. I'd be interested in doing the same with some post-quantum ciphers, especially since two of them have been officially adopted by the NIST.

rob74 4y ago

Refreshing to see "crypto" meaning cryptography, not cryptocurrencies... And also good that they mention right from the start that you shouldn't use your (or their) self-made cryptography in production (although they could have emphasized it a bit more).

Mordisquitos 4y ago
> you shouldn't use your (or their) self-made cryptography in production Absolutely, and that was the very first thing I thought when I saw the title. For some reason I've got the "don't roll your own crypto" commandment heavily ingrained into my brain (even though I've never been in any context where I might have tried), together with "don't let the frying pan handle stick out over the edge of the cooker in case a kid grabs it" (even though I have no kids, nor nephews etc), as well as trigger discipline and "every gun is loaded" (even though I've never touched a gun in my life and have never lived in the USA).
- bowsamic 4y ago
  Those other mantras work but the crypto one is dangerous because it actually implicitly discourages people from playing with it and learning about it
  - bramblerose 4y ago
    The fundamental problem with cryptography (that doesn't apply as much to other areas) is that it's not a subject you can learn by playing with it. That's a result of the complexity of building a correct solution, the ease of building a solution that _looks_ correct at first glance but isn't, and the extreme adversarial nature of the problem. In most of software a "looks correct at first glance" solution is fine -- the 1% that is broken will not have significant consequences. In cryptography, your adversary will find that 1% and abuse it.
    - jonathanstrange 4y ago
      You mostly learn cryptography by doing cryptanalysis, and that certainly is a form of playing with ciphers. To be fair, modern cryptanalysis also involves a bit of math and reading some papers. None of this is something that hobby cryptographers can't do. In fact, there is no real difference between "professional" and hobby cryptographers. Many of the professional ones started as hobby cryptographers, and there are plenty of allegedly professional "cryptographers" who do not have sufficient experience in cryptanalysis. Moreover, anybody can make a fairly secure Feistel cipher, for example, it's just hard to create an efficient one. Note that proofs of security either don't exist or are based on unreasonable assumptions. Cryptography is still mostly a black art, not a science. In a nutshell, you really shouldn't reinforce the "don't roll your own crypto" mantra. It just means you'll get less skilled cryptographers in the end. Bear in mind that nearly all debacles in cryptography were caused by professional cryptographers.

laszlojamf 4y ago

"I know just enough to be dangerous" I'm stealing that!

defrost 4y ago

My own introduction to AES and developing further variations was via the print version of the algorithm in 1981 edition of Computer Networks by Andrew S. Tanenbaum & David J. Wetherall, talking about combinatorics and groups at length with people good in that field, and then tinkering with extending early versions of Cayley [-1] If you are going to dabble in cryptography it might be wise to approach it via the theory, work in the domain symbolically, and generate code that provably "works as designed" so that you can focus on attacks on the design in a symbolic domain. You then have a secure element in a security eco-system ... which leaves the issue of wether the end-points of that element are insecure or indeed whether the entire security locale can be avoided [pi] [-1] https://en.wikipedia.org/wiki/Magma_(computer_algebra_system) https://en.wikipedia.org/wiki/Magma_(computer_algebra_system... [pi] insert picture of padlocked gate with no fence in otherwise open field.

Beldin 4y ago
You probably meant DES instead of AES. AES is from 2001, DES from mid-70s. (First published in '75, official standard in '77, according to Wikipedia).

pca006132 4y ago

Just know that GitHub now supports mathjax in markdown.

baby 4y ago

Oh this is pretty! I built my own cute course on how to implement AES as well: https://davidwong.fr/blockbreakers/ https://davidwong.fr/blockbreakers/

emacs28 4y ago

One interesting thing is that modern processors have an AES instruction set [1] integrated into them so that primitive AES operations can be individually called and accelerated in hardware. You can run these instructions from C and it significantly speeds up the AES algorithm compared to writing out the algorithm explicitly in C. [1] https://en.m.wikipedia.org/wiki/AES_instruction_set https://en.m.wikipedia.org/wiki/AES_instruction_set

MarekKnapek 4y ago

Implementing AES from scratch is easy and fun, just read the spec and implement it 1:1, until ... you encounter GCM mode and its Galois Field "weird" math. Very. Not. Fun.

dchest 4y ago
Here's a (not so fast) implementation of multiplication in GF(2^128) in 32 lines of code! :) http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/sys/crypto/gmac.c?rev=1.10&content-type=text/x-cvsweb-markup http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/sys/crypto/gmac...
zgs 4y ago
Most cryptographic operations are easy to implement. The best part is when you make a mistake, you'll most likely get random nonsense out the end. Floating point code is much more difficult, often you'll get an answer that's almost correct or worse one that's correct most places...
- fstokesman 4y ago
  Heard about a great floating point implementation bug just today. When nintendo released Super Mario 64 for the Wii virtual console, they essentially just made their own emulator that plays a single ROM. The emulator is pretty accurate, though they made a mistake when implementing floating point operation rounding: All operations end up rounding upwards to the next floating point number (as opposed to alternating, depending on the result). A consequence of this was that some of the moving platforms in the game that had a periodic up/down pattern would slowly (over the course of literal days) creep upwards. Ended up being exploited in a speedrun category where the player attempts to press the A button as little as possible.
  - sireat 4y ago
    Shades of the floating point truncation bug in Vancouver Stock Exchange Index in the early 1980s: https://en.wikipedia.org/wiki/Vancouver_Stock_Exchange#Rounding_errors_on_its_Index_price https://en.wikipedia.org/wiki/Vancouver_Stock_Exchange#Round... The bug caused the index to creep up to twice the real index.

Grimburger 4y ago

If you want to roll your own you should be using AES intrinsics (accessible in most [all?] languages) to replicate how the actual crypto code you use every day works. The article and code is more about understanding the math, which is great and fundamental, but it is not really about the implementation side of things. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#othertechs=AES https://www.intel.com/content/www/us/en/docs/intrinsics-guid... https://developer.arm.com/documentation/ddi0596/2020-12/SIMD-FP-Instructions/AESD--AES-single-round-decryption- https://developer.arm.com/documentation/ddi0596/2020-12/SIMD... https://en.wikipedia.org/wiki/AES_instruction_set https://en.wikipedia.org/wiki/AES_instruction_set

bjornsing 4y ago

And now for the countdown: 3, 2, 1, "You should never roll your own crypto!"

implements 4y ago

Can other people’s crypto binaries ever be fully trusted? - and there’s the other issue of ‘software rot’ making those binaries and associated data potentially unusable in the future. Home risk is mainly theft of hardware by burglars looking for cash resale rather than cryptanalyst hackers - so for purely personal use, and to guarantee future readability, perhaps rolling your own AES from source isn’t so misguided if it’s just to protect the odd spreadsheet or personal letter from prying eyes?

fstokesman 4y ago
If you code to a standard, this is less of a problem. If you implement AES in a way that produces a different output to someone elses implementation, then you by definition haven't implemented AES. From a binary trust perspective, this is maybe a good way of ensuring that you're running the code you really think you are - but really you just kick the can down the road. You didn't build the hardware, and thus you don't know it's doing with your data once the instructions start executing. Is it storing them off to a side-buffer? Is the CPU detecting AES-like behaviour and triggering some surreptitious path? Who knows. This is where projects like precursor (https://player.vimeo.com/video/677854277?h=8ad58eece9 https://player.vimeo.com/video/677854277?h=8ad58eece9) are really interesting. To be really, super sure that your code is running as expected, you have to build the world from the ground up.

_8j50 4y ago

I would be interested in alternative s-box implementations for Rijndael. Also, "Software AES bad"

nayuki 4y ago

Other AES learning resources: https://www.nayuki.io/page/aes-cipher-internals-in-excel https://www.nayuki.io/page/aes-cipher-internals-in-excel , https://www.nayuki.io/res/cryptographic-primitives-in-plain-python/aescipher.py https://www.nayuki.io/res/cryptographic-primitives-in-plain-... , https://en.wikipedia.org/wiki/Advanced_Encryption_Standard https://en.wikipedia.org/wiki/Advanced_Encryption_Standard , https://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html https://www.moserware.com/2009/09/stick-figure-guide-to-adva... , https://www.youtube.com/watch?v=mlzxpkdXP58 https://www.youtube.com/watch?v=mlzxpkdXP58

bjoli 4y ago

After having implemented AES I tried to implement GCM, but failed at doing it from some papers. Then I failed translating it from a reference C implementation to scheme. Then I gave up and implemented OCB(3) mode. And I was happy to see that it is now free for all. The parents are lapsed.