Hacker News Reader

Comment by daurnimator | Hacker News Reader

Lua string comparison IS constant time (its always just a pointer comparison).

The timing attack (i.e. memcmp) would happen at the string interning step; which cannot be avoided: but as a lua_State persists longer than a single request, I'm unsure if a timing attack here is plausible.

View on HN

I don't understand how you can compare two strings in constant time by doing a pointer comparison. Can you elaborate?

Does Lua do string interning? If it does then every string the same will be at the same memory location so you can do a simple address comparison.

edit: someone answered this in a sibling post with 'yes'.

reference: http://www.luafaq.org/gotchas.html#T9

Strings are interned in Lua which means identical strings have the same reference.

That's interesting... Would interning change the speed at which strings are generated, then?

Yes, strings are hashed at creation time.

This means strings can never be modified => a new one is created.

The down side is that string modification (including appending) in a loop is expensive.

Of course, languages like Java have StringBuffer objects. In Lua, if you are generating a string, and you know that it will need a lot of concatenations, you can use something like this:

    local string_buffer = {}
    while condition() do
      table.insert(string_buffer, getString())
    end
    local string = table.concat(string_buffer)

Maybe you could instantiate every string in a global radix tree?

Even then, how would you know which string the one you have is, unless you compare it?

Reply on news.ycombinator.com