Re: [ANN] Lua 5.3.0 (work2) now available

[Joseph Wallace <tangent128@...>]

On 03/26/2014 02:21 AM, Luiz Henrique de Figueiredo wrote:
>> I spent all of yesterday translating 32-bit ISAAC to Lua
> Another good exercise would be the cryptographic hash functions,
> such as MD5 or SHA2 from this for C code instance
> 	http://www.opensource.apple.com/source/OpenSSL098/OpenSSL098-35/src/crypto/sha/sha512.c
> 	http://www.saphir2.com/sphlib/
> 	https://polarssl.org
>
> FWIW, the referenc doc on SHA <http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf> defines the bitwise operations and says this in section 2.2.2::
>
> 	>> Right-shift operation, where x >> n is obtained by discarding the right- most n bits of the word x and then padding the result with n zeroes on the left.

Two years ago I wrote an implementation of the Keccak hash (some variant
of which is to become SHA-3) in Lua 5.2 using the bit32 library for a
class project; this evening I ported it to 5.3.

Keccak happens to operate on 64-bit words, which 5.3 happily
accomodates. The original 5.2 keccak implementation represented words as
a {high, low} table and defined some "bit64" functions to deal with
them; tearing those out* made the code cleaner and improved speed ~300%.

[*] I had to retain a left-rotate function since there aren't any rotation operators, but it was drastically simpler than before.

-- Lua 5.3 implementation of Keccak
-- SHA-3 will be a version of Keccak, though the exact parameters are TBD

-- import globals for use in module
local setmetatable	= setmetatable
local char	= string.char
local concat	= table.concat

-- for debug usage
local print	= print
local io	= io

local _ENV = {}

-- helper function to do 64-bit left rotate
local function lrotate64(value, displace)
	displace = displace % 64
	local rightDisplace = 64 - displace
	return value << displace | value >> rightDisplace
end

-- the Keccak constants and functionality

local ROUNDS = 24

local roundConstants = {
0x0000000000000001,
0x0000000000008082,
0x800000000000808A,
0x8000000080008000,
0x000000000000808B,
0x0000000080000001,
0x8000000080008081,
0x8000000000008009,
0x000000000000008A,
0x0000000000000088,
0x0000000080008009,
0x000000008000000A,
0x000000008000808B,
0x800000000000008B,
0x8000000000008089,
0x8000000000008003,
0x8000000000008002,
0x8000000000000080,
0x000000000000800A,
0x800000008000000A,
0x8000000080008081,
0x8000000000008080,
0x0000000080000001,
0x8000000080008008
}

local rotationOffsets = {
-- ordered for [x][y] dereferencing, so appear flipped here:
{0, 36, 3, 41, 18},
{1, 44, 10, 45, 2},
{62, 6, 43, 15, 61},
{28, 55, 25, 21, 56},
{27, 20, 39, 8, 14}
}

-- metatable for a Keccak state
State = {}
State.__index = State


function State.new(rate)
	
	if rate == nil then rate = 1024 end
	
	local newState = {}
	
	newState.rate = rate
	
	for x = 1,5 do
		
		newState[x] = {}
		
		for y = 1,5 do
			newState[x][y] = 0
		end
	end
	
	return setmetatable(newState, State)
	
end

function State:Absorb(buffer)
	
	local blockBytes = self.rate / 8
	local blockWords = blockBytes / 8
	
	-- append 0x01 byte and pad with zeros to block size (rate/8 bytes)
	
	buffer = buffer .. char(0x01)
	local totalBytes = #buffer
	buffer = buffer .. char(0):rep(blockBytes - (totalBytes % blockBytes))
	totalBytes = #buffer
	
	-- convert into table of little-endian numbers
	local words = {}
	
	--convert blocks of 64 bits, 8 bytes at a time
	for i = 1, totalBytes - (totalBytes % 8), 8 do
		
		local c1,c2,c3,c4,c5,c6,c7,c8 = buffer:byte(i,i+7)
		
		local word
			= c8 * 0x0100000000000000
			+ c7 * 0x01000000000000
			+ c6 * 0x010000000000
			+ c5 * 0x0100000000
			+ c4 * 0x01000000
			+ c3 * 0x010000
			+ c2 * 0x0100
			+ c1 * 0x01
		
		--words[(i-1)/8 + 1] = word
		words[#words + 1] = word
		
	end
	
	
	local totalWords = #words
	
	-- OR final word with 0x80000000 to set last bit of state to 1
	
	words[totalWords] = words[totalWords] | 0x8000000000000000
	
	local function to64(high, lo)
		return (high << 32) | lo
	end
	
	-- XOR blocks into state
	for startBlock = 1, totalWords, blockWords do
		
		local offset = 0
		
		for y = 1, 5 do
			for x = 1, 5 do
				
				if offset < blockWords then
					local index = startBlock+offset
					--self[x][y] = self[x][y] ~ to64(words[loWordIndex+1], words[loWordIndex])
					self[x][y] = self[x][y] ~ words[index]
					offset = offset + 1
				end
			end
		end
		
		--self:debug()
		self:keccakF()
	end
end

-- returns [rate] bits from the state, without permuting afterward.
-- Only for use when the state will immediately be thrown away,
-- and not used for more output later

local function extractByte(word, bitOffset)
	return (word >> bitOffset) & 0xFF
end

function State:CheapSqueeze()
	
	local blockBytes = self.rate / 8
	local blockWords = blockBytes / 4
	
	-- fetch blocks out of state
	
	local words = {}
	local offset = 1
	
	for y = 1, 5 do
		for x = 1, 5 do
			
			if offset < blockWords then
				words[offset] = self[x][y]
				offset = offset + 1
			end
		end
	end
	
	--translate to string
	local chars = {}
	
	for i = 1, #words do
		local word = words[i]
		
		chars[i] = char(
			extractByte(word,0),
			extractByte(word,8),
			extractByte(word,16),
			extractByte(word,24),
			extractByte(word,32),
			extractByte(word,40),
			extractByte(word,48),
			extractByte(word,56)
		)
	end
	
	return concat(chars)
	
end

function State:Squeeze()
	
	local string = self:CheapSqueeze()
	
	self:keccakF()
	
	return string
	
end

function State:debug(note)
	
	if note then
		io.write(note .. ":\n")
	end
	
	local fmt = " %016X"
	
	for y = 1, 5 do
		for x = 1, 5 do
			io.write(fmt:format(self[x][y]))
		end
		io.write("\n")
	end
	
end


-- the full permutation function
function State:keccakF()
	--local ROUNDS = 3
	for round = 1, ROUNDS do
		
		--self:debug("round " .. round)
		
		self:Theta()
		
		--self:debug "post-theta"
		
		local b = self:RhoPi()
		
		--self.debug(b, "post-pi")
		
		self:Chi(b)
		
		--self:debug "post-chi"
		
		self:Iota(round)
		
		--self:debug "post-iota"
	end
end

-- substeps:

function State:Theta()
	
	local parities = {}
	
	for x = 1,5 do
		parities[x] = 0
		
		for y = 1,5 do
			parities[x] = parities[x] ~ self[x][y]
		end
	end
	
	for x = 0,4 do
		local flip = parities[(x-1)%5 + 1] ~ lrotate64(parities[(x+1)%5 + 1], 1)
		
		for y = 1,5 do
			self[x+1][y] = self[x+1][y] ~ flip
		end
	end
	
	
	
end

function State:RhoPi()
	local permuted = {}
	
	for y = 0,4 do
		permuted[y+1] = {}
		
		for x = 0,4 do
			permuted[y+1][(2*x + 3*y)%5 + 1] = lrotate64(self[x+1][y+1], rotationOffsets[x+1][y+1])
		end
	end
	
	return permuted
end

function State:Chi(permuted)
	
	for x = 0,4 do
		for y = 0,4 do
			local combined = (~ permuted[(x+1)%5 +1][y+1]) & permuted[(x+2)%5 +1][y+1]
			self[x+1][y+1] = permuted[x+1][y+1] ~ combined
		end
	end
end

function State:Iota(round)
	self[1][1] = self[1][1] ~ roundConstants[round]
end

-- primitive functions (assume rate is a whole multiple of 64 and length is a whole multiple of 8)

local function keccakHash(rate, length, data)
	
	local state = State.new(rate)
	
	state:Absorb(data)
	
	return state:CheapSqueeze():sub(1,length/8)
	
end

local function byte2hex(byte)
	return ("%02X"):format(byte:byte())
end

local function keccakHashHex(rate, length, data)
	return (keccakHash(rate, length, data):gsub(".", byte2hex))
end

-- SHA-3 profiles:

-- outputting hex strings:

function keccak224(data)
	return keccakHashHex(1152, 224, data)
end

function keccak256(data)
	return keccakHashHex(1088, 256, data)
end

function keccak384(data)
	return keccakHashHex(832, 384, data)
end

function keccak512(data)
	return keccakHashHex(576, 512, data)
end

-- output raw bytestrings

function keccak224Bin(data)
	return keccakHash(1152, 224, data)
end

function keccak256Bin(data)
	return keccakHash(1088, 256, data)
end

function keccak384Bin(data)
	return keccakHash(832, 384, data)
end

function keccak512Bin(data)
	return keccakHash(576, 512, data)
end

--return module

return _ENV