3 ms·

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

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

by pbsd 13y ago

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)