חשילות (קריפטוגרפיה)

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בקריפטוגרפיה, חשילות (Malleability) היא מושג שהוטבע לראשונה בשנת 2000 על ידי דני דולב האוניברסיטה העברית, סינטיה דוורק חטיבת המחקר של IBM ומוני נאור מכון ויצמן[1] והוא הרחבה של המושג בטחון סמנטי בסכמות הצפנת מפתח פומבי, חתימה דיגיטלית ומפתח סימטרי. באופן פורמלי בהקשר של הצפנה, 'אי-חשילות' היא דרישה מחמירה של בטחון סמנטי, שבהינתן טקסט מוצפן בלבד יהיה בלתי אפשרי לייצר טקסט מוצפן שונה, כך שקיים קשר או יחס כלשהו בין הטקסטים המקוריים המתאימים להם, זאת מבלי לפענחו. במילים אחרות לא ניתן להיעזר בטקסט המוצפן בשום צורה ישירה או עקיפה. התפישה הזו מתאימה גם בהקשר של סכמת התחייבות והוכחה באפס ידיעה. בהקשר של חתימה דיגיטלית הרעיון ידוע כ'זיוף קיומי' (Existential forgery) שהוא המקביל לחשילות. בטחון סמנטי לעומת זאת רק מחייב שהתוקף לא יצליח ללמוד מהטקסט המוצפן בלבד שום מידע ישיר או עקיף אודות טקסט המקור שלא ניתן היה להשיג בדרך אחרת.

הוכח שאם סכמת הצפנה אי-חשילה, היא חסינה כנגד התקפת מוצפן-נבחר החזקה כפי שנוסחה לראשונה על ידי ראקוף וסימון, שבה בידי התוקף טקסט-מוצפן אותו הוא מעוניין לפענח וביכולתו להגיש באופן מקוון שאילתות ל'אורקל פענוח' לפענוח כל טקסט-מוצפן אחר שיבקש, למעט הטקסט המותקף. נהוג לסמנה CCA2 או CCApost. סכמות הצפנה דטרמיניסטיות כמו RSA, אינן עונות להגדרה זו ולכן לא חסינות כנגד התקפת מוצפן-נבחר. גם סכימות הסתברותיות כמו אל-גמאל ובלום-גולדווסר המוגדרות כבטוחות סמנטית, אינן עמידות כנגד התקפת מוצפן נבחר בהגדרה החזקה שלה.

על בסיס הגדרת חשילות אפשר לבנות סכימת הצפנת מפתח פומבי שתהיה אי-חשילה, דהיינו עמידה בפני התקפת CCA. ראה הצפנת קריימר-שאופ. בעיקרון ניתן לבנותה מכל פונקציה חד-כיוונית עם דלת מלכודת (trap-door) והיא נקראת גם הסתברותית כיוון שהיא מערבת שימוש במספרים אקראיים ולכן מסתמכת גם על הנחת העבודה שמחולל המספרים האקראיים בטוח מבחינה קריפטוגרפית.

תיאור כללי[עריכת קוד מקור | עריכה]

חשילות בתחום המטלורגיה פירושה היכולת לעמוד בלחצים ולשנות צורה מבלי להישבר (או תכונת הפלסטיות). אפשר להמחיש את הרעיון החשילות בהקשר של קריפטוגרפיה על ידי מכרז. לצורך המשל נניח שהמשתתפים במכרז כלשהו יכולים להצפין את הצעותיהם על ידי פונקציית מפתח פומבי E של מפרסם המכרז, זאת כדי שאחרים לא יוכלו ללמוד על הצעותיהם לפני שיוגשו. האינטרס של כל מציע הוא ללמוד את הצעות המתחרים האחרים לפני שיגיש את הצעתו, כך שיוכל לדאוג ששלו תהיה הנמוכה מביניהם וסיכוייה להתקבל יהיו הגבוהים ביותר. תכונת החשילות במקרה זה היא שבהינתן ההצעה E(A) של המציע A, יהיה ביכולתו של המציע B (שרואה את E(A) כלומר את ההצעה המוצפנת בלבד) להציע את E(B) כך שיתקיים בסבירות גבוהה E(B) < E(A), זאת מבלי לפענח את E(A). ההנחה היא ש-B יכול לנסות הצפנה של ערכים שונים בשאיפה למצוא קשר כלשהו בינם ל-E(A) ובכך להצליח להגיש הצעה שתקיים את התנאי האמור בסבירות מסוימת, מבלי לדעת מה היא ההצעה בדיוק.

בהקשר של חתימה דיגטלית, זיוף קיומי מתייחס למצב שבו בהינתן חתימה לגיטימית S(m_1) על המסר m_1, המתקיף יוכל בעזרתה לייצר חתימה S(m_2) שתהיה תקפה עבור מסר אחר כלשהו m_2, גם אם הוא חסר משמעות.

בצופן סימטרי ניתן לראות תכונת אי-חשילות בעיקר בפרוטוקול תקשרות כמו קרברוס שבו, המשתתפים A ו-B משתפים ביניהם מפתח הצפנה סימטרי K וכחלק ממהלכי הפרוטוקול A שולח ל-B מסר סתמי (Nonce) מוצפן K_{AB}(N) ומצפה לקבל בתגובה הצפנה של מסר אחר שהוא פונקציה פשוטה שלו: K_{AB}(f(N)), כאשר f(x)=x+1 למשל. בטחון הפרוטוקול מסתמך על הנחה (שלא הוכחה) שבהינתן רק הצפנת המסר הראשון, המתקיף לא יוכל לייצר את K_{AB}(f(N)) כך שיתקבל כלגיטימי בעיני B. זוהי בדיוק אי-חשילות בהקשר זה.

בהקשר של הוכחת ידיעה ניתן להגדיר אי-חשילות באופן שהמוודא B לא יוכל להשתמש בהוכחה של A כדי להתחזות אליו כלפי צד שלישי E בדומה להתקפת אדם באמצע. כלומר B ישמש מעין 'תווך' שמעביר את כל ההוכחות שניתנות על ידי A ל-E וכן את כל האתגרים שמציב E בחזרה ל-A. בניסיון להוכיח ל-E שכביכול הוא (B) בעל הידיעה ובעצם להתחזות ל-A.

הגדרה של סכמת התחייבות היא, שצד הגון A המעוניין להתחייב לצד הגון B על קיומה של פיסת מידע כלשהי \alpha מבלי לחשוף בפניו את המידע עצמו. סביר להניח שעלול להימצא קשר או יחס כלשהו R בינו לבין ערך אחר נניח \beta שחושב על ידי צדדים רמאים C,D (שיכולים להיות גם A,B עצמם או אחד מהם), אותו נסמן R(\alpha,\beta). אי-חשילות בהקשר זה תהיה התכונה שהפרוטוקול יוכל להבטיח שלא יהיה ניתן ליצור יחס R כזה, שלא ניתן היה לחישוב ללא גישה לצדדים ההגונים A ו-B אלא אם כן \alpha=\beta. הדברים האמורים נכונים גם אם A אינו מודע לקיומם של C או D או להיפך. ניתן לראות שיש קשר הדוק בין סכמת התחייבות להוכחת אפס-ידיעה.

הגדרה כללית[עריכת קוד מקור | עריכה]

לצורך הגדרה כללית המתאימה לכל תחומי ההצפנה המדוברים, נניח ש-P מתייחס לפרימיטיב קריפטוגרפי מאילו המנויים, אם P הוא פרימיטיב הצפנה הוא יקרא הסתברותי. נתון GP שהוא מחולל המייצר צמד מפתחות-הצפנה (e,d) (פומבי/פרטי בהתאמה). הפונקציה E_e(b,r) נקראת הצפנה של הסיבית b\in \{0,1\} ומחרוזת אקראית r באורך p(n) שהיא פונקציה כלשהי של הקלט n והפונקציה D_d(c) היא הפענוח. אזי עבור כל מחרוזת אקראית אפשרית r מתקיים D_d(E_e(b,r))=b. כאשר b=0,1. המערכת המתוארת תקרא בלתי ניתנת להבחנה (indistinguishability), אם עבור כל מכונה דמיונית M, קיים c>0 המקיים:

|\Pr[M(e,E_e(0,r))=1] - \Pr[M(e,E_e(1,r))=1]|<1/n^c

הוכח שאי-יכולת הבחנה היא דרישה חשובה לצורך בטחון סמנטי בהקשר של התקפת מוצפן-נבחר. בהקשר זה מציאת יחס R(\alpha,\beta) כלשהו שניתן להבחנה בין שני טקסטים מוצפנים \alpha, \beta אפילו בלא ידיעת מקורם, חשובה כשבירת הצופן. במילים אחרות עבור כל מתקיף אפשרי A קיים סימולטור A' כך שכל יחס R(\alpha,\beta) שניתן לחישוב על ידי A בעזרת פונקציה (רמז או היסטוריה כלשהי של \alpha) ניתן להפקה על ידי A' מבלי שתהיה לו גישה לתהליך ההצפנה.

לא ניתן לפתור את הבעיה על ידי חתימה דיגיטלית כלומר שהשולח יצרף את חתימתו למשלוח כך E(m), S_A(E(m)), כיוון שאם אלגוריתם ההצפנה E בר-חשילות אזי התוקף יכול להתעלם מהחתימה ולייצר את הערך E(m+1), S_B(E(m+1)) כאשר S_B היא חתימת המתקיף. גם הכנסת החתימה בתוך הטקסט המוצפן לא תועיל.

דוגמאות[עריכת קוד מקור | עריכה]

בצופן זרם בדרך כלל מבצעים XOR של סיביות הטקסט m עם פונקציה S של המפתח k ומתקבל E(m)=m\oplus S(k). אפשר לראות שניתן בקלות ליצור הצפנה של המסר m\oplus x עבור כל x כיוון ש-E(m)\oplus x=m\oplus x\oplus S(k)=E(m\oplus x).

ב-RSA המתקיף יכול לייצר הצפנה של mx מתוך E_e(m) עבור כל x כיוון שפונקציית ההצפנה E_e(m)=m^e\bmod\ n כאשר e,n הם מפתחות פומביים מקיימת את הזהות הבאה: E_e(m)\cdot x^e\bmod\ n=(mx)^e\bmod\ n=E_e(mx). מסיבה זו נהוג לרפד את המסר לפני ההצפנה. בשני המקרים מתקבל מסר מוצפן אחר לגיטימי גם אם לא בהכרח בשליטה מלאה של התוקף.

בצופן סימטרי שמופעל במצב CBC שבו כל גוש טקסט קריא מחובר ב-XOR עם הטקסט המוצפן הנוכחי לפני שהוא מוצפן. קיימת תופעה ידועה שאם משנים סיבית אחת בטקסט המוצפן הגוש המפוענח משתבש לחלוטין אבל הגוש הבא חוזר להיות תקין למעט הסיבית המקבילה לזו ששונתה בגוש הקודם כשהיא הפוכה ממנה. בגלל תופעה זו ניתן למעשה לבצע שינויים נקודתיים בסיביות מסוימות במחיר של אובדן גוש אחד. בעקרון אפשר למנוע התקפות מסוג זה על ידי קוד אימות מסרים.

סכמת הצפנה בטוחה סמנטית כנגד התקפת מוצפן-נבחר[עריכת קוד מקור | עריכה]

כדי לבנות מודל כזה יש צורך להשתמש בסכמת הוכחת אפס-ידיעה בטוחה. הרעיון הוא ליצור קבוצה גדולה של מפתחות הצפנה ופענוח ולהשתמש רק בחלק מהם בהתאם לערך שמושג על ידי פונקציית גיבוב חד-כיוונית. כדי להבטיח שההצפנה תהיה עקבית, כלומר שמתקיף לא ניסה ערכים שונים על מנת לרמות את המערכת, משתמשים בסכמת התחייבות של הוכחת אפס ידיעה לא אינטראקטיבית, המאפשרת לוודא לאחר מעשה שהערכים מקיימים את התנאי שכל ההצפנות מתייחסות לערך זהה. המפתח הפומבי כולל שלושה מרכיבים, אוסף של זוגות מפתחות \langle e_i^0,e_i^1\rangle, כאשר i=1,...,n. מחרוזת אקראית U לצורך הוכחת אפס ידיעה. ומשפחה H של פונקציות גיבוב חד-כיווניות אוניברסליות. תהליך ההצפנה מורכב מארבעה שלבים:

  1. יוצרים זוג מפתחות חתימה דיגיטלית. מפתח אימות פומבי ומפתח חתימה פרטי. אפשר להשתמש בסכמה חד-פעמית.
  2. מצפינים את המסר באמצעות מספר מפתחות הצפנה מתוך הרשימה כפונקציה של ערך הגיבוב של מפתח האימות שמופק בשלב 1.
  3. מכינים הוכחת אפס-ידיעה (לא אינטראקטיבית) של עקביות ההצפנה, כלומר שלא הוצפנו ערכים שונים.
  4. חותמים על כל התוצאות באמצעות מפתח החתימה שהוכן בשלב 1.

לפענוח מבצעים תהליך הפוך. והחתימה הדיגיטלית צריכה להיות משויכת לחותם באופן מוכח כלשהו. פונקציית הגיבוב מתפקדת כאן כמו בחתימה דיגיטלית, היא מאפשרת להקטין את n (מספר זוגות המפתחות) מבלי לפגוע בבטחון הסמנטי.

הכנת מפתחות[עריכת קוד מקור | עריכה]

  1. באמצעות המחולל GP מייצרים 2n זוגות: (e_i^0,d_i^0),(e_i^1,d_i^1) כאשר i=1,...,n.
  2. מייצרים מחרוזת אקראית U
  3. מייצרים ערך אקראי h\in_R H

המפתח הפומבי הוא n זוגות: \langle h,e_1^0,e_1^1,...,e_n^0,e_n^1,U\rangle, המפתח הפרטי הוא: \langle d_1^0,d_1^1,...,d_n^0,d_n^1\rangle.

הצפנה[עריכת קוד מקור | עריכה]

הקלט הוא המסר m=b_1,...,b_k

  1. מייצרים מפתחות חתימה דיגטלית, כאשר F מפתח אימות פומבי ו-P מפתח חתימה פרטי.
  2. מחשבים את h(F) שהיא פונקציית גיבוב, כאשר התוצאה היא מחרוזת n סיביות v_1,v_2,...,v_n.
  3. עבור 1\le i\le k
    1. עבור 1\le j\le n
      1. בוחרים פונקציית גיבוב חד-כיוונית אקראית r_{ij}{\in}_R\{0,1\}^{p(n)}
      2. מחשבים את c_{ij}=E_{e_j^{v_j}}(b_i,r_{ij}). הצפנה של הסיבית b_i באמצעות מפתח ההצפנה e_j^{v_j}.
    2. באמצעות הוכחת אפס ידיעה של ערכי c_i=e_1^{v_1},...,e_n^{v_n} מייצרים את ההוכחות p_i באמצעות העדים r_{i1},...,r_{in}.
  4. מייצרים חתימה s על הרצף (c_i,p_i) כאשר i=1,...,k. והטקסט המוצפן הוא: \langle F,s,(c_1,p_1),...,(c_k,p_k)\rangle.

פענוח[עריכת קוד מקור | עריכה]

  1. מוודים שהחתימה s תקפה באמצעות מפתח האימות הפומבי F שהתקבל ביחד עם המסר המוצפן.
  2. עבור 1\le i\le k מוודים שערכי c_i עקביים באמצעות הוכחת אפס-הידיעה שניתנה (באמצעות הערכים (p_1,...,p_k,U)).
  3. מחשבים את h(F) כשהפלט הוא v_1,...,v_n.
  4. אם בדיקת אמיתות ההוכחה באפס ידיעה התקבלה עבור כל k הערכים אזי מחלצים את המסר באמצעות \langle d_1^{v_1},...,d_n^{v_n}\rangle עבור 1\le i\le k כדי לקבל את b_i.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ "Nonmalleable Cryptography" (2000). SIAM Journal on Computing 30 (2): 391–437. doi:10.1137/S0097539795291562.