רשת פייסטל הופיעה לראשונה בצופן לוציפר שפותח במשותף על ידי הורסט פייסטל ודון קופרשמידט במסגרת עבודתם ב-IBM. השימוש בבנייה הפך נפוץ לאחר שהממשל הפדרלי של ארצות הברית אימץ את תקן ההצפנה DES שהתבסס על לוציפר.
כאמור, צפנים רבים הם בעלי מבנה פייסטל. עובדה זו הובילה לכך שהקהילה המדעית השקיעה מאמץ אקדמי רב בניתוח תכונות המבנה. בעבודתם משנת 1988 הוכיחו מיכאל לובי וצ'ארלס רקופף שאם פונקציית השלב מתנהגת בצורה פסבדו-אקראית תחת מפתח ההצפנה אזי שילובה בתוך רשת פייסטל יניב תמורה פסאודו-אקראית לאחר 3 איטרציות ותמורה פסאודו-אקראית חזקה לאחר 4 איטרציות. אחד היתרונות של רשת פייסטל על-פני רשת החלפה-תמורה הוא שפונקציית השלב אינה חייבת להיות הפיכה.
פרטי הבנייה.
באופן כללי, מבנה פייסטל ממפה טקסט גלוי באורך formula_1 סיביות המחולק לשניים formula_2 בהתאמה, לטקסט מוצפן formula_3 באורך formula_1 בהתאמה, באמצעות formula_5 מפתחות הצפנה formula_6 בתהליך formula_5 שלבי. בכל שלב, מחצית הקלט האחת מוזנת לפונקציה formula_8 שבתורה מפיקה מהקלט ומפתח ההצפנה המתאים formula_9 פלט פסאודו-אקראי המשמש כמפתח להצפנת מחצית הקלט השנייה באמצעות XOR ואז הן מחליפות מקומות. אפשר לראות שבכל שלב היות ש-XOR הפיכה, אם חוזרים על אותה הפעולה עם המפתח המתאים מתקבל הקלט המקורי. מכאן שהפענוח יכול להתבצע באופן דומה אך בסדר הפוך של הסבבים ועם החלק המתאים של המפתח.
ביתר פירוט תהי formula_10 פונקציית שלב ויהיו formula_11 מפתחות הצפנה, הנקראים תת-מפתחות, המתאימים לאיטרציות formula_12 בהתאמה. הבנייה עובדת באופן הבא:
formula_16
formula_18
פענוח הצופן נעשה באופן דומה בסדר איטרציות הפוך formula_19
formula_20
formula_22
ביטחון.
אם מסמנים את רשת פייסטל ב-formula_23 סבבים:
כאשר formula_25 הן formula_23 פונקציות שונות (לא בהכרח הפיכות) הממפות מחרוזת באורך formula_27 סיביות למחרוזת באורך formula_27 סיביות. אפשר לראות שעבור כל ערך formula_23 הרשת formula_30 היא תמורה הפיכה ויעילה ללא תלות בפונקציות הפנימיות. ביתר פירוט אם formula_10 היא פונקציה פסאודו-אקראית אז רשת פייסטל עם סבב בודד formula_32 המוגדרת כ:
היא פרמוטציה עם מפתח מעל formula_34 כאשר formula_35, אך היא אינה פסאודו אקראית כי formula_5 הסיביות הראשונות של הפלט (formula_37) שוות ל-formula_5 הסיביות האחרונות של הקלט (formula_14) ללא תלות במפתח. מעבר לבעיה שחלק מהטקסט המקורי פשוט לא הוצפן כלל ונותר במצבו הגלוי, עובדה זו כשלעצמה מצביעה בבירור שהפונקציה אינה פסאודו אקראית כי מקרה כזה שבו רק מחצית הקלט השתנתה, יכול להתרחש בסבירות מאוד מאוד נמוכה אילו היה מדובר בפונקציה אקראית אמיתית.
יתרה מזו, במקרה כזה קל לנחש את המפתח. למשל במקרה של DES עם סבב אחד, התוצאה תהיה formula_40 וכן formula_41, במצב כזה הקלט והפלט של הפונקציה הפנימית ידוע. כלומר אנחנו יודעים ש-formula_42. לכן אם מבצעים את התמורה ההפוכה של formula_43 (ב-DES התמורה formula_43 רק מבצעת "סידור מחדש" של הסיביות לפי טבלה קבועה), על formula_45 מתקבלים ערכי ביניים שהם תוצאה של תיבות ההחלפה (S-box), כל תיבת החלפה מקבלת שש סיביות ומחזירה ארבע. כזכור הקלט לתיבות ההחלפה הוא XOR של תיבת ההרחבה formula_46 עם חלק מהמפתח במקרה זה המפתח היחידי formula_47 וכל חלק משפיע על תיבת החלפה אחרת. כך שאפשר לדעת אם ניחוש של 6 סיביות הצליח פשוט על ידי בדיקה שקלט ופלט הפונקציה הפנימית מתאים בפוזיציות הללו. היות שתיבות ההחלפה מכווצות את הקלט, עבור כל 6 סיביות מפתח ישנם רק ארבעה פלטים אפשריים. יוצא איפה שאפשר לצמצם את החיפוש בכוח גס של המפתח מ-formula_48 ל-formula_49 שזה formula_50 ניסיונות (במחשב רגיל חיפוש כזה לא לוקח יותר ממספר מילי שניות). היות שההתקפה האמורה הסתמכה על מבנה הפונקציה הפנימית המשמעות היא שבמקרה של DES רשת פייסטל עם סבב אחד לא נחשבת בטוחה.
רשת פייסטל בשני סבבים.
רשת פייסטל בשני סבבים formula_51 כדלהלן:
כאשר formula_53 ו-formula_54 הם שני מפתחות נפרדים ובלתי תלויים זה בזה, עדיין אינה פסאודו אקראית משום שאפשר לבצע את הטריק הבא: מצפינים שני מסרים כאשר formula_5 הסיביות האחרונות שלהם זהות, לדוגמה formula_56, formula_57 ומקבלים מהם שני טקסטים מוצפנים formula_58 ו-formula_59 בהתאמה. ה-XOR של המחצית הראשונה של formula_60 עם המחצית הראשונה של formula_61 דהיינו formula_62 שווה ל-formula_63. לכן התקפת הבחנה פשוטה יכולה לשבור את האלגוריתם. אם השוויון האמור מתקיים המתקיף מחזיר '1' אחרת '0'. הסיבה לכך נובעת מהעובדה שהמפתחות לא הספיקו להשפיע על כל הפלט במידה שווה בשל מספר הסבבים המועט. לתופעה זו קוראים אפקט מפולת. כלומר השאיפה היא שלאחר מספר ראוי של סבבים עם מפתחות שונים, כמעט כל סיביות הפלט יושפעו במידה שווה במקרה הממוצע ולכן התקפה כזו לא תהיה אפשרית.
ניחוש המפתח קשה יותר אך עדיין בר ביצוע. למשל במקרה של DES אפשר לראות שעם שני סבבים אפשר לבצע התקפה דומה ל-DES בסבב אחד המתוארת לעיל כי הקלט והפלט של הפונקציה הפנימית בשני הסבבים ידוע. כלומר אפשר לנחש את המפתחות בזמן של formula_64 אפילו אם המפתחות בלתי תלויים זה בזה כלל. אף על פי שתהליך הרחבת המפתח של DES למעשה משתמש במפתח המאסטר בשינויים קלים כדי להכין את מפתחות הסבבים כך שסיביות מסוימות של formula_53 ו-formula_54 למעשה זהות, דבר שיכול לעזור להתקפה.
רשת פייסטל בשלושה סבבים.
רשת פייסטל בשלושה סבבים formula_67 המוגדרת כדלהלן:
באופן מפתיע כן נחשבת פסאודו אקראית בהנחה שמשתמשים בשלושה מפתחות נפרדים והפונקציה הפנימית היא פסאודו-אקראית. אך היא אינה פסאודו-אקראית חזקה.
ניחוש המפתח במקרה של DES עם שלושה סבבים קשה יותר. אפשר לראות שבמצב זה אין בידי המתקיף מידע מלא על קלט/פלט הפונקציה הפנימית בכל הסבבים כמו בדוגמאות הקודמות ולכן כוח גס ישיר אינו אפשרי כיוון שחסר למתקיף מידע האם הניחוש שלו הצליח. לדוגמה בסבב השני הפלט הוא formula_69 כאשר שני הערכים האמורים ידועים אבל הקלט formula_70 נותר בלתי ידוע. מצד שני אנחנו יודעים ש-formula_71 וכן formula_72 אבל הפלט של formula_73 ו-formula_74 לא ידוע.
אבל במקום להסתמך על ניחוש הקלט והפלט המלאים של הפונקציה הפנימית בכל הסבבים, המתקיף יכול להתמקד ביחס שבין החלקים השונים של הקלט שמקצתם ידוע. היות שהפלט בסבב הראשון הוא formula_75 והפלט בסבב השלישי הוא formula_76 יוצא ש-XOR של הפלט מהסבב הראשון עם הפלט מהסבב השני שווה ל-
כאשר הערך האחרון ידוע. על בסיס נתון זה והעובדה שתהליך הרחבת המפתח של DES מחלק את המפתח לשני חצאים, כל חצי משפיע רק על החצי המתאים מהקלט (רק ארבע תיבות החלפה), ואם נוסיף לכך את העובדה שהתמורה המפזרת ידועה גם היא כך שאפשר לדעת כל סיבית מהיכן הגיעה, יוצא שאפשר לבצע התקפה לניחוש חצי מהמפתח בזמן של formula_78 זאת בתנאי שיש דרך לדעת האם ניחוש הצליח. היות שהקלט לסבב הראשון ידוע, אפשר לנחש חצי מהמפתח לחשב את ארבע תיבות ההחלפה המושפעות מחצי זה, באותה מידה לבדוק להיכן הסיביות עברו בעקבות הפיזור ובכך לקבל מחצית מפלט הסבב הראשון. באותה דרך אפשר לחשב את אותן הפוזיציות בפלט הסבב השלישי (כזכור הקלט לסבב השלישי ידוע). עם מידע זה אפשר לוודא שהניחוש נכון על ידי השוויון המתואר לעיל. כמובן שניחוש נכון אינו מעיד בהכרח שנמצא המפתח הנכון אלא רק בהסתברות של formula_79 כלומר מתוך formula_78 מפתחות אפשריים נשארים עם formula_81 אפשרויות תקפות עבור חצי מפתח ו-formula_82 עבור המפתח כולו. כך שאם בידי המתקיף מספר זוגות קלט/פלט של DES הוא יכול לנחש את המפתח במלואו בזמן כולל של formula_83 ועם זיכרון בסדר גודל של formula_84. התקפה בסיבוכיות כזו ניתנת לביצוע כיום על מחשב אישי בזמן מאוד קצר.
ההתקפה המתוארת הסתמכה על המבנה הפנימי של הפונקציה הפסאודו-אקראית והיא רלוונטית רק לגבי DES. אין הדבר מעיד בהכרח על כך שרשת פייסטל בשלושה סבבים אינה בטוחה, כל עוד הפונקציה הפנימית נחשבת פסאודו אקראית בטוחה.
רשת פייסטל בארבעה סבבים.
הוכח שאם מוסיפים סבב רביעי מתקבלת תמורה פסאודו-אקראית חזקה, כדלהלן:
הוכח שהמבנה המתואר הוא פונקציה פסאודו אקראית חזקה והיא הנפוצה ביותר בצפנים מודרניים. בכל אופן קיימת קריפטואנליזת "התקפת הבחנה גנרית" נגד מבנה פייסטל עד שבעה סבבים בסיבוכיות של formula_103 כאשר formula_5 מתייחס לגודל מחצית הקלט בסיביות.
רשת פייסטל כללית.
צפנים מודרניים מגיעים לפעמים עם רשת פייסטל בסגנון שונה מרשת פייסטל הקלאסית שהגיעה עם DES. היא נקראת רשת פייסטל כללית (General Feistel Network) בקיצור GFN שהיא מעין הכללה של מבנה פייסטל בכמה שינויים. קיימים כמה סוגים ביניהם:
בין הצפנים המודרניים שמיישמים רשת פייסטל בסגנון שונה מ-DES הם: RC6 ו-CLEFIA המיישמים רשת פייסטל מסוג 2, MARS המיישם רשת פייסטל מסוג 3, CAST הבנוי מרשת פייסטל מסוג 1 ועוד רבים. מהיבט תאורטי הביטחון המוכח של רשת פייסטל הקלאסית החל עם עבודתם של לובי וראקוף, בהנחה ש-formula_23 הפונקציות הפנימיות נבחרו באופן אקראי ובלתי תלוי. הנושא נחקר על ידי רבים אחרים כמו מאורר, נאור וריינגולד, ואודני, פיטרזק ופטרין. האחרון הוכיח שרשת פייסטל הקלאסית עם שישה סבבים מספיק טובה נגד התקפת מוצפן נבחר עם formula_106 שאילתות עבור כל formula_107. לגבי הכללה של רשת פייסטל אין ידע תאורטי נרחב כמו בקלאסית.
רשת פייסטל בלתי מאוזנת.