AEs-Implementierung



  • Hi,

    Eine AES-Implementierung von mir. Meine erste.
    Nachdem mir das Implementieren von RSA gefallen hat, versuchte ich mich daran.

    Git-Repo:

    Geschwindigkeiten muss ich auch noch testen... mal sehen. Ist noch nicht "optimiert", das ist nur eine vorläufige Version.
    Wichtig wäre mir erstmal allgemeine Fehler auszumerzen bevor ich mich an die Optimierung mache, daher nur her mit der Kritik.

    Das ganze ist übrigens mit MinGW GCC 4.8 gemacht, in einer schlechten Mischung aus C++11 und C++98. Das muss auch noch schöner gehen, finde ich.

    Und die Kommentare sind eine Schande.



  • Was willste denn da mit Iteratoren? Der Algorithmus arbeitet ganz klar auf bits, nicht auf irgendwelchen abstrakten Objekten. 😉 Und die ganzen Templates bringen dir auch nichts, auf welchen verschiedenen Int-Typen soll das denn laufen? AES nutzt recht deutlich nur 32-bit Words an dieser Stelle. Die GF8-Klasse ist zwar eine lustige Idee, aber letztlich auch unbrauchbar, weil der allgemeine Algorithmus viel zu langsam ist. Man braucht ja nur *2 und *3 oder so, wenn ich mich richtig erinnere.

    Nur mal das, was mir beim kurzen Überfliegen aufgefallen ist.

    PS: Ich will dich nicht entmutigen, aber eine Praxistaugliche AES-Implementierung ist momentan wohl nur mit Assembler möglich. Die "naive" Implementierung (wie bei dir) ist viel, viel, viel langsamer. Es gibt einen Trick das ganze über 4 große Tabellen zu implementieren, das ist dann auch mit C++ relativ schnell, aber leider nicht mehr sicher, seit Cache-Timing Angriffe in Mode sind. Ausgefeiltere Verfahren nutzen da bit-slicing, aber ich fürchte das wird in C++ so schnell auch nichts. Zudem haben die Intel-Prozessoren AES mittlerweile in der Hardware implementiert, und dagegen kommst du ohne entsprechende intrinsics natürlich gar nicht mehr an.

    Könnte dich interessieren:
    https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
    http://eprint.iacr.org/2009/129.pdf



  • Schon mal vielen Dank für die Rückmeldung, cooky 🙂 👍
    (P.S.: Ich lache heute über deine Aussage, ich brauche zwei Wochen - das waren vier Tage :p )

    Ich wollte doch keine Praxistaugliche AES-Implementierung schreiben!
    Nein, das war erstens fürs lernen und zweitens für eine schöne Lösung.

    Tatsächlich hast du Recht, die template-isierung ist irgendwie sinnlos. Na gut, die entferne ich komplett.

    Die GF8-Klasse ist zwar eine lustige Idee, aber letztlich auch unbrauchbar, weil der allgemeine Algorithmus viel zu langsam ist.

    Welcher Algorithmus? Die Multiplikation? Kann sein.
    Die Klasse ist tatsächlich ein wenig Gegaukle gewesen 😃 , die entferne ich und schreib' mir statt der Operatorfunktion eine normale Funktion.

    Man braucht ja nur *2 und *3 oder so, wenn ich mich richtig erinnere.

    Du erinnerst dich falsch. Sobald du mit der inversen Matrix arbeitest, sind da 0xE , 0xB , usw. 😉



  • Einige Templates sind ja nun mal für die Größe des Keys. Die kann ich nicht weg machen, weil so die ganze Sache designed ist - std::array braucht eine Kompilezeit-Konstante.

    Ich hab es jetzt verbessert - wie ist es?



  • Sone schrieb:

    Du erinnerst dich falsch. Sobald du mit der inversen Matrix arbeitest, sind da 0xE , 0xB , usw. 😉

    Ja, klar, aber es sind eben trotzdem nur ein paar spezifische Werte.

    Die Keys als Arrays zu übergeben hat auch nicht wirklich nen Vorteil. Du könntest genau so gut einfach einen void* nehmen. Und was du auch ändern solltest: Mach eine Key-Klasse, die die key-expansion im Konstruktor erledigt. Dann musst du das nicht immer wieder machen, wenn du mehrere Crypter mit dem gleichen Key nutzen willst.



  • extern std::array<byte, 256> const Rcon;
    extern std::array<byte, 256> const SBox;
    extern std::array<byte, 256> const InverseSBox;
    

    Wenn es niemand benutzt, dann brauchst du es auch nicht exportieren.



  • cooky451 schrieb:

    Und was du auch ändern solltest: Mach eine Key-Klasse, die die key-expansion im Konstruktor erledigt. Dann musst du das nicht immer wieder machen, wenn du mehrere Crypter mit dem gleichen Key nutzen willst.

    Natürlich, natürlich. Du hast Recht. Das Wrappe ich dann.

    knivil schrieb:

    extern std::array<byte, 256> const Rcon;
    extern std::array<byte, 256> const SBox;
    extern std::array<byte, 256> const InverseSBox;
    

    Wenn es niemand benutzt, dann brauchst du es auch nicht exportieren.

    Du hast völlig Recht. 👍



  • So, ist on. Wie ist es jetzt?

    Ich habe das Gefühl, eigentlich sollten AddRoundKey & Co. nicht einfach einen Zeiger sondern direkt eine Referenz auf ein Key-Objekt nehmen.



  • Verstehe leider nicht genug von AES um deine Implementierung richtig kritisieren zu können - was ich sehe gefällt mir aber. 👍
    Du hast dich gewaltig gemacht im Vergleich zum Vorjahr. 😉



  • Nun, AES zu implementieren ist nicht schwer. Man muss eigentlich nur vom Paper abschreiben. 🙂



  • knivil schrieb:

    Nun, AES zu implementieren ist nicht schwer. Man muss eigentlich nur vom Paper abschreiben. 🙂

    Mehr oder weniger. Genau wie cooky. Und alle Anderen. 😃
    Nein, aber mal ehrlich - ganz ohne ist das nicht. Ich denke, keiner kann wirklich AES implementieren ohne zu wissen was ein Galoiskörper ist.
    (Edit: Hmm, doch.)
    Die Multiplikation hat mir schon ein ganz klein wenig zu schaffen gemacht - dass dafür so ein richtiger Algo nötig ist, ahnte ich nicht.
    Ich dachte zuerst, man multipliziert und nimmt Modulo des irreduziblen Polynoms (als Zahl 283). Kopf->Tisch

    Ethon schrieb:

    Du hast dich gewaltig gemacht im Vergleich zum Vorjahr. 😉

    Vielen Dank! 🙂



  • Na ja, also ich habe die Variante mit den Lookup-Tables implementiert, da muss man zumindest noch mal in's andere Paper gucken. 😉



  • Sone schrieb:

    knivil schrieb:

    Nun, AES zu implementieren ist nicht schwer. Man muss eigentlich nur vom Paper abschreiben. 🙂

    Mehr oder weniger. Genau wie cooky. Und alle Anderen. 😃
    Nein, aber mal ehrlich - ganz ohne ist das nicht. Ich denke, keiner kann wirklich AES implementieren ohne zu wissen was ein Galoiskörper ist.
    (Edit: Hmm, doch.)

    Kommt auch drauf an ob man vom Original-Paper abschreibt oder von einer Referenz-Implementierung. Oder nem Paper/Artikel der das ganze etwas erklärt -- sollte ja einiges zu dem Thema geben.

    Wenn man nur eine funktionierende, möglichst performante Implementierung will, dann nimmt man sich wohl am besten eine ... naja, funktionierende, möglichst performante Implementierung, überträgt die auf die gewünschte Zielplattform und tut halt schön linear optimieren wo man was zu optimieren findet.





  • cooky451 schrieb:

    Na ja, also ich habe die Variante mit den Lookup-Tables implementiert, da muss man zumindest noch mal in's andere Paper gucken. 😉

    Wieso? Ist die Variante nicht einfach, dass man bspw. alle Multiplikationen im Galoiskörper vorberechnet o.ä.? Das kannst du aber auch ohne Paper, oder nicht?



  • Das Orginalpaper ist ganz gut. Ich hatte nur das.



  • Sone schrieb:

    Wieso? Ist die Variante nicht einfach, dass man bspw. alle Multiplikationen im Galoiskörper vorberechnet o.ä.?

    Kommt drauf an was du mit o.ä. meinst, man berechnet deutlich mehr vor als das.

    knivil schrieb:

    Das Orginalpaper ist ganz gut. Ich hatte nur das.

    Yep, da sollte auch der Trick mit den 4 Tables drin beschrieben sein. Schade, dass man das heute wegen Timing Angriffen nicht mehr benutzen kann.


Log in to reply