הצפנה מרובה

הצפנה מרובה (Multiple encryption) היא דרך להצפין מידע פעמים מרובות באמצעות מפתחות הצפנה שונים. קַסְקָדָת (Cascade) הצפנה היא הצפנה מרובה באמצעות אלגוריתמים שונים (ומפתחות שונים). הבחנה זו לא תמיד נעשית, לרוב מתייחסים להצפנה מרובה באופן כללי כאל קסקדה. מקובל שהצפנה מרובה עם מפתח זהה לא רק שאינה מניבה ביטחון רב יותר אלא אף מחלישה אותו ברוב המקרים, משום שההצפנה השנייה עלולה לבטל את הראשונה חלקית או באופן מלא. במיוחד בצפנים בהם ההצפנה והפענוח נעשים בפונקציה זהה. בפנקס חד-פעמי למשל, הצפנה חוזרת עם אותו מפתח שקולה לפענוח וכן בכל צופן זרם. יתרה מזו, סיבוכיות ההתקפה כנגד המערכת אינה עולה באופן ניכר, כיוון שהתוקף יודע שנעשה שימוש במפתח זהה (ההנחה היא תמיד שמספר ההצפנות, האלגוריתמים ששימשו להצפנה וכן סדר ההצפנה, ידועים לתוקף). המסקנה היא שמפתחות ההצפנה צריכים להיבחר באופן שיהיו בלתי תלויים סטטיסטית. כלומר לא תהיה דרך קלה להסיק מהו מפתח אחד בהינתן השני.

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

בהגדרה כללית כאשר מציינים 'צפנים' בלשון רבים, מתכוונים בעיקר להצפנה סימטרית או א-סימטרית חוזרת עם מפתחות הצפנה שונים, לא בהכרח עם אלגוריתמים שונים (ראה בהמשך לגבי אלגוריתמים שונים). ישנן כמה תצורות עיקריות של הצפנה מרובה:
 
הצפנה עוקבת: בשיטה זו שנקראת גם קסקדה, פלט הצופן הראשון מהווה קלט לצופן השני והשני לשלישי וכן הלאה. כאמור חובה על המפתחות להיות בלתי תלויים סטיסטית זה בזה. המודל הזה אומץ על ידי הרשת החברתית האנונימית Tor, קיצור של The Onion Routing. האנלוגיה ברורה, תהליך הפענוח דומה לקילוף בצל, כל שכבה מייצגת הצפנה אחת. במקרה של TOR, המטרה אינה הגברת הביטחון אלא הסתרת זהות המשתמש על ידי הצפנת חבילת המידע ומקורה מספר פעמים באמצעות מפתחות הפומביים של השרתים האנונימיים. תהליך הניתוב של חבילה עובר דרכם, כאשר כל אחד מהם מסיר שכבת הצפנה אחת בהתאם למפתח הפרטי שברשותו.
הצפנה מרוכבת (product cipher): הוצעה לראשונה על ידי שאנון והיא בעצם הבסיס התאורטי לצפני בלוקים מודרניים. הרעיון הוא שילוב לא ליניארי כלשהו של מספר טרנספורמציות לחיזוק הביטחון. בשיטה זו אין מגבלה שמפתחות ההצפנה בין כל טרנספורמציה יהיו בלתי תלויים. מעשית המפתחות שבשימוש כל טרנספורמציה, הן פונקציה, לפעמים פשוטה של מפתח אחר, בדרך כלל קטן.
הצפנה מקבילית:  היא הצפנה של טקסט-המקור עם כל מפתח בנפרד ושילוב ביניהם באופן שיבטיח כי פענוח יצליח רק אם מפענחים את כל החלקים, כמו עם טרנספורמציית הכול או לא כלום, אפשר להשיג זאת עם חיבור ב-XOR כמו בפנקס חד-פעמי או על ידי סכמת חלוקת סוד.  
הצפנה מרובה היברידית: אם משלבים בין השיטות השונות מתקבלת מערכת היברידית. דרך אחת לבנות מודל כזה היא באמצעות עץ הצפנות. שורש העץ הוא השכבה הראשונה של ההצפנה, הוספת שכבה מקבילית מרחיבה את העץ לרוחב, כלומר מוסיפה צמתים. ואילו הוספת שכבה רציפה או עוקבת מעמיקה את העץ בפקטור שהוא פונקציה של מספר הצופנים המרכיבים את סדרה. תוצאת הצפנת העץ היא פלט כל הצמתים שאין להם בנים.

הצפנה כפולה
התצורה הפשוטה ליישום הצפנה כפולה עוקבת היא להצפין את בלוק המידע פעמיים בזה אחר זה, עם מפתחות הצפנה שונים, כאשר פלט הצופן הראשון מהווה קלט לצופן השני, כדלהלן:
להצפנה מבצעים: 
לפענוח מבצעים:

התקפת היפגשות באמצע

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

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

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

הצפנה משולשת
בהצפנה משולשת מצפינים את המידע שלוש פעמים ברציפות עם מפתחות הצפנה שונים כדלהלן: . או בקיצור EEE כלומר שלוש הצפנות עוקבות. למעשה DES משולש שהוצע על ידי וולטר טאצ'מן שהיה ממפתחי DES, הוא מעין פשרה לשמירה על תאימות עם המערכות הקיימות תוך הגברת הביטחון. בשיטה זו משתמשים רק בשני מפתחות. מצפינים עם הראשון, מפענחים עם השני וחוזרים ומצפינים עם הראשון, כדלהלן:

הסימון המקוצר של השיטה הוא EDE, כלומר הצפנה/פענוח/הצפנה והיא עמידה קצת יותר כנגד התקפת נפגש באמצע של מרקל והלמן. הבחירה במבנה הייחודי הזה לא מניבה ביטחון משולש (כיוון ששניים מהמפתחות זהים). אך המבנה אומץ על ידי IBM בעיקר בשל שיקולי תאימות וכן אומץ על ידי תקן איזו ISO 8732. הסיבה היא שבדרך זו אפשר להשתמש באותה חומרה לביצוע הצפנה בשיטה הרגילה או המשולשת. כיוון שאם קובעים  מתקבלת הצפנה יחידה, אילו היו בוחרים בשלוש הצפנות עוקבות (EEE) התוצאה לא הייתה כזו. אך יש לזכור שהצפנת DES משולש איטית פי שלושה בהשוואה להצפנה בודדת עם מפתח אחד ואף פי כמה יותר בהשוואה לאלגוריתמים מודרניים כמו AES.

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

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

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

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

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

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

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

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

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

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

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

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

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

שים לב להתרחבות הצופן פי שלושה במקרה של הצפנה כפולה.

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

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

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

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

לשחזור מחשבים את  ואז .

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

 (תוצאת כל שלב היא ).
פלט הצופן הוא .
לפענוח תחילה מחשבים 
עבור כל הרכיבים  מחשבים .
פלט הפענוח יהיה  בתנאי ש- עבור כל .

לקריאה נוספת

הערות שוליים

קריפטוגרפיה