4 ms·

> It's kinda surprising that symmetric-key algorithms have been so resistant to attacks. Not really. RSA was subject to attacks because it relies on arithmetic

by rsj_hn 5y ago

> It's kinda surprising that symmetric-key algorithms have been so resistant to attacks. Not really. RSA was subject to attacks because it relies on arithmetic, which has a lot of structure and you can exploit that structure. Thus a number-theoretic advance in factoring becomes an attack on RSA. The reason why ECC is so much stronger on a per-bit basis is because there is a lot less (known) structure to group multiplication on a curve than to integer multiplication. But with the primitives used in symmetric cryptography -- basically substitution or in math terms a permutation -- there is almost no mathematical structure to exploit from general permutations of elements. Incidentally, one of the concerns that many have about AES is the agressive design and reliance on inversion in the S-boxes which does have some arithmetic structure. E.g. in AES, the permutations are obtained from taking the reciprocal of field elements, so there is some math there. The Soviets famously went in a different direction, generating their s-boxes randomly so there would be no structure whatsoever. Those heavy-duty ciphers are built like tanks and stood up well over time, their only weakness was small block sizes for early versions of the cipher.

cvwright 5y ago
On the contrary, I find it amazing that bit shift and XOR can be combined in such a way to provide strong security at all. Maybe it just goes to show, if you have 128 or 256 bits of key, that’s actually a heck of a lot.
- tptacek 5y ago
  I'm a little over my skis on this (I'm not a cryptographer) but for the underlying insight on why this works, I think you can start with the idea of iterated ciphers --- the design argument that a very simple function that is repeated (in "rounds") with an a key that has been expanded to fit those rounds (the "key schedule") "outperforms" --- gains adequate security with less computation --- a sufficiently complicated function. Once you have that idea, it seems natural to find the simplest and most efficient round function. Past that: I spent a long time blowing off block cipher cryptanalysis (I'm pretty much exclusively interested in crypto bugs that will actually let me own up a system, and you are essentially never going to cryptanalyze a block cipher for a vulnerability research project) but a lot of block cipher design clicked for me once I took the time to work through linear and differential cryptanalysis. So I guess my point here would be: if you're blown away that you can get such durably effective security --- so much so that 3DES is still in some ways resilient in 2021 --- well, (1) you should be and (2) Aleks' post here is I think probably a really good way to understand why this stuff works. Also, 128 bit numbers are just very big. :)
- pbsd 5y ago
  Strictly speaking, shift and xor alone will not net you a secure cipher, seeing that those are both linear GF(2) operations. You would need something else in the mix to generate some nonlinearity, like integer addition, multiplication, etc. But on the subject of extremely simple constructions, you can compose many random permutations of a particular form---state[i] = state[i] xor F(state[j], state[k]), where state[i] is the ith bit of the state and F is a randomly chosen boolean function--- and obtain something asymptotically secure [1]. [1] https://arxiv.org/abs/math/0411098 https://arxiv.org/abs/math/0411098
  - a1369209993 5y ago
    > You would need something else in the mix to generate some nonlinearity, like integer addition, multiplication, etc. Worth noting that bitwise AND also works (indeed, you can build addition from it), if you don't want to implement anything that operates on bits in non-parallel for some reason. (Which is to say/emphasize that it's linear GF(2) operations that are insufficient, not GF(2) operations in general.)
    - pbsd 5y ago
      Yeah that is true. Also you could still stick with xor and shift/rotate, but make the shifts data-dependent. That would make it nonlinear (technically a multiplication), but analysis is generally more difficult.
      - a1369209993 5y ago
        > but make the shifts data-dependent Ah, yes; cryptography usually assumes only fixed-amount shifts since some early shifters were non-contant-time, but variable-amount shifts are a thing you can do (and don't necessarily have side-channel problems on modern hardware).

by rsj_hn 5y ago

cvwright 5y ago

On the contrary, I find it amazing that bit shift and XOR can be combined in such a way to provide strong security at all. Maybe it just goes to show, if you have 128 or 256 bits of key, that’s actually a heck of a lot.

tptacek 5y ago
I'm a little over my skis on this (I'm not a cryptographer) but for the underlying insight on why this works, I think you can start with the idea of iterated ciphers --- the design argument that a very simple function that is repeated (in "rounds") with an a key that has been expanded to fit those rounds (the "key schedule") "outperforms" --- gains adequate security with less computation --- a sufficiently complicated function. Once you have that idea, it seems natural to find the simplest and most efficient round function. Past that: I spent a long time blowing off block cipher cryptanalysis (I'm pretty much exclusively interested in crypto bugs that will actually let me own up a system, and you are essentially never going to cryptanalyze a block cipher for a vulnerability research project) but a lot of block cipher design clicked for me once I took the time to work through linear and differential cryptanalysis. So I guess my point here would be: if you're blown away that you can get such durably effective security --- so much so that 3DES is still in some ways resilient in 2021 --- well, (1) you should be and (2) Aleks' post here is I think probably a really good way to understand why this stuff works. Also, 128 bit numbers are just very big. :)
pbsd 5y ago
Strictly speaking, shift and xor alone will not net you a secure cipher, seeing that those are both linear GF(2) operations. You would need something else in the mix to generate some nonlinearity, like integer addition, multiplication, etc. But on the subject of extremely simple constructions, you can compose many random permutations of a particular form---state[i] = state[i] xor F(state[j], state[k]), where state[i] is the ith bit of the state and F is a randomly chosen boolean function--- and obtain something asymptotically secure [1]. [1] https://arxiv.org/abs/math/0411098 https://arxiv.org/abs/math/0411098
- a1369209993 5y ago
  > You would need something else in the mix to generate some nonlinearity, like integer addition, multiplication, etc. Worth noting that bitwise AND also works (indeed, you can build addition from it), if you don't want to implement anything that operates on bits in non-parallel for some reason. (Which is to say/emphasize that it's linear GF(2) operations that are insufficient, not GF(2) operations in general.)
  - pbsd 5y ago
    Yeah that is true. Also you could still stick with xor and shift/rotate, but make the shifts data-dependent. That would make it nonlinear (technically a multiplication), but analysis is generally more difficult.
    - a1369209993 5y ago
      > but make the shifts data-dependent Ah, yes; cryptography usually assumes only fixed-amount shifts since some early shifters were non-contant-time, but variable-amount shifts are a thing you can do (and don't necessarily have side-channel problems on modern hardware).