branchless programming
-
@It0101 sagte in branchless programming:
Habt ihr damit Erfahrungen gemacht? Macht das Sinn, in Ausnahmefällen diese Technik anzuwenden?
Ja, das ergibt sehr viel Sinn, wenn man das z.B. im HPC verwendet und signifikant Rechenzeit (z.B. Die Simulation läuft anstatt 7 Tagen nur noch 5 Tage auf dem Cluster) einsparen kann. D.h man sollte auch nur die zentralen Schleifen, in denen die meiste Zeit verbracht wird, sich genauer anschauen. I.d.R. profitieren Programme von solchen Mikrooptimierungen nicht.
-
@It0101 Es gibt eine sehr gute Verwendung dafür, undzwar Code, der resistent gegen Seitenkanalangriffe ist (klassisches Beispiel: Timing-Attacks bei Überprüfung einer PIN-Eingabe). Natürlich braucht man noch viel mehr, aber das ist sicherlich ein Teilaspekt.
-
@HarteWare
Wie funktioniert das, Seitenkanal resistenter Code und branchless Programming?So ein Seitenkanal Angriff stell ich mir so vor, dass aufgrund einer physikalischen Größe eines Kryptographie Systems, Rückschlüsse auf den Schlüssel gezogen werden. So zum Beispiel Stromverbrauch und Schlüsselgröße bei RSA.
Als Gegenmaßnahme kenne ich nur die Randomisierung der physikalischen Größe s.d. diese weniger mit dem Kryptographieprozess korreliert.
-
@Quiche-Lorraine
Klassisches Beispiel:static char s_correctPin[8]; bool checkPinBad(char const* pin) { for (size_t i = 0; i < 8; i++) if (pin[i] != s_correctPin[i]) return false; return true; } bool checkPinBetter(char const* pin) { char accu = 0; for (size_t i = 0; i < 8; i++) { char const x = pin[i] ^ s_correctPin[i]; accu |= x; } return accu == 0; }
Bei
checkPinBad
kann es etliche Wege geben über die man u.U. feststellen kann welches die erste falsche Stelle war. In manchen Fällen kannst du einfach mitstoppen wie lange es dauert bis du die Antwort bekommst. In anderen Fällen kannst ducheckPinBad
mehrfach mit dem selben PIN aufrufen, aber so dass beim ersten Aufrufpin[0]
undpin[1]
in unterschiedlichen Cache-Lines liegen, beim 2. Aufrufpin[1]
undpin[2]
usw. Zwischen den Aufrufen stellst du irgendwie sicher dass die Daten nicht im Cache stehen. Danach schaust du welche Cache Lines jetzt im Cache vorhanden sind und welche nicht (z.B. wieder über Timing). Daraus kannst du wieder ableiten welches die erste falsche Stelle war. D.h. du brauchst max. 10 Wiederholungen dieser Prozedur pro Stelle. Nicht wirklich viel.Bei
checkPinBetter
wird es schwierig, da die Funktion immer gleich lang braucht und immer alle Speicherstellen inpin
unds_correctPin
ansieht. Du hast also zwei "side channels" zugemacht.Idealerweise kompiliert man das dann noch ohne Optimierungen oder schreibt es gleich in Assembler, damit sichergestellt ist dass der Compiler nicht Schweinchen Schlau spielt und etwas so optimiert dass sich wieder messbare Unterschiede ergeben.
-
Ok verstehe ich.
Aber dein Code gefällt mir nicht. Nehmen wir mal an, der PIN wäre als nullterminierter String kodiert. Wenn der Benutzer nun einen PIN mit weniger als 7 Zeichen eingibt, liest deine Funktion über den Parameter pin hinaus. Eine verbesserte Version sähe so aus.
bool checkPinBetter2(char const* pin) { char accu = 0; if (strlen(pin) != strlen(s_correctPin)) return false; for (size_t i = 0; i < 8; i++) { char const x = pin[i] ^ s_correctPin[i]; accu |= x; } return accu == 0; }
Wenn nun aber der PIN binär kodiert ist und der Benutzer keine 8 Bytes angibt, so liefert deine Funktion auch manchmal true zurück obwohl der Benutzer keine 8 Zeichen eingegeben hat. Eine verbesserte Version sähe so aus.
bool checkPinBetter2(char const* pin, unsigned int len) { char accu = 0; if (len != sizeof(s_correctPin)) return false; for (size_t i = 0; i < 8; i++) { char const x = pin[i] ^ s_correctPin[i]; accu |= x; } return accu == 0; }
Und siehe da, da haben wir wieder unsere Branches...
-
Das scheinst du dann nicht richtig verstanden zu haben.
Es soll ja extra kein vorzeitiger Abbruch erfolgen. Man könnte dazu die Abfrage in die Schleife packen (so daß also immer die Maximalanzahl an Schleifendurchgängen erfolgt):bool checkPinBetter2(char const* pin) { char accu = 0; size_t len = strlen(pin); for (size_t i = 0; i < sizeof(s_correctPin); i++) { char const x = i < len ? pin[i] : 0; char const y = x ^ s_correctPin[i]; accu |= y; } return accu == 0;
Trotzdem könnte so immer noch ein Timing-Unterschied bzgl. der Abfrage möglich sein (dazu müßte man dann noch ein bißchen mehr tricksen - dazu dann statt
0
ebenfalls einen Indexzugriff durchführen).
Besser wäre natürlich noch die Schleifenanzahl zusätzlich zu erhöhen, damit aus der Gesamtlaufzeit nicht auf die Länge descorrectPin
geschlossen werden kann.Alternativ vorher den Eingabe-Pin einfach auf eine vordefinierte Größe aufblähen und die restlichen Werte mit dem Rest des korrekten Pins auffüllen:
const size_t max_len = 16; static char s_correctPin[max_len] = "ABCDEFGHxxxxxxxx"; // PIN ist nur "ABCDEFGH" static char s_dummyPin[max_len] = "xxxxxxxxxxxxxxxx"; static char s_checkPin[max_len]; bool checkPinBetter3(char const* pin) { size_t len = strlen(pin); for (size_t i = 0; i < max_len; i++) { s_checkPin[i] = i < len ? pin[i] : s_dummyPin[i]; // Rest von oben, nur mit Schleife bis max_len und s_checkPin anstatt pin }
Generell mag ich aber auch diese Art der Programmierung persönlich nicht, aber in heutigen Zeiten muß man sicherheitskritischen Code doppelt und dreifach absichern.
-
@Quiche-Lorraine sagte in branchless programming:
Aber dein Code gefällt mir nicht.
-
@Quiche-Lorraine sagte in branchless programming:
Nehmen wir mal an,
Nehmen wir mal an das wäre ein einfaches Beispiel gewesen
Und siehe da, da haben wir wieder unsere Branches...
Und wurscht ist es auch. Der einzige problematische Branch hier ist der mit
len != sizeof(s_correctPin)
. Das hilft dem Angreifer vermutlich nicht sehr. Aber auch den könnte man vermeiden wenn es wirklich drauf ankommt. Nur ist der Code der dafür nötig ist sicher kein schönes, einfaches Beispiel mehr dafür wie man sowas branchless machen kann.@Th69
Naja, den Angreifer wissen zu lassen dass der PIN die falsche Länge hat ist vermutlich kein grosses Problem. Denn dadurch spart er sich nicht viel. Egal wie lange der Code ist, alle kürzeren Kombinationen durchzuprobieren dauert immer nur einen Bruchteil der Zeit die man benötigt um alle Kombinationen mit der korrketen Länge zu probieren.
-
@Quiche-Lorraine
Hier, bitte, ohne Branches (ausgenommen den einen für die Bedingung der Schleife, die immer gleich oft durchlaufen wird):char s_correctPin[] = { '1', '2', '3', '4', '5', '6' }; int checkPin(char const* userPin) { unsigned char accu = 0; char const* p = userPin; for (size_t i = 0; i < sizeof(s_correctPin); i++) { unsigned char const cch = (unsigned char)s_correctPin[i]; unsigned char const uch = (unsigned char)*p; accu |= (uch ^ cch); unsigned char x = uch; x |= x >> 4; x |= x >> 2; x |= x >> 1; x &= 1; p += x; } accu |= (unsigned char)*p; accu |= accu >> 4; accu |= accu >> 2; accu |= accu >> 1; return (accu & 1) ^ 1; }
-
@hustbaer
Danke
-
@hustbaer sagte in branchless programming:
unsigned char x = uch; x |= x >> 4; x |= x >> 2; x |= x >> 1; x &= 1; p += x;
Nachdem ich endlich gerafft habe, dass all diese Zeilen nur dafür da sind, um die Nullterminierung zu behandeln, hab ich mich gefragt, ob sich das statt kreativ pfiffig nicht auch langweilig simpel formulieren lässt.
Auf (x86) CPU-Ebene gedacht kann man für "branchless" ja durchaus die
CMP
-Instruktion verwenden, nur eben ohne den sonst üblicherweise folgenden bedingten Sprung - man muss lediglich die vonCMP
gesetzten Flags auslesen.Und tatsächlich, ein simples
p += (x == 0);
sollte es hier auch tun:bool cmp(int a, int b) { return a == b; }
==> https://godbolt.org/z/jGb3WE
cmp(int, int): cmp edi, esi sete al ret
Ob das für andere CPUs auch so schön geht, kann ich nicht sagen, für x86 macht es den Code jedenfalls kürzer und lesbarer.
Edit: Ich hatte schon den Verdacht, dass das eventuell nicht mit jeder CPU-Architektur geht. Für ARM sieht mir das immer noch "branchless" aus, aber AVR gcc 9.2.0 erzeugt hier:
cmp(int, int): mov r19,r25 mov r18,r24 ldi r24,lo8(1) cp r18,r22 cpc r19,r23 breq .L2 ldi r24,0 .L2: ret
breq
scheint mir ein bedingter Sprung zu sein. Ich denke das Bitgefummel ist wohl letztendlich doch zuverlässiger.