Problem with feistel network

[Maelstorm_1973]

I have a good one for you guys. I’m trying to code a feistel network and it’s giving me some problems. Mainly, the issue is that whatever I encode, I don’t get back when I reverse it. I don’t see any problems with the code, so I’m wondering if the problem is with my implementation. A feistel network is used to turn an irreversible logic operation (and, or, nand, nor, etc…) into a reversible operation. It’s used extensively in cryptography for block ciphers. The most well known block cipher that uses this is DES.

local function feistelNetwork(data, key)
	
	-- Splits a 32bit data word into two 16bit parts.	
	local function splitData(data)
		local lo = bit32.band(data, 0x0000FFFF)
		local hi = bit32.band(bit32.rshift(data, 16), 0x0000FFFF)
		return lo, hi
	end
	
	-- Combines two 16bit parts into a single 32bit data word.
	local function combineData(lo, hi)
		return bit32.bor(bit32.band(bit32.lshift(hi, 16), 0xFFFF0000), bit32.band(lo, 0x0000FFFF))
	end
	
	-- Performs an AND operation using a feistel network.
	local function feistelANDf(data, key)
		local l1, r1 = splitData(data)
		local k1, k2 = splitData(key)
		
		local r2 = bit32.bxor(bit32.band(r1, k1), l1)
		local l2 = r1
		
		local r3 = bit32.bxor(bit32.band(r2, k2), l2)
		local l3 = r2
		
		print(string.format("0x%08X 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X", l1, r1, l2, r2, l3, r3))
		return combineData(l3, r3)
	end
	
	-- Performs an AND operation using a feistel network.
	local function feistelANDr(data, key)
		local l1, r1 = splitData(data)
		local k1, k2 = splitData(key)

		local r2 = bit32.bxor(bit32.band(r1, k2), l1)
		local l2 = r1

		local r3 = bit32.bxor(bit32.band(r2, k1), l2)
		local l3 = r2

		print(string.format("0x%08X 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X", l1, r1, l2, r2, l3, r3))
		return combineData(l3, r3)
	end


	-- Testing
	local rx = feistelANDf(data, key)
	local ry = feistelANDr(rx, key)
	print(string.format("0x%08X 0x%08X", rx, ry))
	if data ~= ry then
		print("Failed")
	else
		print("Success")
	end
end

feistelNetwork(0x7B04829A, 0xC299BA74)

This is the result:

0x0000829A 0x00007B04 0x00007B04 0x0000B89E 0x0000B89E 0x0000FB9C
0x0000B89E 0x0000FB9C 0x0000FB9C 0x00007A06 0x00007A06 0x0000C198
0xFB9CB89E 0xC1987A06
Failed

It goes in with 0x7B04829A, but it comes out with 0xC1987A06. So I’m not sure if the problem is the encoding or decoding as I’m not sure what the expected encoded value is. The key in both cases is the same.

EDIT:

Well, I worked it out on paper and it does work. So I’m not sure what the problem with my code is.

[IDoLua (I CantBeBothered)]

Here’s the fixed code, let me explain:

local function feistelNetwork(data, key)
	
	-- snipped off stackoverflow: https://stackoverflow.com/questions/9079853/lua-print-integer-as-a-binary/9080080
	local function toBits(num,bits)
		-- returns a table of bits, most significant first.
		bits = bits or math.max(1, select(2, math.frexp(num)))
		local t = {} -- will contain the bits        
		for b = bits, 1, -1 do
			t[b] = math.fmod(num, 2)
			num = math.floor((num - t[b]) / 2)
		end
		return t
	end

	-- Splits a 32bit data word into two 16bit parts.	
	local function splitData(data)
		local lo = bit32.band(data, 0b1111111111111111) -- changed hex to bin for a 1:1 binary view
		local hi = bit32.band(bit32.rshift(data, 16), 0b1111111111111111) -- changed hex to bin for a 1:1 binary view
		return lo, hi
	end

	-- Combines two 16bit parts into a single 32bit data word.
	local function combineData(lo, hi)
		return bit32.bor(bit32.band(bit32.lshift(hi, 16), 0b11111111111111110000000000000000), bit32.band(lo, 0b1111111111111111))
	end

	-- Performs an AND operation using a feistel network.
	local function feistelANDf(data, key)
		local l1, r1 = splitData(data)
		local k1, k2 = splitData(key)
		
		local f1 = bit32.bxor(r1, k1)
		local r2 = bit32.bxor(f1, l1)
		local l2 = r1
		
		local f2 = bit32.bxor(r2, k2)
		local r3 = bit32.bxor(f2, l2)
		local l3 = r2

		warn(string.format("0x%08X 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X", l1, r1, l2, r2, l3, r3))
		return combineData(l3, r3)
	end

	-- Performs an AND operation using a feistel network.
	local function feistelANDr(data, key)
		local l1, r1 = splitData(data)
		local k1, k2 = splitData(key)

		local f1 = bit32.bxor(l1, k2)
		local l2 = bit32.bxor(r1, f1)
		local r2 = l1
		
		local f2 = bit32.bxor(l2, k1)
		local l3 = bit32.bxor(r2, f2)
		local r3 = l2

		warn(string.format("0x%08X 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X", l1, r1, l2, r2, l3, r3))
		return combineData(l3, r3)
	end


	-- Testing
	local rx = feistelANDf(data, key)
	local ry = feistelANDr(rx, key)
	print(string.format("Encoded: 0x%08X | Decoded: 0x%08X", rx, ry))
	local bits0=toBits(data)
	local bits1=toBits(key)
	local bits2=toBits(rx)
	local bits3=toBits(ry)
	print("Data", table.concat(bits0))
	print("Key ", table.concat(bits1))
	print("Enc ", table.concat(bits2))
	print("Dec ", table.concat(bits3))
	if data ~= ry then
		print("Failed")
	else
		print("Success")
	end
end

feistelNetwork(0x7B04829A, 0xC299BA74)

Your issue lies in the fact you were using the exact same process for both encode and decode. Fiestel ciphers don’t work that way, they almost do, but not quite

Assume A is the unmodified value below.
Assume K is the unmodified key below.

Encoding

---

1. Get L1 (bitwise low half of A), and R1 (bitwise high half of A)
2. Get K1 (bitwise low half of K), and K2 (bitwise high half of K)
3. Get F1 through XORing R1 by K1
4. Get R2 through XORing F1 by L1
5. Optional Set L2 to R1 for symmetry, otherwise L2 is substituted with R1
6. Get F2 through XORing R2 by K2
7. Get R3 through XORing F2 by L2/R1
8. Optional Set L3 to R2 for symmetry, otherwise L3 is substituted with R2
9. Finalization (equiv. B for decode) is bitwise OR with L3/R2 (left-shifted 16 bits) and with R3

Decoding

---

1. Get L1 (bitwise low half of B), and R1 (bitwise high half of B)
2. Get K1 (bitwise low half of K), and K2 (bitwise high half of K)
3. Get F1 through XORing L1 by K2
4. Get L2 through XORing R1 by F1
5. Optional Set R2 to L1 for symmetry, otherwise R2 is substituted with L1
6. Get F2 through XORing L2 by K1
7. Get L3 through XORing R2/L1 by F2
8. Optional Set R3 to L2 for symmetry, otherwise R3 is substituted with L2
9. Finalization is bitwise OR with L3 (left-shifted 16 bits) and with R3/L2

Not much of an explanation, but enjoy.

[Maelstorm_1973]

Thanks for the reply. I found the problem. The splitData function was returning lo, hi when it should have been hi, lo. It’s now working properly.