4 ms·

is it unusual to use "bitwise and" inside the feistel function? i thought that normally xor or modular addition or shifts or permutations (nx1 s-boxes) were us

is it unusual to use "bitwise and" inside the feistel function? i thought that normally xor or modular addition or shifts or permutations (nx1 s-boxes) were used, which keep all the information (in some sense). "bitwise and" isn't like that (i don't have the right word for this distinction, sorry. maybe "invertible" is the word?) but is used here. anyone know why? or is this a distinction i've invented that has no basis in fact? obviously it doesn't matter (decryption still works) as long as it's inside the feistel function itself. so i guess maybe i am just muddling that with how things must be outside that?

tptacek 13y ago
Rogaway's SEAL also used AND. Apropos nothing (because I noticed this when looking for another cipher with AND in its round function): to appreciate how simple the design of SIMON (or SPECK) is, read the first (or second) half of the NSA paper... then read the Kelsey and Schneier's Twofish paper.
pbsd 13y ago
There are 2 separate aspects here: AND (the instruction itself) and invertibility. Indirectly, every decent round function ever created has had AND. At the bit level, you can't have a nonlinear function without AND. The carry bit in additions, for example, is given by a_i&b_i ^ a_i&cin ^ b_i&cin. Using AND directly, though, is pretty rare though not unheard of, since as CPU instructions go AND is doing relatively little work compared to more powerful instructions such as ADD, SUB, MUL, or table lookups. You see AND, though not bitwise, a lot more in hardware-friendly designs that employ NLFSRs as primitives. As for invertibility, in Feistel ciphers it is not really a requirement, as you point out, f only really needs to be a PRF. That being said, I have heard the argument that making f invertible does preserve information before; I do not know where this argument comes from, and as far as I know it's not formalized anywhere. DES and Blowfish are Feistel ciphers without invertible f, and don't have that bad of a security record.
- andrewcooke 13y ago
  i was just thinking about this in the shower and came up with this handwaving justification: if you have two random values, using AND biases the number of set bits on average (you get 3/4 zeroes in the output). in other words, it lowers the (shannon) entropy in the circuit, on average, while an invertible function preserves entropy (it has to, right?). entropy sounds like a smart thing to preserve in a PRF so this would seem like an argument for invertibility. BUT it's only preserving entropy on average, and what you really care about is the entropy in the difference between input and ouptut in any single round. which is not the same thing at all (identity function is great for the former, not so good for the latter). so you could imagine there's some trade-off... forgive me if this makes no sense. it just seemed interesting when i thought of it :o)

tptacek 13y ago

Rogaway's SEAL also used AND. Apropos nothing (because I noticed this when looking for another cipher with AND in its round function): to appreciate how simple the design of SIMON (or SPECK) is, read the first (or second) half of the NSA paper... then read the Kelsey and Schneier's Twofish paper.

pbsd 13y ago

There are 2 separate aspects here: AND (the instruction itself) and invertibility. Indirectly, every decent round function ever created has had AND. At the bit level, you can't have a nonlinear function without AND. The carry bit in additions, for example, is given by a_i&b_i ^ a_i&cin ^ b_i&cin. Using AND directly, though, is pretty rare though not unheard of, since as CPU instructions go AND is doing relatively little work compared to more powerful instructions such as ADD, SUB, MUL, or table lookups. You see AND, though not bitwise, a lot more in hardware-friendly designs that employ NLFSRs as primitives. As for invertibility, in Feistel ciphers it is not really a requirement, as you point out, f only really needs to be a PRF. That being said, I have heard the argument that making f invertible does preserve information before; I do not know where this argument comes from, and as far as I know it's not formalized anywhere. DES and Blowfish are Feistel ciphers without invertible f, and don't have that bad of a security record.

andrewcooke 13y ago
i was just thinking about this in the shower and came up with this handwaving justification: if you have two random values, using AND biases the number of set bits on average (you get 3/4 zeroes in the output). in other words, it lowers the (shannon) entropy in the circuit, on average, while an invertible function preserves entropy (it has to, right?). entropy sounds like a smart thing to preserve in a PRF so this would seem like an argument for invertibility. BUT it's only preserving entropy on average, and what you really care about is the entropy in the difference between input and ouptut in any single round. which is not the same thing at all (identity function is great for the former, not so good for the latter). so you could imagine there's some trade-off... forgive me if this makes no sense. it just seemed interesting when i thought of it :o)