Realizing one general way to construct symmetric ciphers

May 2, 2021

One of the areas of cryptography that's always seemed magical to me is symmetric ciphers. I believed that they worked, but it felt amazing that people were able to construct functions that produced random-looking output but that could be inverted if and only if you had the key (and perhaps some other information, like a nonce or IV). I recently read Soatok's Understanding Extended-Nonce Constructions, which set off a sudden understanding of a general, straightforward way to construct symmetric ciphers (although not all ciphers are built this way).

A provably secure general encryption technique is the one-time pad. One way to do one-time pad encryption on computers is to have your OTP be a big collection of random bytes (known by both sides) and then use the fact that 'A xor B xor A' is just B. The sender XORs their message with the next section of their OTP, and the receiver just XORs it again with the same section, recovering the original message (this is a form of XOR cipher). However, one-time pads are too big for practical use. What we would like is for each side to generate the one-time pad from a smaller, easier to handle seed.

What we need is a keystream, or more exactly a way to generate a keystream from an encryption key and probably some other values like a nonce (a one-time pad is a keystream that requires no generation). The keystream we generate needs to have a number of security properties like randomness and unpredictability, but the important thing is that our keystream generation function doesn't have to be invertible; in fact, it shouldn't be invertible. There are a lot of ways to do this, especially since it's sort of what cryptographic hashes do, and it's easy for me to see how you could possibly create keystream generation functions.

What I've realized and described is a stream cipher, as opposed to a block cipher. While I'd heard to the two terms before, I hadn't understood the cryptographic nature of this distinction, vaguely thinking it was only about whether you had to feed in a fixed size input block or could use more flexible variable-sized inputs. Now I've learned better in the process of writing this entry and learned something more about cryptography.

(I could probably learn and understand more about how it's possible to construct block ciphers if I read more about them, but there's only so far I'm willing to go into cryptography.)


Comments on this page:

By Andrew at 2021-05-02 02:19:33:

Good keystream generators, good hashes, and good pseudorandom number generators are all sort of related. It's all about having uniform, unpredictable output, and mixing up your state in ways that make it hard for anyone to figure out what your inputs were, or your hidden state is, given the output.

By dozzie at 2021-05-02 07:28:02:

Block ciphers often use Feistel network. Not all of them (e.g. Rijndael, known as AES), but it's common enough that it's a good starting point.

To sum up, you take a block, split it in two halves, and left half you write on the right intact, the same left half you mangle with key (e.g. compute their hash) and the result you XOR with the right half, writing it on the left. The result is that you swap the halves, with only left half of the result being encrypted. Then you repeat such rounds as many times as the cipher's setup says (e.g. 64 rounds, but at least 2 rounds, because half the data is still in plain text).

With Feistel network you don't even need the mangling function to be reversible, you just need to be able to make the same calculation during deciphering (that's why you write the half you mangle with the key in clear text; obviously, if you don't know the key, you can't repeat the calculation and recover the other half).

Written on 02 May 2021.
« Discovering outside people attempting to do dynamic DNS updates to us
Understanding OpenSSH's future deprecation of the 'ssh-rsa' signature scheme »

Page tools: View Source, View Normal, Add Comment.
Search:
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Sun May 2 00:56:40 2021
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.