ฉันมักจะอ่านเกี่ยวกับความปลอดภัยของรูปแบบลายเซ็นในการตั้งค่าผู้ใช้หลายคน ลิงค์1 ลิงค์2แต่ฉันไม่พบคำจำกัดความที่แท้จริง ฉันอยากจะแน่ใจว่าฉันเข้าใจถูกต้อง ดังนั้นคำถามของฉันคือ: หากเราพิจารณา Def 1 Def 2 จะเหมาะสมสำหรับการตั้งค่าผู้ใช้หลายคนหรือไม่
Def 1: รูปแบบลายเซ็นให้ผลตอบแทน k-bits ของความปลอดภัยในการตั้งค่าผู้ใช้คนเดียว หากมีความเป็นไปได้สูงสุดที่ผู้โจมตีสามารถปลอมแปลงลายเซ็นได้ $t/2^k$ และสิ่งนี้ถือเป็น $t \leq 2^k$.
def 2: รูปแบบลายเซ็นให้ผลตอบแทน k-bits ของการรักษาความปลอดภัยในการตั้งค่าผู้ใช้หลายคน หากความน่าจะเป็นที่ผู้โจมตีที่ได้รับคีย์สาธารณะ N รายการสามารถปลอมแปลงลายเซ็นสำหรับคีย์สาธารณะ N รายการใด ๆ ได้มากที่สุด $t/2^k$ และสิ่งนี้ถือเป็น $t \leq 2^k$.
ขั้นแรก โปรดทราบว่ามีการลดลงระหว่างการรักษาความปลอดภัยแบบผู้ใช้หลายคนและการรักษาความปลอดภัยแบบผู้ใช้คนเดียวแบบมาตรฐานสำหรับรูปแบบลายเซ็น: มันได้รับการพิสูจน์แล้ว ในปี พ.ศ. 2545 โดย Galbraith, Malone-Lee และ Smart (GSM) ว่าสำหรับระบบลายเซ็นใด ๆ จะโจมตีโครงร่างในการตั้งค่าผู้ใช้หลายคนด้วย $N$ คีย์สาธารณะไม่สามารถเพิ่มอัตราส่วนความสำเร็จของผู้โจมตี (ซึ่งเป็นผลหารของความน่าจะเป็นของความสำเร็จและเวลาในการทำงาน) โดยปัจจัยมากกว่า $N$ เมื่อเทียบกับการโจมตีโครงร่างในการตั้งค่าผู้ใช้คนเดียว
นี่เป็นผลลัพธ์ที่ชัดเจน การใช้สัญกรณ์ของคุณหมายความว่าในการตั้งค่า MU ขอบเขตของคุณถูกล้อมรอบด้วย $\frac{Nt}{2^k}$ คุณมี $\frac{t}{2^k}$ ในการตั้งค่า SU แต่เราไม่ทราบการโจมตีเชิงปฏิบัติใด ๆ ที่บรรลุขอบเขตดังกล่าวสำหรับรูปแบบลายเซ็น ขอให้สังเกตว่าหากเป็นกรณีนี้ หากเรามี N ขนาดใหญ่ เช่น 2^32 ผลกระทบต่อความปลอดภัยของโครงร่างลายเซ็นจะยิ่งใหญ่มาก!
เรามักจะชอบ แน่นขึ้น การลด
สังเกตว่าการโจมตี กับแผนลายเซ็น ในการตั้งค่าที่มีผู้ใช้หลายคนจะไม่ถูกรวมเข้ากับการโจมตี MAC ในการตั้งค่านั้น ซึ่งไม่จำเป็นต้องดีเท่าแบบแผนลายเซ็นตามที่กล่าวไว้ในบทความยอดเยี่ยม "ดูที่ความหนาแน่นอีกครั้ง" กระดาษโดย Chatterjee, Menezes และ Sarkar และผลสืบเนื่องของมัน "ดูความแน่น II อีกครั้ง". ทั้งสองเป็นการอ่านที่ยอดเยี่ยมในประเด็นประเภทนี้
ฉันขอแนะนำให้คุณอ่าน "ความปลอดภัยของ Signature Schemes ในการตั้งค่าผู้ใช้หลายคน" โดย Menezes และ Smart จากปี 2004 เนื่องจากเกี่ยวข้องกับข้อกำหนดด้านความปลอดภัยในการตั้งค่า MU สำหรับรูปแบบลายเซ็น:
เราโต้แย้งว่าคำนิยามความปลอดภัยที่ยอมรับกันดีสำหรับรูปแบบลายเซ็น [18] ไม่เพียงพอสำหรับการตั้งค่าผู้ใช้หลายคน โชคดีที่ดูเหมือนว่าคำจำกัดความนี้สามารถขยายไปยังบัญชีสำหรับการโจมตีเหล่านี้ได้อย่างง่ายดายในการตั้งค่าผู้ใช้หลายคน
พวกเขายังเกี่ยวข้องกับสิ่งที่เรียกว่า "Key Substitution Attacks" ซึ่งครอบคลุมอยู่ในคำจำกัดความของพวกเขา
สะดุดตาที่สุด (เน้นของฉัน):
ในข้อ 2.2 เราแย้งว่าฝ่ายตรงข้ามของแผนลายเซ็นในการตั้งค่าผู้ใช้หลายคนจะประสบความสำเร็จหากสร้างการปลอมแปลงที่มีอยู่หรือการแทนที่คีย์ ไม่ว่าในกรณีใด การโจมตีจะกระทำต่อคีย์สาธารณะหนึ่งคีย์. ดังนั้นจึงเพียงพอแล้วที่จะต้องพิจารณาการตั้งค่าผู้ใช้หลายคนซึ่งมีคีย์สาธารณะเพียงคีย์เดียวในขั้นต้น สิ่งนี้จะไม่สูญเสียความหมายทั่วไป เนื่องจากฝ่ายตรงข้ามที่โจมตีเอนทิตีหนึ่งสามารถจำลองเอนทิตีอื่นๆ โดยการเลือกคีย์สาธารณะของตนเพื่อให้ทราบคีย์ส่วนตัวที่เกี่ยวข้อง.
เห็นได้ชัดว่าศัตรูในการตั้งค่าผู้ใช้คนเดียวจะลดลงเป็นหนึ่งโดยธรรมชาติในการตั้งค่าผู้ใช้หลายคน
และพวกเขาสรุปด้วยว่าไม่มีจริง ความต้องการ ที่จะต้องกังวลเกี่ยวกับการตั้งค่าผู้ใช้หลายคนสำหรับรูปแบบลายเซ็นทันทีที่เราสามารถผูกเข้ากับรหัสสาธารณะและได้ผลลัพธ์ที่น่าสนใจมาก:
รูปแบบลายเซ็นที่ปลอดภัยในการตั้งค่าผู้ใช้คนเดียวสามารถแปลงเป็นรูปแบบที่ปลอดภัยภายใต้ข้อกำหนดใหม่ของเราในการตั้งค่าผู้ใช้หลายคนโดยการแฮชคีย์สาธารณะพร้อมกับข้อความเมื่อคำนวณข้อความย่อย
หมายเหตุ: สิ่งนี้อธิบายได้อย่างชัดเจนว่าเหตุใดเราจึงเพิ่มรหัสสาธารณะในข้อความย่อยในรูปแบบลายเซ็น "Schnorr-like" "สพป". (ที่จริงอาจเป็นเพราะ DJB พบข้อบกพร่อง ในการลดการตั้งค่าจากผู้ใช้คนเดียวเป็นการตั้งค่าผู้ใช้หลายคนที่ GSM มอบให้ในปี 2545 แต่ในขณะเดียวกันเราก็มี หลักฐานอื่น นั่นแสดงว่าไม่จำเป็นสำหรับลายเซ็น Schnorr ... แต่ DJB ลองใช้เมื่อเขาสร้าง EdDSA ฉันเดา ;))
นอกจากนี้ โปรดสังเกตว่ารูปแบบการโจมตีสำหรับการปลอมแปลงในการตั้งค่าผู้ใช้หลายคนคือการให้ฝ่ายตรงข้าม $n$ ลงนาม oracles, หนึ่งรหัสสำหรับแต่ละรหัสสาธารณะและได้รับอนุญาตให้ทำได้มากที่สุด $คิว$ สอบถามไปยังออราเคิลเหล่านี้ ในตอนท้ายของการโจมตี ฝ่ายตรงข้ามจะต้องส่งออก (โดยมีความเป็นไปได้มากที่สุด $\epsilon$) ทูเพิลที่มี:
ความปลอดภัยของโครงร่างดังกล่าวจะถูกกำหนดขึ้นอยู่กับ $คิว$, $n$. สิ่งนี้เรียกว่าโมเดล "ผู้ใช้หลายคนที่ไม่สามารถคาดเดาได้ต่อการโจมตีด้วยข้อความที่เลือก" (MU-UF-CMA)
นอกจากนี้ ก่อนที่จะ "กำหนด" ความปลอดภัยสำหรับรูปแบบลายเซ็นในการตั้งค่าใดๆ เราจำเป็นต้องทราบ "ความปลอดภัยประเภทใด" ที่เราพยายามจะบรรลุ เป็นการดีที่จะกล่าวว่า "รูปแบบลายเซ็นให้ความปลอดภัยระดับ k-bit ในการตั้งค่าผู้ใช้คนเดียว" แต่กับการโจมตีประเภทใด ในหัวข้อที่ว่า กระดาษน้ำเชื้อ โดย Goldwasser Micali และ Rivest เป็นการอ่านที่ดีแม้ว่าจะค่อนข้างเก่าและขาดการตั้งค่าผู้ใช้หลายคนอย่างแน่นอน
แนวคิดทั่วไปเกี่ยวกับความปลอดภัยสำหรับรูปแบบลายเซ็นเรียกว่า "EUF-CMA" ซึ่งหมายถึง "การมีอยู่ที่ไม่สามารถแก้ไขได้ภายใต้การโจมตีข้อความที่เลือกแบบปรับเปลี่ยนได้" นั่นคือการยากที่ฝ่ายตรงข้ามจะพบข้อความ "ปลอมแปลง" สำหรับ ให้รหัสสาธารณะ (นอกจากนี้ยังมีแนวคิดของ SUF-CMA "Strong Existential Unforgeability under Chosen Message Attack" ซึ่งกำลังพยายามลดความอ่อนไหวของรูปแบบลายเซ็น)
แต่ในการตั้งค่าผู้ใช้หลายคน มีแนวคิดอื่นที่น่าสนใจ นั่นคือแนวคิดของ "การโจมตีทดแทนที่สำคัญ" (KSA) ซึ่งเราสามารถสร้างคีย์สาธารณะใหม่ที่จะตรวจสอบคู่ (ข้อความ ลายเซ็น) ที่กำหนดได้ และมีการโจมตีแทนที่คีย์ในแผนลายเซ็น EUF-CMA ที่ปลอดภัยที่พิสูจน์ได้! (เช่น ใน NTRUSign หรือใน "Short ลายเซ็นโดยไม่ต้องใช้ oracles แบบสุ่ม") สิ่งที่น่าสนใจจริงๆ ของ KSA ก็คือ ผู้ลงนามที่เป็นอันตราย ก็สามารถเป็นนักแสดงในฉากแบบนี้ได้!
ในที่สุด "การมีความปลอดภัย k-bit" เป็นจริง กับรูปแบบการโจมตีบางอย่าง (แต่อันไหนล่ะ) และเป็นแนวทางให้เราได้จริงๆ เปรียบเทียบ การเข้ารหัสคีย์สาธารณะด้วยการโจมตี crypto/bruteforce คีย์สมมาตร เป็นวิธีที่เราใช้เพื่อให้มีเมตริกที่ช่วยให้เราเปรียบเทียบได้ แต่บางครั้งก็ค่อนข้างยากที่จะประเมินในแง่สัมบูรณ์ มีกระดาษเช่นบน https://www.keylength.com/ ที่ช่วยให้คุณเห็นวิธีต่างๆ ที่เราต้อง "ประเมิน" ความปลอดภัยของ crypto แบบอสมมาตร เมื่อเปรียบเทียบกับ crypto แบบสมมาตร และอย่างที่คุณเห็น ค่าต่างๆ กำลังเปลี่ยนจากกระดาษหนึ่งไปยังอีกกระดาษหนึ่ง
ในท้ายที่สุดสิ่งที่เราพยายามประเมินด้วยเมตริก k-bit คือความยากในการทำลายแผนบางอย่างเมื่อเทียบกับการโจมตีแบบเดรัจฉาน (แนะนำให้อ่าน. บทความนี้โดย DJB ในการโจมตีแบบเดรัจฉาน) แต่นั่นคือการใช้สิ่งที่ดีที่สุด เป็นที่รู้จัก การโจมตีโครงร่างคีย์สาธารณะเหล่านี้ และดังนั้นจึงไม่แน่นอน มันเป็นมาตรการที่สัมพันธ์กัน
คำจำกัดความของคุณโดยใช้ $t/2^k$ ประมาณว่าเป็นการโจมตีแบบเดรัจฉาน: จำนวนครั้งที่พยายามหารด้วย "จำนวนสูงสุด"
ดังนั้น สิ่งที่คุณพูดคือโดยพื้นฐานแล้วเรานิยาม "การมีความปลอดภัยระดับ k-bit" ว่า "ยากพอๆ กับการโจมตีแบบ bruteforce บนคีย์ k-bit" ซึ่งฉันเห็นด้วยอย่างยิ่ง พวกเราทำ.
แต่เป็น "คำจำกัดความที่ถูกต้องโดยทั่วไปของ ความปลอดภัย" สำหรับรูปแบบลายเซ็นคีย์สาธารณะจะไม่ขึ้นอยู่กับแนวคิดของ "บิตของความปลอดภัย" มันยังคงมีแนวคิดของพารามิเตอร์ความปลอดภัย $k$ และยังคงใช้ค่า $\mathbb{1}^k$ เป็นข้อมูลป้อนเข้าตามปกติ แต่จะใช้เป็นวิธีจำกัดฝ่ายตรงข้ามให้ทำน้อยกว่าการโจมตีด้วยกำลังดุร้ายธรรมดา และด้วยเหตุนี้จึงเป็นข้อมูลป้อนเข้าไปยังฝ่ายตรงข้ามด้วย แต่จะมีการกำหนดโดยใช้รูปแบบการโจมตีบางอย่างเช่นข้างต้น
นี่คือเหตุผลที่ฉันพูดถึง "รูปแบบการโจมตี" ก่อนหน้านี้ และไม่สามารถให้คำจำกัดความที่ดีไปกว่า "ใช่ แน่นอน: bruteforce ควรมีความยากแบบเดียวกับในการตั้งค่าผู้ใช้คนเดียวสำหรับการปลอมแปลงในผู้ใช้หลายคน"
แต่เนื่องจากเราไม่มีการลดลงทั่วไปที่ "รัดกุม" มากไปกว่านั้น เราจึงไม่สามารถพูดได้อย่างแน่นอนว่าเป็นกรณีนี้จริงหรือไม่โดยทั่วไป แต่แน่นอนว่าเป็นกรณีของลายเซ็น Schnorr ตามทั้งสองอย่าง ข้างต้น เชื่อมโยง เอกสาร.
ขอให้สังเกตว่าคำตอบของ fgrieu บอกเป็นนัยถึงแนวคิดเรื่องความรัดกุมเช่นกัน แต่จากมุมมองกลับกัน
ฉันจะถือว่า $t$ คือจำนวนของ "ปฏิบัติการ" (เช่น ปฏิบัติการกลุ่ม) ที่ศัตรูทำ และจำนวนของการดำเนินการดังกล่าวที่ผู้ใช้ที่ถูกต้องตามกฎหมายต้องลงนามและตรวจสอบมีน้อย (เช่น ไม่กี่ครั้ง $k$; หรือที่พหุนามมากสุดใน $k$).
คำถาม Def 2 มีไว้สำหรับ ความปลอดภัยสำหรับ $N$ ผู้ใช้. สำหรับความจริง ความปลอดภัยในการตั้งค่าผู้ใช้หลายคนเราจะต้องกำหนด $N$ จาก $k$แต่ฉันไม่สามารถอ้างแหล่งที่มาได้ ฉันจะแทนที่ $N$ โดย $2^{\อัลฟ่า k}$ สำหรับบางคนที่มีเหตุผล $\alpha>0$. ผู้ปฏิบัติมักจะพอใจกับ $\alpha=1/4$ (ยอม $N=2^{32}$ สำหรับ $k=128$ ) นักทฤษฎีอาจต้องการชนสิ่งนั้น $\alpha=1$.
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
