רשת החלפה-תמורה

בקריפטוגרפיה, רשת החלפה-תמורה (substitution-permutation network) או בקיצור SPN, היא מבנה איטרטיבי של פונקציה פנימית המהווה מרכיב עיקרי בליבת צופן בלוקים, ומופיעה בצפנים מודרניים רבים ביניהם AES, סרפנט, ARIA, SAFER. רשת החלפה תמורה היא פרדיגמה המיישמת את העקרונות של קלוד שאנון אבי תורת האינפורמציה, בכל סבב של הפונקציה הקלט "מעורבב" תוך שימוש בתיבות החלפה (קבועות או דינאמיות), "מפוזר" באמצעות תמורות ליניאריות או מטריצות הפיכות ומחובר עם המפתח להוספת סודיות. מהיבט תאורטי אפשר להוכיח שמבנה זה במספר סבבים מתאים, עמיד ביותר נגד התקפות קריפטואנליטיות ידועות והוא מועמד טוב לתמורה פסאודו-אקראית חזקה.

מראה רשת החלפה-תמורה בשלושה סבבים, $S_{i}$ מייצגים תיבות החלפה שאחראיות על הערבוב (confusion). הפיזור (diffusion) קורה לאחר ההחלפה ומיוצג על ידי הקווים המסתעפים לכל הכיוונים.

ערבוב ופיזור

התכונה העיקרית הנדרשת מצופן בלוקים היא שיתנהג לפחות על פניו כתמורה אקראית. לתמורה אקראית אמיתית באורך $n$ סיביות דרושים $\log(2^{n}!)\approx n\cdot 2^{n}$ סיביות כדי לייצגה במלואה. אפשר לחשוב עליה כעל פונקציה (או טבלה ענקית) שמתאימה עבור כל $x$ באורך $n$ סיביות $y$ כלשהו באורך $n$ סיביות. אם $n$ גדול (כגון $n\geq 64$) מספר כזה לא מעשי לחלוטין מהיבט של כמות הזיכרון הנדרשת כדי להכילה. מצד שני כדי שצופן בלוקים יהיה בטוח $n=64$ סיביות נחשב לבלוק קטן יחסית ורצוי שיהיה לפחות 128 סיביות בהתאם לתקנים הנוכחיים. לכן דרושה דרך אחרת יותר "תמציתית" לייצג פונקציה בסדר גודל כזה באופן שתתנהג כתמורה אקראית. קלוד שאנון, שפיתח את התאוריה של סודיות מושלמת, הציע פרדיגמה בסיסית לבניית פונקציה כזו שתראה אקראית ועדיין תהיה פרקטית. הרעיון הוא לצרף יחדיו מספר תמורות אקראיות קטנות $\{p_{i}\}$, לתמורה $P$ גדולה יותר. למשל אם הבלוק באורך 128 סיביות אפשר לחלקו ל-16 מקטעים כל אחד בגודל בית אחד ואז אפשר להגדיר את התמורה $P$ על ידי הסדרה $p_{1},p_{2},...,p_{16}$ שכל אחת מהן היא תמורה אקראית בגודל 8 סיביות. בהינתן הקלט $x$ באורך 128 סיביות ומפתח $k$, מחלקים את בלוק הקלט לשישה עשר מקטעים $x_{1},x_{2},...,x_{16}$ וכן המפתח $k_{1},k_{2},...,k_{16}$ ומעבירים בזה אחר זה את כל המקטעים של הקלט בתמורות המתאימות עם המפתחות המתאימים לפי הסדר:

$P_{k}(x)=p_{1}(x_{1}),p_{2}(x_{2}),\cdots ,p_{16}(x_{16})$.

היות שהתמורות אינן ליניאריות והן תלויות במפתח הסודי, הפעולה הזו אמורה לספק "ערבוב" (confusion) במובן שכל קלט שונה יניב פלט שונה ובלתי תלוי שנראה על פניו כאקראי. כל תמורה בגודל בית אחד תופסת $8\cdot 2^{8}$ סיביות או 256 בתים בזיכרון. היות שדרוש מפתח שונה עבור כל תמורה, אורך המפתח הכולל צריך להיות $16\cdot 8\cdot 2^{8}$ או 32Kb. מספר זה קטן מאוד בהשוואה ל-$128\cdot 2^{128}$ אילו הייתה זאת תמורה אקראית אמיתית.

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

אפקט מפולת

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

אפשר להוכיח שאם שני התנאים הבאים מתקיימים מובטח אפקט מפולת מלא בתוך שבעה סבבים בלבד:

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

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

רשת החלפה-תמורה

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

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

בחירת תיבות החלפה קבועות שתהיינה גם הפיכות אינה משימה פשוטה. בחירה אקראית לא מניבה את התוצאות שמצפים להן. למשל אם תיבת החלפה $S$ פועלת על קלט באורך 4 סיביות (בטווח של אפס עד 15), אפשר לראות שישנם ארבעה מקרים אפשריים בהם התוצאה של $S(x)$ שונה רק בסיבית אחת מהתוצאה של $S(x')$ כאשר $x\neq x'$, לכן בהסתברות של $4/15$ (יותר מ-25 אחוז) התוצאות לא יהיו שונות ביותר מסיבית אחת. אם מחברים את ההסתברות של כל התיבות מגלים שבחירת תיבות החלפה באופן עיוור אינה נבונה, במיוחד אם רוצים להגן מפני קריפטואנליזה דיפרנציאלית, אלא יש צורך לחפש בקפדנות אחר ערכים שמניבים אפקט מפולת אופטימלי, או במילים אחרות שפעילות תיבות ההחלפה תהיה גבוהה ככל האפשר.

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

הכנת המפתחות

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

פענוח

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

ביטחון

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

תנאי הכרחי לביטחון ברשת החלפה-תמורה הוא מספר חזרות מתאים. אפשר לראות שמספר נמוך מדי של חזרות יכול להביא לשבירת הצופן. בצופן AES למשל נקבע מספר הסבבים הדרוש בהתאם לאורך המפתח, עבור מפתח באורך 128 סיביות נקבעו 10 סבבים ואילו עבור מפתח 256 סיביות נקבעו 14 סבבים. קריפטואנליזה של AES עם מספר סבבים מופחת, מראה שאפשר לשבור אותו בפחות זמן מהדרוש להתקפת כוח גס.

קריפטואנליזה

• רשת החלפה תמורה בסבב אחד. כדי להמחיש מדוע מספר החזרות חשוב, נניח למען הפשטות שרשת ההחלפה-תמורה מבוצעת רק פעם אחת. נתונה הפונקציה $y=F_{k}(x)$ המקבלת את הבלוק הקריא $x$ ואת $k$ שהוא מפתח סודי אקראי, מבצעת את סדרת הפעולות המתוארת ומחזירה את $y$. המתקיף מקבל את $y$ ומנסה לגלות את $k$. במקרה כזה כל מה שהוא צריך לעשות זה לבצע את פעולות ההחלפה והפיזור בסדר הפוך ולבטל את השפעתן על התוצאה (צריך לזכור שמפרט הצופן ידוע לו ולכן הוא יכול להשתמש בפונקציית הפענוח) ואז מה שנשאר בידו הוא $x\oplus k$. כאן מניחים למען הפשטות שהמפתח נוצל כמו שהוא ללא תהליך הכנה מקדים כי מדובר בסבב אחד. אם יהיו בידו מספר בלוקים מוצפנים שהוצפנו עם אותו מפתח יש לו סיכוי טוב לנחש את המפתח בניתוח סטטיסטי (כמו בפנקס חד-פעמי). יתרה מזו, אם במקרה ידוע למתקיף בלוק אחד $x$ (כלומר במקרה של התקפת גלוי-ידוע), הוא יכול לחשוף את המפתח בקלות כי $k=x\oplus (x\oplus k)$. זוהי למעשה שבירה מוחלטת של הצופן.
• רשת החלפה תמורה בשני סבבים. לעומת זאת אילו רשת ההחלפה תמורה הייתה מבוצעת בשני סבבים, המשימה הייתה יותר קשה. לצורך הפשטות נניח שבלוק הצופן הוא 64 סיביות והמפתח הוא 128 סיביות כך שהחצי הראשון של המפתח אותו מסמנים $k^{a}$ משמש לסבב הראשון כמו שהוא והחצי השני $k^{b}$ לסבב השני. ההנחה שמשתמשים במפתח ללא כל הכנה מוקדמת אינה מקלה על המתקיף כיוון שהמפתח אמור להיות קשה לניחוש מראש. היריב מקבל את $y=F_{k}(x)$ והוא מנסה לגלות את $k$ מתוך $x$ ו-$y$. אם נסמן את ארבע הסיביות הראשונות של התוצאה $y$ ב-$w_{1}$, יוצא ש-$w_{1}=\alpha _{1}\oplus k_{1}^{b}$. כלומר חיבור ארבע הסיביות הראשונות של תוצאת הביניים מהסבב הראשון המסומנים כאן ב-$\alpha _{1}$ עם ארבע הסיביות הראשונות של החצי השני של המפתח המסומנים ב-$k_{1}^{b}$. המתקיף כמובן אינו יודע מה ערכם של $\alpha _{1}$ או $k_{1}^{b}$. ערכו של $\alpha _{1}$ יכול להיות מושפע לכל היותר מארבע תיבות החלפה כי במקרה הגרוע כל סיבית של $\alpha _{1}$ הגיעה מתיבה אחרת. אבל המתקיף יכול לדעת בדיוק אלו תיבות החלפה השפיעו עליו כי התמורה המפזרת ידועה. באותה דרך, חשבון פשוט מראה ש-16 סיביות מהמפתח $k^{a}$, בפוזיציות ידועות, השפיעו על תוצאות ארבע תיבות ההחלפה הללו. מה שהמתקיף יכול לעשות הוא כך. תחילה הוא מנחש את 16 הסיביות של $k^{a}$ במיקומים האמורים, מבצע XOR שלהם עם 16 הסיביות המתאימות של $x$, מחשב את $\alpha _{1}$ ובודק אם $\alpha _{1}\oplus k_{1}^{b}=w_{1}$, כאשר $k_{1}^{b}$ גם הוא חלק מהניחוש. יוצא איפה שבאמצעות כוח גס בזמן של $2^{20}$ לכל היותר הוא יכול לנחש בהסתברות גבוהה את כל הערכים האפשריים של 20 סיביות מהמפתח המקיימים את השוויון האמור. אם מניחים למען הפשטות שניחוש לא נכון יוביל לערך אקראי של $\alpha _{1}\oplus k_{1}^{b}$ אז ההסתברות של ניחוש אחד נכון היא $1/2^{|w_{1}|}=1/16$, כך שקיימות בערך $2^{20}/16=2^{16}$ אפשרויות לעבור את הבדיקה. לכן כדי לשפר את סיכויי ההצלחה בניחוש המפתח הנכון אפשר לבדוק זוגות ערכים נוספים של $x$ ו-$y$ והפתרונות המשותפים שלהם יכילו את המפתח הנכון בהסתברות גבוהה. אם למשל משתמשים ב-8 זוגות קלט/פלט כאלו המתקיף יכול לגלות את $k_{1}^{b}$ בזמן של $8\cdot 2^{20}=2^{23}$. אם חוזרים על ההתקפה על יתר חלקי המפתח, 16 במספר, מגיעים לזמן כולל של $16\cdot 2^{23}=2^{27}$ לגילוי המפתח במלואו. הלקח מההתקפה המתוארת הוא שאפשר היה לנחש את המפתח בשיטת הפרד ומשול. קל יותר לבצע 16 התקפות שכל אחת מהן היא בזמן של $2^{23}$ מאשר לבצע התקפה אחת בזמן כולל של $2^{128}$ והסיבה לכך נעוצה בעובדה שהשפעת המפתח לא "התפזרה" היטב ובשלב השני לא כל סיביות המפתח השפיעו על כל סיביות הפלט.
• רשת החלפה תמורה בשלושה סבבים. אפשר לראות שקל לבצע התקפת הבחנה על רשת החלפה-תמורה בשלושה סבבים לאור האמור לעיל שאפקט המפולת לא הושלם במלואו. המתקיף יכול פשוט לבקש הצפנה של זוגות קלטים הנבדלים רק בסיבית אחת ולבחון את התוצאות. היות שבהסתברות גבוהה סיביות אחדות של הקלט במיקומים מסוימים יוותרו ללא שינוי כי הפונקציה טרם הספיקה להגיע אליהם, אחרי מספר ניסיונות המתקיף יכול להבחין בכך ולהצליח בהתקפה בסיכוי גבוה.

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

ראו גם

• AES
• רשת פייסטל