Cryptanalysis (by alaric)

Cryptanalysis is the science/art of analysing an encryption system's design to try and figure out how you'd break it.

If encryption systems were used properly, this would be very hard. After all, in that case, all you'd ever have access to was the design of the encryption system and a stream of intercepted encrypted messages.

However, in practice, it's possible to guess parts of the messages (perhaps most start with "Dear ..."), or even to occasionally steal a decrypted message and pair it up with its encrypted version, then study the relationships between them (known plaintext attacks). Or sneak a spy into the organisation being studied, and just ask them to send emails to the person at the other end of the encrypted link, in the middle of the night, at agreed times, so it's easy to spot the encrypted version of the message. Then you have a chosen plaintext attack, which is the most powerful kind.

For example, I'm interested in encryption algorithms made out of S-boxes. S-boxes are invertible lookup tables; a very simple four-bit S-box might be:

Since each possible output value occurs only once, each output value has a single corresponding input value, so we can create a table that 'undoes' that substitution, for decryption.

Most algorithms use fixed S-boxes, but I'm interested in having them generated from the user's key. Software implementations of algorithms can be easily made using S-boxes up to 16 bits in size (which requires 128KB of RAM), and there's a lot of information in a 16-bit S-box (the first entry can have 65536 possible values; the second can have 65535, since one option is already taken; and so on - so there's 65536! possible setups of such an S-box, and log₂ 65536! = log₂ 65536 + log₂ 65535 + log₂ 65534 + ... log₂ 2 = about 119KB of actual entropy.

But let's see how they perform under cryptanalysis...

Pages: 1 2 3 4

2 Comments

• 

  By Try the Ghost, Wed 20th Feb 2008 @ 8:34 am

  This thread has been dead for quite some time, but if you're still interested, here are my thoughts:

  In option 1, you're adding one extra round of S-boxes and diffusion. This buys you an extra avalanche, and therefore a lot more complexity for the attacker. Essentially you've got a three round block cipher with two complete avalanches. No matter how strong your S-boxes, the small number of avalanches will leave it vulnerable to differential cryptanalysis (and possibly other exotic attacks, like impossible linear, and meet in the middle). Your best bet is to have many rounds, so as to increase your total number of avalanches. For me, I'm not satisfied with anything less than 6 complete avalanches. I believe DES had about 5.5, and Blowfish has 7.5. In your case, it takes two passes of S-boxes for the first avalanche, and then one avalanche per round thereafter. However, no matter how many avalanches you have, a 32-bit block cipher is susceptible to a complete "codebook" attack where the interceptor just records plaintext/ciphertext combos for all possible 32-bit inputs -- that table would fit on your iPod several times over.

  So option 2 is much stronger. You've now got a 64-bit block cipher. After three rounds you have a complete avalanche, and then every two rounds thereafter (I think). With a 16 round cipher you'd have something like 7.5 full avalanches. Have you considered using several 16-bit S-boxes? In this particular design, 4 separate 16-bit S-boxes would fit quite naturally. Lots more key setup time, but then the attacker is faced with a very, very hard task.

  p.s. I loved how you deduced that XORing inputs into an S-box doesn't make the S-box any stronger. In fact, if your S-box is 16 bits and based on only on the user key, then your S-box contains billions of times as much information as your subkeys. Mad entropy, like you said. With key dependent S-boxes, you can scrap subkeys -- they don't add any non-linearity or diffusion, as you so cleanly stated. In my own ciphers, which tend to be based on key dependent S-boxes, I often skip subkeys.

• 

  By alaric, Thu 21st Feb 2008 @ 6:58 pm

  Yes indeed! I wouldn't recommend using the results of either such options as a 'real cipher', since 32 bit blocks are indeed trivially codebooked, and too few layers of avalanche do ease cryptanalysis greatly. I'm studying them more as basic components, so that their weaknesses can be found and mitigated when using them as parts of a larger whole.

  What I've since become more interested in is less linear operations between the S-boxes. Analyses of the implications of a small change in the input, as I've done, rely to a certain extent on the simplicity of the diffusion between layers. While the S-boxes provide a high level of good old key-dependent unguessability, I'm interested in finding functions that efficiently diffuse changes across as much width as possible, with things like key dependence being lower priorities.

  See: http://www.snell-pym.org.uk/archives/2005/07/04/avalanche-functions/

  I posted my own further examinations of the S-box layering later:

  http://www.snell-pym.org.uk/archives/2006/09/24/cryptanalysis-2/#more-311

Other Links to this Post

RSS feed for comments on this post.

Leave a comment