←  APIs and Utilities

ComputerCraft | Programmable Computers for Minecraft

»

SHA-256 in Pure Lua

Anavrins's Photo Anavrins 19 Feb 2016

I ended up making my own take at implementing SHA256 in Lua and ended up being around 15x faster.
With some rough speed test I could only get up to 105 hash/sec, my implementation was able to get to 1500 hash/sec.
It's still not much compared to say, gpus, but it's quite something for CC.
I also noticed the same thing as Shazz, that any input that's (64*n)+55 bytes in length will produce the incorrect hash, I didn't go deep into the problem, but I know it's the pre-processing part that produces an incorrect padding.
That bug is not present in my implementation.
Here's the pastebin: 6UV4qfNF
Edited by Anavrins, 19 February 2016 - 09:44 PM.
Quote

Creator's Photo Creator 19 Feb 2016

 Anavrins, on 19 February 2016 - 09:41 PM, said:

I ended up making my own take at implementing SHA256 in Lua and ended up being around 15x faster.
With some rough speed test I could only get up to 105 hash/sec, my implementation was able to get to 1500 hash/sec.
It's still not much compared to say, gpus, but it's quite something for CC.
I also noticed the same thing as Shazz, that any input that's (64*n)+55 bytes in length will produce the incorrect hash, I didn't go deep into the problem, but I know it's the pre-processing part that produces an incorrect padding.
That bug is not present in my implementation.
Here's the pastebin: 6UV4qfNF

Nice. If what you say is true, I might use it in my Delta networking framework.
Quote

Anavrins's Photo Anavrins 19 Feb 2016

 Creator, on 19 February 2016 - 09:54 PM, said:

Nice. If what you say is true, I might use it in my Delta networking framework.
Here's what I used to test the speed Pvy0zFXt
Usage is "speedtest old" and "speedtest new"
Quote

Creator's Photo Creator 19 Feb 2016

 Anavrins, on 19 February 2016 - 10:25 PM, said:

 Creator, on 19 February 2016 - 09:54 PM, said:

Nice. If what you say is true, I might use it in my Delta networking framework.
Here's what I used to test the speed Pvy0zFXt
Usage is "speedtest old" and "speedtest new"

Added it to the framework.
Quote

sci4me's Photo sci4me 20 Feb 2016

I gotta say, a quick glance at the code, and, it looks great. I am curious to see if your bitop implementations are actually faster than the CC ones however.
Quote

Anavrins's Photo Anavrins 24 Feb 2016

 sci4me, on 20 February 2016 - 01:02 AM, said:

I gotta say, a quick glance at the code, and, it looks great. I am curious to see if your bitop implementations are actually faster than the CC ones however.
Well, whether it's faster or not, they were needed, rrotate is not in CC, and CC's rshift gave incorrect results with numbers near 2^32.

Also, replacing line 136 with local extra = -(len + 9)%64 will fix the padding error in OP's implementation.
Edited by Anavrins, 24 February 2016 - 03:06 AM.
Quote

Kronix's Photo Kronix 29 Feb 2016

How exactly does one go about comparing passwords?
Edited by Kronix, 29 February 2016 - 04:31 AM.
Quote

Dragon53535's Photo Dragon53535 29 Feb 2016

Hash the password and save it. Then when the user inputs their password hash that and compare against the already hashed version, if they're the same then they inputted the same password.
Quote

3d6's Photo 3d6 29 Feb 2016

 Anavrins, on 19 February 2016 - 09:41 PM, said:

I ended up making my own take at implementing SHA256 in Lua and ended up being around 15x faster. With some rough speed test I could only get up to 105 hash/sec, my implementation was able to get to 1500 hash/sec. It's still not much compared to say, gpus, but it's quite something for CC. I also noticed the same thing as Shazz, that any input that's (64*n)+55 bytes in length will produce the incorrect hash, I didn't go deep into the problem, but I know it's the pre-processing part that produces an incorrect padding. That bug is not present in my implementation. Here's the pastebin: 6UV4qfNF
I made it more compact!
local g=string.gsub sha256=loadstring(g(g(g(g(g(g(g(g('Sa=XbandSb=XbxWSc=XlshiftSd=unpackSe=2^32SYf(g,h)Si=g/2^hSj=i%1Ui-j+j*eVSYk(l,m)Sn=l/2^mUn-n%1VSo={0x6a09e667Tbb67ae85T3c6ef372Ta54ff53aT510e527fT9b05688cT1f83d9abT5be0cd19}Sp={0x428a2f98T71374491Tb5c0fbcfTe9b5dba5T3956c25bT59f111f1T923f82a4Tab1c5ed5Td807aa98T12835b01T243185beT550c7dc3T72be5d74T80deb1feT9bdc06a7Tc19bf174Te49b69c1Tefbe4786T0fc19dc6T240ca1ccT2de92c6fT4a7484aaT5cb0a9dcT76f988daT983e5152Ta831c66dTb00327c8Tbf597fc7Tc6e00bf3Td5a79147T06ca6351T14292967T27b70a85T2e1b2138T4d2c6dfcT53380d13T650a7354T766a0abbT81c2c92eT92722c85Ta2bfe8a1Ta81a664bTc24b8b70Tc76c51a3Td192e819Td6990624Tf40e3585T106aa070T19a4c116T1e376c08T2748774cT34b0bcb5T391c0cb3T4ed8aa4aT5b9cca4fT682e6ff3T748f82eeT78a5636fT84c87814T8cc70208T90befffaTa4506cebTbef9a3f7Tc67178f2}SYq(r,q)if e-1-r[1]<q then r[2]=r[2]+1;r[1]=q-(e-1-r[1])-1 else r[1]=r[1]+qVUrVSYs(t)Su=#t;t[#t+1]=0x80;while#t%64~=56Zt[#t+1]=0VSv=q({0,0},u*8)fWw=2,1,-1Zt[#t+1]=a(k(a(v[w]TFF000000),24)TFF)t[#t+1]=a(k(a(v[w]TFF0000),16)TFF)t[#t+1]=a(k(a(v[w]TFF00),8)TFF)t[#t+1]=a(v[w]TFF)VUtVSYx(y,w)Uc(y[w]W0,24)+c(y[w+1]W0,16)+c(y[w+2]W0,8)+(y[w+3]W0)VSYz(t,w,A)SB={}fWC=1,16ZB[C]=x(t,w+(C-1)*4)VfWC=17,64ZSD=B[C-15]SE=b(b(f(B[C-15],7),f(B[C-15],18)),k(B[C-15],3))SF=b(b(f(B[C-2],17),f(B[C-2],19)),k(B[C-2],10))B[C]=(B[C-16]+E+B[C-7]+F)%eVSG,h,H,I,J,j,K,L=d(A)fWC=1,64ZSM=b(b(f(J,6),f(J,11)),f(J,25))SN=b(a(J,j),a(Xbnot(J),K))SO=(L+M+N+p[C]+B[C])%eSP=b(b(f(G,2),f(G,13)),f(G,22))SQ=b(b(a(G,h),a(G,H)),a(h,H))SR=(P+Q)%e;L,K,j,J,I,H,h,G=K,j,J,(I+O)%e,H,h,G,(O+R)%eVA[1]=(A[1]+G)%e;A[2]=(A[2]+h)%e;A[3]=(A[3]+H)%e;A[4]=(A[4]+I)%e;A[5]=(A[5]+J)%e;A[6]=(A[6]+j)%e;A[7]=(A[7]+K)%e;A[8]=(A[8]+L)%eUAVUY(t)t=t W""t=type(t)=="string"and{t:byte(1,-1)}Wt;t=s(t)SA={d(o)}fWw=1,#t,64ZA=z(t,w,A)VU("%08x"):rep(8):format(d(A))V',"S"," local "),"T",",0x"),"U"," return "),"V"," end "),"W","or "),"X","bit32."),"Y","function "),"Z"," do "))()
Quote

Anavrins's Photo Anavrins 01 Mar 2016

 3d6, on 29 February 2016 - 09:58 PM, said:

I made it more compact!
Sweet :D, can I ask you what you used to compact it?
Quote

3d6's Photo 3d6 01 Mar 2016

 Anavrins, on 01 March 2016 - 02:33 AM, said:

 3d6, on 29 February 2016 - 09:58 PM, said:

I made it more compact!
Sweet :D, can I ask you what you used to compact it?
Notepad++

It costs 10+n bytes to add a gsub rule, which saves (n-1)*c-(10+n) bytes, where n is the length of the string and c is the number of them present. There are a few more optimizations/gsub rules that could be set, but detecting them would require rigorous calculations and I don't think anyone has made a program like that. Not to mention that we will soon run out of characters to replace things with, and have to settle with two-character replacements, ensuring that there are no accidents along the way.
Quote

LoganDark's Photo LoganDark 07 Mar 2016

I'd be interested if you could implement bcrypt in Lua.
Quote

Anavrins's Photo Anavrins 07 Mar 2016

 LoganDark, on 07 March 2016 - 08:58 PM, said:

I'd be interested if you could implement bcrypt in Lua.
I've been actually looking into implementing Blowfish and bcrypt in CC a few days ago, but note that that algorithm is designed to be slow and having it in CC will make it even slower.
Quote

Creator's Photo Creator 07 Mar 2016

Anavrins, I am using implementation of the SHA256 algorithm, and am very happy with it. Can I distribute software on the CC forums that uses it?
Quote

Anavrins's Photo Anavrins 07 Mar 2016

 Creator, on 07 March 2016 - 09:50 PM, said:

Anavrins, I am using implementation of the SHA256 algorithm, and am very happy with it. Can I distribute software on the CC forums that uses it?
Sure go ahead :)
Edited by Anavrins, 07 March 2016 - 09:55 PM.
Quote

LoganDark's Photo LoganDark 07 Mar 2016

 Anavrins, on 07 March 2016 - 09:16 PM, said:

 LoganDark, on 07 March 2016 - 08:58 PM, said:

I'd be interested if you could implement bcrypt in Lua.
I've been actually looking into implementing Blowfish and bcrypt in CC a few days ago, but note that that algorithm is designed to be slow and having it in CC will make it even slower.
Wouldn't that be perfect for password systems? It would take quite a bit longer to brute-force it.
Quote

Anavrins's Photo Anavrins 07 Mar 2016

 LoganDark, on 07 March 2016 - 11:09 PM, said:

Wouldn't that be perfect for password systems? It would take quite a bit longer to brute-force it.
You have to assume that if someone wants to crack a password that was found in a CC program, he will certainly not crack it from within CC.
Cracking outside of CC will always be faster, so might as well make them as fast as possible for convenient in-game use.
BCrypt has an argument that determine the cost factor, it won't be much before a cost factor get's too costly for CC to be any more useful against offline cracking, compared to SHA2 alone.
Edited by Anavrins, 07 March 2016 - 11:22 PM.
Quote

LoganDark's Photo LoganDark 07 Mar 2016

 Anavrins, on 07 March 2016 - 11:13 PM, said:

 LoganDark, on 07 March 2016 - 11:09 PM, said:

Wouldn't that be perfect for password systems? It would take quite a bit longer to brute-force it.
You have to assume that if someone wants to crack a password that was found in a CC program, he will certainly not crack it from within CC.
Cracking outside of CC will always be faster, so might as well make them as fast as possible for convenient in-game use.
BCrypt has an argument that determine the cost factor, it won't be much before a cost factor get's too costly for CC to be any more useful against offline cracking, compared to SHA2 alone.

Well, outside of CC it would still be slower than SHA256. :P
Quote

LoganDark's Photo LoganDark 29 Mar 2016

 Anavrins, on 19 February 2016 - 09:41 PM, said:

I ended up making my own take at implementing SHA256 in Lua and ended up being around 15x faster.
With some rough speed test I could only get up to 105 hash/sec, my implementation was able to get to 1500 hash/sec.
It's still not much compared to say, gpus, but it's quite something for CC.
I also noticed the same thing as Shazz, that any input that's (64*n)+55 bytes in length will produce the incorrect hash, I didn't go deep into the problem, but I know it's the pre-processing part that produces an incorrect padding.
That bug is not present in my implementation.
Here's the pastebin: 6UV4qfNF
Posted Image
It seems I'm having a little bit of an error trying to run your SHA algorithm after having an upcoming project of mine mostly finished.

Edit: just using sha256("msg")
Edited by LoganDark, 29 March 2016 - 02:10 PM.
Quote

Anavrins's Photo Anavrins 29 Mar 2016

 LoganDark, on 29 March 2016 - 02:03 PM, said:

Posted Image
It seems I'm having a little bit of an error trying to run your SHA algorithm after having an upcoming project of mine mostly finished.

Edit: just using sha256("msg")
What CC version are you using, this implies that your using an older version of CC which does not contain bit32.
In any case you can replace the bit32 parts with bit, though I haven't tested it.
Edited by Anavrins, 29 March 2016 - 02:25 PM.
Quote