ฉันมีรหัสสำหรับการคูณพหุนามและเขียนด้วยภาษาซี ฉันได้ยินมาว่าคำสั่งเฉพาะเป็น "เวลาคงที่" หรือไม่นั้นอาจแตกต่างกันไปตามสถาปัตยกรรมและรุ่นโปรเซสเซอร์ และไม่มีเอกสารอย่างเป็นทางการสำหรับพฤติกรรมนี้ฉันจะเข้าใจได้อย่างไรว่ารหัสของฉันเป็นเวลาคงที่หรือไม่
หมายเหตุ: โดย "เวลาคงที่" ฉันหมายถึงซอฟต์แวร์หรือชิ้นส่วนโค้ดที่ทนทานต่อการโจมตีตามเวลา ฉันใช้ UBUNTU บนพีซีรุ่นที่ 10 ของ i7
น่าเสียดายที่ไม่มีเอกสารประกอบจากผู้จำหน่าย CPU คุณไม่สามารถแน่ใจได้ 100% ว่าอัลกอริทึมใดจะเป็นหรือไม่ใช่เวลาคงที่ ที่กล่าวว่ามีกฎทั่วไปที่สามารถใช้เพื่อลดความเสี่ยงของปัญหาได้
คุณอาจต้องการดูที่ https://www.bearssl.org/constanttime.html ซึ่งจะกล่าวถึงประเด็นเหล่านี้ในรายละเอียดเพิ่มเติม
โปรดทราบว่าคำตอบที่ยอดเยี่ยมนี้เป็นของ Ossifrage คลื่นไส้ ว่าเลิกอุดหนุน! ฉันทำสำเนาและวางแล้วสร้างชุมชน การลงคะแนนคำตอบนี้ไม่ได้สร้างประโยชน์อะไรให้กับฉัน ถ้าคุณสามารถลงคะแนนให้พวกเขา อินโฟเซค.
จากตัวอย่างรหัสที่ให้มา เป็นไปได้ที่จะกำหนดรหัสผ่านที่ถูกต้องโดยการจับเวลารหัสเมื่อได้รับอินพุตต่างๆ
ขั้นแรก คุณไม่ควรตรวจสอบรหัสผ่านโดยตรง! ที่ อย่างน้อยที่สุดคุณควรแฮชรหัสผ่านด้วยแฮชรหัสผ่านเช่น Argon2id ก่อน และเปรียบเทียบแฮชรหัสผ่านของอินพุตกับแฮชรหัสผ่านที่คุณเก็บไว้ระหว่างการลงทะเบียนผู้ใช้ (หรือเมื่อผู้ใช้เปลี่ยนรหัสผ่านครั้งล่าสุด)
ยิ่งไปกว่านั้น คุณควรใช้โปรโตคอลข้อตกลงคีย์ที่ตรวจสอบสิทธิ์ด้วยรหัสผ่าน เช่น OPAQUE แต่สิ่งเหล่านี้อาจเกินระดับการชำระเงินของคุณในขณะนี้ จนกว่าจะเห็นการยอมรับและการนำไปใช้อย่างแพร่หลายมากขึ้น
ฉันจะทำอย่างไรเพื่อให้แน่ใจว่ารหัสของฉันไม่เสี่ยงต่อการถูกโจมตีตามเวลาดังกล่าว
วิธีที่ดีที่สุดในการเริ่มต้นคือการใช้รูทีนของไลบรารีหรือแบบดั้งเดิมนั้น คนอื่น ได้เขียนไว้แล้วและมีเหตุผลที่จะคงไว้ ตัวอย่างเช่น ใน NaCl/libsodium คุณสามารถใช้ crypto_verify_32 เพื่อเปรียบเทียบสตริงขนาด 32 ไบต์สองรายการ เช่น แฮช Argon2id สองรายการ หรือรหัสยืนยันข้อความ HMAC-SHA256 สองรายการ จากนั้นความพยายามที่จะตอบคำถามนี้สามารถมุ่งเน้นไปที่ที่เดียวที่จะได้รับความสนใจและการตรวจสอบอย่างละเอียดและจะติดตามความก้าวหน้า
แต่สมมุติว่าคุณไม่มี crypto_verify_32หรือต้องการนำไปปฏิบัติเอง คุณทำอะไรได้บ้าง?
ในการเริ่มต้น คุณต้องเข้าใจว่าการดำเนินการใดมีช่องทางด้านข้าง มันคือ ดึงดูด เพื่อบอกว่าเป็นคำตอบอื่น ๆ ที่ช่องด้านข้างเกิดขึ้นเพียงเพราะ แต่แรก ยกเลิก. แต่นั่นไม่ใช่เรื่องราวทั้งหมด โดยทั่วไปก็มี การดำเนินการหลายอย่าง (ในที่นี้เขียนด้วยภาษาซีเพื่อประกอบ) นั้นอาจใช้ระยะเวลาขึ้นอยู่กับ ค่า ของอินพุต เราเรียกการดำเนินการเหล่านี้ว่า เวลาผันแปร การดำเนินงานตรงกันข้ามกับ เวลาคงที่*:
สำหรับ (i = 0; i < n; i++) ถ้า (x[i] == y[i]) คืนค่า EFAIL; เห็นได้ชัดว่าใช้เวลา การวนซ้ำน้อยลง ดังนั้นจึงรับประกันได้ว่าจะทำงานในเวลาผันแปรขึ้นอยู่กับค่าลับของ x[ผม] และ ย [ฉัน].
เงื่อนไขขึ้นอยู่กับความลับเพียงอย่างเดียว สำหรับ (i = 0; i < n; i++) ถ้า (x[i]) ไม่ดี++;, ถ้า x[ผม] เป็นความลับอาจทำงานในเวลาที่ผันแปรเช่นกัน แม้ว่าการวนซ้ำจะไม่ยกเลิกก่อนกำหนด. ทำไม
นี่คือค่าประมาณคร่าวๆ คำสั่งเครื่องที่ CPU อาจดำเนินการมีลักษณะดังนี้:
0: tmp := x[i]
แยกเป็น 1 ถ้า tmp เป็นศูนย์
แย่ := แย่ + 1
1: ผม := ผม + 1
แยกเป็น 0 ถ้า i < n
เดอะ จำนวนคำแนะนำ ดำเนินการขึ้นอยู่กับค่าของ x[ผม] อยู่ที่การทำซ้ำแต่ละครั้ง: เราข้ามไป แย่ := แย่ + 1 ในการวนซ้ำบางอย่าง นี่เป็นรูปแบบที่ดีสำหรับการโจมตีช่วงต้น เช่น., RSA ทำงานเหมือนใน เอกสารสำคัญของ Kocher เกี่ยวกับการโจมตีแบบกำหนดเวลา: ลูปการยกกำลังแบบโมดูลาร์หลักคำนวณ a (พูด) 2048 บิตโมดูลาร์กำลังสองโดยไม่มีเงื่อนไข แต่คำนวณการคูณแบบโมดูลาร์ 2048 บิต อย่างมีเงื่อนไข ขึ้นอยู่กับค่าของเลขชี้กำลังลับ การข้ามการคูณจะเปลี่ยนเวลาที่ใช้โดยการดำเนินการทั้งหมดอย่างมาก
มีเหตุผลอื่นอีก แต่เกี่ยวข้องกับ การทำนายสาขาซึ่งเป็นองค์ประกอบการออกแบบที่สำคัญในสิ่งที่ทำให้ CPU สมัยใหม่ทำงานได้อย่างรวดเร็วในเวิร์กโหลดจำนวนมาก แม้ว่าคุณจะเขียนโค้ดจำนวนเท่ากัน (เช่น จำนวนคำสั่งเครื่องเท่าเดิม และคุณรับประกันได้ว่าจะใช้จำนวนรอบเท่ากันในการคำนวณ ) ในแต่ละสาขาของเงื่อนไข เวลาที่ใช้ในการดำเนินการอาจขึ้นอยู่กับว่าเงื่อนไขดำเนินไปอย่างไร
โดยทั่วไปแล้ว CPU นั้นไม่ดีในการเก็บรักษา คำสั่งใดได้รับการดำเนินการ ความลับดังนั้นอย่าทำให้ ทางเลือกของคำแนะนำ ขึ้นอยู่กับความลับ
การค้นหาตาราง/อาร์เรย์อาจใช้เวลาแตกต่างกัน ขึ้นอยู่กับหน่วยความจำที่ถูกแคชในแคช CPU ดังนั้น หากผ ตำแหน่งในอาร์เรย์ ที่คุณกำลังอ่านนั้นขึ้นอยู่กับความลับ เวลาที่ใช้อาจขึ้นอยู่กับความลับซึ่งถูกนำไปใช้ กู้คืนคีย์ AES ตามเวลาแคช.
(สิ่งนี้ทำให้ AES เป็นการออกแบบที่ค่อนข้างน่าสงสัยเมื่อมองย้อนกลับไป โดยตั้งใจใช้การค้นหาตารางที่ขึ้นกับคีย์! NIST's เผยแพร่เหตุผล (§3.6.2 การโจมตีการนำไปใช้: บทบาทของการปฏิบัติการ) อ้างอย่างน่าสงสัยว่าการค้นหาตาราง "ไม่เสี่ยงต่อการโจมตีแบบกำหนดเวลา" แม้ว่าจะมีรายงานการโจมตีดังกล่าวหลายครั้งนับตั้งแต่นั้นเป็นต้นมา)
ระยะแปรผันเช่น x = y << z อาจใช้เวลามากขึ้นใน CPU บางตัวหาก ซี มีขนาดใหญ่ขึ้นและใช้เวลาน้อยลงหากมีขนาดเล็กลง
(สิ่งนี้ทำให้ RC5 และผู้เข้ารอบสุดท้ายของ AES RC6 การออกแบบที่ค่อนข้างน่าสงสัยเมื่อมองย้อนกลับไปโดยตั้งใจใช้ระยะการหมุนที่ขึ้นกับคีย์!)
ใน CPU บางรุ่น การคูณอาจทำงานเร็วขึ้นหรือช้าลง ขึ้นอยู่กับว่าครึ่งบนของอินพุตเป็นศูนย์หรือไม่
โดยหลักการแล้วการเพิ่มจำนวนเต็ม 64 บิตบน CPU 32 บิตอาจใช้เวลามากขึ้น ขึ้นอยู่กับว่ามีการพกพาหรือไม่ ทั้งนี้เพราะเมื่อ x, ย, และ ซี, เป็นจำนวนเต็ม 64 บิต, ลอจิก x = y + z อาจมีลักษณะดังนี้:
int พกพา = 0;
x[0] = y[0] + z[0];
ถ้า (การเพิ่มก่อนหน้านี้มากเกินไป)
พกพา = 1;
x[1] = y[1] + z[1] + พกพา;
ดังนั้น เวลาที่ใช้อาจขึ้นอยู่กับว่ามีการพกพาจากผลรวมของซีก 32 บิตต่ำไปยังผลรวมของซีก 32 บิตสูงหรือไม่ (ในทางปฏิบัติ มักจะเป็นปัญหาเฉพาะกับ CPU ที่แปลกใหม่หรือสำหรับช่องด้านข้างประเภทอื่นๆ เช่น การวิเคราะห์พลังงาน ซึ่งเกี่ยวข้องกับสมาร์ทการ์ดมากกว่าแล็ปท็อปและโทรศัพท์)
นี่อาจฟังดูล้นหลามเล็กน้อย พวกเราทำอะไรได้บ้าง?
มีการดำเนินการบางอย่างที่ โดยทั่วไปแล้ว ทำงานตลอดเวลาบน CPU ส่วนใหญ่ พวกเขาเป็น:
x & y, x | ย, x ^ ย, ~xและอื่น ๆ ที่ไม่ปรากฏใน C เช่น AND-with-complementx << 3 หรือการหมุนx <<< 3 (ไม่ใช่ภาษาซีมาตรฐาน แต่พบได้ทั่วไปในการเข้ารหัส หมายถึง (x << 3) | (x >> (32 - 3)), ถ้า x เป็น 32 บิต)x + ย, x - ย, เมื่อไร x และ ย คือ (พูด) จำนวนเต็ม 32 บิตที่ไม่ได้ลงนามบน CPU 32 บิต และมักจะเป็นจำนวนเต็ม 64 บิตบน CPU 32 บิตด้วยความช่วยเหลือของคำสั่ง ADD-with-carryเพื่อความชัดเจน: ฉันไม่ได้หมายความอย่างนั้น คอมไพเลอร์ภาษาซี รับประกันการดำเนินการเหล่านี้ในเวลาคงที่หากคุณใช้ในโปรแกรม C ฉันแค่ใช้สัญลักษณ์ C สำหรับการดำเนินการที่ ซีพียู โดยทั่วไปดำเนินการในเวลาคงที่ (เพิ่มเติมเกี่ยวกับคำเตือนนี้ในอีกสักครู่)
“แต่เดี๋ยวก่อน” คุณท้วงว่า “ฉันจะเขียนโปรแกรมที่เป็นประโยชน์จากการดำเนินการเหล่านี้ได้อย่างไร ไม่มีเงื่อนไข? ไม่มีลูป? ไม่มีอาร์เรย์?â
ขั้นแรก คุณไม่จำเป็นต้องหลีกเลี่ยงเงื่อนไข การวนซ้ำ หรืออาร์เรย์ โดยสิ้นเชิง. พวกเขาทำไม่ได้ ขึ้นอยู่กับความลับ. ตัวอย่างเช่น, สำหรับ (i = 0; i < 32; i++) ... x[i] ... ไม่เป็นไร แต่ สำหรับ (i = 0; i < m[0]; i++) ... ไม่เป็นไรถ้า เมตร[0] ควรจะเป็นความลับและ สำหรับ (i = 0; ฉัน < m[0]; i++) ... แท็บ[x[i]] ... ไม่เป็นไรถ้า x[ผม] น่าจะเป็นความลับ
ประการที่สอง คุณยังสามารถสร้างสิ่งเหล่านี้ได้! มันค่อนข้างยุ่งยากกว่าเล็กน้อย ตัวอย่างเช่นสมมติว่า ข เป็น uint32_t ที่เป็น 0 หรือ 1 จากนั้น ข - 1 คือ -1 = 0xffffffff หรือ 0 ตามลำดับ ดังนั้น
x = ((ข - 1) & z) | (~(ข - 1) & y);
สาเหตุ x = ย ถ้า ข คือ 1, หรือ x = z ถ้า ข คือ 0âมาก เช่น x = (ข ? y : z)แต่ไม่มีสาขา. แน่นอนว่าสิ่งนี้ต้องใช้คอมพิวเตอร์ ทั้งสอง ย และ ซีจึงมีผลกระทบด้านประสิทธิภาพบ้าง! ในทำนองเดียวกัน คุณสามารถค้นหาองค์ประกอบของตารางได้โดยการค้นหา ทั้งหมด องค์ประกอบของตารางและเลือกสิ่งที่คุณต้องการด้วยการดำเนินการระดับบิตเช่นนี้ ไม่เร็วเท่า x[ผม]แต่ก็ไม่รั่วเหมือนกัน
โดยทั่วไปแล้วคุณ สามารถ แปลงโปรแกรมที่มีเงื่อนไขให้เป็นวงจรลอจิกที่ไม่มีเงื่อนไข แม้ว่าคุณจะไม่มีก็ตาม ต้องการ เพื่อเหตุผลด้านประสิทธิภาพ มีเคล็ดลับที่คล้ายกันอื่น ๆ อีกมากมายที่คุณสามารถทำได้ คุณอาจร่างรูทีนความเท่าเทียมกันของหน่วยความจำเวลาคงที่ เช่น crypto_verify_32 แบบนี้ สมมติว่า x และ y เป็นอาร์เรย์ uint8_t:
ผลลัพธ์ uint32_t = 0;
สำหรับ (i = 0; i < 32; i++)
ผลลัพธ์ |= x[i] ^ y[i];
กลับ ((ผลลัพธ์ - 1) >> 8) & 1;
แบบฝึกหัด: สิ่งนี้ส่งคืน 0 สำหรับเท่ากับและ 1 สำหรับไม่เท่ากัน หรือ 0 สำหรับไม่เท่ากัน และ 1 สำหรับเท่ากับ
การเขียนโปรแกรมเช่นนี้และการนำระบบเข้ารหัสเช่น X25519 มาใช้ ให้กำลังใจ การใช้งานที่มีลักษณะเช่นนี้ แทนที่จะเป็นระบบเข้ารหัสเช่น RSA หรือ AES นั้น ให้กำลังใจ การใช้งานที่เกี่ยวข้องกับสาขาที่ขึ้นอยู่กับความลับหรือการค้นหาตารางที่ขึ้นกับความลับเป็นการเริ่มต้นที่ดีสำหรับการเสียบช่องทางด้านเวลา
แต่มีการจับ! จำได้ไหมเมื่อฉันบอกว่าคอมไพเลอร์ C ไม่รับประกันเวลาคงที่? คอมไพเลอร์ C อัจฉริยะเช่น Clang/LLVM อาจ จำได้ ว่าฉลาด crypto_verify_32 ลูปด้านบนสามารถดำเนินการได้ ได้อย่างมีประสิทธิภาพมากขึ้น โดยการทำให้ยกเลิกก่อนเวลา และอาจยกเลิกการทำงานอย่างหนักที่คุณทำเพื่อเขียนใหม่เป็นวงจรลอจิกที่ทำงานในเวลาคงที่ (ในกรณีอื่นๆ อาจช่วยคุณได้ เช่น การแปลง x = (ข ? y : z); เป็นคำสั่งย้ายแบบมีเงื่อนไข CMOV โดยไม่มีสาขา แต่โดยปกติแล้วคุณไม่สามารถพึ่งพาความปรารถนาดีของคอมไพเลอร์ C ได้)
มีเคล็ดลับบางอย่างที่คุณสามารถทำได้เพื่อขัดขวางสิ่งนี้ เช่น ชิ้นส่วนแอสเซมบลีแบบอินไลน์ที่ทำให้คอมไพเลอร์ทิ้งสมมติฐานทั้งหมดสำหรับการปรับให้เหมาะสม:
ผลลัพธ์ uint32_t = 0;
สำหรับ (i = 0; i < 32; i++)
ผลลัพธ์ |= x[i] ^ y[i];
asm ระเหย ("" ::: "หน่วยความจำ");
กลับ ((ผลลัพธ์ - 1) >> 8) & 1;
สิ่งนี้อาจใช้ได้หรือไม่ได้กับคอมไพเลอร์ของคุณ เพื่อความมั่นใจ คุณต้องตรวจสอบรหัสเครื่องที่สร้างขึ้นโดยคอมไพเลอร์จริงๆ และถึงอย่างนั้น คอมไพเลอร์ก็อาจทำการปรับให้เหมาะสมแบบทันท่วงที เขียนใหม่ รหัสเครื่องตามการวิเคราะห์โปรไฟล์ โดยเฉพาะในภาษาระดับสูงกว่าเช่น Java ดังนั้นคุณอาจต้องการ เขียนตรรกะในการประกอบ (หรือในภาษาการเขียนโปรแกรมเช่น qhasm ที่สามารถสร้างแอสเซมบลีที่ปรับแต่งแล้วได้อย่างน่าเชื่อถือมากกว่าคอมไพเลอร์ C) และเรียกมันจาก C
บางทีสักวันหนึ่งคอมไพเลอร์ C จะนำไฟล์ ความลับ รอบคัดเลือกเช่น คอสต์ หรือ ระเหยซึ่งบังคับให้คอมไพเลอร์สร้างเฉพาะคำสั่งเครื่องที่รู้จักใน CPU บางรุ่น!â ให้รันในเวลาคงที่เมื่อทำงานกับออบเจกต์ และป้องกันไม่ให้คอมไพเลอร์ใช้ทางลัด เช่น ยกเลิกก่อนกำหนดที่ขึ้นอยู่กับความลับ ห่วง แต่วันนั้นยังมาไม่ถึง
นอกจากนี้ยังมีเรื่องของคำสั่งเครื่องที่ทำงานจริงในเวลาคงที่บน CPU ซึ่งบางครั้งได้รับการจัดทำเป็นเอกสารและบางครั้งก็เชื่อถือได้ ดังนั้นนอกจากจะทำ วิศวกรรม ในการสร้างโปรแกรมของคุณจากวงจรลอจิก คุณต้องทำเช่นกัน ศาสตร์ เพื่อหาว่าการดำเนินการใดที่ปลอดภัยสำหรับใช้งานบน CPU
สิ่งนี้นำเรากลับไปสู่จุดเดิม: คุณต้องการมุ่งเน้นความพยายามในการรักษาสิ่งนี้ให้เป็นรูทีนของไลบรารี เพื่อให้โปรแกรมเมอร์แต่ละคนไม่ต้องติดตามความหลากหลายของคอมไพเลอร์ (และการออกแบบ CPU!) ในโค้ดและเวลาที่สร้างขึ้น ด้วยตัวเองและสามารถปล่อยทิ้งไว้ได้ หมีเพื่อนบ้านที่เป็นมิตรของเรา.
มีวิธีตอบโต้อื่นนอกเหนือจากลอจิกเวลาคงที่หรือไม่ บางครั้งใช่.
คุณสามารถส่งเสียงรบกวนแบบสุ่มเข้าไปในตรรกะของคุณ โดยหวังว่ามันจะทำให้การวัดของผู้โจมตีสับสน แต่มีสัญญาณรบกวนอยู่แล้วในการวัด เช่น การตั้งเวลาในระบบปฏิบัติการ ดังนั้นพวกเขาจึงต้องเก็บตัวอย่างมากขึ้น—และปรากฎว่าสัญญาณรบกวนคือ ไม่ใช่มาตรการตอบโต้ช่องทางด้านข้างที่มีประสิทธิภาพมากนัก.
โดยเฉพาะอย่างยิ่ง เสียงประดิษฐ์จะเพิ่มค่าใช้จ่ายของผู้โจมตีมากที่สุดประมาณกำลังสองของอัตราส่วนของเสียงเทียมต่อเสียงจริง ซึ่งต่ำกว่าสิ่งที่มักจะถือว่าเป็นช่องว่างที่ยอมรับได้สำหรับการรักษาความปลอดภัยในการเข้ารหัส ดังนั้นคุณจึงเสียเวลาส่วนใหญ่ไปกับการไม่ทำอะไรเลย
คุณสามารถใช้คุณสมบัติเชิงพีชคณิตของระบบเข้ารหัสเพื่อสุ่มได้ บางครั้งเรียกว่า âblindingâ ตัวอย่างเช่น แทนที่จะใช้คอมพิวเตอร์ y^d ม็อด n ที่ไหน ง เป็นเลขชี้กำลังลับใน RSA คุณสามารถเลือกได้ ร สุ่มคำนวณ s := r^e ม็อด n ที่ไหน e*d â¡ 1 (สมัย (n))คูณ ย โดย ส ที่จะได้รับ (y * r^e) ม็อด n,คำนวณ (y * r^e)^d mod n = (r * y^d) mod nแล้วแบ่งออก ร.
การใช้งานจำนวนมาก เช่น OpenSSL ใช้วิธีนี้เนื่องจากเป็นวิธีที่ง่ายในการปรับเปลี่ยนการใช้งานระบบเข้ารหัสลับที่มีอยู่เช่น RSA ซึ่งมีโครงสร้างพีชคณิตที่จำเป็น ไม่ใช่ความคิดที่ไม่ดีเหมือนสัญญาณรบกวนแบบสุ่ม แต่มันมีค่าใช้จ่าย คุณต้องทำงานพิเศษสำหรับการสุ่ม คุณต้องมีการแบ่งแบบแยกส่วนหรือตรรกะผกผัน และช่องด้านข้างอาจยังรั่วไหลข้อมูลเกี่ยวกับ ร และ ง. ตัวอย่างเช่น แม้แต่การยกกำลังแบบโมดูลาร์แบบปิดตาก็จะทำให้ Hamming Weight รั่วไหล ง เว้นแต่คุณจะใช้มาตรการตอบโต้เพิ่มเติม เช่น การเพิ่มตัวคูณแบบสุ่มของ (น) ถึง ง ก่อนâซึ่งอาจเปิดช่องด้านข้างเพิ่มเติม เป็นต้น
สำหรับกรณีเฉพาะของการเปรียบเทียบสตริงสองไบต์เพื่อความเท่าเทียมกัน (เช่น รหัสยืนยันข้อความสองรหัส) ทางเลือกหนึ่งที่เหมาะสมคือการแฮชสตริงเหล่านี้ด้วยกลุ่มฟังก์ชันสุ่มเทียม เช่น HMAC-SHA256 ภายใต้รหัสลับแบบใช้ครั้งเดียว เคและตรวจสอบว่า HMAC-SHA256_k(x) == HMAC-SHA256_k(y).
ความน่าจะเป็นของผลบวกลวงคือ 1/2256ซึ่งเป็นโอกาสที่น้อยกว่าที่คุณเคยต้องกังวล คุณสามารถใช้ความเท่าเทียมกันของเวลาผันแปรได้อย่างปลอดภัยสำหรับ HMAC เนื่องจากถ้า x เป็น ไม่ เท่ากับ ยแล้วระยะเวลาแม้ใน ไร้เดียงสาที่สุด รูทีนความเท่าเทียมกันของสตริงไบต์ (สมมติว่ามันไม่ได้ประกันตัวที่ศูนย์ไบต์แรกหรืออะไรโง่ ๆ แบบนั้น!) จะเป็นอิสระจากค่าของ x และ ย: มีความน่าจะเป็น 255/256 ที่มันจะหยุดหลังจากวนซ้ำ 1 ครั้ง ความน่าจะเป็น 65535/65536 หลังจากวนซ้ำ 2 ครั้ง เป็นต้น
แน่นอนว่าสิ่งนี้จะช่วยได้ก็ต่อเมื่อคุณสามารถใช้ HMAC-SHA256 ในเวลาคงที่เท่านั้น! โชคดีที่ SHA-256 ได้รับการออกแบบให้ใช้งานเป็นวงจรลอจิกเวลาคงที่ได้อย่างง่ายดาย ดังนั้นการใช้งาน C มีแนวโน้ม เพื่อให้ทนทานต่อแชนแนลข้างเคียงพอสมควร—แต่พูดได้ว่า Python จะทำให้คุณมีปัญหาเพราะแคชจำนวนเต็มขนาดเล็ก ถ้าไม่มีอะไรอย่างอื่น
* น่าเสียดายที่คำศัพท์ทำให้เกิดความสับสนเล็กน้อย ที่นี่ เวลาคงที่ หมายความว่า ระยะเวลาไม่แตกต่างกันไปขึ้นอยู่กับอินพุตและไม่เหมือนกับ ไม่มีอาการ แนวคิดของ “เวลาคงที่” ในวิทยาการคอมพิวเตอร์ มักเขียนเป็น O(1) ซึ่งหมายถึง ระยะเวลาอาจแตกต่างกันไปขึ้นอยู่กับอินพุต แต่ถูกจำกัดด้วยค่าคงที่. ฉันเสียใจ. ฉันไม่ได้คิดค้นคำศัพท์ ฉันอาจเลือก âfixed-timeâ เทียบกับ âเวลาผันแปรâ แต่มันสายเกินไปแล้วเวลาคงที่ââconstant-timeâ เป็นที่ยึดเหนี่ยวในวรรณคดี
นี่คือสองเซ็นต์ของฉัน:
การโจมตีแบบกำหนดเวลาจะใช้เวลาที่ใช้ในการดำเนินการอัลกอริทึมตามอินพุตที่แตกต่างกัน
ใช้ปัญหาที่ง่ายกว่า เช่น ค้นหาว่ามีอักขระตัวเดียวในสตริงลับหรือไม่ ในอัลกอริทึมแบบดั้งเดิม คุณจะวนซ้ำสตริงและคืนค่าบูลีนเมื่อคุณพบอักขระ การดำเนินการนี้จะใช้เวลามากขึ้นตามตัวอักษร ซึ่งจะทำให้ข้อมูลบางอย่างของสตริงลับรั่วไหล
หากเราต้องการให้เวลาคงที่นี้ เราจะทำให้การค้นหาตัวละครใช้เวลาเท่ากันไม่ว่าจะอยู่ที่จุดเริ่มต้นหรือจุดสิ้นสุด เช่น วนซ้ำสตริงทั้งหมดและกลับมาเมื่อคุณสิ้นสุดการวนซ้ำ
อีกสิ่งที่ต้องใช้เวลามากขึ้นคือสาขา สาขาเป็นส่วนของรหัสที่อาจถูกดำเนินการหรือไม่เช่น ถ้า คำแถลง.
ตัวอย่างที่นำมาจากฟังก์ชันการคูณ GF(2^8):
มีสาขา:
ถ้า ((a >> 7) & 1)
a = (a << 1) ^ พหุนาม;
อื่น
<<= 1
ไม่มีสาขา:
const uint8_t mask = -((ก >> 7) & 1); // 0xff หากตั้งค่าบิตสูงสุด มิฉะนั้น 0x00
a = (a << 1) ^ (พหุนาม & หน้ากาก); // ใช้พหุนามเฉพาะเมื่อมาสก์เป็น 0xff
อย่างที่คุณเห็น รหัสที่มีสาขาสามารถดำเนินการได้มากกว่า 1 ครั้งในกรณีใดกรณีหนึ่ง ในขณะที่รหัสที่ไม่มีสาขาจะดำเนินการในการดำเนินการเดียวกันเสมอ
สิ่งที่คุณได้ยินมานั้นถูกต้อง
มันเป็นการต่อสู้ที่ยากเย็นแสนเข็ญ คอมไพเลอร์และฮาร์ดแวร์ไม่ได้ออกแบบมาเพื่อช่วยเหลือคุณ และได้รับการออกแบบโดยจงใจให้ทำสิ่งที่ทำให้สับสนในสิ่งที่คุณพยายามทำ
มาตรฐาน C ไม่ได้กล่าวถึงเรื่องเวลา คอมไพเลอร์อย่าพยายาม เพื่อให้แน่ใจว่าถ้ารหัส C ของคุณดูเหมือนอัลกอริทึมเวลาคงที่ มันจะคอมไพล์รหัสเครื่องเวลาคงที่เสมอ
วิธีหนึ่งคือการเรียนรู้โดยละเอียดว่าคอมไพเลอร์ทำอะไรได้บ้าง และวิธีหลีกเลี่ยงการเพิ่มประสิทธิภาพที่สับสน ฟังก์ชั่นการทำเครื่องหมายเป็น บรรทัดล่างตัวอย่างเช่น อาจมีความสำคัญ
อีกวิธีหนึ่งคือการกำจัดคอมไพเลอร์ออกจากรูปภาพทั้งหมด คุณสามารถคอมไพล์โค้ด C ที่ไวต่อเวลาเพื่อแอสเซมบลีหนึ่งครั้ง ตรวจสอบแอสเซมบลีเพื่อให้แน่ใจว่ายังคงเป็นอัลกอริทึมเวลาคงที่ ตรวจสอบในโค้ดแอสเซมบลี และใช้สิ่งนั้น ไม่ใช่ซีดั้งเดิม เป็นซอร์สเมื่อสร้างโปรแกรมของคุณ
ที่ระดับรหัสเครื่องมีปัญหาที่คล้ายกัน ซีพียูไม่ได้ลอง เพื่อให้แน่ใจว่าลำดับคำสั่งคงที่จะทำงานในเวลาคงที่เสมอ กลไกหลายอย่างในฮาร์ดแวร์ (โดยเฉพาะแคช) พยายามเร่งความเร็ว แต่ก็ไม่สำเร็จเสมอไป โค้ดสามารถทำงานช้าลงได้ในกรณีพิเศษเฉพาะเจาะจงมาก ซึ่งการเร่งความเร็วไม่ได้ผล อาจทำให้ข้อมูลรั่วไหลได้
ฉันไม่รู้ว่าจะแก้ไขปัญหานี้อย่างไร ยกเว้นการรู้จักฮาร์ดแวร์เป็นอย่างดีและการวัดผล
2 เซ็นต์ที่ต่ำต้อยของฉัน: เทคนิคการทำ bitslicing ถ้าราคาไม่แพงในกรณีของคุณ: https://timtaubert.de/blog/2018/08/bitslicing-an-introduction/
ฉันไม่ต้องการทำซ้ำ (ทำให้แย่ลง) คำที่คุณสามารถอ่านได้ในหน้าที่เชื่อมโยง แต่ฉันถูกถามมากกว่าลิงก์ ดังนั้นสมมติว่าโดยพื้นฐานแล้ว bitslicing จะจำลองการใช้งานฮาร์ดแวร์ในซอฟต์แวร์: อัลกอริทึมทั้งหมดจะถูกแสดง เป็นลำดับของการดำเนินการบูลีนของอะตอม ซึ่งจะดำเนินการในเวลาคงที่ ขออภัยที่ไม่สามารถให้รายละเอียดเพิ่มเติมได้ เพิ่งทราบเกี่ยวกับเทคนิคนี้ในระหว่างการสัมมนาเกี่ยวกับแนวทางปฏิบัติที่ดีที่สุดของการเข้ารหัสประยุกต์: ฉันไม่ได้ลงลึกไปกว่านี้ แต่ดูเหมือนว่าคุณต้องการสิ่งที่คุณต้องการ เนื่องจากคุณต้องการทนต่อเวลา เป็นส่วนที่เฉพาะเจาะจงมากในโค้ดของคุณ ดังนั้นค่าใช้จ่ายในการดำเนินการอาจมีราคาไม่แพงในกรณีของคุณ (แน่นอนว่ามันจะเป็นฝันร้ายที่เจ็บปวดสำหรับโค้ดขอบเขตกว้าง)
นี่คือข่าวดี: อัลกอริทึมของคุณไม่จำเป็นต้องเป็น "เวลาคงที่" เพียงแค่ต้องเป็นอิสระจากข้อมูลที่ป้อนเข้า ไม่เป็นไรหากมีการเปลี่ยนแปลงแบบสุ่ม พวกมันมีประโยชน์จริง ๆ ถ้ารูปแบบสุ่มมีขนาดใหญ่กว่ารูปแบบที่ขึ้นกับข้อมูล
การเข้าถึงหน่วยความจำนั้นทำงานอย่างฉาวโฉ่ในเวลาที่ผันแปร ดังนั้นหากคุณมีรูปแบบการเข้าถึงที่ขึ้นกับข้อมูล นั่นเป็นสิ่งที่ไม่ดี ยกตัวอย่าง ตาราง [x[i]]การเข้าถึง x[i] ในลูปไม่ใช่เวลาคงที่ แต่เวลาไม่ได้ขึ้นอยู่กับข้อมูล การเข้าถึงตาราง [x[i]] ขึ้นอยู่กับข้อมูล ดังนั้นจึงสามารถรับข้อมูลเกี่ยวกับข้อมูลได้
การดำเนินการคูณและหารอาจขึ้นอยู่กับข้อมูล ดังนั้นนั่นคือสิ่งที่คุณต้องทดสอบ
หากคุณสามารถยอมรับคำตอบว่า "น่าจะเป็นเวลาคงที่" (แทนที่จะเป็น "เวลาคงที่แน่นอน") คุณก็สามารถประเมินเชิงทดลองได้ว่าโค้ดของคุณเป็นเวลาคงที่หรือไม่ ทำเช่นนั้นฉันขอแนะนำเครื่องมือ เพื่อน. หากต้องการอ้างอิง GitHub Readme:
มันทำงานอย่างไร? โดยสรุปรหัสนี้ใช้เวลาสองแบบที่แตกต่างกัน อินพุต รันโค้ดหลาย ๆ ครั้งสำหรับแต่ละอินพุตและการวัด ต้องใช้เวลาเท่าไร หากมีความแตกต่างทางสถิติกับ เวลา (เฉลี่ย) ที่ใช้ในการรันด้วยอินพุตที่แตกต่างกัน การนำไปใช้ถือว่าไม่คงที่ตามเวลา สำหรับรายละเอียด โปรดอ่านของเรา กระดาษหรือดูที่แหล่งที่มา
และ:
รหัสของฉันผ่านการทดสอบนี้ หมายความว่าเวลาคงที่จริงหรือ? ไม่ได้อย่างแน่นอน. [...]
เครื่องมือที่คล้ายกันคือ ct-fuzzซึ่งใช้การทดสอบฟัซซี่สีเทาบ็อกซ์ตามความครอบคลุมเพื่อตรวจจับการรั่วไหลของเวลา ข้อมูลเพิ่มเติมเกี่ยวกับวิธีการในกระดาษ ct-fuzz: Fuzzing สำหรับการรั่วไหลของไทม์มิ่ง.
ด้วย ductect และ ct-fuzz คุณไม่สามารถแน่ใจได้ 100% ว่ารหัส C ของคุณเป็นเวลาคงที่ แต่หากมีการรั่วไหลของเวลาที่สำคัญ คุณจะพบได้ และหากเครื่องมือไม่พบการรั่วไหลของไทม์มิ่ง คุณก็สามารถ "มั่นใจอย่างสมเหตุสมผล" ว่าไม่มีการรั่วไหล
สามารถใช้เครื่องมืออื่นๆ สองสามอย่างเพื่อระบุแบบคงที่ว่าชิ้นส่วนของโค้ด C เป็นเวลาคงที่หรือไม่:
ctgrindสร้างขึ้นบน valgrind ติดตามทุกบิตของหน่วยความจำลับและตรวจสอบว่าเงื่อนไขไม่ขึ้นอยู่กับบิตลับ
การตรวจสอบแคชซึ่งตามนั้น GitHub Readme:
CacheAudit เป็นตัววิเคราะห์แบบคงที่ของช่องฝั่งแคช การตรวจสอบแคช ใช้เป็นอินพุตไบนารีโปรแกรม x86 32 บิตและการกำหนดค่าแคช และได้รับการรับประกันความปลอดภัยเชิงปริมาณอย่างเป็นทางการสำหรับ ชุดของฝ่ายตรงข้ามแคชที่ครอบคลุม ได้แก่ ผู้ที่อิงตาม การสังเกตสถานะของแคช ร่องรอยของการเข้าชมและการพลาด และการดำเนินการ ครั้ง.
เนื่องจากเครื่องมือเหล่านั้นใช้การวิเคราะห์แบบสถิต คุณจึงมั่นใจได้มากขึ้นว่าไม่มีการรั่วไหลของเวลาหากไม่พบเครื่องมือใดๆ อย่างไรก็ตาม ไม่มีเครื่องมือใดที่มีโมเดลฮาร์ดแวร์ที่ชัดเจนว่าอะไรรั่วไหลและอะไรไม่รั่วไหล ซึ่งหมายความว่าพวกเขาถือว่า ตัวอย่างเช่น การคูณเป็นเวลาคงที่ หากการคูณไม่ใช่เวลาคงที่จริง ๆ เครื่องมือเหล่านั้นจะไม่ตรวจพบการรั่วไหลของเวลาที่อาจเกิดขึ้น ดูของปีเตอร์กรีน คำตอบ สำหรับข้อมูลเพิ่มเติมเกี่ยวกับการดำเนินการที่อาจรั่วไหล แต่ CacheAudit และ ctgrind สันนิษฐานว่าเป็นเวลาคงที่
คุณสามารถทำการวัดเวลาที่แม่นยำโดยใช้ฟังก์ชันภายใน __rdtscp() จากนั้นทำสถิติเกี่ยวกับผลลัพธ์
ฟังก์ชันนี้เปิดเผยการลงทะเบียนภายใน 64 บิตที่เพิ่มขึ้นในแต่ละรอบสัญญาณนาฬิกา ความถี่สัญญาณนาฬิกาเป็นความถี่ของโปรเซสเซอร์อย่างเป็นทางการตามที่เห็นใน /proc/cpuinfo หลังเครื่องหมาย @
โปรเซสเซอร์รุ่นที่ 10 ควรมีการตั้งค่าสถานะ Constant_tsc ดังที่เห็นใน /proc/cpuinfo
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
