SipHash for Lua 5.1.5 patch

[lua@...]

The attached patch makes SipHash the string has compression algorithm 
for Lua 5.1.5 [1].  While there have been other patches for Lua 5.1 to 
fix the hash collision security issues, this patch has the advantage of 
being fairly simple and using strong cryptography which did not exist 
for hash compression algorithms at the time.

SipHash.h uses a fixed key in the patch, which should probably be 
changed.  There are various ways to change the key, such as running this 
Lua script in the lua-5.1.5/src/ directory before compiling Lua 5.1.5:

----------------------------------------------------------------------------
#!/usr/bin/env lua
io.input("/dev/urandom")
print "#include <stdint.h>"
for i = 1,2 do
  s = "uint64_t sipKey" .. i .. " = 0x"
  for k = 1,8 do
    c = io.read(1)
    s = s .. string.format("%02x",string.byte(c,1,1))
  end
  s = s .. "ULL;"
  print(s)
end
----------------------------------------------------------------------------

Anyway, my next project is to make a Lua 5.4 version of this patch.

-- Sam

[1] There is a lot of great stuff in Lua 5.4, but there is a lot to be 
said about Lua 5.1, including LuaJIT, luau (Roblox), GopherLua, and 
LUA_GLOBALSINDEX (Yes, _ENV is great, but LUA_GLOBALSINDEX can be pretty 
convenient).  Mainly LuaJIT, so I can tell MaraDNS users we can move 
over to LuaJIT if Lua performance ever becomes a bottleneck.
--- lua-5.1.5/src/SipHash.h.orig        2020-08-08 10:57:10.219800000 -0700
+++ lua-5.1.5/src/SipHash.h     2020-08-08 10:56:50.914817800 -0700
@@ -0,0 +1,3 @@
+#include <stdint.h>
+uint64_t sipKey1 = 0xded6cbc72f7eeb4fULL;
+uint64_t sipKey2 = 0x81875fe84b1705d7ULL;
--- lua-5.1.5/src/lstring.c.orig	2020-08-08 10:46:42.114111000 -0700
+++ lua-5.1.5/src/lstring.c	2020-08-08 11:01:34.880104700 -0700
@@ -16,6 +16,7 @@
 #include "lobject.h"
 #include "lstate.h"
 #include "lstring.h"
+#include "SipHash.h"
 
 
 
@@ -71,14 +72,67 @@
   return ts;
 }
 
+uint64_t SipHash(const char *str, size_t l) {
+  uint64_t v0, v1, v2, v3, m;
+  int shift = 0, round = 0;
+  size_t offset = 0;
+
+  // We calculate the hash via SipHash, for security reasons
+  v0 = sipKey1 ^ 0x736f6d6570736575ULL;
+  v1 = sipKey2 ^ 0x646f72616e646f6dULL;
+  v2 = sipKey1 ^ 0x6c7967656e657261ULL;
+  v3 = sipKey2 ^ 0x7465646279746573ULL;
+  m = 0;
+  while(offset <= l) {
+    if(offset < l) {
+      m |= (uint64_t)(str[offset] & 0xff) << shift;  
+      shift += 8;
+    }
+    while(shift >= 64 || offset == l) { // "while" to avoid goto
+      if(offset == l && shift != 64) {
+        m |= (uint64_t)(l & 0xff) << 56;
+        offset++;
+      }
+      shift = 0;
+      v3 ^= m;
+      for(round = 0; round < 2; round++) {
+        v0 += v1; v2 += v3;
+        v1 = (v1 << 13) | (v1 >> 51);
+        v3 = (v3 << 16) | (v3 >> 48);
+        v1 ^= v0; v3 ^= v2;
+        v0 = (v0 << 32) | (v0 >> 32);
+        v2 += v1; v0 += v3;
+        v1 = (v1 << 17) | (v1 >> 47);
+        v3 = (v3 << 21) | (v3 >> 43);
+        v1 ^= v2; v3 ^= v0;
+        v2 = (v2 << 32) | (v2 >> 32);
+      }
+      v0 ^= m;
+      shift = 0;
+      m = 0;
+    }
+    offset++;
+  }   
+  v2 ^= 255;
+  for(round = 0; round < 4; round++) {
+    v0 += v1; v2 += v3;
+    v1 = (v1 << 13) | (v1 >> 51);
+    v3 = (v3 << 16) | (v3 >> 48);
+    v1 ^= v0; v3 ^= v2;
+    v0 = (v0 << 32) | (v0 >> 32);
+    v2 += v1; v0 += v3;
+    v1 = (v1 << 17) | (v1 >> 47);
+    v3 = (v3 << 21) | (v3 >> 43);
+    v1 ^= v2; v3 ^= v0;
+    v2 = (v2 << 32) | (v2 >> 32);
+  }
+  return v0 ^ v1 ^ v2 ^ v3;
+} 
 
 TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
   GCObject *o;
-  unsigned int h = cast(unsigned int, l);  /* seed */
-  size_t step = (l>>5)+1;  /* if string is too long, don't hash all its chars */
-  size_t l1;
-  for (l1=l; l1>=step; l1-=step)  /* compute hash */
-    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
+  unsigned int h; /* seed */
+  h = (unsigned int)SipHash(str,l);
   for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
        o != NULL;
        o = o->gch.next) {