Thread by @justintroutman

#Loki is trending, which provides a great opportunity to share cryptography’s tie-in with the Norse god and, slightly less so, the Marvel universe.

LOKI is a family of Australian block ciphers dating back to ‘89, designed by Dr. Lawrie Brown, Dr. Jennifer Seberry, and Dr. Josef Pieprzyk. (Dr. Seberry’s work was a fundamental part of my introduction to symmetric cryptography in the 90s. She’s a pioneer.)

LOKI89, and its improvement, LOKI91, are both Feistels, and while they didn’t become widely used (due to susceptibility to cryptanalysis), they did offer rich insight into block cipher design (e.g., differential cryptanalysis) during an impending post-DES time in cryptography.

LOKI97, also a Feistel (I’ll dissect this one in a bit), was the first published submission to the AES selection competition, but was broken by Knudsen (also cryptanalyzed LOKI91) and Rijmen (co-designer of Rijndael, the eventual winner).

LOKI97 is a neat design, because it incorporates several different structures. While the encryption routine is a balanced Feistel (128-bit input broken into two 64-bit words), the key schedule itself is a Feistel too (256-bit key broken into four 64-bit words), but unbalanced.

The key schedule is an unbalanced Feistel because it feeds three of the key words (192 bits) into a function (identical to the encryption’s round function) and then XORs that 64-bit output with the remaining fourth key word. This is called being “source heavy.”

This output is then used as key material for combining with a 64-bit word of the plaintext. Some key schedules are pretty simple, but this one is quite involved and was designed to eliminate any symmetry between subkeys (learnings from DES’s weaknesses).

(Knudsen and Rijmen did end up finding biases in certain values of round keys, due to imbalances in the round function, which the key schedule uses. That said, LOKI97 nicely captures early research into “how do we take something DES-like but make it better than DES?”)

Let’s keep taxonimizing LOKI97’s key schedule. So far, we know it’s a source-heavy unbalanced Feistel. Because all bits are used during a round, it’s also “complete”, and because the functions and word sizes stay the same throughout, it’s “homogenous” and “consistent.”

It’s also “even”, since the number of cycles (rounds needed for all bits to be a part of both source and target blocks at least once) equals the number of rotations (rounds needed for bits to return to starting points).

(What actually happens in the round function itself is essentially an SPN [Substitution-Permutation Network] that layers S-boxes, P-boxes, and an expansion function. This doesn’t affect the taxonomy, but it’s a detail worth noting and one you’ll recall from DES.)

Lastly, let’s talk branches and cycles: LOKI97’s encryption routine works on two 64-bit words, making it “2-branch”, while the key schedule works on four 64-bit words, making it “4-branch.”

A cycle refers to the # of rounds needed for all bits to be “worked on.” LOKI97’s encryption routine has two branches and iterates over 16 rounds, giving it 8 cycles. The key schedule has four branches and needs 48 rounds to make all subkeys (3 per round), giving it 12 cycles.

The key schedule is a homogenous, even, complete, and consistent source-heavy (192:64) 4-branch, 6-cycle Unbalanced Feistel Network.” That makes the key schedule look a lot, taxonomy-wise, like the SM4 block cipher I tackled in an earlier thread:

https://twitter.com/justintroutman/status/1408167687184920580

(LOKI97’s encryption routine is a 2-branch, 8-cycle classical, balanced Feistel, so much of the taxonomy we use for UFNs doesn’t really apply; technically, just like DES, we could say it’s a “homogenous, even, complete, and consistent 2-branch, 8-cycle classical Feistel Network.”

With that, I’m officially open for “Get Your Unbalanced Feistel Taxonomized Here!” service, but cannot commit to any SLAs related to delivery times. In the meanwhile, you can read more about LOKI97 here: lpb.canb.auug.org.au/adfa/research/…

Didn't correct the error when I caught it the first time: it's a 12-cycle UFN, not a 6 cycle one.