Vraag Kan een SHA-1-hash allemaal nullen zijn?


Is er een invoer die door SHA-1 wordt berekend tot een hexwaarde van veertig nullen, d.w.z. "0000000000000000000000000000000000000000"?


27
2017-12-14 17:39


oorsprong


antwoorden:


Ik denk het niet.

Er is geen eenvoudige manier om te laten zien waarom het niet mogelijk is. Als dat het geval was, zou dit zelf de basis zijn van een algoritme om botsingen te vinden.

Langere analyse:

De voorbewerking zorgt ervoor dat er altijd minstens één is 1 bit in de invoer.

De loop over w[i] zal de originele stroom alleen laten, dus er is minstens één 1 bit in de invoer (woorden 0 tot 15). Zelfs bij een slim ontwerp van de bitpatronen, moeten ten minste enkele van de waarden van 0 tot 15 niet-nul zijn, omdat de lus geen invloed op hen heeft.

Notitie: leftrotate is rond, dus er gaan geen 1 bits verloren.

In de hoofdlus is het gemakkelijk te zien dat de factor k is nooit nul, dus temp kan niet nul zijn, omdat alle operanden aan de rechterkant nul zijn (k nooit is).

Dit laat ons de vraag of je een bitpatroon kunt maken waarvoor (a leftrotate 5) + f + e + k + w[i] geeft 0 terug door de som te overlopen. Hiervoor moeten we waarden vinden voor w[i] zoals dat w[i] = 0 - ((a leftrotate 5) + f + e + k)

Dit is mogelijk voor de eerste 16 waarden van w[i] aangezien u volledige controle over hen hebt. Maar de woorden 16 tot 79 zijn opnieuw gemaakt door xorde eerste 16 waarden.

Dus de volgende stap zou kunnen zijn om de loops af te rollen en een systeem van lineaire vergelijkingen te maken. Ik laat dat als een oefening voor de lezer ;-) Het systeem is interessant omdat we een lus hebben die extra vergelijkingen creëert totdat we een stabiel resultaat krijgen.

In principe is het algoritme zo gekozen dat je individuele 0 woorden kunt creëren door invoerpatronen te selecteren, maar deze effecten worden gecounterd door xorde invoerpatronen om de 64 andere ingangen te creëren.

Slechts een voorbeeld: maken temp 0, we hebben

a = h0 = 0x67452301
f = (b and c) or ((not b) and d)
  = (h1 and h2) or ((not h1) and h3)
  = (0xEFCDAB89 & 0x98BADCFE) | (~0x98BADCFE & 0x10325476)
  = 0x98badcfe
e = 0xC3D2E1F0
k = 0x5A827999

wat ons geeft w[0] = 0x9fb498b3, etc. Deze waarde wordt dan gebruikt in de woorden 16, 19, 22, 24-25, 27-28, 30-79.

Woord 1 wordt op dezelfde manier gebruikt in de woorden 1, 17, 20, 23, 25-26, 28-29, 31-79.

Zoals je ziet, is er veel overlap. Als u de invoerwaarde berekent die u een 0-resultaat zou geven, heeft die waarde uiteindelijk invloed op 32 andere invoerwaarden.


10
2017-09-24 13:32



Ja, het is ongelooflijk onwaarschijnlijk. D.w.z. een op de 2 ^ 160 of 0.00000000000000000000000000006842277657836021%.


18
2017-12-14 17:42



Omdat SHA1 cryptografisch sterk is, zou het ook rekenkundig onhaalbaar zijn (althans met de huidige computertechnologie - alle weddenschappen zijn uit voor opkomende technologieën zoals quantum computing) om erachter te komen welke gegevens zouden resulteren in hash helemaal nul, totdat dit in de praktijk is gebeurd. als jij werkelijk moet de "0" -hash gebruiken als een schildwacht en zorg ervoor dat u een juiste bewering invoegt (dat u niet alleen hash-invoergegevens hebt ingevoerd in uw "nul" hash-schildwacht) die overleeft in productie. Het is een faaltoestand waar uw code permanent op moet letten. WAARSCHUWING: uw code zal permanent worden verbroken als dit het geval is.

Afhankelijk van uw situatie (als uw logica de lege tekenreeks als een speciaal geval kan verwerken om het van invoer te verbieden), kunt u de SHA1-hash ('da39a3ee5e6b4b0d3255bfef95601890afd80709') van de lege reeks gebruiken. Het is ook mogelijk om de hash te gebruiken voor elke string die zich niet in uw inputdomein bevindt, zoals sha1 ('a') als uw invoer numeriek is als een invariant. Als de invoer voorbewerkt is om een ​​reguliere versiering toe te voegen, zou een hash van iets zonder de decoratie ook werken (bijv. Sha1 ('abc') als je ingangen zoals 'foo' zijn versierd met aanhalingstekens tot iets als 'foo' ' ).


14
2018-03-21 14:19



De post van Aaron klopt niet. Het wordt opgehangen aan de binnenkant van de SHA1-berekening terwijl we negeren wat er aan het einde van de ronde-functie gebeurt.

Zie in het bijzonder de pseudo-code van Wikipedia. Aan het einde van de ronde wordt de volgende berekening gedaan:

h0 = h0 + a
h1 = h1 + b 
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e

Dus een output van alle 0 kan gebeuren als h0 == -a, h1 == -b, h2 == -c, h3 == -d, en h4 == -e in deze laatste sectie gaan, waar de berekeningen mod 2 ^ 32 zijn.

Om je vraag te beantwoorden: niemand weet of er een input bestaat die alle nul-outputs produceert, maar cryptografen verwachten dat er gebaseerd is op het simpele argument van daf.


5
2017-07-10 04:12



Zonder enige kennis van SHA-1-internals, zie ik niet in waarom een ​​bepaalde waarde onmogelijk zou moeten zijn (tenzij expliciet vermeld in de beschrijving van het algoritme). Een nulwaarde is niet meer of minder waarschijnlijk dan welke andere specifieke waarde dan ook.


3
2017-12-14 17:42



In tegenstelling tot alle huidige antwoorden hier, weet niemand dat. Er is een groot verschil tussen een kansschatting en een bewijs.

Maar je kunt gerust aannemen dat het niet zal gebeuren. Sterker nog, je kunt er gerust van uitgaan dat vrijwel ELKE waarde niet het resultaat zal zijn (ervan uitgaande dat het niet is verkregen door sommige SHA-1-achtige procedures). Je kunt dit aannemen zolang SHA-1 veilig is (het is eigenlijk niet meer, tenminste in theorie).

Mensen lijken zich niet realiseerbaar hoe onwaarschijnlijk het is (als de hele mensheid al zijn huidige middelen zou richten op het vinden van een nul-hash door bruteforcing, zou het ongeveer xxx duren ... van het huidige universum om het te kraken).

Als u weet dat de functie veilig is, is het niet verkeerd om aan te nemen dat dit niet zal gebeuren. Dat kan in de toekomst veranderen, dus neem aan dat sommige kwaadwillige ingangen die waarde kunnen geven (verwijder bijvoorbeeld de HDD van de gebruiker niet als je een nul-hash vindt).

Als iemand nog steeds denkt dat het niet "schoon" is of zoiets, kan ik je vertellen dat er niets is gegarandeerd in de echte wereld, vanwege de kwantummechanica. Je neemt aan dat je niet door een stevige muur kunt lopen alleen vanwege een waanzinnig lage kans.

[Ik ben klaar met deze site ... Mijn eerste antwoord hier, ik probeerde een leuk antwoord te schrijven, maar het enige dat ik zie is een stelletje downwounder-idioten die het bij het verkeerde eind hebben en niet eens kunnen vertellen waarom ze het doen . Je gemeenschap heeft me echt teleurgesteld. Ik gebruik deze site nog steeds, maar alleen passief]


0
2018-01-03 23:34



In tegenstelling tot alle antwoorden hier, is het antwoord simpelweg Nee.

De hash-waarde bevat altijd bits die op 1 zijn ingesteld.


-3
2018-01-18 16:16