Attacks on composite-order subgroup

Attacks on composite-order subgroups Failure to
generate Diffie-Hellman primes according to best practices
can result in devastating attacks. Not every TLS server
uses “safe” primes. Out of approximately 70,000 distinct
primes seen across both export and non-export TLS scans,
4,800 were not safe, meaning that (p − 1)/2 was composite.
(Incidentally, we also found 9 composite p.) These groups
are not necessarily vulnerable, as long as g generates a group
with at least one sufficiently large subgroup order to rule out
the Pohlig-Hellman algorithm as an attack.
In some real-life configurations, however, choosing such
primes can lead to an attack. For efficiency reasons, some
implementations use ephemeral keys g
x with a short exponent
x; commonly suggested sizes for x are as small as 160 or 224
bits, intended to match the estimated strength of a 1024- or
2048-bit group. For safe p, such exponent lengths are not
known to decrease security, as the most efficient attack will
be the Pollard lambda algorithm. But if the order of the
subgroup generated by g has small factors, they can be used
to recover information about exponents. From a subset of
factors {q
e1
1
. . . q
ek
k
} with Q
i
q
ei
i = z, Pohlig-Hellman can
recover x mod z in time P
i
ei
√qi. If x ≤ z, this suffices to
recover x. If not, Pollard lambda can use this information
to recover x in time p
x/z. This attack was first described
as hypothetical by van Oorschot and Wiener [51].

ผลลัพธ์ (ไทย) 1:

โจมตีในกลุ่มคอมโพสิตสั่งล้มเหลวในการสร้างโรงแรมไพรม์ Hellman กำลังตามแนวทางปฏิบัติสามารถส่งผลในการโจมตีทำลายล้าง ไม่ได้ทุกเซิร์ฟเวอร์ TLSใช้โรงแรมไพรม์ "ปลอดภัย" จากประมาณ 70,000 แตกต่างกันโรงแรมไพรม์เห็นทั่วทั้งส่งออก และไม่ส่งออกสแกน TLSไม่ได้ 4,800 ปลอดภัย หมายความ ว่า (p − 1) / 2 คือคอมโพสิต(บังเอิญ เรายังพบ p ประกอบ 9) กลุ่มเหล่านี้ไม่จำเป็นต้องเสี่ยง ตราบใดที่ก.สร้างกลุ่มมีอย่างน้อยหนึ่งกลุ่มย่อยขนาดใหญ่เพียงพอเพื่อออกกฎPohlig-Hellman อัลกอริทึมเป็นการโจมตีในการกำหนดค่าบางอย่างของจริง อย่างไรก็ตาม การเลือกดังกล่าวโรงแรมไพรม์สามารถนำการโจมตี เหตุผลประสิทธิภาพ บางปฏิบัติใช้คีย์ชั่วคราวx ที่ มีเลขชี้กำลังที่สั้นx ขนาดที่แนะนำทั่วไปสำหรับ x มีขนาดเล็ก 160 หรือ 224บิต ไว้ที่ระดับประมาณ 1024 - หรือกลุ่ม 2048 บิต สำหรับ p เซฟ ยาวยกดังกล่าวไม่เรียกว่าลดความปลอดภัย การโจมตีที่มีประสิทธิภาพจะเป็นเป็นอัลกอริทึมการแลมบ์ดา Pollard แต่ถ้าลำดับของการกลุ่มย่อยที่สร้างขึ้น โดย g มีปัจจัยเล็ก สามารถนำไปใช้การกู้คืนข้อมูลเกี่ยวกับเลขชี้กำลัง จากชุดย่อยของปัจจัย {qe11. . . qekk} กับ Qผมqeiฉัน = z, Pohlig-Hellman สามารถกู้คืน x z มดในเวลา Pผมei√qi ถ้า x ≤ z นี้ก็เพียงพอที่จะกู้คืนเท่านั้น ถ้า ไม่ แลมบ์ดา Pollard สามารถใช้ข้อมูลนี้การกู้คืนเวลา p xx / z โจมตีครั้งแรกอธิบายไว้สมมุติ โดย van Oorschot และ Wiener [51]

ผลลัพธ์ (ไทย) 2:

การโจมตีในคอมโพสิตสั่งกลุ่มย่อยล้มเหลวในการ
สร้าง Diffie-Hellman เฉพาะตามแนวปฏิบัติที่ดี
จะส่งผลในการโจมตีทำลายล้าง ไม่ทุกเซิร์ฟเวอร์ TLS
ใช้ช่วงเวลาที่ "ปลอดภัย" ออกจากประมาณ 70,000 ที่แตกต่างกัน
เฉพาะเห็นทั้งการส่งออกและไม่มีการส่งออกสแกน TLS,
4,800 ไม่ปลอดภัยหมายความว่า (P - 1). / 2 เป็นคอมโพสิต
(อนึ่งนอกจากนี้เรายังพบ 9 คอมโพสิตพี.) กลุ่มคนเหล่านี้
ไม่จำเป็นต้องมี ความเสี่ยงตราบใดกรัมสร้างกลุ่ม
คำสั่งกลุ่มย่อยอย่างน้อยหนึ่งที่มีขนาดใหญ่พอที่จะออกกฎ
ขั้นตอนวิธีการ Pohlig-Hellman เป็นการโจมตี.
ในบางการกำหนดค่าในชีวิตจริงอย่างไรก็ตามการเลือกเช่น
ช่วงเวลาที่สามารถนำไปสู่การโจมตี สำหรับเหตุผลที่มีประสิทธิภาพบาง
การใช้งานใช้ปุ่มจีรังกรัม
X กับตัวแทนสั้น
X; ขนาดที่แนะนำทั่วไปสำหรับ x เป็นขนาดเล็กเป็น 160 หรือ 224
บิตตั้งใจเพื่อให้ตรงกับความแข็งแรงของประมาณ 1024 หรือ
กลุ่ม 2048 บิต สำหรับ P ปลอดภัยความยาวสัญลักษณ์ดังกล่าวจะไม่
เป็นที่รู้จักกันเพื่อลดการรักษาความปลอดภัยเช่นการโจมตีที่มีประสิทธิภาพมากที่สุดจะ
เป็นอัลกอริทึมแลมบ์ดาพอลลาร์ แต่ถ้าสั่งซื้อของ
กลุ่มย่อยที่สร้างขึ้นโดยมีปัจจัยกรัมขนาดเล็กที่พวกเขาสามารถนำมาใช้
ในการกู้คืนข้อมูลเกี่ยวกับเลขยกกำลัง จากระบบย่อยของ
ปัจจัย {Q
E1 1 . . Q EK K } ด้วย Q ฉันQ EI i = Z, Pohlig-Hellman สามารถกู้คืน x mod Z ในเวลาที่ P ผมEI √qi ถ้า x ≤ Z นี้พอเพียงที่จะกู้คืน X ถ้าไม่ได้, พอลลาร์แลมบ์ดาสามารถใช้ข้อมูลนี้ในการกู้คืนในเวลา x P X / Z การโจมตีครั้งนี้เป็นครั้งแรกเป็นเพียงสมมติฐานโดยรถตู้และ Wiener Oorschot [51]

ผลลัพธ์ (ไทย) 3:

การโจมตีบนคอมโพสิตเพื่อความล้มเหลวของกลุ่มย่อยสร้าง Diffie เฮลแมนจำนวนเฉพาะตามแนวทางปฏิบัติที่ดีที่สุดได้ผลในการโจมตีแรง ไม่ทุก TLS เซิร์ฟเวอร์ใช้ " เซฟ " ไพร์ม ออกประมาณ 70 , 000 รวมจำนวนเฉพาะเห็นทั้งการส่งออกและการส่งออกไม่ TLS แสกน4 , 800 ไม่ปลอดภัย หมายความว่า ? ( − 1 ) / 2 คือ คอมโพสิต( อนึ่ง เราพบ 9 คอมโพสิตหน้า ) กลุ่มเหล่านี้ไม่จําเป็นต้องเสี่ยงตราบเท่าที่ G จะสร้างกลุ่มอย่างน้อยหนึ่งขนาดใหญ่เพียงพอกลุ่มย่อย เพื่อออกกฎการ pohlig เฮลแมนขั้นตอนวิธีเป็นโจมตีในการกำหนดค่าบางจริง อย่างไรก็ตาม การเลือกดังกล่าวจำนวนเฉพาะสามารถนำไปสู่การโจมตี สำหรับเหตุผลประสิทธิภาพ บางซึ่งจะใช้คีย์ไม่ยั่งยืนกรัมX กับอะไรสั้นๆx ; โดยทั่วไปแนะนำขนาด X จะเป็นขนาดเล็กหรือ 224บิต จะตรงกับประมาณความแรงของ 1024 - หรือ2048 บิต ) เพื่อความปลอดภัย เช่น ความยาวไม่ยกกำลัง Pเป็นที่รู้จักกันเพื่อลดการรักษาความปลอดภัยมีประสิทธิภาพมากที่สุดจะเป็นโจมตีพอลลาร์ดแลมบ์ดาเป็นขั้นตอนวิธี แต่ถ้าสั่งซื้อของกลุ่มย่อยที่สร้างขึ้นโดย G มีปัจจัยเล็ก ๆ พวกเขาสามารถใช้การกู้คืนข้อมูลเกี่ยวกับเลขยกกำลัง . จากบางส่วนของปัจจัย { QE11. . . . . . . . คิวเอกเค} Qฉันคิวแปผม = Z , pohlig เฮลแมนได้กู้คืน x mod z ในเวลา pฉันแป√ Qi ถ้า x ≤ Z นี้พอเพียงเพื่อกู้คืน X ถ้าไม่ พอลลาร์ด แลมด้าสามารถใช้ข้อมูลนี้การกู้คืน X ในเวลา pX / Z . โจมตีนี้เป็นครั้งแรกที่อธิบายเช่นสมมุติโดยรถตู้และ oorschot ไส้กรอก [ 51 ]