Rolling your own crypto: Everything you need to build AES from scratch | Hacker News Reader

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

github.com

231 pointslxm89 comments

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).

> 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).

Those other mantras work but the crypto one is dangerous because it actually implicitly discourages people from playing with it and learning about it

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.

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.

The "don't roll your own crypto" is a mantra mostly useful for deciding what to put into production, not as a general ban on even touching the stuff before you become some kind of mythical, long-bearded, tome-possessing wizard.

I thought this was pretty obvious but I guess this important context was not sufficiently disseminated given the prevalence of the latter position.

Almost all mantras that are stated in absolutes will be accepted by the public in every single possible way. Unfortunately, and I know it sounds unbelievable, for a lot of people it really has become "don't even think of learning about crypto", not just "don't use your own crypto in prod"

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."

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.

> It’s absolutely worth it to roll your own crypto if you want to learn from it

No. If you want to "learn from it", the first thing you should do is buy a copy of Bruce Schneier's Applied Cryptography.

Just reading (and fully understanding !) that book will alone put you in a position where you already know more about cryptography than 90% of other people.

If after that you still want to play around with rolling your own crypto, then fine, go for it. But be aware you are very much making your own bed and should be prepared to lie in the inevitable mucky consequences.

For the rest of us, frankly, no matter what your choice of programming language is, there will be at least one if not many more well respected long-established crypto libraries. Most people should just do themselves a favour and just use those libraries.

As the saying goes ... crypto is hard. A tiny, easily overlooked, mistake in your crypto code can have major consequences.

That’s super personal. I am the type of person who learns by doing, much less reading, and I reject not being “allowed” to do it this way. I will of course study the reading material as I go, but “doing while learning” is an absolute necessity for me, as is studying existing codebases. You learn your way, I learn my way, but don’t tell me my way is wrong just because it’s crypto.

I honestly think, as a community, we’re being far too dogmatic about our advice here, and we should recognise that there is value in learning things by example, and that more people having a better understanding of crypto is generally a Good Thing.

Using it in production, of course, is an entirely different matter, but that’s not what I’m contesting.

> don’t tell me my way is wrong just because it’s crypto.

The way where people think they learn cryptography by making their own implementation is, indeed, wrong. Cryptography is about ensuring specific requirements in the face of active adversaries.

Self-implemented crypto misses many well-known caveats, causing them to be easily breakable. As such, it is not reasonable to consider them as something that aims learn about ensuring security properties in the face of active adversaries... but then that effort is not actually teaching about crypto, which is exactly that.

This is also the reason that the established wisdom for learning cryptography is to learn to break systems first. Almost everyone can make a cryptographic system they cannot break. For most folks, that means little. For those skilled at breaking crypto, that carries weight.

But you're approaching it from the wrong perspective: the idea isn't to use the crypto you implement yourself, the idea is to gain a better understanding of how the "magic" works. Of course my hand-rolled RSA/AES crypto is breakable, I know that because that's the default assumption.

It's akin to saying, "you're not allowed to build your own smoke detector because it will be unsafe!". Of course I know that, I want to understand the differences between a photoelectric and ionization smoke detector, how they work in practice, because reading some PDF schematics just doesn't cut it for me.

I honestly don't understand the line of reasoning of all this crypto gatekeeping.

Fun fact: while I was doing my crypto deep dive in 2015, my language of choice being Haskell, I found issues in several libraries, specifically around entropy, and even one library with modulo bias [1]. They were acknowledged and addressed. It was a super fun learning exercise, and seeing all these comments how it's supposedly almost illegal to do this misses the point of people exploring and learning in their own ways.

https://github.com/vincenthz/hs-crypto-numbers/commit/bceb54...

>I found issues in several libraries, specifically around entropy, and even one library with modulo bias

This is exactly what the other people in this thread mean when they say "learn by breaking other crypto", assuming you didn't write those libraries.

One of the reasons I want to learn how these things work in detail is that I want to understand the whole stack I’m working with, from top to bottom. As part of my quest to implement an asymmetrical encryption algo, I ended up wondering “how do I create truly random entropy?”, and went down that rabbit hole.

It’s all about intent: my intent is understanding “how does this work?”, “how do I do this the right way?”, not breaking, and that’s how I found these things.

I don’t care about breaking stuff, it’s just not appealing to me. My whole frustration with this discussion is that for some reason, my intentions are not the True Way of the Crypto Experts, and then I’m not allowed to proceed.

It’s such utter nonsense, and this whole discussion made me realise the situation is actually worse than I thought. If these commenters here are representative of the wider crypto community, they’re really a bunch of elitist gatekeepers that cannot understand the difference between being the NSA and a mere mortal trying to learn things in their own way.

Hear that? Learn from breaking crypto ... just not your own.

On a related note, Beldin here just contributed a new entry into cryptopals: the Gatekeeper hash, but only certain people can see the link.

Just no. This idea that people are not allowed to learn by doing things and must read huge books first is absurd. The guidelines for learning you gave here are impractical for majority of people who are interested. It is actually good when people are trying to learn about security.

Just about worst thing these absurd rules achieve is that effectively only rule breakers are allowed in.

> Just no. This idea that people are not allowed to learn by doing things and must read huge books first is absurd.

No, its not absurd.

Sure, I agree, for many things in life you can "learn by doing".

But this is cryptography.

There is no escaping that cryptography IS mathematics and an algorithm built on top of that mathematics.

Unfortunately the only way to learn the theory is by reading and understanding books or academic papers.

Otherwise you are just taking shortcuts based on a summary that someone else has written for you on a short blog or forum post. Which, aside from the fact that you are skipping the detail and hence not really learning, also brings us into the region of trust...

If you have no interest in learning the dry theory behind the cryptography, then you have no business rolling your own crypto. Because if you are not willing to understand the theory then you are going to make serious mistakes.

> If you have no interest in learning the dry theory behind the cryptography, then you have no business rolling your own crypto.

As someone who wholeheartedly buys into the “thou shalt not roll thine own crypto” mantra, this attitude is just sad. Everyone who wants to has all the business rolling their own crypto for learning purposes, and you have no business telling them they shouldn’t. Stifling this sort of exploration is fundamentally wrong.

This is kind of ridiculous. Everyone has to start somewhere whether it is by doing or by reading books. Even crypto experts started by doing at some point. It's not like the person is going to be using their own crypto in production.

... and people making serious mistakes in their toy experiments at home is a problem how?

First, majority of exploits are not even in math, they are in implementation. Second, as much as math is fun, the claim that you need to start with it is plain absurd.

First thing this mantra does is that we collectively know less a out crypto and security. Second thing it does is that it selects stick-in-ass rule followers away which is exactly contraproductive. And third, it makes us stuck with crappy convoluted code crypto libs had twenty years ago, cause supply of people capable to improve it is not build up.

I also disagree with the “read books instead” stuff. As long as you’re not using your homegrown crypto in production, and more generally as long as you’re not doing stupid things like reusing single-use tokens, why would I care how you choose to spend your learning time? Though if I’m catching these mistakes in pull requests, I might suggest a formal curriculum for the sake of actual software safety.

I see the same problems in internet debates about which programming language to learn first or how to learn programming in general, and a lot of it just doesn’t take into account that learning is a long journey and staying on the path is often more important than taking the fastest or cleanest path. If trying to roll your own stuff is more engaging, great!

Obligatory reply to an endorsement of Applied Cryptography: https://sockpuppet.org/blog/2013/07/22/applied-practical-cry...

No. If you want to "learn from it", you should do whatever you want that works for you. You're not our dad.

> If after that you still want to play around with rolling your own crypto, then fine, go for it. But be aware you are very much making your own bed and should be prepared to lie in the inevitable mucky consequences.

I'm very confused. OP was suggesting to roll your own crypto as a learning exercise. What possible consequences could there be? Let alone "murky" ones?

Will your RSA implementation summon an eldritch monster or something?

It is shocking to me how many people in the computer community explicitly tell curious minds not to even try building a crypto protocol.

It isn't enough to say "you'll never get it right for production, please use a framework or library for production". You simply don't want them to even experiment on their own.

I agree with saying "the most effective way to learn cryptography is through books and tools X, Y, Z". But one would imagine that writing a poor hashing algo would open up a door to alternate dimensions by how superstitious some are about it on this site.

It sounds like you didn't read the disclaimer. The first paragraph specifically tells you not to actually use the crypto you roll for anything important.

The purpose of this is to learn how AES works, not to write a library you would actually use.

> It’s absolutely worth it to roll your own crypto if you want to learn from it.

It's essentially a waste of your time. Because of Schneier's Law: "Any person can invent a security system so clever that she or he can't think of how to break it".

The thing that you might learn from, if you put the work in, would be breaking other people's stuff. Ideally you would find something that's actually in use and vulnerable enough that with some time you'll be able to break it, but that's tricky.

So, if you're a programmer try something like "Cryptopals": https://cryptopals.com/

I think Thomas Ptacek is wrong about a bunch of stuff when it comes to security (there's presumably some way to find HN back-and-forth between us if you decide you care about that), but he wasn't wrong about the Cryptopals exercises. By the time you're doing Set 2 exercises this is stuff real people, who were getting paid and thought they knew what they were doing, got wrong.

When cryptopals is mentioned, i've also gotta mention "Cryptohack": https://cryptohack.org/

That's where i've learnt most of my crypto, although it might be more focussed on the breaking than the making part.

"""It's essentially a waste of your time."""

Strongly disagree. I'm pretty sure rolling your own crypto will strengthen your understanding of crypto (and potential flaws) a lot. Obviously don't use it in production but by all means, do it for the sake of learning. How can this be a waste of time? That's like saying "never implement a search/sort algorithm, just use libraries"...yeah sure use libraries but also implement the stuff to learn.

There are a lot of subdomains within cryptography where "rolling your own" will not meaningfully strengthen your understanding of the underlying concept.

RSA is really good example of this: you can "implement" RSA in Python in an hour, and your understanding will include some of the mathematical fundamentals (prime generation, modular exponentiation, &c.). What it won't include is why or how each of those fundamentals comes with a laundry list of caveats that can completely break any scheme that uses your particular implementation of RSA.

I second the recommendation for cryptopals, as well as all of the resources that Matt Green lists[1].

[1]: https://blog.cryptographyengineering.com/useful-cryptography...

Right, but if you've improved your knowledge of the fundamentals by rolling your own RSA you'll be in a much better position to fully understand detailed articles that explain those caveats.

I'm actually skeptical that this is true: there isn't (in my mind) an intuitive bridge between "select two large primes" and "you have to make sure that there are enough different upper bits between p and q or your system is completely hosed." The former is the "direct" understanding of what makes RSA cryptographically sound, and what rolling your own will teach you; the latter is a weird result in number theory.

RSA is a particularly easy punching bag in this regard, but I think it's true generally (and is generally becoming more true, as we see increasingly clever sidechannels and oracles).

Edit: That being said, I want to moderate my position by saying that I don't think there's anything wrong with playing around with cryptosystems in an attempt to learn them. I do it! I think the risk that people talk about when they say "DRYAC" is that engineers will take their relatively painless experience getting it 10% right in their spare time and think they can get it 100% right without an asymmetric amount of additional effort.

The fact this is even a question shows me how many engineers are just cargo culting whatever they hear someone else say. If you can't understand that a toy project has different trade offs than the NSA you really shouldn't be engineering anything, trade offs are the entire job. Nobody is going to spend the time to implement this guide instead of importing a library.

I think this is unnecessarily harsh. Most of the people who implement cryptographic systems are professional engineers, and are not otherwise incorrect in evaluating their skillsets or capabilities. The problem isn't cargo culting, but the fact that cryptography is much more subtle and un-engineering-like that the rest of our discipline.

How dare you.

If no one is allowed to roll their own crypto, even just to learn how it works (and not use it for anything), then how does one become one of those exalted crypto experts who is allowed to create the libraries that everyone else who doesn't roll their own crypto uses?

Someone has to write those libraries.

First, break stuff. That's what the Cryptopals exercises are doing, but because in our actual world there's lot of good stuff out there now these exercises provide bad examples† you can break. If, in your hypothetical, there is no good crypto, this will be very easy to do just by taking anything you find in the real world, right?

Now, use what you learned (from breaking stuff) to make something which resists the attacks you learned. Congratulations, you have improved the state of the art. This is how actual experts (not sure any of them are or should be "exalted") did it.

† Bad, but, in many cases, very real. Because people stubbornly will not learn this lesson and keep rolling their own we are still finding broken garbage in the real world it's just becoming gradually rarer.

That is certainly valuable. But, so is actually implementing cryptographic algorithms, in a context where if you make a mistake it doesn't really matter, because it isn't in "production."

Or even if you just want to understand how an algorithm works, implementing it yourself will probably help you understand it more than reading, or finding problems in someone else's implementation.

"Roll you own" seems to be interpreted differently in the comments. Absolutely implement existing ciphers/algorithms like AES/RSA/ECC (and various modes of operation/padding) etc. to get a feeling of how they work, and just don't deploy them in production. You'll definitely get a lot from that. Great way to learn while reading the corresponding papers.

What you probably shouldn't do is try to come up with your own encryption scheme/mode of operation/padding scheme and think you've learned something valuable. By all means, try that as well, but know that you've now entered the really dangerous territory.

Cryptography is the easy part of cryptography. You can learn it as a high school student interested in programming and mathematics. I did that in the late 90s, first from Applied Cryptography and then from more advanced books. I implemented a few algorithms back then, and I also wrote a password manager I used until I learned about the existence of better third-party tools.

The real issue is that cryptography is an adversarial field. The human / systems / software aspects are the hard parts. The crypto you wrote yourself doesn't fail because you got the crypto wrong but because your adversary cheats. (I eventually lost interest in cryptography due to the adversarial nature.)

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.

Because there are always someone who think they learnt enough and do their own implementation, putting the data of them and others at risk. Writing secure implementation of crypto algorithms is hard and there are millions of ways that you can screw up.

A lot of things are hard and yet people do them and implement them all the time, that it might be hard is not a reason for people to not implement things - if anything by implementing them is how they'll learn (especially for those, as mentioned elsewhere in this thread, who learn better by doing).

You can screw up all sorts of things - which may (depending on the situation, application, etc) also end up with data at risk (assuming that there is even such a requirement in the first place). That also doesn't mean people shouldn't implement crypto, otherwise they shouldn't implement anything that touches any data at all - after all someone might use the most secure library in the world and accidentally forget to check for user authentication (or whatever else that has nothing to do with crypto itself but still check for privileged data access) in a specific way and let the data leak out.

And honestly i'm personally vehemently against this elitism-preserving "this is for us enlightened few to dabble with, not you plebeian hands" attitude towards crypto that some people have as if it is some forbidden knowledge that only a few high priests can have.

Don’t selfhost. You inevitably will misconfigure your servers and lose your customer data. Bow to amazon overlords and don’t even think otherwise.

Don’t drive. You inevitably will kill some pedestrian. Use Uber and let professionals do it.

I don’t think that’s a healthy attitude. And exposing data because of misconfigured firewall (ahem, DOCKER-USER, ahem) is like 1000x more probable than someone hacking your cryptoschemes.

There must be freedom in software engineering. Even at cost of some grave mistakes.

> Don’t drive. You inevitably will kill some pedestrian. Use Uber and let professionals do it.

It's ironic you say this because I find Uber/taxi drivers to be noticeably more dangerous than average drivers.

"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.

>It's another way of saying "you'll never really understand this so don't try, just rely on a mysterious cabal of experts".

It's more along the lines of, "you absolutely can understand this if you try, buy trying will take years of your life to learn and apply all attack vectors and their mitigations."

The admonition not to roll your own crypto isn't so that people don't look at crypto. Take a look, fiddle, and hack all you want - just not in production. The saying comes from crypto people noticing avoidable security issues that get created many times people have touched or used crypto code - because even 100% correct crypto code is often also broken in practice.

I think it's closer to "don't think you can half-ass your way into an understanding," rather than "you'll never be able to understand this." That "cabal of experts" all had to learn at some point, too.

In general, I think DRYAC is excellent advice, and that we should apply similar reasoning to unsafe programming languages. And that is not to say that people shouldn't use them; only that we, as a community, should be making ourselves more half-ass-resistant.

Most of what I've learned has been by overconfidently trying to do something I didn't understand, and then learning better ways incrementally.

Granted, this is a bad idea when it comes to nuclear engineering. But it's sad when we say it's bad for software engineering, even crypto.

The fact that you want to apply that to C programming is really sad. That's effectively saying that people can play with web apps, but not operating systems.

I am not saying you are wrong. Just that you're no fun at all.

I think you've misunderstood.

There are at least two separate things are stake here: there's professional software engineering, and then there's hobbyist programming.

Software engineering has been undergoing professionalization (in terms of processes and safety standards) for the last 70 years. It's one of the few ways in which software really is an engineering practice: our standards are written in blood (or fraud), just like every other engineering discipline. In this context, DRYAC and "don't write it in C" are excellent principles: we've successfully professionalized and compartmentalized beyond the need for the bad old ways, except in limited cases (corresponding to domain expertise or specific, legacy requirements).

Then there's hobbyist programming, where you can do whatever you please. I write C for fun. I implement hilariously outdated block ciphers for fun[1]. I couldn't write a web app if my life depended on it. The key understanding with hobbyist programming is that it's (1) adequately disclaimed as not usable in professional contexts, or (2) adheres to the same standards as professional, potentially critical, software engineering.

Open source started as case (1) above, and is slowly turning towards case (2) where it matters. And where it matters is cryptography and, increasingly, memory unsafe code.

In other words: you're more than welcome to build a model train set (I do it), but it doesn't qualify either of us to run a railroad. What qualifies us is learning and performing everything else involved in the safe and normal operation of a modern railroad, including knowing not to build steam engines anymore.

[1]: https://github.com/woodruffw/skipjack.rs

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?

They're not special. Cryptographers are mostly (but not exclusively) the products of a few academic programs around the world that teach the specialized math involved in developing and proving (and breaking) crypto algorithms.

The standards are either the outcome of competitions the US government (through NIST) has held over the years, or they're de-facto standards because they're provably better for certain use cases than other algorithms.

Fun fact, crypto in cryptocurrency is cryptography.

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.

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

Imagine a NSA Codebase, having to hold a million hacks for a million different moving targets, they would grind to a total halt. Implementation variety is defense by burdening the attacker with maintenance for a million little ecosystems.

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

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.

Isn't table lookup constant time?

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

(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

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.

> 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.

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.

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 )

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.

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).

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

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

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.

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...

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...

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.

Shades of the floating point truncation bug in Vancouver Stock Exchange Index in the early 1980s:

https://en.wikipedia.org/wiki/Vancouver_Stock_Exchange#Round...

The bug caused the index to creep up to twice the real index.

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

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)

AES is useful beyond AES-GCM.

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

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.

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?

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.

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

"I know just enough to be dangerous"

I'm stealing that!

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.

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

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

Just know that GitHub now supports mathjax in markdown.

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

Also, "Software AES bad"

Reply on news.ycombinator.com