רשת פייסטל

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

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

הרעיון של פייסטל הוא ליצור תמורה פסאודו-אקראית (בקיצור PRP) מפונקציה פסאודו-אקראית שאינה בהכרח הפיכה (בקיצור PRF), שזו תכונה בסיסית הנדרשת מכל צופן בלוקים אחרת פענוח לא יהיה אפשרי תמיד. המבנה הסימטרי גורם לכך שפונקציות ההצפנה והפענוח מבוצעות באופן זהה בהחלפת סדר הזנת המפתחות בלבד. מבנה זה מקטין את גודל היישום של הצופן במיוחד בחומרה, היות שאין צורך ליישם את פונקציות ההצפנה והפענוח בנפרד. רשת פייסטל הוכחה כבטוחה, היא פופולרית ביותר ונכללת בצפנים מודרניים רבים, בהם: DES, Blowfish, KASUMI, Twofish, 3DES, Tiny ו-RC5.

היסטוריה[עריכת קוד מקור | עריכה]

רשת פייסטל הופיעה לראשונה בצופן לוציפר שפותח במשותף על ידי הורסט פייסטל ודון קופרשמידט במסגרת עבודתם ב-IBM. השימוש בבנייה הפך נפוץ לאחר שהממשל הפדרלי של ארצות הברית אימץ את תקן ההצפנה DES שהתבסס על לוציפר.[2]

כאמור, צפנים רבים הם בעלי מבנה פייסטל. עובדה זו הובילה לכך שהקהילה המדעית השקיעה מאמץ אקדמי רב בניתוח תכונות המבנה. בעבודתם משנת 1988[3] הוכיחו מיכאל לובי וצ'ארלס רקופף שאם פונקציית השלב מתנהגת בצורה פסבדו-אקראית תחת מפתח ההצפנה אזי שילובה בתוך רשת פייסטל יניב תמורה פסאודו-אקראית לאחר 3 איטרציות ותמורה פסאודו-אקראית חזקה לאחר 4 איטרציות. אחד היתרונות של רשת פייסטל על-פני רשת החלפה-תמורה הוא שפונקציית השלב אינה חייבת להיות הפיכה.

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

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

Feistel cipher diagram.svg

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

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

.
  • הטקסט המוצפן הוא:

פענוח הצופן נעשה באופן דומה בסדר איטרציות הפוך

.
  • כך שבסוף התהליך מתקבל שוב הטקסט הגלוי:

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

אם מסמנים את רשת פייסטל ב- סבבים[4]:

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

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

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

רשת פייסטל בשני סבבים[עריכת קוד מקור | עריכה]

רשת פייסטל בשני סבבים כדלהלן:

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

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

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

רשת פייסטל בשלושה סבבים המוגדרת כדלהלן:

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

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

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

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

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

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

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

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

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

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

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

  1. ^ 1.0 1.1 Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 251.
  2. ^ K.V. Srinivasa Rao, M. Rama Krishna and D. Bujji Babu, 2009. Cryptanalysis of a Feistel Type Block Cipher by Feed Forword Neural Network Using Right Sigmoidal SignalsInternational Journal of Soft Computing, 4: 131-135.
  3. ^ How to Construct Pseudorandom Permutations from Pseudorandom Functions
  4. ^ Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography (2nd edition).