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

https://github.com/francisrstokes/githublog/blob/main/2022/6/15/rolling-your-own-crypto-aes.md

by prostoalex • 4 years ago

231 89 4 years ago

nullc2• 4 years 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.

charlieyu12• 4 years ago

Isn't table lookup constant time?

dchest2• 4 years 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

Here's an implementation that doesn't use tables: https://github.com/openbsd/src/blob/master/sys/crypto/aes.c

zgs2• 4 years 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.

fstokesman4• 4 years 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.

Retr0id2• 4 years 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 )

henearkr• 4 years 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• 4 years 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• 4 years 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).

bowsamic2• 4 years 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

heleninboodler• 4 years ago

I think the title was a nod to the fact that this is something everyone's been taught not to do. It metaphorically could have been titled "Running With Scissors."

stingraycharles4• 4 years ago

It’s absolutely worth it to roll your own crypto if you want to learn from it. I feel like there is almost a stigma against articles like these because we’ve all been conditioned so much to avoid even thinking about it lol.

I did some deep dive into AES and RSA at some point in a distant past, it was a learning experience that to this day allows me to make much better decisions when choosing algorithms.

badsectoracula2• 4 years ago

I always found this "mantra" shortsighted and damaging on the long run - if nobody does their own crypto then who does their crypto? You are incentivizing people against learning this by that and a very significant part of learning something is actually using it in practice.

chmod6002• 4 years ago

"don't roll your own crypto" is good advice, but it's also against the hacker ethos. It's another way of saying "you'll never really understand this so don't try, just rely on a mysterious cabal of experts".

May be true, but not exactly a great message.

Joker_vD• 4 years ago

How does crypto even get created, then? Like, those cryptography experts — they do roll their own crypto, and then it gets standardized as Blowfish/AES/Salsa20/etc. How did they learn to make ciphers that are "good enough" to use in production? Are those people special somehow, and it's not possible to become one of them?

timcavel• 4 years ago

Fun fact, crypto in cryptocurrency is cryptography.

qikInNdOutReply2• 4 years ago

I guess the advice to "not roll your own crypto" can be safely considered compromised and hostile, especially after it came out that the winning curves in some competitions were selected by the NSA.

Do roll your own crypto if you have nation state actors as potential attackers. Make life hard for them.

kickling• 4 years ago

The point is that you probably make their life easier by rolling your own crypto.

fstokesman4• 4 years ago

I put the warnings in the title and the first few paragraphs, but also implicitly at the end, where the reader checks the comments to see a great deal of reiterations of the message

laszlojamf• 4 years ago

"I know just enough to be dangerous"

I'm stealing that!

defrost• 4 years 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...

[pi] insert picture of padlocked gate with no fence in otherwise open field.

Beldin2• 4 years 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• 4 years ago

Just know that GitHub now supports mathjax in markdown.

baby• 4 years ago

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

emacs28• 4 years 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

MarekKnapek• 4 years 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.

dchest2• 4 years 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...

zgs2• 4 years 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...

fstokesman4• 4 years 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.

grishka• 4 years ago

The even better part is that you can generate or find test vectors to test your implementation against a known-correct one.

Retr0id2• 4 years ago

I also made a 1:1 implementation of the spec. The finite field math did cause a bit of head-scratching, but in the end I mostly made sense of things:

https://github.com/DavidBuchanan314/aes-playground/blob/mast...

(I left comments quoting the spec as much as possible, so it should be possible to map it back onto the spec, for anyone interested)

jedisct1• 4 years ago

AES is useful beyond AES-GCM.

Constructions such as AES-CMAC, but also recent ones such as AEGIS only require the AES round function.

Grimburger• 4 years 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-guid...

https://developer.arm.com/documentation/ddi0596/2020-12/SIMD...

https://en.wikipedia.org/wiki/AES_instruction_set

bjornsing• 4 years ago

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

implements• 4 years 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?

fstokesman4• 4 years 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) 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.

badrabbit• 4 years ago

I would be interested in alternative s-box implementations for Rijndael.

Also, "Software AES bad"

nayuki2• 4 years ago

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

bjoli• 4 years 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.

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

Related Stories