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
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
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.
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.
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?
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.
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
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
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++
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
EDIT: just to get an idea (how bad my current code is ), here you have a little graph of the performance of my app:
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
This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
By continuing to use this site, you are consenting to our use of cookies.