| 03-06-2003, 07:37 AM | #1 |
**EDIT** Just to note for those that may come across this thread, about 6 posts down is a modified map that allows you to simply type in a chat message. The hash is then displayed back to you for that message. **EDIT** I am pleased to announce my contribution to encryption in JASS. At this time, I feel that it is the best solution currently available for the level of encryption provided. I may be wrong on this, and would welcome being proven wrong in the hopes that something better can be released for others to use. The idea by this encryption is a fairly simple One Way Xor Hash of a string. Any of you familiar with encryption systems can akin this to Crypt, though to a much lesser degree. The problem with JASS is it is powerfull for interacting with the WC3 world, but horrible for doing anything advanced, especially in the arena of bitwise math...that's because there just isn't any. In order to implement this, I needed an Xor function, so after being frusted that Blizzard didn't even think to provide bitwise operators, I wrote my own functions. Since this is a one way encryption scheme, it can not be decrypted. The idea of this example is to provide a means of encrypting a password, or a special code that someone has to write down, inside of a Game Cache. The only way to prove that that a string is valid, is to compare the hashes of the saved encrypted string, with the hash of a user entered string that supposedly matches it. I'm already working on a system to use the Xor functionality that will provide a way to decrypt, with both the encrypt/decrypt process using a "key" to encrypt a string. The only way to get the string back is via the "key" (i.e. password). The reason I am working on this is because given the limited capabilities of JASS, an emulated Xor encryption scheme is one of the best that you are going to get. I have actually thought about also implementing some sort of Public/Private key encryption, but unfortunately due to the nature of the Game Cache, I see no way of saving a Private Key without it being on everyones computer. This, of course, would make this encryption scheme completely useless. If someone knows of a workaround for this, please let me know, since I just recently started playing with the Game Cache. (and though yes, technicaly it would be possible to have the user run the map for the first time in Single User or by themselves on BNET to allow them to create a private key...but then you have to rely on the user doing the smart thing). And on that note, here is the example map. If you run it in WC3, type the message "example" to see it in action. There is also documentation that gives some of the information above, as well as more descriptions on what goes on under the hood. |
| 03-06-2003, 12:27 PM | #2 |
I don't understand what it does to the password and how you can input this in, and it will know what is what. I know encryption to some extend, but this I have no idea. |
| 03-06-2003, 03:08 PM | #3 |
The basic cocnept at work here, is using a bitwise XOR to obfuscate the password that is entered. Each character is XOR'ed with each other, with the final result being used to seed the Random Number Generator. At this point, a random real number between 0 and 1 is generated (the first number in the series for the given seed) and multiplied by a large fixed number to end up with the hash, which is nothing but a 32 bit integer (31 bit really if you consider positive numbers only, since JASS integers are signed). Due to the fact that you are using this unique data to seed the random number generator, it would be quite difficult to take the resulting hash and 1) break it down to find out the string that was encrypted, and 2) figure out some system that would be able to decrypt any given hash into the corresponding string. This is because this current method is intended as a One Way (encrypt, with no decrypt). And verification of a string is done by comparing two hashes. In order to encrypt a string using the functions in this map, all you have to do is set the global variable udg_password to the string you want encrypted, then call the trigger (ignoring conditions) gg_trg_encrypt. After the encryption has taken place, the result will be stored in the integer udg_hash which can then be saved in the game cache for later comparison. The idea of the hash is the purpose behind a One Way Encryption system, attempting to make it very difficult to decrypt, and the only way of proving that two strings are identical, is to compare two encrypted hashes together. Small example (not real): Input String: "My Password" Resulting Hash: 1065095104 You then save the integer hash to the game cache, the person leaves the game, and later opens a new map. You ask them for their password, set udg_password, call encrypt to get the hash, then compare the current hash with that which is stored in the game cache. Input String: "My password" (p is not uppercase as before) Resulting Hash: 419934845 Comparing the two hashes will result in authentication failure. The two strings do not match. Even though this is only an example, this is meant to also show that even varying the string by a small degree will by no means reflect such in the hash that is generated. Re-enter String: "My Password" Resulting Hash: 1065095104 Now the two hashes match, proving that the strings are identical and authentication is granted. |
| 03-06-2003, 03:38 PM | #4 |
Sorry to use this medium as communication, but FyreDaug, your mailbox is full, and I can not send you a PM. |
| 03-06-2003, 03:45 PM | #5 |
Looks pretty good, note that Game Cache does not work on b.net for more then one player. |
| 03-06-2003, 03:50 PM | #6 |
Also, even if you aren't interested in encryption, but are curious about function recursion, this is still a good download, as one of my functions uses recursion to get a desired result. |
| 03-06-2003, 07:21 PM | #7 |
I'm keeping the previous map in place since it shows how you can set the password to a string using the GUI. Below is a slightly modified map that I think gives a better example of the encryption algorythm in action. All you have to do is type in a chat message, and the hash will be displayed back to you. There is a limit to the length of the string you can use before the result is 0. Type in the same chat message twice, and notice that the hash is the same. Modify the chat message by one character and notice the difference in the hash. Also, use a character that is currently not registered for use to be encrypted, and you will see the error message (right now the only valid characters are SPACE, @, and all numbers and letters). |
| 03-06-2003, 07:26 PM | #8 |
Okay rwxr, I deleted the messages, you can resend it now. And thanks by the way. Deleted all the webhosting requests I forgot about. EDIT: Also this password I PMed you about is not stored in game cache, its for bnet play. Just letting you know. |
| 03-09-2003, 04:15 PM | #9 |
Hi rwxr-xr-x, So much work just to get the C equivalent of | working in JASS. After examing the trigger, you are correct in that this is a one way hash. Also noteworthy is that multiple inputs can give the same output. This fact forces the algorithm to be irreversible. The inputs abc and bac and any other variation of these 3 letters will all give the same result. This type of 'encryption' will defeat 99% of bnet users, but it's the 1% you may have to worry about. It's probably not a big deal though. I think XOR was so appealing because it was just 1 asm op code so it's damn fast. It has the nice property of being able to retrieve the data given the original 'key'. Having a trigger that appears to run in O(n) + C where C is a pretty big constant kind of defeats the original purpose of fast dirty way of quickly obfuscating data. As for private/public key encryption, I also came to the same conclusion as you. Even if the private key resides on a web server (so people can enter their high scores on a webpage), the client is untrustworthy as they can easily generate a false set of data and encrypt it. At this point, I've totally given up on doing any real encryption and just would just go for obfuscation if I were to need one in a map. Anyway, triggers look good. Definitely a great contribution to the community. Looking forward to see more improvements. -Mr.123 |
| 03-09-2003, 04:49 PM | #10 |
Actually it would be the C equivilant of ^ :) But I agree, this is a good example of being able to stop 99% of the users out there, but as is with any encryption scheme, it's affectiveness is only as strong as the size of its key which is almost always user generated. So that 99% number may be even slightly less taking this into factor. Especially when using the XOR method. Preferably, your key would be larger than the actual data you are encrypting, but for the purpose of hiding data in War3, it's just not that big of a deal. I doubt anyone is going to be trying to protect corporate secrets in a war3 map :) Of course, it does annoy me only slightly that there are no bitwise operators in JASS. Even with the XOR code I have, I am only working with 16 bit numbers, not the full 32. I'm actually interested in implementing full 32 bit bitwise operators, including bitwise shift left and right. My motivation behind this is so that I can implement the Tiny Encryption Algorithm in JASS and determine its cost of execution, and whether or not it would be feasible to use. And even if its not, will still be a good exercise and possibly be a good example for others. *EDIT* And on the topic of public/private keys, I've recieved some good feedback for possibilities. I've actually worked a scheme of a combination of ideas that would allow the trigger to always generate the same private key for a specific user, but the problem is it would just be more work than it is worth, making even my XOR implementation look like an uber fast scheme. |
| 03-15-2003, 03:38 AM | #11 |
My recommendation would be to retrieve player names (there's a string function to get them) since they're already password protected on bnet. That plus the password should give you a hash with which no player can steal another's character. The only problem is people altering their own characters. :( |
| 03-15-2003, 08:41 PM | #12 |
My current work does just that (using bnet name). I was at first worried about name spoofers, but the extra ascii code that gets put in them would more than likely fuddle this attempt. Even then, the idea of sending the user encrypted text would be to send only to that user, so even if someone switched letters, everything would be pointless without the encrypted data. BTW, this is an XOR encryption scheme using a key (bnet name) that can encrypt/decrypt text. Only problem right now is data compression. |
| 03-15-2003, 09:12 PM | #13 |
Yeah and theres alot of data to compress eh rwxr? |
| 04-19-2003, 07:42 PM | #14 |
Guest | I was wondering if you could walk through the code here. I am somewhat confused by some of the functions (namely, DecToBin and XOR), and I am sure others will find it useful. |
| 04-19-2003, 11:20 PM | #15 |
Sure...will be a bit tricky to fully walk you through the DecToBin, but I'll give it my best shot. The first thing important to state about DecToBin, is that it is a recursive function, i.e. it calls itself. The main point of DecToBin is to take an integer, and convert it into a string that represents its binary value. Another thing to note is that DecToBin only converts the number into a 16 bit binary, since I am only dealing with values from the ASCII table which range from 0 - 255. This is why the call in the Xor function to DecToBin has 256 as the second argument (256 is the largest number representable in 8 bits, the remaining 8 bits are needed as padding) If we consider nothing more than the string " " (a space), the following example will use the number 32 (which is a space in ASCII). If we take a look at the encrypt trigger itself, the outer loop is used to keep the Xor of each character going until the end of the string is reached. The inner loop does nothing more but check to make sure that the character to be Xor'ed is a valid character, as defined in the init trigger. taking the following code: Code:
if (SubStringBJ(udg_password,i,i) == udg_char[j]) then set t = Xor(udg_charNum[j],t) set valid = true exitwhen true else set j = j + 1 endif the character at position i in udg_password is compared with the character at position j in udg_char[]. If the characters don't match, j is incremented until finaly we find a match, or no match is found at all. Once there is a match, we can call the Xor function with the integer value for that character which is stored in udg_charNum[j]. In this case, our first call to Xor equates to set t = Xor(32,0) Code:
function Xor takes integer x, integer y returns integer
local string string1 = DecToBin(x,256)
local string string2 = DecToBin(y,256)
.
.
endfunctionusing DecToBin as a reference... Code:
function DecToBin takes integer a, integer b returns string
local integer hiNum = a / b
local integer loNum = ModuloInteger(a, b)
local string opStr = ""
set b = R2I(SquareRoot(I2R(b)))
if (b > 1) then
set opStr = opStr + DecToBin(hiNum, b)
set opStr = opStr + DecToBin(loNum, b)
else
return (I2S(hiNum) + I2S(loNum))
endif
return opStr
endfunctionCode:
DecToBin(32,256)
1) hiNum = 0
loNum = 32
b = 16
(b > 1)
set opStr = opStr + A)
set opStr = opStr + B)
A) DecToBin(0,16)
hiNum = 0
loNum = 0
b = 4
(b > 1)
set opStr = opStr + A.i)
set opStr = opStr + A.ii)
A.i) DecToBin(0,4)
hiNum = 0
loNum = 0
b = 2
(b > 1)
set opStr = opStr + A.i.a)
set opStr = opStr + A.i.b)
A.i.a) DecToBin(0,2)
hiNum = 0
loNum = 0
b = 1
(b not > 1)
return ("00")
A.i.b) DecToBin(0,2)
hiNum = 0
loNum = 0
b = 1
(b not > 1)
return ("00")
A.ii) DecToBin(0,4)
hiNum = 0
loNum = 0
b = 2
(b > 1)
set opStr = opStr + A.ii.a)
set opStr = opStr + A.ii.b)
A.ii.a) DecToBin(0,2)
hiNum = 0
loNum = 0
b = 1
(b not > 1)
return ("00")
A.ii.b) DecToBin(0,2)
hiNum = 0
loNum = 0
b = 1
(b not > 1)
return ("00")
B) DecToBin(32,16)
hiNum = 2
loNum = 0
b = 4
(b > 1)
set opStr = opStr + B.i
set opStr = opStr + B.ii
B.i) DecToBin(2,4)
hiNum = 0
loNum = 2
b = 2
(b > 1)
set opStr = opStr + B.i.a
set opStr = opStr + B.i.b
B.i.a) DecToBin(0,2)
hiNum = 0
loNum = 0
b = 1
(b not > 1)
return ("00")
B.i.b) DecToBin(2,2)
hiNum = 1
loNum = 0
b = 1
(b not > 1)
return ("10")
B.ii) DecToBin(0,4)
hiNum = 0
loNum = 0
b = 2
(b > 1)
set opStr = opStr + B.ii.a
set opStr = opStr + B.ii.b
B.ii.a) DecToBin(0,2)
hiNum = 0
loNum = 0
b = 1
(b not > 1)
return ("00")
B.ii.b) DecToBin(0,2)
hiNum = 0
loNum = 0
b = 1
(b not > 1)
return ("00")Taking a look at the above, we see the calls to itself as the following: A->A.i->A.i.a which finally returns the first bits of data, which is "00" and represents the first two high bits (bits 16 and 15 respectively). Then A.i.b is called which returns the second bits of data "00" (bits 14 and 13 respectively). The process continues until all bits are returned. All that is happening is each call reduces the scope of the binary number until it reaches 2 bits of data, starting with highest bit. If we take a look at all of the calls as they are made, we can see how 32 is converted into a binary string. Code:
A->A.i-->A.i.a returns "00"
-->A.i.b returns "00"
->A.ii->A.ii.a returns "00"
->A.ii.b returns "00"
B->B.i-->B.i.a returns "00"
-->B.i.b returns "10"
->B.ii->B.ii.a returns "00"
->B.ii.b returns "00"The loop inside the Xor function then traverses each character in the strings and Xor's them. For those unsure of what XOR does, it is an exclusive OR, in that, only one of two values compared can be a 1 for the result to be a 1. Below is a truth table for OR and XOR to show the difference. Code:
X | Y | XOR | OR --|---|-----|---- 0 | 0 | 0 | 0 0 | 1 | 1 | 1 1 | 0 | 1 | 1 1 | 1 | 0 | 1 As you can see, a 1 and a 1 produces a 0 for XOR, since it is exclusive. So traversing through the two strings and XOR'ing each value, we determine the XOR'ed equivilant of two numbers. Code:
loop
if ((S2I(SubStringBJ(string1,i,i)) + S2I(SubStringBJ(string2,i,i))) == 1) then
set result = result + "1"
else
set result = result + "0"
endif
set i = i + 1
exitwhen i == 17
endloopNow that the two numbers have been effectively XOR'ed, the resulting string needs to be converted back into an integer. The returned value in the Xor function is calling BinToDec(result). Refering to BinToDec... Code:
function BinToDec takes string binStr returns integer
local integer multiplier = 1
local integer outcome = 0
local integer i = 16
local string bit = ""
loop
set bit = SubStringBJ(binStr, i, i)
if (bit == "1") then
set outcome = outcome + multiplier
endif
set multiplier = multiplier * 2
set i = i - 1
exitwhen i == 0
endloop
return outcome
endfunctionSince the previous two numbers 32 and 0 XOR'ed is 32, the string "00000000100000" is in fact converted back to the integer 32, which is returned from the Xor function. Going back to the encrypt function, the integer t is set to 32. Since our test string contained only a space (" "), the outer loop then exits since there are no more characters in the string. If there were in fact more characters in the string, the process would repeat itself. For example, if the next character was "a", then the last XOR'ed result of 32 would then be XOR'ed with 97, and so on. Once all characters in the string have been XOR'ed, the resulting number is then fed to the function SetRandomSeed(t) to randomize the random number generator. To get a hash, we then get a random real between 0 and 1, and multiply it by a very large number: Code:
call SetRandomSeed(t) set udg_hash = R2I(GetRandomReal(0,1) * 0x7FFFFFFF) The large number is a Hex value of a 32 bit integer. The "7F" is used as the highest bits in order to insure a positive integer is produced (JASS integers are 32 bit signed). I hope this explanation helps clear up what is actually going on. As I have also said before, this is by no means considered high encryption, but for the purpose of helping to obfuscate things, it is suitable. The ability to produce an equal hash only becomes more difficult based on the length of the string you enter. |