SHA-familie

De SHA-familie (Secure Hash Algorithm) is een verzameling gerelateerde cryptografische hashfuncties ontworpen door de Amerikaanse National Security Agency en gepubliceerd door het Amerikaanse National Institute of Standards and Technology.

Het doel van deze algoritmen is het berekenen van een verkorte versie van een reeks tekens, een "samenvatting" (Engels: digest), die met een hoge mate van waarschijnlijkheid uniek is voor een gegeven tekenreeks, de "boodschap" (Engels: message). Deze algoritmen heten "veilig", in de bewoordingen van de standaard: "voor een gegeven algoritme is het berekeningstechnisch onuitvoerbaar om:

1. een boodschap te vinden die een gegeven samenvatting oplevert, of
2. twee verschillende boodschappen te vinden die dezelfde samenvatting opleveren.

Elke willekeurige verandering van de boodschap zal met een hoge mate van waarschijnlijkheid een andere samenvatting opleveren."

Vanaf 2020 wordt SHA-1 als onveilig beschouwd, zoals MD5. Met de introductie van de zogenaamde Shambles aanval is er sprake van een praktisch en volledige aanval op de SHA-1 hash functie. Anders gezegd: alle aanvallen die sinds 2007 toepasbaar zijn op MD5 zijn nu ook van toepassing op SHA-1.

Het eerste lid in de familie werd in 1993 gepubliceerd en heet officieel SHA. Vandaag wordt deze echter vaak onofficieel SHA-0 genoemd om verwarring met zijn opvolgers te voorkomen. Twee jaar later werd SHA-1 gepubliceerd. Sindsdien zijn nog vier varianten gepubliceerd met grotere bereiken en een licht veranderd ontwerp: SHA-224, SHA-256, SHA-384 en SHA-512 (soms worden deze samengevat onder de naam SHA-2).

Op 2 oktober 2012 selecteerde NIST KECCAK als het algoritme dat gebruikt zal worden voor SHA-3. KECCAK werd ontwikkeld door de Italiaan Guido Bertoni en de Belgen Joan Daemen, Michaël Peeters en Gilles Van Assche.

SHA-0 en SHA-1

Eén iteratie in de SHA-1-hashfunctie. A, B, C, D en E zijn 32-bit woorden die de staart vormen; F is een niet-lineaire functie die varieert; <<< stelt een linker rotatie voor. K_t is een constante.

De oorspronkelijke specificatie van het algoritme, SHA(-0), werd in 1993 gepubliceerd als de Secure Hash Standard in de Amerikaanse FIPS-standaard PUB 180. Kort na publicatie trok de NSA het algoritme alweer in om het te vervangen door de herziene versie die in 1995 in FIPS PUB 180-1 gepubliceerd werd, SHA-1. Volgens de NSA was de reden hiervan dat er een zwakte in het originele algoritme zat dat de cryptografische veiligheid aantastte. De NSA gaf echter geen verdere informatie over welke zwakheid nu feitelijk gecorrigeerd was. Er zijn sindsdien in zowel SHA-0 als SHA-1 zwakheden ontdekt.

SHA-0 en SHA-1 leveren een berichtsamenvatting op van 160 bits uit een bericht dat een maximumgrootte kan hebben van 2⁶⁴ bits en is gebaseerd op principes die overeenkomen met degene die door professor Ronald Linn Rivest gebruikt werden in de MD4- en MD5-berichtsamenvattingsalgoritmen.

Cryptoanalyse van SHA-0

Op CRYPTO '98 presenteerden twee Franse onderzoekers een aanval op SHA-0 (Chabaud and Joux, 1998): Het is mogelijk om botsingen te vinden met een tijdscomplexiteit van 2⁶¹; minder dan de 2⁸⁰ die een ideale hashfunctie van dezelfde grootte heeft.

In 2004 vonden Biham en Chen bijna-botsingen; twee berichten die bijna dezelfde berichtsamenvatting opleveren. In dit geval waren 142 van de 160 bits gelijk. Ze vonden volledige botsingen in een versie van SHA-0 waarvan slechts 62 van de 80 ronden doorlopen waren.

Daaropvolgend werd op 12 augustus 2004 een botsing voor het volledige SHA-0 aangekondigd door Joux, Carribault, Lemuet and Jalby. Dit werd gedaan door middel van een generalisatie van de aanval van Chabaud en Joux. Het vinden van de botsing vereiste 2⁵¹ berekeningen en zo'n 80.000 cpu-uren op een supercomputer met 256 Itanium-2-processoren.

Op 17 augustus 2004 werden op de Rumpsessie van CRYPTO 2004 voorlopige resultaten aangekondigd door Wang, Feng, Lai en Yu betreffende een aanval op MD5, SHA-0 en andere hashfuncties. De complexiteit van hun aanval op SHA-0 was 2⁴⁰, significant beter dan de aanval door het team van Joux.

In februari 2005 meldde Bruce Schneier een succesvolle aanval door Xiaoyun Wang, Yiqun Lisa Yin en Hongbo Yu die in SHA-0 botsingen zou kunnen genereren in 2³⁹ berekeningen.

Het zou goed kunnen dat een van deze aanvallen de aanval is die de NSA voorzag en dat die leidde tot het terugtrekken van SHA-0 en het uitbrengen van SHA-1.

Cryptoanalyse van SHA-1

In het licht van de resultaten van SHA-0 suggereerden sommige experts dat plannen voor het gebruik van SHA-1 in nieuwe cryptografische systemen heroverwogen dienden te worden. Nadat de resultaten werden gepubliceerd kondigde het NIST aan dat ze van plan waren het gebruik van SHA-1 tegen 2010 uit te faseren ten voordele van de SHA-2-varianten.

In 2005 publiceerden Rijmen en Oswalk een aanval op een gereduceerde versie van SHA-1 die 53 van de 80 stappen doorliep. Deze kon botsingen vinden met een complexiteit van minder dan 2⁸⁰ berekeningen.

In februari 2005 meldde Bruce Schneier een aanval door Xiaoyun Wang, Yiqun Lisa Yin en Hongbo Yu. De aanval (die nog niet gepubliceerd is of aan formele collegiale toetsing is onderworpen) zou:

• botsingen in de standaard 80-rondenversie van SHA-1 kunnen vinden met een complexiteit van 2⁶⁹ berekeningen.
• botsingen in een gereduceerde 58-rondenversie van SHA-1 kunnen vinden met een complexiteit van 2³³ berekeningen.

In de academische wereld van de cryptografie wordt iedere aanval die een tijdscomplexiteit van minder dan de verwachte tijd heeft gezien als dat een algoritme gebroken is. Dat betekent nog niet dat het ook praktisch mogelijk is de aanval uit te buiten.

Een complexiteit van 2⁶⁹ berekeningen is vooralsnog erg moeilijk, afhankelijk van de hoeveelheid tijd en geld die men hier aan wil besteden zijn hier tienduizenden tot honderdduizenden computers voor nodig. Desondanks is het niet onmogelijk dat enkele overheden of zeer grote bedrijven een dergelijke aanval uit zouden kunnen voeren. Dit veronderstelt dat een aanval te paralleliseren is, hetgeen op dit moment nog niet bekend is.

De Electronic Frontier Foundation bouwde in 1999 een DES-kraakmachine die de 2⁵⁶ DES-berekeningen in 56 uur kon uitvoeren. De machine gebruikte gespecialiseerde hardware. Gezien microprocessors naar de wet van Moore inmiddels alweer een stuk krachtiger zijn geworden, zou een dergelijke aanpak wellicht ook voor SHA-1 haalbaar kunnen zijn of binnen afzienbare tijd haalbaar worden.

Het SHA-1 Collision Search Graz-project tracht botsingen te vinden in de SHA-1 functie.

In 2020 publiceerden Gaëtan Leurent en Thomas Peyrin een 10x snellere aanval [9] en sindsdien wordt SHA-1 als onveilig beschouwd, net zoals MD5. Met de introductie van de zogenaamde Shambles aanval is er sprake van een praktisch en volledige aanval op de SHA-1 hash functie. Anders gezegd: alle aanvallen die sinds 2007 toepasbaar zijn op MD5 zijn nu ook van toepassing op SHA-1. Gaëtan Leurent en Thomas Peyrin adviseren HMAC-SHA-1 uit te faseren, en iedereen die nog SHA-1 gebruikt in actie te komen. Waar SHA-1 wordt gebruikt voor TLS, SSH en CA certificaten wordt het uitfaseren van SHA-1 als urgent beschouwd.

Langere varianten

Het NIST heeft nog drie varianten van SHA gepubliceerd, elk met langere samenvattingen. Deze worden genoemd naar de lengte van de samenvatting in bits: SHA-256, SHA-384 en SHA-512. Ze werden voor het eerst in 2001 gepubliceerd in het kladschrift FIPS PUB 180-2 waarna om toestemming en commentaar verzocht werd. Deze nieuwe hashfuncties hebben nog niet zoveel inspectie ondergaan door de publieke cryptografische gemeenschap als SHA-1 en aldus is het vertrouwen in hun cryptografische veiligheid nog minder sterk. In februari 2004 ging het bericht uit dat FIPS PUB 180-2 veranderd was waarbij een extra variant, SHA-224 werd gespecificeerd, bedoeld om overeen te komen met de sleutellengte van dubbele sleutel 3DES.

Gilbert en Handschuh (2003) hebben de nieuwere varianten bestudeerd en geen zwakheden gevonden. De consequenties van de publicatie van het team van Wang en Feng in augustus 2004 waren in september 2004 nog niet geheel duidelijk voor deze SHA-varianten.

Toepassingen

• SHA-224, SHA-256, SHA-384 en SHA-512 zijn de verplichte veilige hashfuncties voor gebruik in federale toepassingen in de V.S., inclusief gebruik door andere cryptografische algoritmen en protocollen, voor de beveiliging van gevoelige niet-geclassificeerde informatie. FIPS PUB 180-1 moedigde ook de omarming en het gebruik aan van SHA-1 door private en commerciële organisaties.
• Een doorslaggevende motivatie voor de publicatie van SHA was het DSA-algoritme, waar het in gebruik wordt genomen.
• De SHA-hashfuncties zijn gebruikt als basis voor de SHACAL-blokcijfers.
• De systemen die op de Xbox-spelcomputer voorkomen dat andere dan door Microsoft vertrouwde software geaccepteerd wordt, maken gebruik van het SHA-1-algoritme.
• Veel cryptogeldsoorten gebruiken SHA-256 hashes, zoals de Bitcoin.

Een beschrijving van SHA-1

Pseudocode voor het SHA-1-algoritme:

Opmerking: Alle variabelen hebben als type een unsigned 32-bits integer

Initialiseer variabelen:
h0 := 0x67452301
h1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x10325476
h4 := 0xC3D2E1F0

Voorbewerking:
voeg "1"-bit aan bericht toe
voeg "0"-bits aan bericht toe totdat berichtlengte mod 512 ≡ 448
voeg lengte van bericht als 64-bit big-endian integer toe aan bericht

Verwerk het bericht in opeenvolgende blokken van 512-bit:
breek bericht op in blokken van 512 bit
for ieder blok
    breek blok op in 16 32-bits big-endian woorden w(i), 0 ≤ i ≤ 15

    Breid de 16 32-bit woorden uit tot 80 32-bit woorden:
    for i from 16 to 79
        w(i) := (w(i-3) xor w(i-8) xor w(i-14) xor w(i-16)) leftrotate 1

    Initialiseer de hashwaarde voor dit blok:
    a := h0
    b := h1
    c := h2
    d := h3
    e := h4

    Hoofdlus:
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f := (b and c) or ((not b) and d)
            k := 0x5A827999
        else if 20 ≤ i ≤ 39
            f := b xor c xor d
            k := 0x6ED9EBA1
        else if 40 ≤ i ≤ 59
            f := (b and c) or (b and d) or (c and d)
            k := 0x8F1BBCDC
        else if 60 ≤ i ≤ 79
            f := b xor c xor d
            k := 0xCA62C1D6

        temp := (a leftrotate 5) + f + e + k + w(i)
        e := d
        d := c
        c := b leftrotate 30
        b := a
        a := temp

    Tel de hash van dit blok op bij het resultaat tot nog toe:
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e

digest = hash = h0 append h1 append h2 append h3 append h4 (expressed as big-endian)

Opmerking: In plaats van de formulering van de originele FIPS PUB 180-1 zoals hier getoond kan het volgende gebruikt worden om de efficiëntie te verbeteren:

(0  ≤ i ≤ 19): f := d xor (b and (c xor d))
(40 ≤ i ≤ 59): f := (b and c) or (d and (b or c))

Zie ook

• MD5
• SHA-1 Collision Search Graz

Externe links

• FIPS PUB 180-4, Secure Hash Standard (maart 2012)
• RFC 3174, US Secure Hash Algorithm 1 (SHA1)

Referenties

• Eli Biham, Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004 (to appear CRYPTO 2004) [10]
• Florent Chabaud, Antoine Joux: Differential Collisions in SHA-0. CRYPTO 1998. pp56–71
• Henri Gilbert, Helena Handschuh: Security Analysis of SHA-256 and Sisters. Selected Areas in Cryptography 2003: pp175–193