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

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

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

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

תיאור כללי

חשילות בתחום המטלורגיה פירושה היכולת לעמוד בלחצים ולשנות צורה מבלי להישבר (או תכונת הפלסטיות). אפשר להמחיש את הרעיון החשילות בהקשר של קריפטוגרפיה על ידי מכרז. לצורך המשל נניח שהמשתתפים במכרז כלשהו יכולים להצפין את הצעותיהם על ידי פונקציית מפתח פומבי $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$ מתייחס לפרימיטיב קריפטוגרפי מאילו המנויים. נתון $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\leq i\leq k$
   1. עבור $1\leq j\leq 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\leq i\leq 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\leq i\leq k$ כדי לקבל את $b_{i}$.