Mixing Cipher Summary Show (original) (raw)

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-lengthcrypto glossary
• introduction to cryptography
• many web articles

2. Balanced Block Mixing Summary

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

3. A Cipher

• akey-selected transformation betweenplaintext andciphertext
• the opponent has ciphertext:
  • the ciphertext appears random
  • differentkeys return different potentialmessages
  • 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 ablock
• emulatessimple substitution with a hugealphabet
• only complete blocks can be ciphered
• each input bit affects every output bit
• any input bit changes about half of output bits

5. Mixing Cipher Structure

• 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 FFTbutterfly
• 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

8. Mixing Block Cipher Implications

• 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

9. Small Mixing Tables

• "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

10. Small Table Keying

• 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

11. Mix Blocks with Small Tables

• 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

12. Medium Block RAM

• 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

• useElectronic CodeBook (ECB) mode instead ofCipher Block Chaining (CBC)
• ECB means noinitialization vector
• ECB means nociphertext expansion
• ECB means random access ciphering
• room for "extra data" for:
  • per-blockdynamic keying
  • per-blockauthentication
  • homophonic ciphering

14. Huge Block RAM

• 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

15. Deciphering

• 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

16. Mixing Cipher CONCLUSION

• 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 hiscurrent address.