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

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

תיאור כללי

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

הגדרה כללית

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

דוגמאות

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