Kryptering med SHA256

SHA256 är inte en krypteringsalgoritm, utan en hashningsalgoritm. Både kryptering och hashning kan användas i kryptografiska sammanhang, men de är inte samma sak och används inte till samma syfte. Kryptering är en tvåvägsrelation -- med en nyckel kan du kryptera din hemliga data till ett otolkningsbart format, och med samma eller en annorlunda nyckel kan du dekryptera den krypterade datan till orginalet. Hashning å andra sidan är en enkelriktad relation -- förutom via brute-force är tanken att du bara ska kunna "kryptera" datan åt ett håll, från ursprungsformatet till ett otolkningsbart format, men inte tillbaka.

För att svara på din fråga så är programmet du länkar inkorrekt -- det innehåller ett race condition som ofta resulterar i att inte alla resultat skrivs ut. Specifikt är det följande rader som felar när programmet körs multitrådat:

byte *hash = SHA256(password, 5, 0);
if (matches(one, hash) || matches(two, hash) || matches(three, hash))
    printResult(password, hash);

I dokumentationen för SHA256 funktionen står det att "If md is NULL, the digest is placed in a static array. Note: setting md to NULL is not thread safe.". md är den tredje parametern, som i ovan kod precis sätts till just 0 (null). SHA256 lägger alltså resultatet i en global, statisk array, och om flera trådar exekverar den sektionen samtidigt kommer de skriva över samma array hejvilt. Ofta kommer en tråd skriva sitt resultat, men läsa en annan tråds resultat på raden efter. Lösningen är att allokera ut-arrayen i förväg och skicka in den som tredje parameter till SHA256, så försvinner data-racet. En alternativ lösning är att använda en mutex för att se till att bara en tråd i taget exekverar just ovanstående sektion, men det är en sämre och mer komplex lösning.

Den bästa lösningen hade nog dock varit att inte försöka skriva parallell kod i C/C++ från första början -- språken är verkligen inte gjorda för det! Bättre att använda ett språk som gör data-races omöjliga genom ett smart typsystem eller dyl., e.g. Rust som garanterar att data som är delad inte får muteras utan mutex och att data som muteras inte får delas. Ett annat språk (som dock inte är lämpligt för just systemprogrammering) är Haskell, som garanterar trådsäkerhet genom att aldrig tillåta mutation, oavsett om datan är delad eller inte.

Följande är implementation och benchmark för båda mina föreslagna lösningar. Jag har kört båda flera ggr i rad, och de ger alltid rätt svar. De kör på min server med 2st Xeon X5570 processorer, och export OMP_NUM_THREADS=16.

Lösning 1 med förallokerad ut-array till SHA256, ca. 0.6s:

int main(int argc, char **argv) {
#pragma omp parallel for
    for (int a = 0; a < 26; a++) {
        byte password[5] = { 97 + a };
        byte* one =   StringHashToByteArray("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad");
        byte* two =   StringHashToByteArray("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b");
        byte* three = StringHashToByteArray("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f");
        for (password[1] = 97; password[1] < 123; password[1]++) {
            for (password[2] = 97; password[2] < 123; password[2]++) {
                for (password[3] = 97; password[3] < 123; password[3]++) {
                    for (password[4] = 97; password[4] < 123; password[4]++) {
                        byte hash[32];
                        SHA256(password, 5, hash);
                        if (matches(one, hash) || matches(two, hash) || matches(three, hash))
                            printResult(password, hash);
                    }
                }
            }
        }
        free(one);
        free(two);
        free(three);
    }
    return 0;
}

Lösning 2 med mutex-lås (mer specifikt omp critical annotering, men i praktiken lär det vara mutex-lås), ca. 10s:

int main(int argc, char **argv) {
#pragma omp parallel for
    for (int a = 0; a < 26; a++) {
        byte password[5] = { 97 + a };
        byte* one =   StringHashToByteArray("1115dd800feaacefdf481f1f9070374a2a81e27880f187396db67958b207cbad");
        byte* two =   StringHashToByteArray("3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b");
        byte* three = StringHashToByteArray("74e1bb62f8dabb8125a58852b63bdf6eaef667cb56ac7f7cdba6d7305c50a22f");
        for (password[1] = 97; password[1] < 123; password[1]++) {
            for (password[2] = 97; password[2] < 123; password[2]++) {
                for (password[3] = 97; password[3] < 123; password[3]++) {
                    for (password[4] = 97; password[4] < 123; password[4]++) {
#pragma omp critical
                        {
                            byte* hash = SHA256(password, 5, 0);
                            if (matches(one, hash) || matches(two, hash) || matches(three, hash))
                                printResult(password, hash);
                        }
                    }
                }
            }
        }
        free(one);
        free(two);
        free(three);
    }
    return 0;
}

Som jag förväntade mig var den första lösningen överlägset den snabbaste. Låsen i den andra lade på otroligt mycket overhead -- så mycket så att den till och med är långsammare än en sekventiell version som tog ca. 4s på samma dator!

-lssl behövs inte faktiskt -- ytterligare ett fel som uppladdaren på Rosettacode gjort. Vidare innehåller libcrypto inte bara krypteringgsalgoritmer, utan även andra kryptografiska funktioner som hashningsalgoritmer.

Ja, som jag sa beror felet på ett data-race som uppstår när det citerade stycket exekveras parallellt. Kör man koden på bara en tråd kan inte data-races uppstå -- varför man kan använda mutexer för att se till att bara en tråd exekverar sektionen i taget.