4 ms·

It’s nontrivial in the middle; it’s trivial as the last step because it involves no key material. I’m pretty suspicious of this approach for long messages, whe

by brians 7y ago

It’s nontrivial in the middle; it’s trivial as the last step because it involves no key material. I’m pretty suspicious of this approach for long messages, where you’ll have ECB-like problems—too many pairs that will survive the transpositions. I’m pretty suspicious of this for short messages because there’s no randomness.

tptacek 7y ago
As discussed on /r/crypto, short messages are also problematic because they expose the cipher to slide attacks. With very short messages, it's easy to find a P=F(P'), C=F(C') pair. You collect a bunch of them to reveal the full state of the key (or enough to make messages intelligible). I like designs like this just as teaching models (which I think was part of the point of designing it). Slide attacks, which I've never played with before, are really neat; my attempt to distill the idea is that, in ciphers with repeating round/key structure, by hunting for pairs P=F(P'), you can effectively reveal a single iteration of the round function. In designs like this, iteration is meant to shield the weak round function from attack; the slide attack collapses security back down to a single application of the round.
- nneonneo 7y ago
  A recent cryptography challenge in a CTF featured the New Data Seal (NDS) cipher, which is the cipher that first inspired the slide attack. NDS has a very weak round function which is iterated 16 times. The 2048-bit key is used as a lookup table, not unlike the S-Box key in the Sarah2 cipher here. Despite the large key size and the reasonable block size of 128 bits, a slide attack can defeat it in less than 4096 plaintext-ciphertext pairs, demonstrating the devastating effectiveness of this approach. Every block cipher since has featured some kind of per-round keying or variance to ward off this attack.
  - tptacek 7y ago
    This is neat. How was the NDS CTF challenge structured? Did someone write it up? I'm kind of fascinated by the concept of fundamental block cipher cryptanalysis being a CTF challenge, since my perception is that it's virtually never at play in real systems you might want to attack (unlike lots of other cryptographic flaws!). Certainly, I wouldn't want to make the case that you should use this toy cipher (but I don't know that its author is making that case either, since they too use the word "toy" to describe it). I'm saying: simple flawed ciphers are extremely useful just as a model for learning how to actually code attacks.
    - nneonneo 7y ago
      Sorry for the late reply. The event was BSides Ottawa; an attendee forwarded the challenges to me and made writeups of the crypto challenges here: https://rctcwyvrn.github.io/posts/2019-12-02-bsides_crypto.html https://rctcwyvrn.github.io/posts/2019-12-02-bsides_crypto.h.... The challenge was quite straightforward; they created a secure random key, displayed an encrypted flag, then let you en/decipher anything you wanted except the encrypted flag (NDS is symmetric so encryption = decryption). Some of the latest crypto-heavy CTFs have also featured pretty sophisticated "fundamental" attacks on ciphers. I've seen attacks on custom LCG-based stream ciphers (Google CTF), fancy math attacks on RSA variants (hxp 36C3 CTF just last week), and even the odd differential attack. Good crypto CTF challenges are really interesting and are great opportunities to learn and build classic attacks :)

by brians 7y ago

tptacek 7y ago

As discussed on /r/crypto, short messages are also problematic because they expose the cipher to slide attacks. With very short messages, it's easy to find a P=F(P'), C=F(C') pair. You collect a bunch of them to reveal the full state of the key (or enough to make messages intelligible). I like designs like this just as teaching models (which I think was part of the point of designing it). Slide attacks, which I've never played with before, are really neat; my attempt to distill the idea is that, in ciphers with repeating round/key structure, by hunting for pairs P=F(P'), you can effectively reveal a single iteration of the round function. In designs like this, iteration is meant to shield the weak round function from attack; the slide attack collapses security back down to a single application of the round.

nneonneo 7y ago
A recent cryptography challenge in a CTF featured the New Data Seal (NDS) cipher, which is the cipher that first inspired the slide attack. NDS has a very weak round function which is iterated 16 times. The 2048-bit key is used as a lookup table, not unlike the S-Box key in the Sarah2 cipher here. Despite the large key size and the reasonable block size of 128 bits, a slide attack can defeat it in less than 4096 plaintext-ciphertext pairs, demonstrating the devastating effectiveness of this approach. Every block cipher since has featured some kind of per-round keying or variance to ward off this attack.
- tptacek 7y ago
  This is neat. How was the NDS CTF challenge structured? Did someone write it up? I'm kind of fascinated by the concept of fundamental block cipher cryptanalysis being a CTF challenge, since my perception is that it's virtually never at play in real systems you might want to attack (unlike lots of other cryptographic flaws!). Certainly, I wouldn't want to make the case that you should use this toy cipher (but I don't know that its author is making that case either, since they too use the word "toy" to describe it). I'm saying: simple flawed ciphers are extremely useful just as a model for learning how to actually code attacks.
  - nneonneo 7y ago
    Sorry for the late reply. The event was BSides Ottawa; an attendee forwarded the challenges to me and made writeups of the crypto challenges here: https://rctcwyvrn.github.io/posts/2019-12-02-bsides_crypto.html https://rctcwyvrn.github.io/posts/2019-12-02-bsides_crypto.h.... The challenge was quite straightforward; they created a secure random key, displayed an encrypted flag, then let you en/decipher anything you wanted except the encrypted flag (NDS is symmetric so encryption = decryption). Some of the latest crypto-heavy CTFs have also featured pretty sophisticated "fundamental" attacks on ciphers. I've seen attacks on custom LCG-based stream ciphers (Google CTF), fancy math attacks on RSA variants (hxp 36C3 CTF just last week), and even the odd differential attack. Good crypto CTF challenges are really interesting and are great opportunities to learn and build classic attacks :)