lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


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
   return copy

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)

local function is_integer_from_range(value, min_value, max_value)
      type(value) == "number"
      and math.floor(value) == value
      and value >= min_value
      and value <= max_value

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
   -- a string
   if type(data) == "string" then
      return #data <= max_bytes
   -- 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
      return true
   -- all other Lua datatypes are rejected
   return false

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

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

The obvious solution is:
   N = 65536
      return (...)-1
      return (...)+1

What value of N can you reach with your own compressor and decompressor?