SHA-1 due for release soon, AES requests?

05-05-2004, 09:52 PM

SHA-1 is the standard by which most hashes are judged, and generates a 160 bit (5 dwords, 40 hex characters) hash.

This can of course be truncated, doublehashed, or should I implement, HMAC keyed.

So I ask you, what encryption standards would you like to see? MD4, MD5, Rijndael Encryption?

Here are a few of the functions which will be required in SHA-1, when I release it in this topic.

(Dont make fun of my primitive base conversions, I've hardly looked into the math of it, or the XOR. That, and my function for SHA-1 will be completely written by me. No external functions written by other people.)

edited out, with other parts (post getting too long, I'm close to finishing SHA-1)

05-06-2004, 12:07 AM

Cubasis

hmm :/

Looks good and all, just wanna mention, and suggest you to be concerned about...string leakage.

The string-system works like... whenever you create a unique (a string you've never created before) string... it creates the string...puts it into a string array, and then you get a pointer to that string. Then if you create the same string later...it will not create another string, but reuse the already created one.
So in certain ways, this sounds like a pretty cool system, but ... when working with alot of big...unique strings, it can be considered a memory leak.
You may notice that Grater stream-lined his password system in the Jass Vault to avoid creating alot of unique big strings, and while this may not sound really all that serious, as... logic implies a string's size is: charCount * 1 byte - That can quickly build up ...if you are dynamically creating alot of big unique strings in-game... And then who knows how big these strings really are... as considering the fact that leaking a simple location...which should just be 2 reals...or 8 bytes...is in fact around 40-60 bytes :/. And that was the result I got when only having 256 mb ram (and ofcourse there is a high problability that after leaking 500000 locations with so little ram, much of it has been moved onto the page-file).

And one final thing, in the following lines (if we give that it was on a fresh map with no other strings), I create .... 19 ... unique strings. That is, 10 strings with only a single symbol content ("0"-"9"), and then 9 more strings, with raising size ("01" - "0123456789")

Code:

local integer i = 0
local s = ""
loop
   exitwhen i >= 10
   set s = s + I2S(i)
   set i = i + 1
endloop

So, in a sense this makes your job pretty much harder I guess. And to myself, this isn't much of a problem if one just keeps it in mind while programming. My own thumb of rule is to not care about String Literals (no matter how big they are), and strings with a content of 1, as those are reused in all string proccessing functions, and are tiny enough to care about.
And then I just keep this problem in mind while coding, stay away from proccessing too big messages and stuff like that.

Anyways, I may very well be a bit to big of a perfectionist fanatic. And the strings leaked involved with these functions may very well be worth the leak.

Cubasis

Oh, and if you are looking for alternative, you can follow Grater's way, he did all his bit-math with a integer array... full of 0's and 1's. As that's a thing you can deffinetely count on not to leak.

05-06-2004, 12:38 AM

The Gearhead

If you look at all my bitwise functions (not conversions) I am using the same string the entire way through, so the memory is already allocated.

However, I have already investigated string leakage, and I will adapty decimal to bit conversion, if necessary. But even then, I am using the same string over and over, so the memory is already allocated.

And, as for the "strings" involved. There's no local string that is not necessary. The other strings are required, as they are to initiate the decimal to binary system. If I removed them, then it wouldn't work.

(Had typed wrong thing, I realized my mistake and corrected the 2nd bolded text)

05-06-2004, 12:45 AM

Cubasis

Hmm, you most likely didn't understand properly.

The problem is... as I said, in EVERY case that you create a new string...it puts it into the string array and it is then leaked/reused.

That's also why I brought that example in the middle of my post.

This line creates (leaks, if you prefer) 3 different strings:

set s = "GaGaGaGa" + "GooGooGooGooGoo"

String 1: GaGaGaGa
String 2: GooGooGooGooGoo
String 3: GaGaGaGaGooGooGooGooGoo

And from there we could go on. If the next line would be:

set s = s + "a"

Then I would also have created (leaked) 2 more strings:

String 4: a
String 5: GaGaGaGaGooGooGooGooGooa

That's the real problem :/. So string creation isn't bound by a variable, instead, ALL strings that go through the engine, be them literals, or results of a conjucation (however you spell that), get created, and added to this string array.

Anyways, as we both know, this leak is well acceptable ... within limits, as it doesn't need to be that serious/big.

Cubasis

05-06-2004, 12:59 AM

The Gearhead

As you can see, I did everything I could to keep strings to a minimum, by avoiding calling the same string fragment over and over.

And, if I remember right, once the handle's memory is allocated it is fine? Is WC3 misallocating extra memory to a string, then?

And if it is, then would it not be relatively impossible to fix it?

If even concetenate strings leak, then there's literally no way to avoid string leakage. And if it leaked nearly as bad as you would think it should (strings are 1024 characters, so that's 1024 x 1 byte = 1kB) then the game would be neigh unplayable.

05-06-2004, 10:44 AM

AIAndy

The problem is that strings are not what you think they are. A string variable is not a reference to a point on the heap where you have that string and can process it.
Instead whenever any string is created through string processing or a string literal, that new string is put in a data structure that assigns a string literal a unique number that will not change.
So a string variable always contains the unique number of the string literal it stores.
When I have the following:
3 string variables named a, b, c.
set a = "foobar"
set b = "foobar"
set c = "foobar"
That will only create one entry in the string table named foobar of which the number is then stored in a, b and c.

On the other hand when I have:
set i = 1
loop
exitwhen i > 10000
set s = I2S(i)
set i = i + 1
endloop

That actually creates 10000 entries in the string table with the content "1", "2", ...
There is no removal in this string table. When you use a string literal once, it remains in the table for the entire map.

05-06-2004, 12:45 PM	#7
The Gearhead	So when I continually add 1s and 0s, it's using the same 1 and 0 entry. So that should be a Good Thing (tm)?

05-06-2004, 02:17 PM

Cubasis

Yeah, but it will still always be creating new strings based on your proccessing, but ofcourse there is a limit to that. So it will basicly in the end (if used often enough) create "ALL" strings from:

00000000000000000000000000000000
too
11111111111111111111111111111111

and all building-strings (so if you're building "11111111111111111111111111111111", it will leak 31 other strings that range in size. (f.ec. "11","111","1111","11111","111111" etc))

So yeah, it's up to you to consider if this is a problem to you or not. If I were you, i'd go with integer-arrays, and build all your functions around this 1 array. So while some actions may be proccess heavyer (f.ex. assigning your array too "111111111111111111111111111" would then need a function that runs through it and puts each element to 1.) it will be completely leak free, and many other functions will actioully be more simple to work with. However the con with that, is that then this API instantly becomes harder to distribute, if it has to be attached to a array to work. But if it's only for your own map, or if people need it much enough, then 1 array doesn't stand in anybody's way.

Cubasis

05-07-2004, 03:55 AM

The Gearhead

I'm almost done, and I streamlined it by making a null-value and appending string so I dont have to do this:

loop
exitwhen StringLength(x) == 32
set x = "0" + x
endloop

Instead, it grabs a substring of appropriate length from a string of 0s with a 1 at the front. The 1 is only ever grabbed when I need to append onto the SHA to create 512 bit blocks.
edited out

Use in your script with:
SHA1core("1010")
Where 1010 is any binary string of length less than or equal to 992.

But good luck getting it to run fully. I have no clue why it stops. And if you change the equation, it usually changes the number of loop runs before it stops. (Edit2: Runs fully, computes hash incorrectly. I'm still examining.)

This is mathematically identical to SHA-1. However, JASS is not doing it.

Can any of you figure out why?

I am still examining exactly why this is wrong though.

Edit3: Forgot the globals I declared:

edited out

Note, since SHA1 is public domain, I use alternate binary codes for inputting strings. Thats what asciistringtobin does.

If you want a real 'answer' from SHA1, you must enter the binary code yourself or find some other solution.

05-10-2004, 08:27 PM	#10
jmoritz	I wouldn't worry too much about memory leaks at first. Just try and get the algorithm to work. Later test is for speed and memory leaks, and optimize where necessary.

05-10-2004, 09:56 PM

#11

The Gearhead

Http://aaron.frieltek.com/sha1abc.jpg

That's the correct computational SHA-1 hash of the code abc. Yay!

That's the first succesful run, but it took... 30 seconds to compute.

As soon as I fix my mathematical (integer, rather than string-based) AND it should go much more quickly. Just changing the XOR to use integers made it take only about 10 seconds. Still, a rediculous amount of time.

The main problem I've encountered is that the loops have a timeout and won't computer more than x number of logical operations before the loop simply stops (along with the rest of the trigger).

My AND is incomplete, and computing improperly right now, but the XOR works fine. With both of those, I can run the entire thing in a second or so. Each of those, along with running at least a hundred times more efficiently, also made it possible to reduce the # of pauses in the script. As is, I have to use this system for an example loop:

loop
exitwhen i == 80
[operations]
set i = i + 1
if ( ModuloInteger(i,10) == 0 ) then
call wait (.01 seconds) / heh, forgot the function name
endif
endloop

On one of them, I had to use a 7, and the other a 6. Now I can use 15 and 10, respectively.

And it's fixed.

I'll post screeny of the hash of 'abc' ("011000010110001001100011").

I have not included an ASCII to Binary code in this one.

Note: you must input binary for this to function. For true SHA-1 results, you must input true ASCII

Globals:

Code:

	set udg_Pow[31] = -2147483648
	set udg_Pow[30] = 1073741824
	set udg_Pow[29] = 536870912
	set udg_Pow[28] = 268435456
	set udg_Pow[27] = 134217728
	set udg_Pow[26] = 67108864
	set udg_Pow[25] = 33554432
	set udg_Pow[24] = 16777216
	set udg_Pow[23] = 8388608
	set udg_Pow[22] = 4194304
	set udg_Pow[21] = 2097152
	set udg_Pow[20] = 1048576
	set udg_Pow[19] = 524288
	set udg_Pow[18] = 262144
	set udg_Pow[17] = 131072
	set udg_Pow[16] = 65536
	set udg_Pow[15] = 32768
	set udg_Pow[14] = 16384
	set udg_Pow[13] = 8192
	set udg_Pow[12] = 4096
	set udg_Pow[11] = 2048
	set udg_Pow[10] = 1024
	set udg_Pow[9] = 512
	set udg_Pow[8] = 256
	set udg_Pow[7] = 128
	set udg_Pow[6] = 64
	set udg_Pow[5] = 32
	set udg_Pow[4] = 16
	set udg_Pow[3] = 8
	set udg_Pow[2] = 4
	set udg_Pow[1] = 2
	set udg_Pow[0] = 1
	set udg_HEXCHAR[0] = "0"
	set udg_HEXCHAR[1] = "1"
	set udg_HEXCHAR[2] = "2"
	set udg_HEXCHAR[3] = "3"
	set udg_HEXCHAR[4] = "4"
	set udg_HEXCHAR[5] = "5"
	set udg_HEXCHAR[6] = "6"
	set udg_HEXCHAR[7] = "7"
	set udg_HEXCHAR[8] = "8"
	set udg_HEXCHAR[9] = "9"
	set udg_HEXCHAR[10] = "A"
	set udg_HEXCHAR[11] = "B"
	set udg_HEXCHAR[12] = "C"
	set udg_HEXCHAR[13] = "D"
	set udg_HEXCHAR[14] = "E"
	set udg_HEXCHAR[15] = "F"
	set udg_APPENDSHA = "10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"

Note on above: APPENDSHA must not have any spaces in it! So when copying the above code, remove any spaces! The forum has placed them there.

May be placed in header. Only SHA1core needs to be called. The dec2bin will not return ASCII character values in binary.

Code:

function dec2bin takes integer Dec returns string
	local integer z = Dec
	local integer i = 30
	local string Sign = "0"
	local string Bin = ""
	if ( Dec < 0 ) then
		set Sign = "1"
		set Dec = 2147483648 + Dec
		set z = Dec
	endif 
	loop
		exitwhen (i == -1 or z == 0)
		if ( z - udg_Pow[i] >= 0) then
			set Bin  = Bin + "1"
			set z  = z - udg_Pow[i]
		else
			set Bin  = Bin + "0"
		endif
		set i = i - 1
	endloop
	set Sign = Sign + Bin
	set Bin = null
	return Sign + SubString(udg_APPENDSHA,1,i+2)
endfunction

function bin2dec takes string Bin returns integer
	local integer i = 2
	local integer Dec = 0
	loop
		exitwhen i == 33
		if ( SubString(Bin,i-1,i) == "1" ) then
			set Dec = Dec + udg_Pow[32-i]
		endif
		set i = i + 1
	endloop
	if ( SubString(Bin,0,1) == "1" ) then
		return 2147483648 + Dec
	endif
	return Dec
endfunction

function XORBIN takes integer A, integer B returns integer
	local integer i = 30
	local integer C = 0
	if ( (A < 0 and B < 0) ) then
		set A = A + 2147483648
		set B = B + 2147483648
	endif
	if ( (A < 0 and B >= 0) or (B < 0 and A >= 0) ) then
		set C = -2147483648
		if ( A < 0 ) then
			set A = A + 2147483648
		else
			set B = B + 2147483648
		endif
	endif
	loop
		exitwhen i < 0
		if ( A >= udg_Pow[i] or B >= udg_Pow[i] ) then
			if ( (A >= udg_Pow[i] and B < udg_Pow[i]) or (B >= udg_Pow[i] and A < udg_Pow[i]) ) then
				set C = C + udg_Pow[i]
			endif
			if ( A >= udg_Pow[i] ) then
				set A = A - udg_Pow[i]
			endif
			if ( B >= udg_Pow[i] ) then
				set B = B - udg_Pow[i]
			endif
		endif
		set i = i - 1				
	endloop 
	return C
endfunction

function ANDBIN takes integer A, integer B returns integer
	local integer i = 30
	local integer C = 0
	if ( (A < 0 and B < 0) ) then
		set C = -2147483648
		set A = A + 2147483648
		set B = B + 2147483648
	endif
	if ( A < 0 ) then
		set A = A + 2147483648
	endif
	if ( B < 0 ) then
		set B = B + 2147483648
	endif
	loop
		exitwhen i < 0
		if ( A >= udg_Pow[i] and B >= udg_Pow[i] ) then
			set C = C + udg_Pow[i]
		endif
		if ( A >= udg_Pow[i] ) then
			set A = A - udg_Pow[i]
		endif
		if ( B >= udg_Pow[i] ) then
			set B = B - udg_Pow[i]
		endif
		set i = i - 1				
	endloop 
	return C
endfunction

function NOTBIN takes integer I returns integer
	return -1 - I
endfunction


function FUNCt takes integer b, integer c, integer d, integer t returns integer
	if ( t < 20 ) then
		return XORBIN(ANDBIN(b,c),(ANDBIN(NOTBIN(b),d)))
	endif
	if ( t < 40 or t >= 60 ) then
		return XORBIN(XORBIN(b,c),d)
	endif
	return XORBIN(XORBIN(ANDBIN(b,c),ANDBIN(b,d)),ANDBIN(c,d))
endfunction

function KONSt takes integer t returns integer
	if ( t < 20 ) then
		return 1518500249
	endif
	if ( t < 40 ) then
		return 1859775393
	endif
	if ( t < 60 ) then
		return -1894007588
	endif
	return -899497514
endfunction

function dec2hex takes integer A returns string
	local integer i = 27
	local integer c = 0
	local string Str = ""
	if ( A >= udg_Pow[28] or A < 0) then
		if ( A < 0 ) then
			set c = c + udg_Pow[3]
			set A = A + 2147483648
		endif
		if ( A >= udg_Pow[30] ) then
			set c = c + udg_Pow[2]
			set A = A - udg_Pow[30]
		endif
		if ( A >= udg_Pow[29] ) then
			set c = c + udg_Pow[1]
			set A = A - udg_Pow[29]
		endif
		if ( A >= udg_Pow[28] ) then
			set c = c + udg_Pow[0]
			set A = A - udg_Pow[28]
		endif
		if ( c < 10 ) then
			set Str = Str + I2S(c)
		else
			set Str = Str + udg_HEXCHAR[c]
		endif
	endif
	loop
		exitwhen i < 0
		set c = 0
		if ( A >= udg_Pow[i-3] ) then
			if ( A >= udg_Pow[i] ) then
				set c = c + udg_Pow[3]
				set A = A - udg_Pow[i]
			endif
			if ( A >= udg_Pow[i-1] ) then
				set c = c + udg_Pow[2]
				set A = A - udg_Pow[i-1]
			endif
			if ( A >= udg_Pow[i-2] ) then
				set c = c + udg_Pow[1]
				set A = A - udg_Pow[i-2]
			endif
			if ( A >= udg_Pow[i-3] ) then
				set c = c + udg_Pow[0]
				set A = A - udg_Pow[i-3]
			endif
		endif
		set Str = Str + udg_HEXCHAR[c]
		set i = i - 4
	endloop
	return Str
endfunction

function ROTATE takes integer Value, integer Amount returns integer
	local integer z = 0
	local integer i = 30
	set Amount = ModuloInteger(Amount,32)
	if ( Value < 0 ) then
		set z = udg_Pow[Amount-1]
		set Value = Value + 2147483648
	endif
	loop
		exitwhen i < 0
		if ( Value >= udg_Pow[i] ) then
			set z = z + udg_Pow[ModuloInteger(Amount+i,32)]
			set Value = Value - udg_Pow[i]
		endif
		set i = i - 1
	endloop
	return z
endfunction

function SHA1core takes string M returns string
	local integer i
	local integer Messages = 1
	local string array Mt
	local integer array W
	local integer array K
	local integer t = 0
	local integer TEMP = 0
	local integer lasta
	local integer lastb
	local integer lastc
	local integer lastd
	local integer laste
	local integer a =  1732584193 
	local integer b =  -271733879
	local integer c = -1732584194
	local integer d =   271733878
	local integer e = -1009589776
	set i = StringLength(M)
	if ( i >= 448 ) then 
		set Mt[0] = SubString(M,0,512) + SubString(udg_APPENDSHA,1,513-StringLength(SubString(M,0,512)))
		set Mt[1] = SubString(M,512,1024) + SubString(udg_APPENDSHA,1,513-StringLength(SubString(M,512,1024)))
		set Messages = 2
	else
		set Mt[0] = M + SubString(udg_APPENDSHA,0,480-i) + dec2bin(i)
	endif
	set M = null
	set i = 0
	loop
		exitwhen t == Messages
			set lasta = a
			set lastb = b
			set lastc = c
			set lastd = d
			set laste = e
			loop
				exitwhen i == 16
				set W[i] = bin2dec(SubString(Mt[t],i*32,i*32+32))
				set i = i + 1
			endloop
			set Mt[t] = null
			loop
				exitwhen i == 80
				set W[i] = ROTATE(XORBIN(W[i-16],XORBIN(W[i-14],XORBIN(W[i-8],W[i-3]))),1)
				set i = i + 1
				if( ModuloInteger(i,16) == 0 ) then
					call TriggerSleepAction( 0.001 )
				endif
			endloop
			set i = 0
			loop
				exitwhen i == 80
				set TEMP = ROTATE(a,5) + FUNCt(b,c,d,i) + e + KONSt(i) + W[i]
				set e = d
				set d = c
				set c = ROTATE(b,30)
				set b = a
				set a = TEMP
				set i = i + 1
				if( ModuloInteger(i,10) == 0 and i != 0) then
					call TriggerSleepAction( 0.001 )
				endif
			endloop
			set i = 0
			set a = a + lasta
			set b = b + lastb
			set c = c + lastc
			set d = d + lastd
			set e = e + laste
		set t = t + 1
	endloop
	return dec2hex(a) + dec2hex(b) + dec2hex(c) + dec2hex(d) + dec2hex(e)
endfunction

05-12-2004, 09:10 PM	#12
The Gearhead	Yeah, so sue me for bumping. I've edited the above post 3 times and nobody has commented in a couple days.