Performance issue

Hey,

My current solution works with nested loops, and I suppose most solutions do. So a more details description would be handy.

Here you have a stripped down version of my current code.

VB.NET:
        Private Sub LoopThroughAllCombinations()
            Dim fullPwStep As String
            Dim currentLvlPwNr As Int64

            For pwLen As Integer = CInt(numMinLenght.Value) To CInt(numMaxLenght.Value)
                fullPwStep = Me.CharSet.Right(0, 1).Repeat(pwLen).Text
                currentLvlPwNr = 0
                Do
                    Me.CurrentPassword = FromDecimal(currentLvlPwNr, Me.CharacterSet, pwLen)

                    ' Do something with the combination

                    currentLvlPwNr += 1
                Loop Until Me.CurrentPassword = fullPwStep
            Next
        End Sub

VB.NET:
        ''' <summary>Convert the value from deciaml to the to-system</summary>
        ''' <param name="value">Required. Int64. The value you want to convert</param>
        ''' <param name="toSystem">Required. String. The symbols of the system you want to convert to</param>
        Public Function FromDecimal(ByVal value As Int64, _
        Optional ByVal toSystem As String = "0123456789", _
        Optional ByVal paddingLength As Int32 = 0) As String
            Dim nrDivisions As Int32 = 0
            Dim charArr() As Char = toSystem.ToCharArray
            FromDecimal = ""

            ' Determine how many divisions will be needed
            Do
                nrDivisions += 1
            Loop Until toSystem.Length ^ nrDivisions > value

            ' Build up the string in the to-system
            For devision As Integer = nrDivisions To 1 Step -1
                FromDecimal &= charArr(CInt(CInt(value Mod toSystem.Length ^ devision) \ CInt(toSystem.Length ^ (devision - 1))))
            Next devision

            ' Return the build up string that represents the value in the to-system, and trim zero-characters at the front
            Return FromDecimal.TrimStart(charArr(0)).PadLeft(paddingLength, charArr(0))
        End Function
    End Module

I think this could be done a lot more efficient, but don't know how. Some help would be welcome :)

Cheers
BN
 
What are you trying to do? It seems like youre going to a lot of extra effort to do something like 123.ToString();
 
Might be an idea if you tell us what exactly you want to do.

BTW: "number crunching" usually is done in C (mostly with some handcoded assembler stuff). The UI can be done with VB.

If you want to crack passwords ;) look at this:
World Fastest MD5 cracker BarsWF : Svarychevski Michail Aleksandrovich
With a top notch ATI or NVidia graphics adapter you can outperform a quad hexacore xeon machine.
 
What are you trying to do? It seems like youre going to a lot of extra effort to do something like 123.ToString();
> That would only be true if the char set was equal to the symbols of the decimal system.

picoflop: I am indeed trying to make a password recovery tool.

I want it to be compatible with the majority of pc's, and don't want to go use a gfx card. I also realize this will not be the fastest tool, and that vb.net isn't the best language for this. But my goal is not to only create this app, but to learn from it how I can optimize code in vb.net :)

Cheers
BN
 
What are you trying to do? It seems like youre going to a lot of extra effort to do something like 123.ToString();
> That would only be true if the char set was equal to the symbols of the decimal system.
Congratulations on not answering the question. Would you like me to continue guessing at what your code is supposed to do?
 
If the charset was ab, it would have to output

a
b
ab
bb
aab
aba
abb
baa
bab
bba
bbb
aaaa
...

And if you look at the next phrase in my previous post, this becomes quite obvious.
 
I also realize this will not be the fastest tool
"Horribly slow" would probably describe it best.

Say you have a charset of 80 chars (uppercase + lowercase + numbers + some special chars).
A password of 5 chars would have a complexity of 80^5 which equals roughly 10^9.5 . If your "do something with the password" takes 1 ms (which is 1^-3 seconds) you would need (in average) 10^6.5 / 2 seconds. That's 18 days. With 6 chars ... multiply with 100.

So ... how fast is your "do something" code??
 
Hey,

My current implementation does about 50k combinations/second on a machine that does about 5m/s with some other apps I tried. So there is a difference of about 2 orders of magnitude.

I hardly doubt that my current implementation is the most efficient possible in vb.net. So how to improve it? :)

Cheers
BN
 
So how to improve it?
a) study mathematics, concentrate on cryptography, NEVER use "managed" code for performance optimized results.
b) check where your bottleneck is



b) you need to "check" somehow if the created password matches. Most likely this function will be the bottleneck. So regardless how fast you can "create" passwords, your performance will depend on your checking function. As long as your checking function is only a REMark, you can hardly judge if your app makes sense at all.
 
Hey,

What do you mean with "managed" code? A small example or link to article with a decent explanation would be very handy here :)

The bottle neck in this case is the password generation. Hashing it and comparing it to some hash takes some time right, but less then generating the password. The comparison also offers less room for improvement as long as I keep working in vb.net I suspect.

This is the reason why I posted an article about looping through combinations, and not password cracking. I have not posted all code cause it is not well documented at the moment, also quite messy, is over 1400 lines long, and uses several other custom classes.

Just to be sure I did not do anything retard in the comparison part I'll post that code here :D

VB.NET:
        Private Sub compareHashes()
            Dim currentHash As String

            Select Case m_hashType
                Case "MD5" : currentHash = Hasher.ToMD5Hash(Me.CurrentPassword)
                Case "MD4" : currentHash = (New Security.CryptoStr(Me.CurrentPassword)).ToMD4Hash().Text
                Case "RIPEMD160" : currentHash = Hasher.ToRIPEMD160Hash(Me.CurrentPassword)
                Case "SHA1" : currentHash = Hasher.ToSHA1Hash(Me.CurrentPassword)
                Case "SHA256" : currentHash = Hasher.ToSHA256Hash(Me.CurrentPassword)
                Case "SHA384" : currentHash = Hasher.ToSHA384Hash(Me.CurrentPassword)
                Case "SHA512" : currentHash = Hasher.ToSHA512Hash(Me.CurrentPassword)
            End Select

            Dim hashNr As Int32 = 0

            While hashNr < Me.RemainingHashesAmount
                If m_remainingHashes(hashNr) = currentHash Then
                    m_crackedHashes.Add(New Hash(m_remainingHashes(hashNr), Me.CurrentPassword))
                    Debug.WriteLine(m_remainingHashes(hashNr) & ": " & Me.CurrentPassword)
                    m_remainingHashes.Remove(m_remainingHashes(hashNr))
                    displayHashResult(m_crackedHashes(Me.CrackedHashesAmount - 1))
                End If
                hashNr += 1
            End While
        End Sub
 
To give you an idea:

VB.NET:
Public Class PasswordFinder

    Private Const AllowedChars As String = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
    Private Const CharsetSizeMinus1 As Integer = 61
    Private TheCharset() As Byte
    Private HashToSearch() As Byte
    Private TheHasher As New System.Security.Cryptography.MD5CryptoServiceProvider

    Public Sub New()
        If CharsetSizeMinus1 + 1 <> AllowedChars.Length Then Throw New Exception("Make sure that charsetsize is correct!")
        ' Fill our charset array
        ReDim TheCharset(AllowedChars.Length - 1)
        For i As Integer = 0 To AllowedChars.Length - 1
            TheCharset(i) = Asc(AllowedChars.Substring(i, 1))
        Next
    End Sub

    Public Sub test()

        Dim pw As String = "9999"   ' worst case in current setup
        Dim encoding As New System.Text.ASCIIEncoding()
        HashToSearch = TheHasher.ComputeHash(encoding.GetBytes(pw))
        Dim t As Date = Now
        FindPassword(4)
        MsgBox("Found in " & (Now - t).Duration.ToString)

    End Sub

    Private Function FindPassword(ByVal MaxLength As Integer) As Boolean

        If MaxLength < 1 Or MaxLength > 8 Then Throw New Exception("bump")

        Dim count As Integer = MaxLength
        Dim offset As Integer = 8 - MaxLength
        Dim b(7) As Byte
        Dim h() As Byte
        Dim i As Integer
        Dim i7 As Integer, i6 As Integer, i5 As Integer, i4 As Integer
        Dim i3 As Integer, i2 As Integer, i1 As Integer, i0 As Integer

        For i3 = 0 To CharsetSizeMinus1
            b(3) = TheCharset(i3)
            For i4 = 0 To CharsetSizeMinus1
                b(4) = TheCharset(i4)
                For i5 = 0 To CharsetSizeMinus1
                    b(5) = TheCharset(i5)
                    For i6 = 0 To CharsetSizeMinus1
                        b(6) = TheCharset(i6)
                        For i7 = 0 To CharsetSizeMinus1
                            b(7) = TheCharset(i7)
                            h = TheHasher.ComputeHash(b, offset, count)
                            ' compare the two hashes:
                            For i = 0 To 15
                                If h(i) <> HashToSearch(i) Then GoTo notfound
                            Next
                            ' if we are here, we found the hash
                            ' we need to save the found pw and do other stuff,
                            ' but for now we simply ...
                            Return True
notfound:
                        Next i7
                        If MaxLength = 1 Then GoTo final
                    Next i6
                    If MaxLength = 2 Then GoTo final
                Next i5
                If MaxLength = 3 Then GoTo final
            Next i4
            If MaxLength = 4 Then GoTo final
        Next i3
        If MaxLength = 3 Then GoTo final
final:
        Return False ' should never be reached of course

    End Function

End Class
In debug mode and on my little notebook, it takes 2 minutes 35 seconds to find the worst case 4 char password.
I have ommited the i2 to i0 loops - trivial to add.

Options for improvement:
- create single functions for each pw-len. This removes the "if maxlength" checks.
- find a faster hash-compare function
- if multicore, use single functions that check half of the charset, or a quarter or whatever the number of cores is.
- play with private, public, shared, const etc declarations
- ???

Basically improving speed can be done by bloating the code with copy&paste work. As a rule of thumb: You pay for improvement in performance with code size.

btw: your original code works with "string". The hasing function work on byte level, so creating a string that later has to be converted to byte does not make sense.


EDIT:
With all optimizations, I hardly get any improvement.
If I comment the "computhash" part and work with an empty h() (which of course never matches) the app runs around .23 seconds. So obviously the password CREATION is not the problem, but the CHECKING. I guess I already said that in the beginning.
To improve: Switch to unmanaged C/C++ ;)
 
Last edited:
Hey,

I was apparently indeed wrong about the bottleneck. Just tested it again:
~5 minutes to get to 9999 with similar setup
~1 minute to get to 9999 with no hash function

This indicates that the implementation you posted is about 2x as fast (even though I run it on a 2.3ghz quad core), and that your password generation is massively faster then mine (so there is room there for improvement after all :)).

I'll have a look into your suggestions and post my results here as soon as I have them. Thnx for the support so far :D

EDIT: just to get an idea (how bad my current code is :p), here you have a little graph of the performance of my app:
viewtopic.php


Cheers
BN
 
I meant to post this this morning but I got busy. It generates about 2 million passwords a second on my 1.86 Core Solo laptop in debug mode. Release mode (optimized/inlined code) may be quicker. The code is also a lot simpler than most in this thread :)

As for bugs.. Well.. Who knows? It seems to work!


If you streamline it so it works only with byte arrays, and not using strings at all it will probably be faster
 

Attachments

  • CharPerm.zip
    14.8 KB · Views: 23
Back
Top