Hi!
This problem is just for fun.
Below is a Lua 5.4 program that defines function censor()
This function receives a single argument (a number) and raises an exception if the argument does not fit in 2 bytes.
You are allowed to provide your own compressor and decompressor to convince the censor that argument fits in 2 bytes after compression.
So, the censor is executing three steps:
1) It compresses the argument by invoking your compressor
2) It checks the size of compressed data (and raises an error if it is too big)
3) It invokes your decompressor to make sure that compression is reversible (and raises an error if it is not).
Your task is to inspect the censor's implementation (see the code below), find its weaknesses and write your own compressor and decompressor to deceive the censor as much as you can.
As a result, the censor must successfully accept some numbers whose size is beyond the limit.
The censor does not trust your code, so compressor and decompressor are invoked in isolated sandboxes to make any communication between them impossible.
Overwise, if they both have access to the same global variable, the decompressor may read the uncompressed data from this variable (saved there by compressor) instead of actually decompressing it.
Some other side channels which can be abused for passing a few bits of data (measuring time, measuring allocated memory size, predictable PRNG values) are also disabled by sandboxing.
local function deep_copy(t, redefined, copy)
copy = copy or {}
for k, v in pairs(t) do
copy[k] = redefined[k] or type(v) == "table" and deep_copy(v, redefined) or v
end
return copy
end
local function create_isolated_env()
local function ni() error("This function is not implemented inside the sandbox", 2) end
local env = {}
local redefined = {
-- the following globals are changed to disable escaping the sandbox
_G = env, debug = {},
-- the following globals are prohibited to disable access files and modules
io = {}, dofile = ni, loadfile = ni, require = ni, package = {},
-- collectgarbage() is prohibited to disable measuring the memory allocated
collectgarbage = ni,
-- os is prohibited to disable measuring the time
os = {},
-- math.randomseed() is prohibited because it returns the same value as os.time()
randomseed = ni,
-- math.random() is prohibited to disable exploiting the predictability of PRNG
random = ni,
-- getmetatable() is prohibited to disable access to the strings metatable (a shared table for all sandboxes)
getmetatable = ni,
-- load() is prohibited to disable VM hacking by running maliciously crafted bytecode
load = ni,
}
return deep_copy(_G, redefined, env)
end
local function is_integer_from_range(value, min_value, max_value)
return
type(value) == "number"
and math.floor(value) == value
and value >= min_value
and value <= max_value
end
local function is_compressed_data_small_enough(data, max_bytes)
-- compressed data may be a number, a string or a byte array
-- a number
if is_integer_from_range(data, 0, 256^max_bytes - 1) then
return true
end
-- a string
if type(data) == "string" then
return #data <= max_bytes
end
-- a byte array
if type(data) == "table" and getmetatable(data) == nil then
for k, v in pairs(data) do
if not is_integer_from_range(k, 1, max_bytes)
or not is_integer_from_range(v, 0, 255) then
return false
end
end
return true
end
-- all other Lua datatypes are rejected
return false
end
local max_size_in_bytes = 2
local function censor(x)
-- compress the argument
local y = loadfile("compressor.lua", "t", create_isolated_env())(x)
-- check the size of compressed data
assert(is_compressed_data_small_enough(y, max_size_in_bytes))
-- decompress to make sure compression was reversible
assert(x == loadfile("decompressor.lua", "t", create_isolated_env())(y))
end
How many different integer numbers can be successfully accepted by the censor?
Your task is to write compressor.lua and decompressor.lua to maximize the range of acceptable integers.
In other words, the following loop must run without raising an exception:
local N = .... -- insert your value for N here
for i = 1, N do
censor(i) -- must not raise an exception
end
The obvious solution is:
N = 65536
compressor.lua
return (...)-1
decompressor.lua
return (...)+1
What value of N can you reach with your own compressor and decompressor?
