cryptography - zahlen - zwei-byte-zeichen




Warum brauchen wir eine konstante Zeit*Single-Byte*Vergleichsfunktion? (2)

Bei der Go-Standardbibliothek gibt es eine ConstantTimeByteEq- Funktion, die folgendermaßen aussieht:

func ConstantTimeByteEq(x, y uint8) int {
    z := ^(x ^ y)
    z &= z >> 4
    z &= z >> 2
    z &= z >> 1

    return int(z)
}

Jetzt verstehe ich die Notwendigkeit für einen Vergleich konstanter Zeitstring (Array, etc.), da ein regulärer Algorithmus nach dem ersten ungleichen Element kurzschließen könnte. Aber ist in diesem Fall kein regelmäßiger Vergleich zweier fester Ganzzahlen eine konstante Zeitoperation auf CPU-Ebene?


Der Punkt ist wahrscheinlich, Verzweigungsfehler zu vermeiden, zusätzlich zu dem Ergebnis als 1 oder 0 anstelle von wahr oder falsch (Folgemaßnahmen als bitweise Operationen).

Vergleichen Sie, wie das kompiliert:

var a, b, c, d byte
_ =  a == b && c == d

=>

0017 (foo.go:15) MOVQ    $0,BX
0018 (foo.go:15) MOVQ    $0,DX
0019 (foo.go:15) MOVQ    $0,CX
0020 (foo.go:15) MOVQ    $0,AX
0021 (foo.go:16) JMP     ,24
0022 (foo.go:16) MOVQ    $1,AX
0023 (foo.go:16) JMP     ,30
0024 (foo.go:16) CMPB    BX,DX
0025 (foo.go:16) JNE     ,29
0026 (foo.go:16) CMPB    CX,AX
0027 (foo.go:16) JNE     ,29
0028 (foo.go:16) JMP     ,22
0029 (foo.go:16) MOVQ    $0,AX

Mit diesem:

var a, b, c, d byte
_ =  subtle.ConstantTimeByteEq(a, b) & subtle.ConstantTimeByteEq(c, d)

=>

0018 (foo.go:15) MOVQ    $0,DX
0019 (foo.go:15) MOVQ    $0,AX
0020 (foo.go:15) MOVQ    $0,DI
0021 (foo.go:15) MOVQ    $0,SI
0022 (foo.go:16) XORQ    AX,DX
0023 (foo.go:16) XORQ    $-1,DX
0024 (foo.go:16) MOVQ    DX,BX
0025 (foo.go:16) SHRB    $4,BX
0026 (foo.go:16) ANDQ    BX,DX
0027 (foo.go:16) MOVQ    DX,BX
0028 (foo.go:16) SHRB    $2,BX
0029 (foo.go:16) ANDQ    BX,DX
0030 (foo.go:16) MOVQ    DX,AX
0031 (foo.go:16) SHRB    $1,DX
0032 (foo.go:16) ANDQ    DX,AX
0033 (foo.go:16) MOVBQZX AX,DX
0034 (foo.go:16) MOVQ    DI,BX
0035 (foo.go:16) XORQ    SI,BX
0036 (foo.go:16) XORQ    $-1,BX
0037 (foo.go:16) MOVQ    BX,AX
0038 (foo.go:16) SHRB    $4,BX
0039 (foo.go:16) ANDQ    BX,AX
0040 (foo.go:16) MOVQ    AX,BX
0041 (foo.go:16) SHRB    $2,BX
0042 (foo.go:16) ANDQ    BX,AX
0043 (foo.go:16) MOVQ    AX,BX
0044 (foo.go:16) SHRB    $1,BX
0045 (foo.go:16) ANDQ    BX,AX
0046 (foo.go:16) MOVBQZX AX,BX

Obwohl die letztere Version länger ist, ist sie auch linear - es gibt keine Zweige.


Nicht unbedingt. Und es ist schwer zu sagen, was der Compiler nach den Optimierungen ausgeben wird. Sie könnten mit einem anderen Maschinencode für das Highlevel "Ein Byte vergleichen" enden. Wenn Sie nur ein winziges bisschen in einem Seitenkanal verlieren, könnte sich Ihre Verschlüsselung von "im Grunde unzerbrechlich" zu "hoffentlich nicht mehr das Geld, das für einen Riss benötigt wird" ändern.