[algoritme] Hash collisions

[keesdewit]

Als je van 0 tot 16^32 telt en dan voor ieder integer een MD5 hash berekent, wanneer krijg je dan de eerste collision? Wie weet hier een efficiëntere manier voor dan onderstaand?

Ik heb zelf al een generator gemaakt:

Tabel:

SQL:

CREATE TABLE [dbo].[tblHash16](
    [id] [bigint] NOT NULL,
    [hash] [char](16) NOT NULL,
 CONSTRAINT [PK_tblHash16] PRIMARY KEY CLUSTERED 
(
    [id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

Stored procedure:

SQL:

CREATE PROCEDURE [dbo].[prcGenerateHash16]
AS
    BEGIN
        DECLARE @Counter BIGINT = 0

        WHILE (@Counter < 1000000000)
        BEGIN

            INSERT INTO tblHash16 ([id], [hash]) values (@Counter, LEFT(CONVERT(nchar(32), HASHBYTES('MD5', CONVERT(varchar(7), @Counter)), 2), 16))
            SET @Counter = (@Counter + 1)
    END
END

Met deze code sla ik alleen de helft van de hash op. Alle collisions die hier uit voort komen zijn de moeite waard om volledig te hashen.

Nu loopt zo'n cursor niet zo snel, dus heb ik een console applicatie gemaakt die het hashen op zich neemt ipv sql server:

Visual Basic .NET:

    Sub Main()
        Console.WriteLine("Start")
        Dim thrd As New Threading.Thread(AddressOf StartGenerate)
        thrd.Priority = Threading.ThreadPriority.Highest
        thrd.Start()
    End Sub

    Private Sub StartGenerate()
        Using db As dbDataContext = New dbDataContext()
            Dim counter As Integer = db.GetLastHash()

            counter += 1

            Dim strHash As String = String.Empty

            For i As Integer = counter To (counter + 100000000)
                strHash = Left(GetMD5(i.ToString()), 16)
                db.InsertHash(strHash, i)
            Next
        End Using
        Console.WriteLine("Done?")
        Console.Read()
    End Sub
    Private Function GetMD5(ByVal str As String) As String
        Using pv As MD5CryptoServiceProvider = New MD5CryptoServiceProvider()
            Return BitConverter.ToString(pv.ComputeHash(System.Text.Encoding.UTF8.GetBytes(str))).Replace("-", "")
        End Using
    End Function

Dit maakte het proces 10x sneller nl. ~1200 p/s ipv 110 p/s
Als je 16^32 berekend dan kom je op 3,4028236692093846346337460743177e+38 dat zijn nogal wat hashes, in ieder geval teveel voor sql server of de methode die ik hanteer.

Wie heeft een snellere manier om collisions te vinden binnen deze integer span?

Op dit moment zit ik op: 1083501273 en er zijn nog geen collisions.

[Verwijderd]

Hoe heerlijk naïef. Brute force collisions bepalen is gewoon dom en ondoenlijk, want de algoritmes zijn erop ontworpen dat dat enigszins traag is. Collisions bepalen kun je beter doen aan de hand zwaktes in het algoritme, zoals je bijvoorbeeld hier kunt lezen.

Overigens, snap je dat je hashes van strings of string representaties van integers berekent en niet zozeer van integers zelf?

[Zoijar]

Wikipedia: Birthday problem

[Voutloos]

^ check.

Stel je kijkt in die tabel naar 50%, 64 bits (het aantal bits in linkerhelft van een md5 output). Dan weet je dus dat je 5 miljoen seconden nodig hebt om 50% kans op een collission te hebben, en dan moet je nog hopen dat de overige 64 bits ook nog kloppen. :x En dat is met de aanname dat je snelheid 1000/s blijft en niet afneemt als je meer opgeslagen hebt (grotere index, werkset past niet meer in geheugen, disk vol, whatever).

Trouwens, als je al jouw aanpak wilt blijven volgen, kan je maar beter meer parallel doen of een flinke GPU aan t werk zetten. En minder conversiestappen / efficientere opslag; een md5 als hex opschrijven is ook maar een suffe conventie, het gaat puur om 128 bits. Grappig genoeg is je char 16 juist precies 128 bits.
256^16 == 16^32 == 2^128

[ Voor 4% gewijzigd door Voutloos op 01-10-2011 14:07 ]

[keesdewit]

@Voutloos: Parallel uitvoeren gaat inderdaad sneller. 4 threads doet nu zo'n 4000 p/s. 5 miljoen seconden wordt nu dus 1.25 miljoen seconden of wel 14,5 dagen.

[Voutloos]

Blijft lang, aangezien je dan nog maar 50% kans op een collission in een halve hash hebt.
Bovendien vraag ik me af of je wel berekend hebt hoeveel storage je nodig hebt, en of je je gehannes met datatypes gefixed hebt.

Al met al zou je aanpak nog altijd gekkenwerk moeten zijn.