[VB6] AHM! (Another Hashing Method)

[Joe]

I wrote another hashing method, and this time its rather decent, IMO. Comment, if thou dare! =)

Code: [Select]

Option Explicit

Private Const Alphabet = "3412785609PLMZAQWSXMKONJIEDCVFRBUHTFCVGY"

Public Function Hash(S As String) As String
    Dim Ret As String, Ret2 As String, i As Byte, V1 As Byte, V2 As Byte
   
P1: For i = 1 To Len(S)
        Let V1 = Asc(Mid(S, i, 1)) Mod 34
        Let V2 = Int(Asc(Mid(S, i, 1)) / 34)
        Let Ret = Ret & Chr((V1 + V2) Mod 128)
    Next i
   
P2: For i = 1 To Len(Ret) Step 2
        If Len(Ret) < i + 1 Then GoTo P3
        Let V1 = Asc(Mid(Ret, i, 1))
        Let V2 = Asc(Mid(Ret, i + 1, 1))
        Ret2 = Ret2 & Chr(V1 + V2)
    Next i
   
P3: Let Ret = Ret2: Let Ret2 = vbNullString
    For i = 1 To Len(Ret)
        Let V1 = Asc(Mid(S, i, 1)) Mod 34
        Let V2 = Int(Asc(Mid(S, i, 1)) / 34)
        Let Ret2 = Ret2 & Chr(V1) & Chr(V2)
    Next i
   
    Let Hash = MakeReadable(Pad(Ret2))
End Function

Private Function Pad(S As String) As String
    Randomize: Dim i As Byte, Padding As String
   
    For i = 1 To 128
        Let Padding = Padding & Chr(i + 127)
    Next i
   
    Let Pad = Left(S & Padding, 128)
End Function

Private Function MakeReadable(Data As String) As String
    Dim Ret As String, i As Integer
    For i = 1 To Len(Data)
        Let Ret = Ret & Mid(Alphabet, Val(Asc(Mid(Data, i, 1)) Mod Len(Alphabet)) + 1, 1)
    Next i
    Let MakeReadable = Ret
End Function

Code: [Select]

Hash("joetheodd")

Code: [Select]

0000:  37 32 39 32 48 31 41 32 30 39 50 4C 4D 5A 41 51   7292H1A209PLMZAQ
0010:  57 53 58 4D 4B 4F 4E 4A 49 45 44 43 56 46 52 42   WSXMKONJIEDCVFRB
0020:  55 48 54 46 43 56 47 59 33 34 31 32 37 38 35 36   UHTFCVGY34127856
0030:  30 39 50 4C 4D 5A 41 51 57 53 58 4D 4B 4F 4E 4A   09PLMZAQWSXMKONJ
0040:  49 45 44 43 56 46 52 42 55 48 54 46 43 56 47 59   IEDCVFRBUHTFCVGY
0050:  33 34 31 32 37 38 35 36 30 39 50 4C 4D 5A 41 51   3412785609PLMZAQ
0060:  57 53 58 4D 4B 4F 4E 4A 49 45 44 43 56 46 52 42   WSXMKONJIEDCVFRB
0070:  55 48 54 46 43 56 47 59 33 34 31 32 37 38 35 36   UHTFCVGY34127856
EDIT -
And if you want to send this over a network, you can hash to DWORD[32]. I suppose inserting the normal hash as a Non-NTString works too, but thats beside the point. =)

Code: [Select]

Public Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (ByRef Destination As Any, ByRef Source As Any, ByVal numBytes As Long)

Public Function HashAsDWORD(S As String) As Long()
    Dim Hashed As String: Let Hashed = Hash(S)
    Dim Ret(32) As Long
   
    For i = 1 To 128 Step 4
        Ret(i) = GetDWORD(Mid(Hashed, i, 4))
    Next i
   
    Let HashAsDWORD = Ret
End Function

Public Function GetDWORD(Data As String) As Long
    Dim lReturn As Long
    Call CopyMemory(lReturn, ByVal Data, 4)
    GetDWORD = lReturn
End Function

[iago]

www.javaop.com/~iago/joehash.bas

To summarize, working backwards:
- MakeReadable does nothing secure.  All characters will be less than 34, and the "Language" is longer than 34.
- Pad does nothing.  Since the characters are sequential, it's easy to eliminate

- P3 and P1 are full of collisions, which is a weakness.  And any output character can be narrowed down to 2 characters.  That's easily bruteforced, since it'll take len(fullstring) ** 4 guesses, which isn't terribly high unless you're hashing huge amounts of data.  Even then, you could probably do some statistical checking. 
- P2 is also full of collisions.  Besides that, it does nothing but sum every pair of characters.  That can be again narrowed down to a polynomial number of guesses. 

Better than your last one, though :-P

(No, I'm not going to write a proof-of-concept dehasher or hash-cloner)

[Joe]

Eh, I terminated it at 16 characters and made my brother a password for MSN by hashing his name. MSN rated it a "medium" security password.

EDIT -
MakeReadable() was meant to make it plain text, as it would spit out some nice, non-plain-text results. It wasn't meant to randomize it any.
Pad() was meant to pad it, not randomize it. That way all the results are the same length, and can be, for example, inserted in a DWORD[32] array instead of specifing the length of the array.

[iago]

Eh, I terminated it at 16 characters and made my brother a password for MSN by hashing his name. MSN rated it a "medium" security password.

EDIT -
MakeReadable() was meant to make it plain text, as it would spit out some nice, non-plain-text results. It wasn't meant to randomize it any.
Pad() was meant to pad it, not randomize it. That way all the results are the same length, and can be, for example, inserted in a DWORD[32] array instead of specifing the length of the array.

Then why use a weird character string?  Why not map them to ABC..Z?

And why not pad it with "0"'s, after it's completed?  Or why not pad with values before starting? 

[Joe]

Then why use a weird character string?  Why not map them to ABC..Z?

Because the way I pad it, the padding would be ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890ABCD etc. This way, looks semi-random at first sight, so you can't find the length of the original string without at least a bit of effort.

And why not pad it with "0"'s, after it's completed?

Again, the hashed string (before padding) is the same length as the original string (I think?) so padding it with 0's makes the original length rather obvious.

Or why not pad with values before starting?

I'd have to cast it to Byte[128] instead of a string. No real disadvantage, but that'd be annoying.

[iago]

Also, what happens if they put a string of 1000 characters? The returned string would be 1000 characters, and wouldn't fit into your pretty little 128-byte paradigm?

[Joe]

Pad() would terminate it at 128 bytes. =)

[iago]

But what if the original string is too long?  Pad() wouldn't add anything, but your new string would still be longer than 128!

[Joe]

VisualBasic uses unicode C-Style strings, so it won't be terminated until it gets to a null terminator. Also, a Chr(0) won't be recongnized as a NT, for some reason I don't understand. Hence, there is no maximum length string. If you were to pass a string more longer than the ammount of RAM you have, however, you simply need to get a hobby.

[MyndFyre]

VisualBasic uses unicode C-Style strings, so it won't be terminated until it gets to a null terminator. Also, a Chr(0) won't be recongnized as a NT, for some reason I don't understand. Hence, there is no maximum length string. If you were to pass a string more longer than the ammount of RAM you have, however, you simply need to get a hobby.

You can easily pass a string beyond the amount of RAM you have; that is why Windows uses Virtual Memory (I thought that you were into OS development, Joe).

[Joe]

Well, it would need to be loaded in physical ram to be used, wouldn't it? I suppose you could push the beginning to VRAM and load the ending, but thats a little nutty. Alright, the least memory any computer still in (everyday) use is 64MB, agree? Are you really going to waste your day generating and passing a 64MB string? Power users have 512MB or more of RAM, which would be even more silly.

[MyndFyre]

It wouldn't be too bad.  I've memory-mapped a file to fill up my hard drive (so that I could fill up the space so I could defrag it better).  I could quickly generate a full 16gb file in under a minute, writing 0s to it the entire file.

[Joe]

Come to think about it, thats a great idea! =)

[iago]

VisualBasic uses unicode C-Style strings, so it won't be terminated until it gets to a null terminator. Also, a Chr(0) won't be recongnized as a NT, for some reason I don't understand. Hence, there is no maximum length string. If you were to pass a string more longer than the ammount of RAM you have, however, you simply need to get a hobby.

No, VB doesn't use C-Style strings.  VB-strings are prepended with the length, then the string itself with no terminator.  Something like:
"26abcdefghijklmnopqrstuvwxyz" for the string "abcdefghijklmnopqrstuvwxyz". 

And the point was, the reason you said you padded it was "Pad() was meant to pad it, not randomize it. That way all the results are the same length, and can be, for example, inserted in a DWORD[32] array instead of specifing the length of the array".  However, if the string you're attempting to hash is overly long, it's not going to fit into a 128-byte structure.  What that means is that it will probably get truncated, causing a whole mess of collision-issues with long strings. 

[MyndFyre]

VisualBasic uses unicode C-Style strings, so it won't be terminated until it gets to a null terminator. Also, a Chr(0) won't be recongnized as a NT, for some reason I don't understand. Hence, there is no maximum length string. If you were to pass a string more longer than the ammount of RAM you have, however, you simply need to get a hobby.

No, VB doesn't use C-Style strings.  VB-strings are prepended with the length, then the string itself with no terminator.  Something like:
"26abcdefghijklmnopqrstuvwxyz" for the string "abcdefghijklmnopqrstuvwxyz". 

And the point was, the reason you said you padded it was "Pad() was meant to pad it, not randomize it. That way all the results are the same length, and can be, for example, inserted in a DWORD[32] array instead of specifing the length of the array".  However, if the string you're attempting to hash is overly long, it's not going to fit into a 128-byte structure.  What that means is that it will probably get truncated, causing a whole mess of collision-issues with long strings. 

Come to think of it, I don't think VB uses Unicode, either.  I'm fairly certain it only uses either plain ASCII or the system-dependent value.

[Joe]

From disassembling stealthbot, strings looked like

00 XX 00 XX 00 XX 00 XX 00 XX

Where XX is whatever character goes there, thats unicode right?

[MyndFyre]

Code: [Select]

.text:004015F0 aHelloWorld:                            ; DATA XREF: .text:004019A5o
.text:004015F0                 unicode 0, <Hello, world!>,0
Huh, my mistake.  But no VB6 program comes with unicows.dll (the MS Unicode Extensions DLL for Win9x).  The VB runtime must do all the marshalling then.

That almost suprises me.