Mixing Cipher Summary Show

1. Author Background
2. Balanced Block Mixing Summary
3. A Cipher
4. A Block Cipher
5. Mixing Cipher Structure
6. Latin Square
7. Orthogonal Latin Squares Mixing
8. Mixing Block Cipher Implications
9. Small Mixing Tables
10. Small Table Keying
11. Mix Blocks with Small Tables
12. Medium Block RAM
13. Huge Block Advantages
14. Huge Block RAM
15. Deciphering
16. Mixing Cipher CONCLUSION

1. Author Background

• 3 decades electrical engineering
• 16 years cryptographic technology
• 3 fundamental crypto patents
• book-length crypto glossary
• introduction to cryptography
• many web articles

• massive speed (a full block per clock)
• arbitrary block width (power-of-2 elements)
• huge blocks avoid ciphertext expansion
• huge blocks allow random-access ciphering
• structured chip layout
• reasonable on-chip RAM requirements
• unique patented technology

3. A Cipher

• a key-selected transformation between plaintext and ciphertext
• the opponent has ciphertext:
  • the ciphertext appears random
  • different keys return different potential messages
  • there are too many keys to try them all
  • the real message is "a needle in a haystack"

4. A Block Cipher

• accumulates multiple data elements in a block
• emulates simple substitution with a huge alphabet
• only complete blocks can be ciphered
• each input bit affects every output bit
• any input bit changes about half of output bits

• network of small mixing tables
• "FFT-like" network for power-of-2 block sizes
• normal FFT expands data so does not work
• orthogonal Latin squares replace FFT butterfly
• each input affects every output

6. Latin Square

• every value occurs once in each row and column
• any change in column or row selects a different value
• when mixing values, every change propagates to the next layer

7. Orthogonal Latin Squares Mixing

• a selected pair of Latin squares
• every possible output value occurs exactly once
• even a single bit input change affects both outputs
• each mixing is one table lookup
• each mixing takes one RAM access time

• any input change affects all network outputs
• bandwidth is one block per clock
• latency is one clock per layer (picture shows 4 layers)
• each layer gets a different block every clock
• @ 450MHz, throughput is 450,000,000 blocks/sec

• "order 4" oLs tables:
• 16 entries of 4 bits each (8 bytes)
• 30,13,22,01,02,21,10,33,11,32,03,20,23,00,31,12
• mix 2 bits + 2 bits into 4 bits
• efficient in hardware

• each table one of 6912 possible oLs pairs
• 64 bits storage, 12.75 bits of keying
• key-selected mixing tables are unknown to opponent
• processor loads tables into chip before ciphering
• data changes always affect entire block
• adding 2 outer layers helps keying affect entire block

• for 4-bit block, 1 table, 1 layer = 8 bytes
• for 8-bit block, 2 tables/layer, 2 layers = 32 bytes
• for 16-bit block, 4 tables/layer, 3 layers = 96 bytes
• for 4-byte block, 8 tables/layer, 4 layers = 256 bytes
• for 8-byte block, 16 tables/layer, 5 layers = 640 bytes
• (mixing values; to this add 2 outside keying layers)
• 8-byte block has 204 bits of keying per layer
• 8 bytes @ 450 MHz is 3.6 gigabytes/sec

• 16-byte block => 32 tables/layer, 6 layers + 2 = 2048 bytes
• 32-byte block => 64 tables/layer, 7 layers + 2 = 4608 bytes
• need at least 64-byte block for huge block advantages
• bandwidth: 1 block per clock
• latency: 1 clock per layer

13. Huge Block Advantages

• use Electronic CodeBook (ECB) mode instead of Cipher Block Chaining (CBC)
• ECB means no initialization vector
• ECB means no ciphertext expansion
• ECB means random access ciphering
• room for "extra data" for:
  • per-block dynamic keying
  • per-block authentication
  • homophonic ciphering

• 64-byte block => 128 tables/layer, 8 layers + 2 = 10,240 bytes
• 64 bytes @ 450MHz is 28.8 gigabytes/sec
• 128-byte block => 256 tables/layer, 9 layers + 2 = 22,528 bytes
• 256-byte block => 512 tables/layer, 10 layers + 2 = 49,152 bytes
• 512-byte block => 1024 tables/layer, 11 layers + 2 = 106,496 bytes
• 512 bytes @ 450MHz is 230.4 gigabytes/sec

• make interconnect between layers bidirectional
• use inverse table contents
• exchange table input and output lines
• or enable separate inverse tables
• layers operate in reverse order

• extremely fast ciphering
• allows huge blocks:
• huge blocks can be ciphered independently
• huge blocks need no ciphertext expansion
• relatively simple chip layout

Terry Ritter, and his current address.