[CC-1.47] SHA-1 in Pure Lua adapted to use the native bit API

Hello there, I adapted this implementation of SHA-1 to computercraft, code is here: http://pastebin.com/LvUWBWHS
Tested with some test vectors found around the web, including from Wikipedia.

This involved some difficult to resolve bugs, so let me state them:
-bit.brshift shifts bytes in a strange way; don't know if it ignores a sign bit, or fills in with strange bits instead of zeros, but bit.blogic_rshift seems to work fine;
EDIT: here's a clear explanation by Gopher:

coolis: brshift isn't strange, brshift is the signed version, blogic_rshift is the unsigned version. Signed right-shift copies fills with the sign bit instead of 0, so that for example -2>>1 == -1,

-some additons inside had to be modulo 2^32, and they weren't, so I fixed that.

Thank you much! I will be using this in my os for passwords!

Cool bro. Well… your name is "Cool".

Great job! I've been using one that I found online here –> http://regex.info/code/sha1.lua (Made by Jeffrey Friedl)
It's far longer, but it does include the ability to use a custom key. In case anyone's interested in trying it out, I'll link to the programs I use to test it out.

hash –> http://pastebin.com/SqGfsU95 –creates a hash from a key and text
crack –> http://pastebin.com/TVhA9zq2 –attempts to crack the hash with a brute force dictionary attack
english-words –> http://www.mediafire.com/?y9gio9yhcbbebys –list of 500 000 english words, required for brute force dictionary attack. Uses Canadian words, as I'm in Canada.

Unfortunately, the guy who made this code doesn't seem to like lua, and the code seems rather messy, at least to me. I wouldn't even know where to start trying to program an encryption algorithm, so maybe this code is really efficient afterall. The point is to show how difficult it is to crack SHA-1, even when you know the key. The 'crack' program will find the hashed phrase eventually, but only if it is passed the correct key, and the phrase happens to be a single word in the dictionary. It can easily be foiled by not using a dictionary word, or keeping the key a secret.

I don't know how difficult it is to do, but if you can, could you try to find a way to add the ability to encrypt with a custom key. I started this post simply to ask that, then figured I'd link to an example to help you out if you're interested, then figured I'd upload my programs to help test it out. Anyway, I hope you learn something, and maybe someday I'll try to figure out how all this works :P/>

Yeah, I found it too, but since it defined it's own bit-ops…; anyway, maybe setting a key will be useful for someone. Thanks!

I've found that using sha1 for pure hashing doesn't particularly require any key, which seems to be the most common usage.
A key is required for using HMAC message digests, but that appears to be much less common, and I've personally never used it either.

I've been spending an abnormal about of time thinking about this lately while porting over my cryptd server to test it out with computercraft.
(I keep running around in circles if it's even going to be worth it to release or not)
But excluding sha1 hmac is one design descision I settled on as well.

Cruor, on 17 December 2012 - 08:19 AM said:

snip

'Cause I memorize powers of 2 in my spare time…NOT! Lol, I didn't wrote the original code (a I say in the main post), I just fixed it and adapted it for CC.
Guess you'll have to ask the original author!

Cruor, on 17 December 2012 - 08:19 AM said:

Looking at one of these lines:
band((h0+a)%2^32, 4294967295)
why did you actually type 4294967295 instead of just 2^32 - 1? :P/>

Speed. Much much faster to use literals when and if possible. especially in loops.

I do see your point in that it is not consistant however.

dissy, on 17 December 2012 - 08:26 AM said:

Cruor, on 17 December 2012 - 08:19 AM said:

Looking at one of these lines:
band((h0+a)%2^32, 4294967295)
why did you actually type 4294967295 instead of just 2^32 - 1? :P/>

Speed. Much much faster to use literals when and if possible.

THEEEEN, why does it say 2^32 and not 4294967296? ;P

Like i said… I see your point that it is not consistant

dissy, on 17 December 2012 - 08:26 AM said:

Cruor, on 17 December 2012 - 08:19 AM said:

Looking at one of these lines:
band((h0+a)%2^32, 4294967295)
why did you actually type 4294967295 instead of just 2^32 - 1? :P/>

Speed. Much much faster to use literals when and if possible. especially in loops.

I do see your point in that it is not consistant however.

Cruor, on 17 December 2012 - 08:27 AM said:

dissy, on 17 December 2012 - 08:26 AM said:

Cruor, on 17 December 2012 - 08:19 AM said:

Looking at one of these lines:
band((h0+a)%2^32, 4294967295)
why did you actually type 4294967295 instead of just 2^32 - 1? :P/>

Speed. Much much faster to use literals when and if possible.

THEEEEN, why does it say 2^32 and not 4294967296? ;P

Well, I didn't know that it would speed up; I thought that 2^32 was interpreted as a constant. If that's not the case (e.g. no one replies about it for 1 hour or so), I'll change it. Fact is I wrote the 2^32, and the original author the 'full' numbers.
EDIT: just checked efficiency, 28(fucntion returns/s)*2864(string length) characters per second, on average.

TBH I'm not sure how Lua does multiple-pass interpreting (if at all)

I use literals in TCL because I know this is not the case, and it does speed it up noticably.
I do the same in C "just in case" because it depends on the compiler. Modern compilers take care of that for you so it doesn't help (nor does it hurt), but for some older compilers it does speed things up.

Is there a command in Lua to time how long a function executes in cpu time, or a profiler? If so we can check and see

dissy, on 17 December 2012 - 08:40 AM said:

snip

I've got a benchmarking module! (stole from somewhere ;)/>) Just a second.
EDIT: apparently, using os.clock (which is what is important to us), there's no difference. Here's the important part of the benchmarking module that shows what it was doing:

function M.Bench(name,func,loops,...)
loops=loops or 100
local q0=os.clock()
for i=1,loops do
  if i%10000==0 then
   sleep(0)
  end
  func(...)
end
local q1=os.clock()
local result=bench_results[name] or {count=0,diff=0}
local diff=(q1-q0)
result.count=result.count+loops
result.diff=result.diff+diff
total_diff=total_diff+diff
bench_results[name]=result
end

And the actual functions used:

a=function()
b=2^32
end
local d
c=function()
d=4294967295
end
bench.BenchTable({incalc=a,precalc=c},1000000)
bench.Results()

woot! Well that's awesome news. Looks like Lua does interpret 2^32 as a constant after all.
Since it doesn't matter for speed, might as well go for readability and keep it.

BTW that is a very handle module, might stash that away for later myself.
The only other profiler I came across in Google looks like a module with the full blown interpreter, which I just now apt-get installed.
Will be tricky working around CC specific APIs, but for things like this should be quite handy in the future.

Thanks!

dissy, on 17 December 2012 - 09:04 AM said:

snip

I just created a github repository named utils where you can find the module. Click below!
It's written for being loaded as a function and returning the API table, so adapt it to your needs.