Läsaren A lämnade en i går en intressant kommentar med en länk till en artikel av Jean-Philippe Aumasson som i sin artikel visar att delar av artikeln om svagheter i arraybaserade strömkrypton skriven av Souradyuti och Preneel delvis är felaktig. Mer exakt är Souradyuti och Preneel attack på strömkryptot ISAAC inte korrekt, utan bygger på en feltolkning av ISAAC-algoritmen. Aumasson skriver:
At Asiacrypt’06, Paul and Preneel presented [5] (JS: Artikeln om svagheter i arraybaserade strömkrypton) distinguishers for several stream ciphers and pseudo-random generators with RC4-like construction, including ISAAC. However their analysis is based on a incorrect version of the algorithm, probably due to the hardly understandable code given in [2] (JS: Artikel av ISAACs skapare Robert Jenkins som innehåller beskrivningen av ISAAC): in their paper, at line 4 of Algorithm 3, the internal state updated is not the current one, but the next; (JS: Mitt förtydligande) they wrote “4 : m[i + 1] = . . . ” instead of “4 : m[i] = . . . ”.In ISAAC’s code, the statement *(m++) = (...) indeed affects the current value pointed by m at the expression given, then increments the pointer.
Based on this incorrect algorithm, the authors observe that the output at iteration i comes equal to 2si with probability 1 2 (1 + 2−8 ). From the bias over the parity they construct a distinguisher running in time 2**17. However this does not apply to the real algorithm of ISAAC
Hoppsan! Attackerna på andra strömkrypton, exempelvis Py pch Py6 tror jag är korrekta, men den generella problematik runt arraybaserade strömkrypton som Souradyuti och Preneel presenterar borde i och med detta få sig en törn.
En personlig reflektion är att när jag en gång i tiden implementerade ISAAC i hårdvara minns jag att jag tyckte att algoritmbeskrivningen var svår att förstå. Och att kvaliteten, eller om man så vill läsbarheten och tydligheten i beskrivningar av algoritmer varierar inser man rätt snabbt om man tittar på några olika algoritmer. NISTs beskrivningar brukar vara en fröjd att arbete med mycket detaljerade exempel, testvektorer, tips och tydliga förklaringar av nomenklatur och symboler.
Tyvärr är det sällan beskrivningarna är lika genomarbetade som NISTs, speciellt inte i konferensartiklar. I den pågående eSTREAM-utvärderingen av nya strömkrypton har detta varit ett återkommande problem. Vid utvärdering av vilka kandidater som skulle gå vidare till tredje omgången var tydlighet och hur komplett (med exempel, vektorer etc) beskrivningarna av kanditatalgoritmerna med som urvalskriterie. I utvärderingsrapporten av fas två skriver man bla:
Zk-Crypt has poor documentation. This is a great obstacle to anyone trying to attempt cryptanalysis. In particular, within a limited timeframe, anyone looking over the set of eSTREAM submissions with a view to attempting cryptanalysis on one of them, will almost certainly pick an algorithm that can be understood more readily.
Zk-Crypt gick inte heller vidare till tredje omgången.
När jag började bygga hårdvaruimplementationer av eSTREAM-kandidaterna och kom till MICKEY-128, som i sammanhanget ändå har en bra och tydlig beskrivning samt exempelkod och testvektorer, hittade jag diskrepanser mellan beskrivningen i artikeln och exempelkoden. Dessa diskrepanser (fel i beskrivningen) var tydligen ingen som utvärderat algoritmen utifrån bara artikeln noterat. Efter konversation med MICKEY-128:s skapare Steve Babbage och Matthew Dodd blev artikeln sedan upprättad.
Jag tycker att Aumassons artikel pekar på hur viktigt det är att många personer läser varandras artiklar, testar att implementera algoritmerna, gör analyser. Det är därför algoritmer som utvärderas djupare och oftare är mer trovärdiga (förutsatt att ingen har hittat några hål i algoritmen.) Krypton är skapade av människor, och människor gör ibland fel, men med fler personer, tror jag, minskar risken för att felen inte upptäcks.
Är allt nu frid och fröjd för ISAAC? Nja, inte riktigt. Aumasson visar i sin artikel att det ändå finns svagheter i ISAAC, även om dessa inte ser ut att leda till en praktisk attack. Aumasson presenterar även en variant av ISAAC kallad ISAAC+ som enligt Aumasson tar bort de svagheter han hittat.
Jag får nog ta och titta över min gamla hårdvaruimplementation av ISAAC, och om inte annat bygga om den till ISAAC+. Men det får bli senare i dag, nu är det dags att fortsätta sova (klockan är 05:15).
Stort tack till A för en ypperlig kommentar!
No related posts.
Related posts brought to you by Yet Another Related Posts Plugin.
