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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

ערבוב ופיזור[עריכת קוד מקור | עריכה]

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

.

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

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

אפקט מפולת[עריכת קוד מקור | עריכה]

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

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

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

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

רשת החלפה-תמורה[עריכת קוד מקור | עריכה]

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

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

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

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

הכנת המפתחות[עריכת קוד מקור | עריכה]

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

פענוח[עריכת קוד מקור | עריכה]

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

ביטחון[עריכת קוד מקור | עריכה]

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

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

קריפטואנליזה[עריכת קוד מקור | עריכה]

  • רשת החלפה תמורה בסבב אחד. כדי להמחיש מדוע מספר החזרות חשוב, נניח למען הפשטות שרשת ההחלפה-תמורה מבוצעת רק פעם אחת. נתונה הפונקציה המקבלת את הבלוק הקריא ואת שהוא מפתח סודי אקראי, מבצעת את סדרת הפעולות המתוארת ומחזירה את . המתקיף מקבל את ומנסה לגלות את . במקרה כזה כל מה שהוא צריך לעשות זה לבצע את פעולות ההחלפה והפיזור בסדר הפוך ולבטל את השפעתן על התוצאה (צריך לזכור שמפרט הצופן ידוע לו ולכן הוא יכול להשתמש בפונקציית הפענוח) ואז מה שנשאר בידו הוא . כאן מניחים למען הפשטות שהמפתח נוצל כמו שהוא ללא תהליך הכנה מקדים כי מדובר בסבב אחד. אם יהיו בידו מספר בלוקים מוצפנים שהוצפנו עם אותו מפתח יש לו סיכוי טוב לנחש את המפתח בניתוח סטטיסטי (כמו בפנקס חד-פעמי). יתרה מזו, אם במקרה ידוע למתקיף בלוק אחד (כלומר במקרה של התקפת גלוי-ידוע), הוא יכול לחשוף את המפתח בקלות כי . זוהי למעשה שבירה מוחלטת של הצופן.
  • רשת החלפה תמורה בשני סבבים. לעומת זאת אילו רשת ההחלפה תמורה הייתה מבוצעת בשני סבבים, המשימה הייתה יותר קשה. לצורך הפשטות נניח שבלוק הצופן הוא 64 סיביות והמפתח הוא 128 סיביות כך שהחצי הראשון של המפתח אותו מסמנים משמש לסבב הראשון כמו שהוא והחצי השני לסבב השני. ההנחה שמשתמשים במפתח ללא כל הכנה מוקדמת אינה מקלה על המתקיף כיוון שהמפתח אמור להיות קשה לניחוש מראש. היריב מקבל את והוא מנסה לגלות את מתוך ו-. אם נסמן את ארבע הסיביות הראשונות של התוצאה ב-, יוצא ש-. כלומר חיבור ארבע הסיביות הראשונות של תוצאת הביניים מהסבב הראשון המסומנים כאן ב- עם ארבע הסיביות הראשונות של החצי השני של המפתח המסומנים ב-. המתקיף כמובן אינו יודע מה ערכם של או . ערכו של יכול להיות מושפע לכל היותר מארבע תיבות החלפה כי במקרה הגרוע כל סיבית של הגיעה מתיבה אחרת. אבל המתקיף יכול לדעת בדיוק איזה תיבות החלפה השפיעו עליו כי התמורה המפזרת ידועה. באותה דרך, חשבון פשוט מראה ש-16 סיביות מהמפתח , בפוזיציות ידועות, השפיעו על תוצאות ארבע תיבות ההחלפה הללו. מה שהמתקיף יכול לעשות הוא כך. תחילה הוא מנחש את 16 הסיביות של במיקומים האמורים, מבצע XOR שלהם עם 16 הסיביות המתאימות של , מחשב את ובודק אם , כאשר גם הוא חלק מהניחוש. יוצא איפה שבאמצעות כוח גס בזמן של לכל היותר הוא יכול לנחש בהסתברות גבוהה את כל הערכים האפשריים של 20 סיביות מהמפתח המקיימים את השוויון האמור. אם מניחים למען הפשטות שניחוש לא נכון יוביל לערך אקראי של אז ההסתברות של ניחוש אחד נכון היא , כך שקיימות בערך אפשרויות לעבור את הבדיקה. לכן כדי לשפר את סיכויי ההצלחה בניחוש המפתח הנכון אפשר לבדוק זוגות ערכים נוספים של ו- והפתרונות המשותפים שלהם יכילו את המפתח הנכון בהסתברות גבוהה. אם למשל משתמשים ב-8 זוגות קלט/פלט כאלו המתקיף יכול לגלות את בזמן של . אם חוזרים על ההתקפה על יתר חלקי המפתח, 16 במספר, מגיעים לזמן כולל של לגילוי המפתח במלואו. הלקח מההתתקפה המתוארת הוא שאפשר היה לנחש את המפתח בשיטת הפרד ומשול. קל יותר לבצע 16 התקפות שכל אחת מהן היא בזמן של מאשר לבצע התקפה אחת בזמן כולל של והסיבה לכך נעוצה בעובדה שהשפעת המפתח לא "התפזרה" היטב ובשלב השני לא כל סיביות המפתח השפיעו על כל סיביות הפלט.
  • רשת החלפה תמורה בשלושה סבבים. אפשר לראות שקל לבצע התקפת הבחנה על רשת החלפה-תמורה בשלושה סבבים לאור האמור לעיל שאפקט המפולת לא הושלם במלואו. המתקיף יכול פשוט לבקש הצפנה של זוגות קלטים הנבדלים רק בסיבית אחת ולבחון את התוצאות. היות שבהסתברות גבוהה סיביות אחדות של הקלט במיקומים מסוימים יוותרו ללא שינוי כי הפונקציה טרם הספיקה להגיע אליהם, אחרי מספר ניסיונות המתקיף יכול להבחין בכך ולהצליח בהתקפה בסיכוי גבוה.

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

ראו גם[עריכת קוד מקור | עריכה]


הערות שוליים[עריכת קוד מקור | עריכה]