If/else เสี่ยงต่อการถูกโจมตีจากช่องทางด้านข้างหรือไม่?

ฉันมีสาขาใน c ++:

ถ้า (x & 1)
{
    x = function_1(x);
}
อื่น
{
    x = function_2(x);
}

ถ้า ฟังก์ชัน_1 และ ฟังก์ชัน_2 เป็นเวลาคงที่และใช้เวลาเท่าๆ กันในการคำนวณ การแตกสาขาดังกล่าวยังเสี่ยงต่อการถูกโจมตีจากช่องทางด้านข้างหรือไม่ ผู้โจมตีสามารถรู้ได้อย่างไรว่าเงื่อนไขใดถูกดำเนินการ?

สิ่งนี้เริ่มต้นจากการแก้ไขคำตอบของ fgrieu แต่มันยาวมาก ดังนั้นฉันจึงตัดสินใจโพสต์เป็นคำตอบแยกต่างหาก

ฉันเห็นด้วยกับทุกสิ่งที่ fgrieu เขียนในคำตอบของเขา

ฉันจะอ้างอิงคำตอบของ fgrieu ที่นี่เพื่อเน้นมากขึ้น:

โซลูชันที่เชื่อถือได้ถัดไปเพียงตัวเดียวสำหรับการดำเนินการตามเวลาคงที่ในภาษาระดับสูง ซึ่งขาดสิ่งบ่งชี้เกี่ยวกับสภาพแวดล้อมเป้าหมายคือ: ตรวจสอบให้แน่ใจว่าเส้นทางการดำเนินการโค้ดและรูปแบบการเข้าถึงหน่วยความจำไม่ขึ้นกับข้อมูล.

หากเราไม่พิจารณารูปแบบการเข้าถึงหน่วยความจำ เนื่องจากไม่อยู่ในขอบเขตของคำถาม ที่ยกมาสามารถ เท่านั้น ในทางทฤษฎีสามารถทำได้ด้วยเวลาเข้าถึงหน่วยความจำคงที่และการดำเนินการตามเวลาคงที่ของทุกคำสั่ง แน่นอนว่าสิ่งเหล่านี้มาพร้อมกับค่าใช้จ่ายของรอบสัญญาณนาฬิกาที่เพิ่มขึ้นและการเข้าถึงหน่วยความจำเพิ่มเติม

รูปแบบการเข้าถึงหน่วยความจำหมายถึงการโจมตีช่องทางด้านข้างประเภทอื่นที่ต้องใช้หน่วยความจำเข้าถึงโดยสุ่มแบบลืมเลือน (ORAM) เพื่อป้องกันการโจมตีช่องทางด้านข้าง

ถ้า function_1 และ function_2 เป็นเวลาคงที่และใช้เวลาเท่ากัน เวลาในการคำนวณ การแตกแขนงเช่นนี้ยังมีช่องโหว่อยู่หรือไม่ การโจมตีช่องทางด้านข้าง?

ส่วนใหญ่ใช่ if/else เสี่ยงต่อการถูกโจมตีด้วยจังหวะเวลาเนื่องจากเมื่อคุณใช้คำสั่ง if/else คุณสามารถคาดหวังจากคอมไพเลอร์หรือสภาพแวดล้อมรันไทม์เพื่อดำเนินการสาขาได้อย่างง่ายดาย ไม่ว่าในกรณีใดคุณมักจะพยายามหลีกเลี่ยง

การเลือกฟังก์ชันที่จะเรียกใช้โดยดัชนีอาร์เรย์ เช่น ในคำตอบของ mentallurg ใน Python นั้นไม่ใช่วิธีการที่แย่นัก แต่ก็มีเวลาเข้าถึงหน่วยความจำคงที่ และโค้ดที่ Python เรียกใช้งานเพื่อให้การเรียกใช้ฟังก์ชันเป็นเวลาต่อเนื่อง

ก่อนที่ฉันจะเริ่ม

• ในกรณีของการเข้าถึงหน่วยความจำ โปรดทราบว่าเนื่องจากเราสนใจการโจมตีแบบกำหนดเวลา เราจึงสนใจเฉพาะการเข้าถึงหน่วยความจำเท่านั้น เวลา และไม่ รูปแบบ ที่อาจทำให้ข้อมูลรั่วไหลได้ เพราะจะทำให้สถานการณ์ของเราซับซ้อนขึ้นอีกเล็กน้อย
• ฉันพิจารณาแคชในตอนท้ายเท่านั้น สำหรับตอนนี้ เราไม่พิจารณาแคช เนื่องจากทุกคนทราบดีว่าแคชของ CPU อาจเป็นฝันร้ายที่สุดของนักเข้ารหัสในสถานการณ์เช่นนี้
• ฉันคิดว่าแต่ละคำสั่งที่ไม่มีการเข้าถึงหน่วยความจำจะใช้รอบสัญญาณนาฬิกาเดียวกันในการดำเนินการ

การวิเคราะห์คำตอบของ Mentallurg :

ลองใช้โค้ด Python ง่ายๆ นี้เป็นตัวอย่าง

def f1(x):
    กลับ x + 1

def f2(x):
    กลับ x + 2

def หลัก ():
    ฟังก์ชัน = [f1, f2]
    x = int(อินพุต("ป้อนค่า:"))
    ผม = x % 2
    ผลลัพธ์ = ฟังก์ชัน[i](x)
    พิมพ์(ผล)

ถ้า __name__=='__main__':
    หลัก()

สิ่งนี้ได้รับการคอมไพล์เป็น Python bytecode ต่อไปนี้ (เอาต์พุตของ pycdas สำหรับ .pyc ที่คอมไพล์ด้วย Python 3.10):

        [รหัส]
            ชื่อไฟล์: test.py
            ชื่อวัตถุ: หลัก
            จำนวนอาร์กิวเมนต์: 0
            Pos Only Arg จำนวน: 0
            KW เท่านั้น Arg จำนวน: 0
            ชาวบ้าน: 4
            ขนาดกอง: 3
            ค่าสถานะ: 0x00000043 (CO_OPTIMIZED | CO_NEWLOCALS | CO_NOFREE)
            [ชื่อ]
                'f1'
                'f2'
                'int'
                'ป้อนข้อมูล'
                'พิมพ์'
            [ชื่อวาร์]
                'ฟังก์ชั่น'
                'x'
                'ผม'
                'ผลลัพธ์'
            [ฟรีวาร์]
            [เซลล์วาร์]
            [ค่าคงที่]
                ไม่มี
                'ป้อนค่า:'
                2
            [การถอดชิ้นส่วน]
                0 LOAD_GLOBAL 0: f1
                2 LOAD_GLOBAL 1: f2
                4 BUILD_LIST 2
                6 STORE_FAST 0: ฟังก์ชัน
                8 LOAD_GLOBAL 2: ภายใน
                10 LOAD_GLOBAL 3: อินพุต
                12 LOAD_CONST 1: 'ป้อนค่า:'
                14 CALL_FUNCTION 1
                16 CALL_FUNCTION 1
                18 STORE_FAST 1:x
                20 LOAD_FAST 1:x
                22 LOAD_CONST 2:2
                24 BINARY_MODULO           
                26 STORE_FAST 2: i
                28 LOAD_FAST 0: ฟังก์ชัน
                30 LOAD_FAST 2: i
                32 BINARY_SUBSCR           
                34 LOAD_FAST 1:x
                36 CALL_FUNCTION1
                38 STORE_FAST 3: ผลลัพธ์
                40 LOAD_GLOBAL 4: พิมพ์
                42 LOAD_FAST 3: ผลลัพธ์
                44 CALL_FUNCTION1
                46 POP_TOP                 
                48 LOAD_CONST 0: ไม่มี
                50 RETURN_VALUE

การค้นหาและการดำเนินการของบรรทัด ผลลัพธ์ = ฟังก์ชัน[i](x) ทำจากบรรทัดไบต์ 26-36 ลองมาดูที่ BINARY_SUBSCR ผู้ประกอบการ ต้องใช้สองอาร์กิวเมนต์ รายการ (อาจเป็น dict หรือ tuple ก็ได้ แต่ขอไม่เน้นเรื่องนี้) เป็นรายการแรกและดัชนีจากสแต็ก (รายการที่โหลดไว้ก่อนหน้านี้ โหลด_FAST) ส่งกลับค่าที่ดัชนีนั้นและลดกองลง 1

ทีนี้ลองมาดูกันว่า BINARY_SUBSCR ถูกนำไปใช้ใน CPython สามารถพบการนำไปใช้งานได้ ที่นี่ และมีดังต่อไปนี้:

        เป้าหมาย (BINARY_SUBSCR) {
            ทำนาย (BINARY_SUBSCR);
            PyObject *sub = POP();
            PyObject *คอนเทนเนอร์ = TOP();
            PyObject *res = PyObject_GetItem(คอนเทนเนอร์, ย่อย);
            Py_DECREF(คอนเทนเนอร์);
            Py_DECREF(ย่อย);
            SET_TOP (ความละเอียด);
            ถ้า (ความละเอียด == NULL)
                ข้ามข้อผิดพลาด;
            กระโดด (INLINE_CACHE_ENTRIES_BINARY_SUBSCR);
            ส่ง();
        }

ตอนนี้สามารถมุ่งเน้นไปที่การวิเคราะห์ทั้งหมด PyObject *res = PyObject_GetItem(คอนเทนเนอร์, ย่อย);. นี่เป็นวิธีการทั่วไปและจนกว่าจะมีการเรียกค้นรายการ วิธีการอื่นๆ จะถูกเรียกในขั้นกลาง แน่นอนเราสามารถคาดหวัง $O(1)$ ความซับซ้อน มันยังคงตรวจสอบ ในตอนท้าย PyList_GetItem เรียกว่ามีดังต่อไปนี้

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t ฉัน)
{
    ถ้า (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        ส่งคืน NULL;
    }
    ถ้า (!valid_index(i, Py_SIZE(op))) {
        _Py_DECLARE_STR(list_err, "รายการดัชนีอยู่นอกช่วง");
        PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));
        ส่งคืน NULL;
    }
    ส่งคืน ((PyListObject *)op) -> ob_item[i];
}

ดังที่เราเห็นในบรรทัดสุดท้าย มันมี $O(1)$ ความซับซ้อนแน่นอนว่าเนื่องจากความซับซ้อนของภาษาระดับสูง ภาษาเหล่านี้จึงไม่เคยถูกนำมาใช้ในทางปฏิบัติสำหรับแอปพลิเคชันดังกล่าว ลองใช้โค้ดนี้ในภาษาระดับล่าง เช่น C เพื่อดูว่ามันสร้างอะไร

#รวม <stdio.h>

int f1(int x) {
    กลับ x + 1;
}

int f2(int x) {
    กลับ x + 2;
}

int หลัก () {
    int x;
    scanf("%d", &x);
    int (*(ฟังก์ชั่น[2]))(int) = {f1, f2};
    int ฉัน;
    ฉัน = x %2;
    ผลลัพธ์ int = ฟังก์ชั่น [i] (x);
}

นี่คือ x86_64 จาก Godbolt พร้อม GCC ล่าสุดที่ไม่มีการเพิ่มประสิทธิภาพ :

f1:
        เพิ่ม   $sp,$sp,-8
        สว      $fp,4($sp)
        เคลื่อนไหว    $fp,$sp
        สว      $4,8($ฉพ)
        ล      $2,8($ฉพ)
        นพ
        เพิ่ม   $2,$2,1
        เคลื่อนไหว    $sp,$ฉพ
        ล      $fp,4($sp)
        เพิ่ม   $sp,$สเป,8
        จูเนียร์ $31
        นพ

f2:
        เพิ่ม   $sp,$sp,-8
        สว      $fp,4($sp)
        เคลื่อนไหว    $fp,$sp
        สว      $4,8($ฉพ)
        ล      $2,8($ฉพ)
        นพ
        เพิ่ม   $2,$2,2
        เคลื่อนไหว    $sp,$ฉพ
        ล      $fp,4($sp)
        เพิ่ม   $sp,$สเป,8
        จูเนียร์ $31
        นพ

$LC0:
    .ascii "%d\000"
หลัก:
    เพิ่ม $สเป,$sp,-56
    สวิส $31,52($sp)
    สวิส $เอฟพี,48($sp)
    ย้าย $เอฟพี,$sp
    เพิ่ม $2,$fp,32
    ย้าย $5,$2
    ลุย $2,%สวัสดี($LC0)
    เพิ่ม $4,$2,%lo($LC0)
        แจล __isoc99_scanf
        นพ

        ลุย     $2,%สูง(f1)
    เพิ่ม $2,$2,%lo(f1)
    สวิส $2,36($fp)
    ลุย $2,%สูง(f2)
        เพิ่ม   $2,$2,%lo(f2)
        สว      $2,40($ฉพ)
        ล      $3,32($ฉพ)
        หลี่      $2,-2147483648 # 0xffffffff80000000
    หรือ $2,$2,0x1
    และ $2,$3,$2
        บีเจซ    $2,$L6
        นพ

        เพิ่ม   $2,$2,-1
        หลี่      $3,-2 # 0xfffffffffffffffe
    หรือ $2,$2,$3
        เพิ่ม   $2,$2,1
$L6:
    สวิส $2,24($fp)
    ลว $2,24($fp)
    นพ
    sll $2,$2,2
    เพิ่ม $3,$fp,24
    เพิ่ม $2,$3,$2
        ล      $2,12($2)
        ล      $3,32($ฉพ)
        นพ
        เคลื่อนไหว    $4,$3
        เคลื่อนไหว    $25,$2
        25 ดอลลาร์สหรัฐฯ
        นพ

        สว      $2,28($ฉพ)
        เคลื่อนไหว    $2,$0
        เคลื่อนไหว    $sp,$ฉพ
        ล      $31,52($sp)
        ล      $fp,48($sp)
        เพิ่ม   $sp,$sp,56
        จูเนียร์ $31
        นพ

โดยเฉพาะอย่างยิ่งเราสนใจคำแนะนำเหล่านี้ในการเรียกใช้ฟังก์ชันที่เหมาะสม :

        ล      $2,24($ฉพ)
        นพ
        sll     $2,$2,2
        เพิ่ม   $3,$เอฟพี,24
        แอดดู    $2,$3,$2
    ลว $2,12($2)
    ลว $3,32($fp)
    นพ
    ย้าย $4,$3
    ย้าย $25,$2
    จาร์ $25
        นพ

        สว      $2,28($ฉพ)
        เคลื่อนไหว    $2,$0

อย่างที่เราเห็นว่าไม่มีการสร้างสาขา ยกเว้นจาก jalr ซึ่งเรียกใช้ฟังก์ชันที่เหมาะสม

การวิเคราะห์คำตอบของ fgrieu

แน่นอน มันง่ายที่จะเห็นว่านี่เป็นเวลาคงที่ :

#รวม <stdio.h>

int f1(int x) {
    กลับ x + 1;
}

int f2(int x) {
    กลับ x + 2;
}

int หลัก () {
    int x;
    scanf("%d", &x);
    int (*(ฟังก์ชั่น[2]))(int) = {f1, f2};
    int ม = -(x&1); // ตัวแปรมาสก์ m ต้องเป็นชนิดเดียวกับ x
    x = (ฟังก์ชัน_1(x) & ม.) | (function_2(x) & ~m);
    พิมพ์f(x);
}

อีกครั้ง Goldbolt พร้อมตัวเลือกเดียวกัน :

f1:
        กด rbp
        ย้าย rbp, rsp
        mov DWORD PTR [rbp-4], แก้ไข
        ย้าย eax, DWORD PTR [rbp-4]
        เพิ่ม eax, 1
        ป๊อป rbp
        เกษียณ
f2:
        กด rbp
        ย้าย rbp, rsp
        mov DWORD PTR [rbp-4], แก้ไข
        ย้าย eax, DWORD PTR [rbp-4]
        เพิ่ม eax, 2
        ป๊อป rbp
        เกษียณ
.LC0:
        .string "%d"
หลัก:
        กด rbp
        ย้าย rbp, rsp
        กด rbx
        ย่อย rsp, 40
        เลียแร็กซ์ [rbp-24]
        ย้าย rsi, rax
        ย้าย edi, OFFSET FLAT:.LC0
        ย้าย eax, 0
        โทร __isoc99_scanf
        mov QWORD PTR [rbp-48], OFFSET FLAT:f1
        mov QWORD PTR [rbp-40], OFFSET FLAT:f2
        ย้าย eax, DWORD PTR [rbp-24]
        และ eax, 1
        ไม่เป็นไร
        mov DWORD PTR [rbp-20], eax
        ย้าย eax, DWORD PTR [rbp-24]
        ย้าย edi, eax
        ย้าย eax, 0
        ฟังก์ชันการโทร_1
        และ eax, DWORD PTR [rbp-20]
        ย้าย ebx, eax
        ย้าย eax, DWORD PTR [rbp-24]
        ย้าย edi, eax
        ย้าย eax, 0
        ฟังก์ชันการโทร_2
        mov edx, DWORD PTR [rbp-20]
        ไม่ใช่ edx
        และ eax, edx
        หรือ eax, ebx
        mov DWORD PTR [rbp-24], eax
        ย้าย eax, DWORD PTR [rbp-24]
        ซีดีคิว
        ย้าย rdi, rax
        ย้าย eax, 0
        โทรพิมพ์ฉ
        ย้าย eax, 0
        mov rbx, QWORD PTR [rbp-8]
        ออกจาก
        เกษียณ

เรามุ่งเน้นไปที่ส่วนนี้ซึ่งการมอบหมายงานให้ m เสร็จสิ้นและการแยกสาขาแบบอินไลน์:

        ย้าย eax, DWORD PTR [rbp-24]
        และ eax, 1
        ไม่เป็นไร
        mov DWORD PTR [rbp-20], ea
        ย้าย eax, DWORD PTR [rbp-24]
        ย้าย edi, eax
        ย้าย eax, 0
        ฟังก์ชันการโทร_1
        และ eax, DWORD PTR [rbp-20]
        ย้าย ebx, eax
        ย้าย eax, DWORD PTR [rbp-24]
        ย้าย edi, eax
        ย้าย eax, 0
        ฟังก์ชันการโทร_2
        mov edx, DWORD PTR [rbp-20]
        ไม่ใช่ edx
        และ eax, edx
        หรือ eax, ebx
        mov DWORD PTR [rbp-24], eax

เราสามารถเห็นการประมวลผลเวลาคงที่

ดังนั้นความแตกต่างระหว่างโซลูชันเหล่านี้คืออะไร:

ทั้งสองเป็นไปตามมาตรการวิเคราะห์ต่อต้านเวลา แต่อันที่สองยังซ่อนรูปแบบการเข้าถึง มันเรียกใช้ทั้งสองฟังก์ชันเสมอ เนื่องจากเรายังไม่ได้กล่าวถึงแคช เมื่อมีแคช แคชที่สองจึงดูปลอดภัยกว่าจากการโจมตีช่องทางด้านข้างตามเวลาเพียงเพราะต้องการรหัสของทั้งสองฟังก์ชันให้อยู่ในแคชเพื่อดำเนินการตามคำสั่ง ในกรณีที่สอง เฉพาะอันที่ถูกเรียกใช้เท่านั้นที่ถูกแคช หากเราถือว่าในช่วงเวลาใดเวลาหนึ่ง ฉ.1 ถูกเรียกและ f2 ถูกไล่ออกจากแคช จะมีความแตกต่างในเวลาที่ f2 จะถูกเรียกอีกครั้ง

สำหรับวิธีแก้ปัญหาอื่น ๆ และอ่านเพิ่มเติมเกี่ยวกับเรื่องนี้ที่คุณสามารถพิจารณาได้ [1] และ [2].

คุณสามารถใส่ฟังก์ชันลงในอาร์เรย์และอ้างอิงตามดัชนี

ใน Python จะมีลักษณะดังนี้:

def f1( x ):
    ...

def f2( x ):
    ...

ฟังก์ชัน = [ f1, f2 ]

ผม = x % 2

ผลลัพธ์ = ฟังก์ชัน[ i ]( x )