6 ms·

Sarah2 Cipher

39 points by mnem 7y ago

miles 7y ago
The title itself is a bit of a cipher; perhaps the first sentence would better serve? "Sarah2 is a cipher meant to be implemented by hand with only simple tools."
nneonneo 7y ago
Hmm, I’m not actually convinced this is secure. Good S-boxes are not trivial to come up with; bad ones are vulnerable to attacks like differential cryptanalysis or linear cryptanalysis (where the S-box is modeled approximately as a linear function of its inputs). While the S-box here is secret, it’s not inconceivable that an attacker could collect enough ciphertexts (or plaintext/ciphertext pairs) to establish statistical correlations. Second, the whole encryption is modeled on a series of identical encryption rounds (no per-round subkeying). I would not be surprised if this structure makes it vulnerable to a slide attack - which is an attack that specifically attacks weak round functions no matter how many times they are iterated. Although I haven’t spent enough time to be certain these attacks will work, the design of the cipher does not inspire confidence. The cipher achieves poor diffusion after log2(n) rounds on highly repetitive text (e.g. “a” repeated 16 times yields “rjrjmlmlskskjbjb” after log2(n)-1=3 rounds), meaning that the minimum round count feels entirely too low to be safe.
- merlincorey 7y ago
  It sounds to me like you are more advanced in cryptography than I am, but, I do agree and I was similarly worried about the relative strengths of various s-box keys. I don't know if it's just assumed or if was an actual oversight on the part of the author, but I found it strange that there is no mention of the Vigenere cipher which the first step greatly resembles. I also was confused why they referred to transposition as permutation... and why the last round of transposition is optional "because it's so trivial". My understanding of things is that if it's so trivial you can leave it out, then it's not really adding much security in the first place.
  - 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.
- clarry 7y ago
  > Good S-boxes are not trivial to come up with; bad ones are vulnerable to attacks like differential cryptanalysis or linear cryptanalysis (where the S-box is modeled approximately as a linear function of its inputs). Last time I looked into this, the consensus seemed to be that even random S-boxes are likely to be good, or at least "good enough." And that it's actually not that hard to filter out boxes that are likely to be bad. I don't have references handy but google gets me this, for instance: https://kste.dk/assets/slides/secretsbox.pdf https://kste.dk/assets/slides/secretsbox.pdf
  - nneonneo 7y ago
    The NSA quite famously rewrote the S-Boxes of DES to make them resistant to differential cryptanalysis. Later studies indicated that minor changes to the DES S-Boxes could significantly weaken them (see https://web.archive.org/web/20120520040808if_/http://www.sans.org:80/reading_room/whitepapers/vpns/s-box-modifications-effect-des-like-encryption-systems_768 https://web.archive.org/web/20120520040808if_/http://www.san... for an overview). Larger S-Boxes might be better; Blowfish for example uses larger key-dependent S-Boxes and yet seems to be reasonably secure. However, they’re also used in conjunction with per-round subkeys; I don’t know how Sarah2 would fare without these per-round keys.
- nneonneo 7y ago
  Also, some thoughts on usability: - The key is huge and really unwieldy. Disguising it (for subtle key distribution) could be hard. Solitaire here has a bit of a better story (nobody looks twice at a pack of cards), but in general a good key-derivation function could help. (A bad key derivation function could totally compromise this scheme - which is why it’d be good to specify one!) - There’s no specifies incremental mode of operation (which is a useful property), which means that you’d have to manually break your ciphertext into blocks. It’d be good to specify an optimal block size. - The creator claims in other places (e.g. Reddit) that certain types of attacks don’t apply because this is a hand cipher. However a hand cipher doesn’t mean that both parties must be operating the cipher by hand! It seems like a common use-case would be for one party to have access to technology (e.g. a spymaster), in which case a bug could enable automated attacks on the system. What I do like about this cipher is the conceptual simplicity; I’m just bothered by the claim that it is a “strong” cipher without convincing evidence of that being true.
  - tptacek 7y ago
    My intuition on the slide attack vs. human cipher argument is that the cipher is only ever run by hand; there's no way to generate plaintext/ciphertext pairs automatically, because no computer system ever runs it. Humans won't generate enough message pairs to make the attack feasible. (I haven't though this through carefully, just spitballing).
throw0101a 7y ago
See also the LC4 "low tech" cipher: * https://news.ycombinator.com/item?id=16586257 https://news.ycombinator.com/item?id=16586257 * http://scienceblogs.de/klausis-krypto-kolumne/2018/05/14/the-low-tech-cipher-lc4/ http://scienceblogs.de/klausis-krypto-kolumne/2018/05/14/the... And a tweaked version thereof, LS47: * https://gitea.blesmrt.net/exa/ls47 https://gitea.blesmrt.net/exa/ls47 * https://weekly-geekly.github.io/articles/352448/index.html https://weekly-geekly.github.io/articles/352448/index.html
miles 7y ago
Just found this /r/cryto thread on Sarah2 from a little more than a week ago: https://www.reddit.com/r/crypto/comments/ea00yb/sarah2_a_strong_penandpaper_cipher/ https://www.reddit.com/r/crypto/comments/ea00yb/sarah2_a_str... and this one on Lobsters from a day or two ago: https://lobste.rs/s/yuwgdd/sarah2_strong_pen_paper_cipher https://lobste.rs/s/yuwgdd/sarah2_strong_pen_paper_cipher
mike_d 7y ago
This looks like it would be vulnerable to a slide attack (https://en.wikipedia.org/wiki/Slide_attack https://en.wikipedia.org/wiki/Slide_attack) I may have missed it, but there appears to be no instructions on how to decrypt?
- nneonneo 7y ago
  Pretty sure you just run the encryption algorithm in reverse - unpermute (split input into two halves and interleave), then reverse-map through the S-Box.

39 points by mnem 7y ago

The title itself is a bit of a cipher; perhaps the first sentence would better serve? "Sarah2 is a cipher meant to be implemented by hand with only simple tools."

nneonneo 7y ago

Hmm, I’m not actually convinced this is secure. Good S-boxes are not trivial to come up with; bad ones are vulnerable to attacks like differential cryptanalysis or linear cryptanalysis (where the S-box is modeled approximately as a linear function of its inputs). While the S-box here is secret, it’s not inconceivable that an attacker could collect enough ciphertexts (or plaintext/ciphertext pairs) to establish statistical correlations. Second, the whole encryption is modeled on a series of identical encryption rounds (no per-round subkeying). I would not be surprised if this structure makes it vulnerable to a slide attack - which is an attack that specifically attacks weak round functions no matter how many times they are iterated. Although I haven’t spent enough time to be certain these attacks will work, the design of the cipher does not inspire confidence. The cipher achieves poor diffusion after log2(n) rounds on highly repetitive text (e.g. “a” repeated 16 times yields “rjrjmlmlskskjbjb” after log2(n)-1=3 rounds), meaning that the minimum round count feels entirely too low to be safe.

merlincorey 7y ago
It sounds to me like you are more advanced in cryptography than I am, but, I do agree and I was similarly worried about the relative strengths of various s-box keys. I don't know if it's just assumed or if was an actual oversight on the part of the author, but I found it strange that there is no mention of the Vigenere cipher which the first step greatly resembles. I also was confused why they referred to transposition as permutation... and why the last round of transposition is optional "because it's so trivial". My understanding of things is that if it's so trivial you can leave it out, then it's not really adding much security in the first place.
- 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.
clarry 7y ago
> Good S-boxes are not trivial to come up with; bad ones are vulnerable to attacks like differential cryptanalysis or linear cryptanalysis (where the S-box is modeled approximately as a linear function of its inputs). Last time I looked into this, the consensus seemed to be that even random S-boxes are likely to be good, or at least "good enough." And that it's actually not that hard to filter out boxes that are likely to be bad. I don't have references handy but google gets me this, for instance: https://kste.dk/assets/slides/secretsbox.pdf https://kste.dk/assets/slides/secretsbox.pdf
- nneonneo 7y ago
  The NSA quite famously rewrote the S-Boxes of DES to make them resistant to differential cryptanalysis. Later studies indicated that minor changes to the DES S-Boxes could significantly weaken them (see https://web.archive.org/web/20120520040808if_/http://www.sans.org:80/reading_room/whitepapers/vpns/s-box-modifications-effect-des-like-encryption-systems_768 https://web.archive.org/web/20120520040808if_/http://www.san... for an overview). Larger S-Boxes might be better; Blowfish for example uses larger key-dependent S-Boxes and yet seems to be reasonably secure. However, they’re also used in conjunction with per-round subkeys; I don’t know how Sarah2 would fare without these per-round keys.
nneonneo 7y ago
Also, some thoughts on usability: - The key is huge and really unwieldy. Disguising it (for subtle key distribution) could be hard. Solitaire here has a bit of a better story (nobody looks twice at a pack of cards), but in general a good key-derivation function could help. (A bad key derivation function could totally compromise this scheme - which is why it’d be good to specify one!) - There’s no specifies incremental mode of operation (which is a useful property), which means that you’d have to manually break your ciphertext into blocks. It’d be good to specify an optimal block size. - The creator claims in other places (e.g. Reddit) that certain types of attacks don’t apply because this is a hand cipher. However a hand cipher doesn’t mean that both parties must be operating the cipher by hand! It seems like a common use-case would be for one party to have access to technology (e.g. a spymaster), in which case a bug could enable automated attacks on the system. What I do like about this cipher is the conceptual simplicity; I’m just bothered by the claim that it is a “strong” cipher without convincing evidence of that being true.
- tptacek 7y ago
  My intuition on the slide attack vs. human cipher argument is that the cipher is only ever run by hand; there's no way to generate plaintext/ciphertext pairs automatically, because no computer system ever runs it. Humans won't generate enough message pairs to make the attack feasible. (I haven't though this through carefully, just spitballing).

throw0101a 7y ago

See also the LC4 "low tech" cipher: * https://news.ycombinator.com/item?id=16586257 https://news.ycombinator.com/item?id=16586257 * http://scienceblogs.de/klausis-krypto-kolumne/2018/05/14/the-low-tech-cipher-lc4/ http://scienceblogs.de/klausis-krypto-kolumne/2018/05/14/the... And a tweaked version thereof, LS47: * https://gitea.blesmrt.net/exa/ls47 https://gitea.blesmrt.net/exa/ls47 * https://weekly-geekly.github.io/articles/352448/index.html https://weekly-geekly.github.io/articles/352448/index.html

miles 7y ago

Just found this /r/cryto thread on Sarah2 from a little more than a week ago: https://www.reddit.com/r/crypto/comments/ea00yb/sarah2_a_strong_penandpaper_cipher/ https://www.reddit.com/r/crypto/comments/ea00yb/sarah2_a_str... and this one on Lobsters from a day or two ago: https://lobste.rs/s/yuwgdd/sarah2_strong_pen_paper_cipher https://lobste.rs/s/yuwgdd/sarah2_strong_pen_paper_cipher

mike_d 7y ago

This looks like it would be vulnerable to a slide attack (https://en.wikipedia.org/wiki/Slide_attack https://en.wikipedia.org/wiki/Slide_attack) I may have missed it, but there appears to be no instructions on how to decrypt?

nneonneo 7y ago
Pretty sure you just run the encryption algorithm in reverse - unpermute (split input into two halves and interleave), then reverse-map through the S-Box.