Drawing an ASCII Tie Fighter for Post-Quantum Cryptography

5 hours ago 1

This is a funny short story about contributing to internet standards. The real heroes of the story are Filippo Valsorda and all the other contributors to post-quantum cryptography standards (PQC). Without their efforts internet communications would be less secure, so thank you :)

As I understand the situation, the internet standard being discussed is “Concrete Hybrid PQ/T Key Encapsulation Mechanisms” (KEMs) which combine PQ algorithms with traditional algorithms. The reasoning being that PQ algorithms are relatively new which is not great for cryptography which would prefer using algorithms that have survived many years of scrutiny and analysis, such as EdDSA.

Therefore, it is desirable to have a “hybrid” KEM designed such that the hybrid “fails gracefully” by only losing the quantum safety property if the PQ algorithm is insecure, but doesn't compromise safety to traditional attack vectors that exist without sufficiently powerful quantum computers. My intuition is this will allow for more confident experimentation and deployment of PQ algorithms, as the stakes are much lower for actually rolling out the new algorithms with this construction.

There are three concrete hybrid KEM instances that are defined within the standard, they are named but the names may change in the future:

MLKEM768-P256
MLKEM768-X25519 (aka “X-Wing”)
MLKEM1024-P384

Note that the X-Wing KEM was first published in January 2024, much earlier than the other KEMs in this draft. You may have already guessed that the name of the "X-Wing" KEM is relevant to the title of the blog post :)

These hybrid KEMs are made up of 5 components:

Traditional component that is either a “nominal group” or a traditional KEM
A post-quantum KEM
A pseudo-random number generator (PRG)
A key-derivation function (KDF)
And finally, a label which is a byte string that labels the specific combination of the above components.

For the X-Wing KEM the label is the byte string “0x5C2E2F2F5E5C”, which if printed out as ASCII looks like an X-Wing from Star Wars:

\./ /^\

Note that the newline was added to better visualize the ASCII art of an X-Wing, the newline isn't present in the actual KEM label byte string.

This is where my concrete understanding of the context is fuzzier, and figuring it all out would require digging through IETF mailing list exchanges. As far as I could tell from a quick read the new KEM constructions being proposed were going to have real names instead of ASCII art to match the actual name of the construction, basically what name you'd end up configuring in OpenSSL, NGINX, etc.

This naming discussions was taking time and the label being used for key derivation means that implementations of this draft standard couldn't be deployed, as that label was not finalized and could change later.

Filippo asked on the IETF mailing list whether the label and the name could be disconnected for the new set of KEM constructions and instead follow the lead of X-Wing using small ASCII art of spaceships. This would let the naming discussion continue while allowing implementers to begin deploying their experiments without fear of having the labels change at a later time.

So Filippo created a few new ASCII art pieces, one of an imperial TIE fighter for MLKEM768-P256 and another of an imperial Lambda shuttle for MLKEM1024-P384:

|A| | |V| /-\

Filippo posted about this on Mastodon, where Frederik Braun suggested changing the TIE fighter to |-o-|. Filippo wanted to keep the characters used at exactly 6 bytes, so I suggested:

Frederik and Filippo approved of my rendition, and submitted a pull request which was eventually merged into the draft. I love little easter-eggs left in internet standards by authors so it felt special to be able to contribute my own for future readers' enjoyment. Happy implementing! :)

Wow, you made it to the end! ...and you're thinking, what now?