3 ms·

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 h

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).

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).