Bitwise Operations (and hex)

Garry's Mod coding
#1

UPDATED 08/29/2010 5:56PM

Added source to the actual repo for the new version of FakeBitOps.

http://adorablebin.googlecode.com/svn/trunk

Check that out and quit worrying about getting updates here. If and when I get the module done, it’ll go under that repo.

This used to be in the Garrysmod.org section. But I have moved it here and deleted the content of the old thread and posted the link to this thread there.

Hey guys, I’m hacking together some stuff that requires bitwise operations, so I made a pure lua library for dealing with binary and hex data. It’s emulated binary operations, so all of it is done through string manipulation.

I’ve lurked here for awhile and figured it could be useful to some of you, so I’m posting it here.

License is BSD. I’d be happy if some of you could contribute. Just ask to join the google code and I’ll accept. Even if you’re just going in there to clean or document.

Hope you find it useful.

Almost the entire library is documented here:

Binary Operations Available:
NOT
XOR
OR
AND
Zero Padding Left
Zero Padding Right
Left Rotate With Carry Over
Right Rotate With Carry Over
Left Rotate Without Carry Over
Right Rotate Without Carry Over
Binary to Hex

Hex Operations Available:
NOT
XOR
OR
AND
Bitwise Zero Padding Left (specify 64 as length and FF will become 00000000000000FF)
Bitwise Zero Padding Right (specify 64 as length and FF will become FF00000000000000)
Left Bitwise Rotate With Carry Over
Right Bitwise Rotate With Carry Over
Left Bitwise Rotate Without Carry Over
Right Bitwise Rotate Without Carry Over
Hex to Binary

Number Operations Available:
Number to hex
Number to binary

String Operations Available:
String to binary
String to hex

There is zero error handling at the moment, so try and keep your string lengths divisible by 8 for binary, divisible by 2 for hex.

Let me know what you think or if you want to join up.

Follow me on twitter, @adorablepuppy

#2

Gave my thoughts in the other thread.

I’m tempted to do some experiments, see how much slower it is to calculate the results as opposed to just look them up. It’d give the advantage of scaling to any length of bits, although repeating your method works perfectly well.

#3

Mine does scale to any length in bits, with the exception that it will not process under 8 bits binary and under 2 hex. I think that’s a reasonable limitation, since I don’t foresee myself using under 8 bits.

HexToBits(“FFFFFF”) will return “111111111111111111111111111111111111111111111111” and vice-a-versa BitsToHex(“111111111111111111111111111111111111111111111111”) returns “FFFFFF”
(if the above doesn’t appear right, thats 48 1’s in a row.)
The meat of the power is at the bottom. Ignore the predefined tables of numbers because directly, you should never need to use them.

#4

Updated and overhauled.

Codebase reduced from over 1000 lines to under 400 some of which are documentation.

I removed much of the hard coding. No more hard coded XOR, AND, OR, NOT. Instead, these are proper functions.

Added a couple new functions. Improved rotate and zero padding which are now 2 functions instead of 6.

Redefined my understanding and code of Carry over for rotate. Now supports no carry, zero carry, and one carry.

Renamed to FakeBitOps from adorablebin.

Tons of error messages inserted (though, not nearly complete)

I also discovered that my version of lua is limited to 32-bit hex numbers. Not sure if it’s any different with 64 bit versions. (i would hope so)

#5

Convert this to a Lua module. Please.

There are also a few minor optimizations you could make.

#6

I’m updating some things on it today, as I found a couple errors when going to implement a hashing function with it.

Also, I’m setting some defaults for functions like rotate, xor, or, and, and any other functions that would require a direction or carry specification.

Edit:
I am also open to suggestions for optimizations/fixes/additions/whatever. Post here, or post a message on the project to let me know what I can do to make it better.

I’ll see about converting it into a module today. If not, the source will still be posted. NEW BSD LICENSE.

Edit edit:

I’m currently working out issues in extra zero padding for hex digit calculations.

Also coming soon, MultiAnd, MultiOr, MultiXor, MultiHexAnd, MultiHexOr, MultiHexXor. Soon means, not in the svn yet.
While I already have these functions done, I’m holding them pending the fix of the hex padding bugs.

#7

UPDATED.

Check the SVN logs for full update status. Summary is: Added multi functions for hex and bin, added random functions for returning random binary strings and hex strings, adjusted zeropadding. Added defaults to most things that require amounts, directions, or carrys.

Implemented SHA1 with my library. SHA1 is on the repo, rev 7. Returns correct hash strings for string under 48-bits. I’m not sure why it’s messing up after that.

If anyone can figure this out, let me know, I’ll be working on it.

Repo here: http://adorablebin.googlecode.com/svn/trunk/

Update. I think I’ve found the reason SHA1 isn’t coming out right for message with > 12 characters. It all boils down to the upper limit of hex addition on a 32-bit installation of lua. Making a work around.

#8

FakeBitOps rev8.

I’ve added BinAdd and MultiBinAdd for BINARY ADDITION.

Also, the sha1 implementation is 100% now.

Do not use hex addition if you’re going to need more than your binaries’ alloted address space (0xFFFFFFFF on Lua official). Instead, use your bitstrings in the BinAdd and MultiBinAdd functions.

I will eventually implement BinSubtract and MultiBinSubtract. After than, HexAdd and HexSubtract. But first, I’m going to get an implemnentation of HMAC-SHA1 up (since it was the purpose for me starting this FakeBitOps in the first place).

Get it here: http://adorablebin.googlecode.com/svn/trunk

#9

FakeBitOps rev9 is out. Small changes.

Added BinMultiply, CouldBeBinString, CouldBeHexString.

Renamed sha.lua to FakeCrypto.lua. (not that it’s functions won’t work, it’s just
that it relies on FakeBitOps, which was named because of library that can be compiled into lua)

Changed sha1 into a prototype with bitwise_blocksize and blocksize properties. The sha1 prototype has a function called computehash. To remain compatible with hmac, all hashing functions should be made in the same way.

On to hmac, hmac is partially implemented. I say partially because the output is wrong. I’m trying my best to step through the code, but it does involve getting into the grit of sha1 and many helper functions in the FakeBitOps library. If someone could help me debug the hmac implementation, it would be most appreciated and would earn a permanent credit inside the library.

All files are NEW BSD. HC SVNT DRACONES.
http://adorablebin.googlecode.com/svn/trunk

If you want to join the project as a committer, I can get you access, post here and we’ll pm details.

Allow me to say, the first goals of these libraries are to enable pure lua emulated binary operations. Some of it’s functions may output some goofy stuff, but it does work reliably and now even has a working implementation of sha1.

The second goal of these libraries were to implement some pure lua encryption and hashing algorithms. Specifically sha1, and hmac at first. HOWEVER more are scheduled to be added after hmac is implemented properly.

Current planned functions for FakeBitOps are:
BinSubtract
BinDivide
HexAdd
HexMultiply
HexSubtract
HexDivide

Current planned hashing prototypes for FakeCrypto are
MD5 (Which I will recommend against using)
SHA256
SHA512
Whirlpool

Make a suggestion, it may go on.

#10

Can you think of any useful applications for this?

#11

Most definitely. The entire reason I started this library was so I could author an easy to expand OAuth library.

This will enable Garrysmod and it’s objects and players to richly communicate across popular sites on the internet, such as Twitter, Facebook, LinkedIn, Foursquare, etc, etc.

HMAC will be the final piece I would really need to go back to development on the OAuth libraries and it’s modules.

However, working with string manipulated binary values has become a sort of amusement for me. In useful applications for garrysmod, I can see a whole binary addon for UWSVN. It maybe also useful to make encryption functions with.

Let’s say you’ve got team red, who has a shared key with all the other reds. Then you have team blue, who has a shared key with all the other blues.

When a either team’s members talk, the speech is ran through an encryption algorithm with the shared key. When the message is broadcast to the world, only members of the same team should have the proper key to decode the message. That’s only 1 scenario where it might be useful.

Lua scripters could setup admin systems which use some form of MAC that would make spoofing nearly impossible.

#12

It can be useful when storing boolean values. In fact, entity spawnflags in Source do just that, and rely on bitwise operations to read said values.

#13

rev 10.

Small update. Added Hex2String and Bin2String functions

rev 11.

A few asserts added to a couple functions in FakeBitOps to polish it up a bit. HMAC is now -100%- (no, 50%, I just discovered a flaw, brb.)

This was an important step for this library and I want to thank anyone who’s read or downloaded it. Also, those that have offered constructive criticism.

FakeBitOps and FakeCrypto are going to work their way past the functionality of gm_crypto and should work on ANY stock implementation of lua. (So long as it supports x amount of string functions, tables, etc, etc.

Since it’s NEW BSD, anyone is welcome to use it in their scripts. And with hmac done, it adds new possibilities of authentication between clients and servers.

Enjoy. I’ll be working on the roadmap functions some more. If you have any requests, suggestions, queries, ideas, flames, etc, etc. Post them here.

#14

rev 12:

HMAC-SHA1 is “working” now. Writing up a file of test cases for the current crypto functions. Going to compare values to comparable functions in PHP.

Enjoy the lib so far.

Edit: I have grabbed a set of test cases for HMACSHA1, http://www.faqs.org/rfcs/rfc2202.html, and the library passes all of them until test case 6. Alterations will be necessary of the rev 12 FakeCrypto.

This means that this HMAC will work for any string that is under 64 characters.

[editline]09:53PM[/editline]

rev 13: Same as 12. With message similar to below attached. Forgot to upload the tests file.

rev 14:
Uploaded the tests file. Deleted sha1.lua from the repo permanently. FakeCrypto has sha1, it would only be confusing.
Turns out I was wrong about the HMAC implementation being wrong. However, I did find an issue with zero length strings, due to a couple asserts on HexZeroPad. This made it impossible to compute hashes for zero length strings. This is fixed in this version.

FakeTest.lua out. This version tests only the functions in FakeCrypto. More to come.

All tests are positive so far.

Leave your opinions on the project below.

#15

I’m probably missing something blindingly obvious, but couldn’t you use the built in bitwise operations?

#16

The problem is that bitwise operations aren’t built into all standard lua binaries. And while Gmod does have some bitwise operators available, it doesn’t cover enough to build cryptographic libraries from it. Another reason is the constraint of actual numbers. Hex values above 0xFFFFFFFF are not represented properly. Strings bypass this number limitation.

Gmod operators are:
| OR
& AND
<< Bit shift left
>> Bit shift right

Right off the start you can see that it’s missing XOR (unless the wiki is dreadfully incomplete, which is a problem of it’s own.)

And xor isn’t the only missing functionality. With representing binary values as straight numbers, we have absolutely 0 control of the underlying bitlength. We also have no control over the ordering of the bytes. What type of carry (or lack of carry) to use during shift operations. Etc. etc. I could go on, but I think my point has been well made. The current implementation isn’t extensive enough, or if it is, it isn’t well documented enough.

Also, in the documentation there is a note in there that says “Bitwise operators are only available in the Garry’s Mod Lua environment, although there are modules that add bitwise functions.”. Which isn’t greatly worded, as bitwise operations can be added to standard lua by compiling the BitOps module into the lua binary. Thus, for compatibility’s sake. . .

What I wanted to do is build a set of tools that not only Gmod users can utilize, but also ANY lua user out there, regardless if they compiled the binary themselves or not.

And that is this library.

Also, rev 15 is out. I introduced 2 new functions in prep for programming md5 into crypto. In FakeBitOps you’ll find Endian and HexEndian, introducing the ability to change endianness.

#17

rev 16 is out. And it’s a minor release.

I added truncation options to BinAdd, to remain compliant to the current sha1 implementation the default truncation amount is 32 and default direction is left. The amount will be changed in the next revision to matched bitstring length.

I added a md5.lua to the repo. This is not yet a working implementation, but I did put it up just in case anyone wanted to take a look at it to see if they could find what I’ve done wrong in implementing it. I am thinking it’s that my endianness doesn’t match up correctly in the upper part of the function or that my truncation of bits to the left is incorrect. Whatever the case, it’s not yet functional.

Tomorrow I’m going to make an effort to finish md5, clean each of the files code up, reorder them based on input and output types, remove any unneeded steps, add local to all things that should be local, and remove unnecessary or repetitive codeblocks. (e.g [01] 512 times as opposed to mystring:gmatch(string.rep("[0,1]",512)

After md5 (from doing md5, hmac-md5 should be done already), I’ve moved making this into a module up on the roadmap. I’m estimating around rev 20 will be the module release where you can actually start to use the full library as a module.

After the module, SHA-2 variants are scheduled to be done. SHA-256 first, then SHA-512.

After SHA-2 variants, whirlpool (if I feel like it).

After whirlpool, I will work on Blowfish, RSA, and DES.

Any requests for changes of the roadmap are welcome. Any suggestions on code cleanup, style, etc, and any other criticisms positive or negative are also welcome.

Flame away. Also, enjoy.

#18

Alright, here’s the deal.

I was working off a local copy of the svn and messed it up pretty bad (the local copy). So I updated my local repo to start over with the svn version, thus losing all my changes to FakeBitOps functions, old error checking removal, and my new assert code.

Thus, I present you with a new svn version, rev 17.

I have added a ton of new custom operators. bxor, band, bor, badd, bmul, brot, bzero, hxor, hand, hor, hadd, hmul, hrot, hzero. There are plans for more operators, like brotR to rotate to the right, bzeroR to pad to the right, etc etc.

Quick guide to using these
[lua]“1010” -bxor- “1000” --output would be “0010”
“1100” -band- “1000” --output would be “1000”
“1010” -bor- “0101” – output would be “1111”
“1010” -badd- “0110” – output would be “00010000”
“0101” -bmul- “0010” – output would be “1010”
“0101” -brot- 1 – output would be “1010”, number is amount to shift left. Carry is NO_CARRY.
“11” -bzero- 8 – output would be “00000011”, number is desired bitlength of resulting string (including current bits)
“F” -hxor- “E” --output would be “1”
“F” -hand- “A” --output would be “a”
“A” -hor- “5” --output would be “f”
“A” -hadd- “F” --output would be “19”
“5” -hmul- “4” --output would be “14”
“E” hrot 2 – output would be “b”, number is amount to shift left. Carry is NO_CARRY.
“1” -hzero- 8 – output would be “01”,number is desired bitlength (including current bits)[/lua]

The minus signs must be there. To my knowledge, there is no way around that. Or perhaps someone could point me to a better version of an ophack, instead of the Pythonic one from lua-users.

There are now far more tests in the FakeTests file. (though still very unfinished, I also haven’t tested for conditions that I have known will break functionality and will take too long to fix.)

In the FakeCrypto, I’ve replaced all the code I currently can with the new operator code. Still works, and it’s way cooler.

All gmatched strings that require more than 1 [01] or [A-Za-z0-9] have been replaced with gmatch(string.rep("[01]",number)) and gmatch(string.rep("[A-Za-z0-9]",number)).

There is a long way to go in this overhaul, so my estimate of module at rev 20 may be slightly off.

Now to get back to writing that assert code for FakeBitOps functions.

#19

This project is going on official hiatus unless someone wants to take over the repo.

It already has the functionality that I required for other projects (hmac-sha1), but is difficult to work in other hashing algorithms. I’ve tried to implement md5 4 times and sha256 4 times, however, something subtle is off in the FakeBitOps library and I don’t have all the time in the world to continue debugging it forever.

To whoever wants it, I will give project ownership rights. If nobody responds, the project will go dormant until I finish my other works.

#20

Nevermind the hiatus.

It’s my duty to get this done. I feel guilty just abandoning it while still using it for other things. So, I want everything in it to work 100%. As such, I’m reworking the entire FakeBitOps library.

I like to throw out bad code, so I’ve taken design flaw notes from the old library and deleted it from my local version of the repo.

My Essential ideas about it are:
1: There needs to be more asserting of types. Too much is slipping through on the current implementation.

2: Nil and blank string arguments should be allowed to pass through most functions.

3: Pad length should never, ever be implicit, no matter if I feed it an odd bitlength or not.

4: strings should not have to be the same lengths to operate in binary ands, ors, xors. It should instead send a string back with the length of the longest string.

5: Shortcut functions should be condensed into one function if they have similar argments and a lower function exists to point to.

  1. Numbers should be implicitly converted to hex when fed to hex functions.

  2. Numbers should be implicitly converted to binary when fed to binary functions.

So far I have done:
CouldBeHexString - tests strings for [^A-Fa-f0-9]. Short circuits true on nil, blank string or number.

CouldBeBinString - tests strings for [^01]. Returns false if it encounters any. Short circuits true on nil, blank string or number.

Number2Hex - Converts number to hex.

Number2Binary - Converts number to binary

Bin2Hex - Converts binary string to hexadecimal string. Nil and blank string safe. Implicitly converts numbers to binary (then subsequently hex)

Hex2Bin - Coverts hexadecimal string to binary string. Nil and blank string safe. Implicityly converts numbers to hex (then subsequently binary)

BAND - Binary AND. Nil and blank string safe. Implicitly converts numbers to binary.

BXOR - Binary XOR. Nil and blank string safe. Implicitly converts numbers to binary.

BOR - Binary OR. Nil and blank string safe. Implicitly converts numbers to binary.

HexOps - This is the first condensed helper function. This function replaces HexXor, HexAnd and HexOr. It’s arguments are func, hexstring1, hexstring2. Nil and blank string safe. Implicitly converts numbers to hex. Returns in hex.

MultiStringOps - This is the second condensed helper function. This function replaces MultiBinAnd, MultiBinXor, MultiBinOr, MultiHexAnd, MultiHexXor, and MultiHexOr. It’s a little bit more complicated. Here are the args and what they do:
func - The underlying function you want to use multiples of.
stype - The type of input you’ll be feeding it or output you want back. This needs to be either hexstring or bitstring and needs to match the inputs of the underlying functions. It will work on numbers, but it’s needs to be specified as bitstring or hexstring.
argstring1 - The first argument of the function, to get things rolling. It’s assigned to the local temp_str before the loop to do the work is started. This should be your first input argument.
… - Comma delimited arguments of the type that you promised stype.

If you get any of the arguments wrong, it will throw the appropriate assert with the appropriate complaint, appended to the end of every assert is the argument that failed, so you know what to look for. MultiStringOps handles nil, blank strings, and numbers like the underlying functions do.

That’s all for now. I’ll work on this more tomorrow, but it won’t be posted until I can get it working with the existing FakeCrypto lib (albeit small changes will be made)

Thanks for reading, even if you don’t care about FakeBitOps. If you don’t like it or think it unnecessary, go ahead and leave me a dumb rating, or post a flame.