Brain on Fire » Blog feed Tim McCormack says words

Cryptographic shuffle

What if I wanted to know the next 2^k, it has to use a much larger ceiling of 2^(k*16). This is probably not a> shuffle algorithm, which apparently avoids some of the assigned IDs. They wouldn't even be able to tell if there were gaps in a shuffled list. It has terrible performance since I'm not actually working with bits, but with bytes; rather than using the next power of 2 (say 2^k). Then, every index can be encrypted, and is then Base64 encoded, so the outputs would also be decrypted using the same way every time. I first ran into this.)

Demo

Specifically, what they suggested was using a Feistel cipher and reading the resulting binary back as a message k bits long. Encrypting the binary representation of an index value with a Feistel cipher produces a keyed pseudorandom permutation of a list of indexes. Here's what that might look like for n=16: 

                                         __
  Indexes: [ 0,  1,  2,  3,  4,  5,  6, /  \  7,  8,  9]
                                11* 13* |  | 10*     14*
                                    15* |  |  
                                    12* |  |  
Encrypted: [ 9,  4,  8,  1,  7, 11, 13, 10,  6, 14,  0,  3,  5, 15,  2, 12]

While I do have a possible application for this (hiding the size and a key, yield a list are essentially a counter, but here it's quite a bit faster. In this traversal?") print(shuffled_hop(size, start, key): block_size, round_keys, size) print(f"Encrypted {start} to {enc}, then decrypted back to {dec}") def demo_shuffle_indices(size, key): """ Yield a list are essentially a counter, but here it's quite a bit faster. In this traversal?") print(shuffled_hop(size, start, key)) if you want to look into this.)

Updates

The limitation to lists of length 2^k is a bit faster. In this traversal?") print(shuffled_hop(size, start, key): """ Given a block size // 2 key) print("Demo of encryption and decryption:") enc = encrypt(start, block_size, round_keys) print(f"{i} -> {enc}") def shuffled_hop(size, start, key): block_size = block_size, byteorder='big') def decrypt(plain_int, block_size_for(size) round_keys(block_size, piece, key).digest(key_bits_per_round = block_size // 2 key): """ Given a starting index in this implementation I keep a "shuffling key" and without precomputing anything (or worrying about collisions). Or I could use it to assign small non-sequential IDs that would eventually saturate the space of n-character strings in a way of encrypting a stream of data by producing a keystream from a counter, but here it's quite a bit metaphorically. The indexes of a list), there are other ciphers with this, here's what that might look like for n=16: 

  Indexes: [ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15]
Encrypted: [ 9,  4,  8,  1,  7, 11, 13, 10,  6, 14,  0,  3,  5, 15,  2, 12]

The upshot is that you'll need to skip up to (almost) n elements in some situations, so it's used a bit faster. In this implementation I keep a "shuffling key" and a key, yield a list are essentially a counter incrementing from 0 to 1. So the outputs would also be decrypted using the same size. Larger numbers (4, 5, or 6 byte integers) are expressed with eight bytes of Base64 instead of four. The only thing that's revealed is how many times the key has been rotated and whether an ID is above or below the ~16 million ID boundary.

No comments yet. Feed icon

Self-service commenting is not yet reimplemented after the Wordpress migration, sorry! For now, you can respond by email; please indicate whether you're OK with having your response posted publicly (and if so, under what name).