הצפנה מרובה

קסקדת הצפנה

המונח קסקדה או אשד מתייחס להצפנה עם מספר אלגוריתמים שונים ועם מפתחות הצפנה שונים. הרעיון הגיוני במקרים מסוימים כמו בסיטואציה שבה שני גורמים או ישויות ברשת מעוניינים לשתף ביניהם מידע סודי וכל אחד מהם סומך רק על אלגוריתם ההצפנה שבאמתחתו ואינו סומך על האלגוריתם השני, כי הוא חושש שתמצא דרך קלה לשבירתו בעתיד הקרוב. כדי שהם יוכלו להתקשר בבטחה, טבעי הדבר לחפש דרך שבה יוכלו לשלב את ביטחון שניהם, כך שאם תתגלה התקפה מעשית טובה כנגד אחד מהם, ביטחון המידע יישען על האלגוריתם השני ולהפך. בהנחה שלא סביר שימצאו בו זמנית דרכים קלות לשבירת כל האלגוריתמים המשתתפים בקסקדה.
במאמר משנת 1993 מצביע יואלי מאורר על חשיבות הצופן הראשון ברצף. למעט פנקס חד-פעמי כל צופן ניתן לשבירה, עובדה זו משליכה כי בהכרח קיימים מאפיינים מסוימים בטקסט המוצפן שייחודיים להצפנה ספציפית. בהצפנה מרובה, מאפיינים אילו עלולים לזלוג מהטקסט המוצפן הראשון לבאים אחריו ובכך להחלישם. או אם קיימת אינטארקציה קלה בין האלגוריתמים כגון במקרים בהם הצופן הראשון מוסיף מחרוזת טקסט קבועה כלשהי לתוצאת ההצפנה. פעולה נפוצה ביישומים מעשיים ונקראת מספר קסם, אזי הצופן השני יהיה פגיע להתקפת גלוי-ידוע. כעת אם האלגוריתם הראשון חלש, משמעות הדבר שנוסף בידי התוקף מידע שמאפשר לפרוץ את הבא אחריו וכן הלאה. כלומר הוכח שהתוצאה הכוללת לא תהיה חזקה יותר מהאלגוריתם הראשון. המסקנה היא שהטענה שהצפנה מרובה תהיה חזקה לפחות כמרכיב החזק ברצף עשויה להיות שגויה.
מאורר הוכיח שקסקדה של אלגוריתמים עם מפתחות שונים ובלתי תלויים זה בזה סטטיסטית, חזקה לפחות כמו האלגוריתם הראשון - בתנאי שהאלגוריתמים המשתתפים בקסקדה קומוטטיביים ביחס זה לזה (כמו בצופני זרם אחדים). כמו כן הוכיח שאפשר להגיע למבנה בטוח של סכמת הצפנה מרובה שבה הביטחון הכולל הוא לפחות כמו האלגוריתם החזק מביניהם. מכאן שבמצב הפעלה OFB שמדמה תכונות צופן זרם אפשר לבנות הצפנה מרובה ממספר אלגוריתמים באופן שיניב ביטחון לפחות כמו החזק מביניהם. למשל על ידי שילוב פנקס חד-פעמי ב-XOR.
ביטחון מערכת הצפנה מרובה תלוי גם בהנחה שכל מפתחות ההצפנה נותרים סודיים. ייתכן שצריך מודל מחמיר יותר, כי צריך לענות על השאלה האם המערכת נותרת חזקה לפחות כהצפנה יחידה, במקרה שאחד המפתחות נחשף. הגדרה זו של התקפת מוצפן נבחר מסומנת ME-CCA, בה נוסף מרכיב שנקרא 'אורקל חשיפת מפתח'. דהיינו לפי המודל יוצאים מהנחה שהתוקף מוסגל לפנות לאורקל היפותטי ולבקש חשיפת מפתח כלשהו (אבל לא את כולם) והשאלה היא כמה יקל בידו הדבר לפרוץ את המערכת כולה.
פרויקט NESSIE פרסם בשנת 2003 המלצות לאלגוריתמים אסימטריים ובין היתר המליץ להגברת הביטחון, להשתמש בהצפנה מרובה עם אלגוריתמים שונים המבוססים על בעיות שונות מתורת המספרים. למשל הצפנה עם RSA וגרסה כלשהי של דיפי-הלמן כמו ECC.
במאמר משנת 1984 הוכיחו שמעון אבן ועודד גולדרייך שחוזק קסקדה עוקבת (דהיינו פלט הצפנה א' משמש קלט להצפנה ב' וכו') כנגד התקפת גלוי-ידוע שווה לסכום גודל המפתחות, עבור  הצפנות כל אחד עם מפתח בגודל  החוזק הכולל יהיה . הם מסכמים כי קסקדה של צופנים אקראיים אינה מהווה צופן אקראי, למרות זאת הקושי שבשבירת סכמה כזו אינו נופל מהקושי שבשבירת אחת מההצפנות. כמו כן הבעיה של הצבת חסם תחתון לשבירת קסקדה ארוכה היא בעיה קשה, קיומו של חסם כזה מצביע על כך ש-.

מבנה גנרי של הצפנה מרובה בשילוב סכמת חלוקת סוד

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

טרנספורמציית הכול או לא כלום

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