144 replies to this topic

[Laszlo]

As it stands now, MP_Init() needs only set up the machine code functions, stored in global variables. They only occupy a few dozen bytes, so there is no need to clear these variables: their names cannot be removed from the list of variables, anyway.

When the MP_ library is in a state to be beta tested, I will think about packaging it nicely. For this pre-alpha state a stand alone test script is good enough. Nevertheless, if anyone has a suggestion, I will consider it.

[daniel2]

This is amazingly brillant!

long integer arithmetic is a perfect candidate for machine code implementation

Would encryption algorithms be another good application for this?

[Laszlo]

Would encryption algorithms be another good application for this?

I am not sure. Microsoft includes AES with key management and hashing in its crypto library, which is installed automatically, at least in newer Windows versions. The necessary functions in machine code format could be several pages long, which makes the scripts ugly and slow to load.

On the other hand, XTEA (my favorite) could be coded in a couple hundred bytes, and it is secure enough for personal use. There are others, less well analyzed ciphers of even smaller code size, so your suggestion could make sense, after all.

[Laszlo]

See here the CPUID function, which is a 27 byte AHK machine code wrapper for the CPUID command of Intel compatible processors. It tells everything about the CPU, its capabilities, version number, unique ID, etc. See here the returned values for different first parameter (the info selector).

[daonlyfreez]

Very interesting.

It returns "AuthenticAMD" on my machine, yet no further information about Family/Model/Revision. Could this be implemented too?

8)

[olfen]

Hi,
I compiled this XTEA c code into a dll using gcc\MinGW:

#include <stdio.h>

#ifdef BUILD_DLL
// the dll exports
#define EXPORT __declspec(dllexport)
#else
// the exe imports
#define EXPORT __declspec(dllimport)
#endif

EXPORT void XTEA_encipher(unsigned int num_rounds, unsigned long* v, unsigned long* k) {
    unsigned long v0=v[0], v1=v[1], i;
    unsigned long sum=0, delta=0x9E3779B9;
    for(i=0; i<num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

EXPORT void XTEA_decipher(unsigned int num_rounds, unsigned long* v, unsigned long* k) {
    unsigned long v0=v[0], v1=v[1], i;
    unsigned long delta=0x9E3779B9, sum=delta*num_rounds;
    for(i=0; i<num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

and to my absolute surprise (hardly knowing c or asm) it seems to work.
But does it actually do proper XTEA, the way I DllCall it?

MCode(ByRef code, hex) { ; allocate memory and write Machine Code there
   VarSetCapacity(code,StrLen(hex)//2)
   Loop % StrLen(hex)//2
      NumPut("0x" . SubStr(hex,2*A_Index-1,2), code, A_Index-1, "Char")
}


XTEA_encipher := "5589E55383EC148B450C8B008945F88B450C83C0048B008945F4C745EC00000000C745E8B979379EC7"
. "45F0000000008B45F03B4508737D8B45F489C2C1E2048B45F4C1E80531D089C3035DF48B45EC83E0038D0C85000000008"
. "B55108B45EC03041189DA31C28D45F801108B55E88D45EC01108B45F889C2C1E2048B45F8C1E80531D089C3035DF88B45"
. "ECC1E80B83E0038D0C85000000008B55108B45EC03041189DA31C28D45F401108D45F0FF00E97BFFFFFF8B550C8B45F88"
. "9028B550C83C2048B45F4890283C4145B5DC3"

XTEA_decipher := "5589E55383EC148B450C8B008945F88B450C83C0048B008945F4C745ECB979379E8B45EC0FAF450889"
. "45E8C745F0000000008B45F03B4508737D8B45F889C2C1E2048B45F8C1E80531D089C3035DF88B45E8C1E80B83E0038D0"
. "C85000000008B55108B45E803041189DA31C28D45F429108B55EC8D45E829108B45F489C2C1E2048B45F4C1E80531D089"
. "C3035DF48B45E883E0038D0C85000000008B55108B45E803041189DA31C28D45F829108D45F0FF00E97BFFFFFF8B550C8"
. "B45F889028B550C83C2048B45F4890283C4145B5DC3"

MCode(enc, XTEA_encipher)
MCode(dec, XTEA_decipher)

; 128 bit key
VarSetCapacity(k, 16, 0)
NumPut(0x11111111, k,  0, "UInt")
NumPut(0x22222222, k,  4, "UInt")
NumPut(0x33333333, k,  8, "UInt")
NumPut(0x44444444, k, 12, "UInt")


v = Tiny !!! ; 64 bit
DllCall(&enc, int,64, uint,&v, uint,&k)
MsgBox % v
DllCall(&dec, int,64, uint,&v, uint,&k)
MsgBox % v


VarSetCapacity(v, 8, 0) ;64 bit
NumPut(1122334455667788, v, 0, "Double")
MsgBox % NumGet(v, 0, "Double")
DllCall(&enc, int,64, int,&v, int,&k)
MsgBox % "Enc: " . NumGet(v, 0, "Double")
DllCall(&dec, int,64, int,&v, int,&k)
MsgBox % "Dec: " . NumGet(v, 0, "Double")

[Laszlo]

This is great! I always wanted to code XTEA, but did not have time. Thanks!

Now we can have lightning fast cryptographically secure random number generators and encrypt messages, files at high speed.

I compared it to a Python implementation. A test case gave identical result, so we can be pretty certain that the code is OK.

MCode(enc, "5589E55383EC148B450C8B008945F88B450C83C0048B008945F4C745EC00000000C745E8B979379EC7"
. "45F0000000008B45F03B4508737D8B45F489C2C1E2048B45F4C1E80531D089C3035DF48B45EC83E0038D0C85000000008"
. "B55108B45EC03041189DA31C28D45F801108B55E88D45EC01108B45F889C2C1E2048B45F8C1E80531D089C3035DF88B45"
. "ECC1E80B83E0038D0C85000000008B55108B45EC03041189DA31C28D45F401108D45F0FF00E97BFFFFFF8B550C8B45F88"
. "9028B550C83C2048B45F4890283C4145B5DC3") ; #rounds, &data64, &key128

MCode(dec, "5589E55383EC148B450C8B008945F88B450C83C0048B008945F4C745ECB979379E8B45EC0FAF450889"
. "45E8C745F0000000008B45F03B4508737D8B45F889C2C1E2048B45F8C1E80531D089C3035DF88B45E8C1E80B83E0038D0"
. "C85000000008B55108B45E803041189DA31C28D45F429108B55EC8D45E829108B45F489C2C1E2048B45F4C1E80531D089"
. "C3035DF48B45E883E0038D0C85000000008B55108B45E803041189DA31C28D45F829108D45F0FF00E97BFFFFFF8B550C8"
. "B45F889028B550C83C2048B45F4890283C4145B5DC3")

MCode(k,11111111222222223333333344444444) ; 128 bit binary key <-- hex stream
v = Tiny !!!                  ; 8 Bytes = 64 bits
DllCall(&enc, int,64, uint,&v, uint,&k)
MsgBox % Bin2Hex(&v,8)        ; CF7B64A2AC2A9441
DllCall(&dec, int,64, uint,&v, uint,&k)
MsgBox % v                    ; original

k = 0123456789012345          ; key128 <-- string16
v = ABCDEFGH                  ; plaintext64 <-- string8
DllCall(&enc, int,32, uint,&v, uint,&k)
MsgBox % Bin2Hex(&v,8)        ; EA0C3D7C1C22557F: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496737
DllCall(&dec, int,32, uint,&v, uint,&k)
MsgBox % v


MCode(ByRef code, hex) { ; allocate memory and write Machine Code there
   VarSetCapacity(code,StrLen(hex)//2)
   Loop % StrLen(hex)//2
      NumPut("0x" . SubStr(hex,2*A_Index-1,2), code, A_Index-1, "Char")
}

Bin2Hex(addr,len) {
   Static fun
   If (fun = "") {
      h=8B4C2404578B7C241085FF7E2F568B7424108A06C0E8042C0A8AD0C0EA052AC2044188018A06240F2C0A8AD0C0EA052AC2410441468801414F75D75EC601005FC3
      VarSetCapacity(fun,StrLen(h)//2)
      Loop % StrLen(h)//2
         NumPut("0x" . SubStr(h,2*A_Index-1,2), fun, A_Index-1, "Char")
   }
   VarSetCapacity(hex,2*len+1)
   dllcall(&fun, "uint",&hex, "uint",addr, "uint",len, "cdecl")
   VarSetCapacity(hex,-1) ; update StrLen
   Return hex
}

XTEA works with 32-bit integers. We have a choice, how to encode them into byte streams. The MCode function uses big endian coding, that is, the most significant byte is written first, to the left (big end first = big endian). Others might use little endian encoding, which can present a problem if you want to exchange encrypted data or keys: you have to cut them into 4-byte chunks (8 hex digits), and reverse the byte order in these blocks.

The following function can come handy, in this case:

Hex2Ints(ByRef code, hex) { ; allocate memory and write little endian integers there
   VarSetCapacity(code, 4 * (n := ceil(StrLen(hex)/8)) )
   Loop %n%
      NumPut("0x" . SubStr(hex,8*A_Index-7,8), code, 4*A_Index-4, "UInt")
}

Another test case from the Python recipe:

>>> z = 'b67c01662ff6964a'.decode('hex')
>>> xtea_decrypt('0123456789012345',z)
'ABCDEFGH'

It can be coded in AHK the following way:

k = 3210765410985432          ; key128 <-- string16 (big endian: 0123456789012345)
Hex2Ints(v,"b67c01662ff6964a") ;compare decrypt to known value:
DllCall(&dec, int,32, uint,&v, uint,&k)
MsgBox % v                    ; DCBAHGFE (big endian: ABCDEFGH)

It also gives the right answer, providing another evidence that olfen's XTEA machine code functions are correct.


Base64 codec, CRC32 are two similar, very useful functions. Any takers?

CBC mode encryption/decryption with XTEA could also be used often. Larger data could be encrypted without AHK loops, the integrity of files could be verified, files could be compared, etc.

Edit 20070919: added notes about endiannes

[majkinetor]

Can this process of converting C function to hexa representation of machine code can be automated some way ?

For instance little converter that will take c function, compile it (lets say that tiny c compiler), disasm it, and give us just text to copy paste.

[olfen]

Can this process of converting C function to hexa representation of machine code can be automated some way ?

For instance little converter that will take c function, compile it (lets say that tiny c compiler), disasm it, and give us just text to copy paste.

That should be feasible, but before posting corresponding code, I would like to test, if it is possible to directly get the machine code from a Dll via GetProcAddress and Laszlo's Bin2Hex.

[Laszlo]

Sure, it can be automated, but it is not that simple. I've found no way to force VS'05 or the gcc compiler to inline everything, and if it breaks up the code to subroutines, you have to manually patch the code with short relative addresses, etc. Or, tweak the source code, until it has no subroutines, external references. (I spent several days to code up the long integer division using floating point instructions: the compiler always wanted to call its static library functions.) TCC gives unnecessarily long source code (sometimes by a factor of 2 or more), so I turned to VS'05. It has a free version, you don't need a Unix box (like MinGW), its assembler syntax is much simpler…

I do use a few hotkeys, though. When the C function is compiled, a disassembler is called, its result is saved in a text file, opened in notepad, the function name is searched for, but I manually mark the instructions to the end of the function (there could be more than one returns). Another hotkey copies the instructions and converts them to hex streams, breaks it up to manageable length lines to be pasted in the AHK script. Learning all the quirks of the hotkeys takes more time than do the whole process manually, unless you plan to code dozens of machine code functions. Do you?

[majkinetor]

Or, tweak the source code, until it has no subroutines, external references.

I assumed c function doesn't depend on c stdlib nor it uses anything appart standard C language and/or API functions.

but I manually mark the instructions to the end of the function (there could be more than one returns)

Of course, but perhaps some other disam marks explicitely end of the function or you can put some special instruction before final ret and search for it.

Learning all the quirks of the hotkeys takes more time than do the whole process manually, unless you plan to code dozens of machine code functions. Do you?

Your hotkies are fine, but its your thing, and I don't want to learn them, I prefer more practical solution. I don't plan to create dozens of machine code functions now as I don't have practical way to do it, and its tiresome to do it all manualy, but If I have some nice automated script to do it for me, it would be nice and I would think about this solution for my projects much more.

So, lets analyse your routine.

When the C function is compiled, a disassembler is called, its result is saved in a text file, opened in notepad, the function name is searched for, but I manually mark the instructions to the end of the function

1. Have a GUI with HiEdit control to nicely color your C code. Besides it, have a button "2Hex"
2. When pressed 2Hex adds special instruction before closing bracket of the function, something that will be easily recognised (NOP maybe, perhaps something else, like some rarely used instruction..) then :
3. Compile using env variables for free MS compiler
4. Call dissassembler
5. Search the code for you function name and extract up to the special instruction + 1 line
6. Call ahk function (your current hotkey) that converts ASM instructions to text

[Laszlo]

I assumed c function doesn't depend on c stdlib nor it uses anything appart standard C language and/or API functions.

Try a simple shift of a 64-bit number. The compiler includes several unnamed functions to the exe (or dll). There are no external references, these functions are in the code, but in different places. If you want machine code, you have to copy them after each other, and edit the addresses. It is hard and error prone.

2. When pressed 2Hex adds special instruction before closing bracket of the function, something that will be easily recognised (NOP maybe, perhaps something else, like some rarely used instruction..)

Unfortunately, the optimizer could remove unnecessary instructions, rearrange lines, writes some of its code after your marker instruction, etc. I could not make it work, but did not spend too much time with it. If someone can, it would be really useful to automate the process.

[olfen]

I put together a script to get the machine code from a dll without using a disassembler. It works with the dll i made for implementing XTEA.
For getting enough offsets to calculate the length of the machine code to extract, the dummy function "add" was added.
The script will only work if the functions are stored consecutively in the dll.
Given the intricacies pointed out by Laszlo its usefullness is probably very limited. :?

hModule := DllCall("LoadLibrary", "str", "tst.dll")

Exports = add,XTEA_decipher,XTEA_encipher

Loop, parse, Exports, `,
{
  ExportsList .= DllCall("GetProcAddress", Uint,hModule, Str,A_LoopField) . "|" . A_LoopField . "`n"
  #Exports++
}

Sort, ExportsList
MsgBox % ExportsList
StringReplace, ExportsList, ExportsList, `n , |, All 
StringSplit, ex, ExportsList, |


tmp := #Exports
Loop % #Exports - 1
{
  b_ind := (tmp * 2) - 1
  b := ex%b_ind%
  
  a_ind := (tmp * 2) - 3
  a := ex%a_ind%
  
  len := b - a
  f_ind := b_ind - 1
  fn := ex%f_ind%
  MsgBox % fn . "`n`n" . Bin2Hex(a ,len)
  
  tmp--
}

DllCall("FreeLibrary", "UInt", hModule)




Bin2Hex(addr,len) { 
   Static fun 
   If (fun = "") { 
      h=8B4C2404578B7C241085FF7E30568B7424108A168AC2C0E804463C0976040437EB02043080E20F88018AC2413C0976040437EB0204308801414F75D65EC601005FC3 
      VarSetCapacity(fun,StrLen(h)//2) 
      Loop % StrLen(h)//2 
         NumPut("0x" . SubStr(h,2*A_Index-1,2), fun, A_Index-1, "Char") 
   } 
   VarSetCapacity(hex,2*len+1) 
   dllcall(&fun, "uint",&hex, "uint",addr, "uint",len, "cdecl") 
   VarSetCapacity(hex,-1) ; update StrLen 
   Return hex 
}

[Laszlo]

Added notes about data exchange between little endian and big endian XTEA implementations.

[majkinetor]

2Laszlo

I forgot for a second the fact that compilers do mass of things on their own and look at the things too optmisiticaly.

About funny instruction, its just a matter of trial and error to see which instruction is the one that doesn't get touched by particular compiler, but give other reasons you gave, it looks like minor problem...

So, we basicly need something that will unite dependencies of a function, either by injection the code of referented functions into it or by including referenced code parts in text (which probably means fixing old addressses). Seems like a lot of things to do. Perhaps there is somewhere out, some utility doing such thing... :roll: or maybe some compiler with fancy options.