צופן בלוקים

בקריפטוגרפיה, צופן בלוקים (באנגלית: Block cipher) הוא פרימיטיב קריפטוגרפי סימטרי הפועל על מחרוזת סיביות באורך קבוע הנקראת בלוק באמצעות טרנספורמציה קבועה. צופן בלוקים מקבל בלוק של סיביות טקסט-גלוי (או תַּמְלִיל פָּשׁוּט) ומפתח הצפנה סודי ומפיק בלוק טקסט-מוצפן (או תַּמְלִיל מֻצְפָּן). כאשר תוצאת הטרנספורמציה נקבעת על ידי מפתח ההצפנה. פענוח מתבצע באופן דומה, אלגוריתם הפענוח מקבל בלוק סיביות טקסט-מוצפן והמפתח שאיתו הוצפן ומחזיר את בלוק הסיביות המקורי. צופן בלוקים הוא פרימיטיב קריפטוגרפי ורסטילי ומשמש מרכיב קריטי כמעט בכל מערכת הצפנה מודרנית.
הבלוק מתייחס למספר הסיביות שהאלגוריתם מסוגל לעבד בבת אחת. אם הקלט להצפנה ארוך יותר אפשר לחלקו לבלוקים באורך הרצוי ולהצפינם בזה אחר זה. על כל פנים במצב כזה כל הבלוקים מוצפנים עם אותו מפתח, עובדה שמשפיעה על ביטחון ההצפנה, משום שאם צופן הבלוקים דטרמיניסטי במקרה שמוצפנים בלוקים זהים של טקסט-גלוי עם אותו מפתח, התוצאות תהיינה בלוקים זהים של טקסט-מוצפן. עובדה זו חושפת מידע מסוים ליריב פוטנציאלי ובסיטואציות מסוימות מהווה חולשה שיש להימנע ממנה. כדי לפתור בעיה זו אפשר להפעיל את הצופן באחד מאופני ההפעלה של צופן בלוקים שמבטיח מידה של אקראיות, כך ששני בלוקים זהים יוצפנו בצורה אחרת והתוצאה תהיה תמיד שונה.
DES שפותח על ידי IBM בשיתוף עם NSA ופורסם ב-1977 הוא דוגמה לאחד מצפני הבלוקים הראשונים והמשפיעים ביותר בקריפטוגרפיה המודרנית. הצופן התבסס על טכניקות שפיתח מהנדס יבם, האמריקאי-גרמני הורסט פייסטל, שאותם יישם תחילה בצופן שלו לוציפר. ממשיכו של DES הקרוי AES שאומץ כתקן הצפנה רשמי ב-2001, נמצא כיום בשימוש מאסיבי ומהווה מרכיב בסיסי וחשוב כמעט בכל מערכת אבטחת מידע מודרנית.

גודל המפתח

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

גודל הבלוק

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

תיבות החלפה

תיבת החלפה (substitution box) בקיצור s-box היא פונקציה לא ליניארית שמחליפה את הקלט בפלט שנקבע לפי ערכים שרירותיים כלשהם. תיבות החלפה שהוצגו לראשונה בצופן DES הן אוסף של פונקציות אי-ליניאריות שתפקידן לפי התאוריה של שאנון להוסיף ערבוב (confusion) לצופן, כך שהקשר בין המפתח לבין הטקסט המוצפן יהיה קלוש ככל האפשר. תיבות ההחלפה ניתנות ליישום במחשב באמצעות טבלאות אחזור בדרך כלל קבועות כמו ב-DES כלומר שערכיהן מקודדים מראש, או דינאמיות (תלויות במפתח ההצפנה) כמו בצופן Blowfish. תיבות החלפה מופיעות בצפנים מודרניים רבים והן מהוות מרכיב אי-ליניארי קריטי שמחזק את הצופן במיוחד נגד קריפטואנליזה דיפרנציאלית, למשל לולא תיבות ההחלפה היה ניתן לפרוץ את DES בקלות. 
בחירת ערכי תיבות ההחלפה היא נושא מורכב. אין שיטה מוכחת לבחירת ערכים אופטימליים המניבים אי-ליניאריות מקסימלית ובדרך כלל הערכים נבחרים אמפירית (ראו סרפנט). ידוע שבפיתוח DES נעשו על ידי NSA שינויים בערכי תיבות ההחלפה מסיבות לא ידועות, יש כאלו שטוענים שהשינויים נעשו במכוון כדי להחליש את הצופן, אך אין הוכחה לכך. לדברי דון קופרשמידט שהיה ממפתחי DES והיה אמון בעיקר על תיבות ההחלפה, בשלב פיתוח הצופן היו מודעים המפתחים לקריפטואנליזה דיפרנציאלית והיא לא פורסמה כיוון שהייתה באותה עת סוד לאומי. לדבריו נעשו מאמצים לבחור את ערכי תיבות ההחלפה כך שהצופן יהיה עמיד נגד התקפה דיפרנציאלית. ואכן שנים לאחר מכן כאשר התגלתה ההתקפה הדיפרנציאלית לראשונה לציבור הרחב, על ידי אלי ביהם ועדי שמיר, התברר שאכן צופן DES עמיד באופן יוצא דופן נגד התקפה זו, בעיקר בזכות תיבות ההחלפה.
תיבות ההחלפה ניתנות לייצוג כמערך דו-ממדי של מספרים שלמים בגודל מסוים. הגודל בסיביות נקבע בשלב התכנון. בהינתן הקלט  בגודל המתאים ההחלפה מתבצעת פשוט על ידי החזרת הערך המצוי בכניסה  בטבלה, כלומר הקלט עצמו משמש אינדקס לערך המתאים בטבלה. במקרה של טבלה דו-ממדית  האיחזור מתבצע על ידי שני ערכים  כאשר אחד מייצג את מספר העמודה והשני את מספר השורה. תיבת ההחלפה נקראת גם טבלת אחזור (lookup table), במחשב איחזור ערך מתבצע בזמן קבוע והוא יעיל.
לדוגמה צופן ריינדל משתמש בטבלת החלפה בגודל  כניסות, כל כניסה מכילה בית אחד (שהוא ערך בטווח 0-255). למען הנוחות הבתים מיוצגים בבסיס הקסדצימלי, כך ששני הניבלים (חצאי בתים) בכל כניסה מיוצגים על ידי שתי ספרות הקסדצימליות. לביצוע ההחלפה הקלט שהוא בגודל בית אחד מחולק לשני חצאים, הניבל המשמעותי (הגבוה) משמש כאינדקס לשורה והשני לעמודה. בתרשים מופיע חלק מטבלת ההחלפה של AES. אם למשל הקלט הוא  הפלט יהיה הערך שבשורה 3 בעמודה 1 שהוא . אפשר להציג זאת כפונקציה  או  כאשר  הם האינדקסים לשורה ולעמודה בהתאמה.

תיבות תמורה

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

ביטחון

בעקרון קשה לתת הגדרה פורמלית לביטחון צופן בלוקים. המודל המקובל של ביטחון מוכח נקרא ביטחון סמנטי והוא משתמש במושג שנקרא 'אי-יכולת הבחנה', דהיינו צופן הבלוקים יהיה בטוח אם היריב לא יוכל להבחין בהסתברות גבוהה מחצי באופן ניכר, בין תוצאת הצפנה עם מפתח הצפנה סודי כלשהו לבין פרמוטציה אקראית אמיתית, במקרה כזה הצופן ייקרא PRP-בטוח. ההנחה היא שהטקסט המוצפן אקראי וכן המפתח נבחר באקראי מתוך מרחב המפתחות המקסימלי בהסתברות שווה, או לפחות נראה כאקראי מבחינה חישובית מה שקרוי פסאודו-אקראי. אפשר להציג זאת באמצעות משחק כדלהלן, נניח ש-E הוא צופן בלוקים שאת ביטחונו אנחנו מעוניינים לבדוק. לצורך המשחק נתון אורקל שמסוגל לבחור מפתח הצפנה אקראי כלשהו ולהצפין כל מסר שיתבקש, הוא יכול לשדר את תוצאת ההצפנה אך אסור לו לחשוף את המפתח. היריב שולח מסר כלשהו  לאורקל שפועל כדלהלן; מטיל מטבע ובמקרה שמתקבל עץ, מחזיר ליריב את תוצאת ההצפנה של  באמצעות  עם מפתח אקראי כלשהו שהוא בחר. אם מתקבל פלי הוא מחזיר תמורה אקראית כלשהי. תפקידו של היריב היא לנחש האם הערך שקיבל מהאורקל הוא תוצאה של הצפנת  ששלח קודם לכן או מספר אקראי לא מעניין. במילים אחרות עליו לנחש מה הייתה תוצאת הטלת המטבע. היריב יצליח בהתקפה אם ינחש נכונה בשיעור העולה על 50% במידה ניכרת או כפי שמקובל לומר בשיעור 'בלתי זניח' לפי פונקציית זניחות כלשהי שנהוג לסמנה . קיימים מספר מודלים של ביטחון המבוססים על עיקרון זה. במודלים מסוימים מוקנה ליריב כוח רב יותר, כאשר באפשרותו לבחור את הטקסטים אותם הוא מעוניין להצפין, במילים אחרות בידיו זוגות של טקסט-מקורי וטקסט-מוצפן מתאים ומשימתו לגלות את מפתח ההצפנה. בגרסאות חלשות יותר ההתקפה נקראת פסיבית במובן שהתוקף יכול רק לראות טקסט מוצפן אך לא את מקורו.
אופני ההפעלה של צופן בלוקים אמורים להבטיח שההצפנה של טקסט ארוך תהיה בטוחה לפחות כביטחון הצפנת בלוק יחיד, על פי המודלים של הביטחון השונים. אופן הפעלה ECB יוצא דופן בכך שלא משנה מה חוזקו של צופן הבלוקים, התוצאה תהיה חלשה במובן שהיא חושפת בפני תוקף פוטנציאלי מידע שאינו אמור לקבל. מרבית סגנונות ההפעלה המודרניים מספקים ביטחון מוכח תחת הנחה סטנדרטית שצופן הבלוקים איתו הם עושים שימוש נקרא PRP בטוח.

צופן בלוקים בר התאמה ייעודי

בצופן כזה ה-tweak מובנה בתוכו בשלב הפיתוח. דוגמה טובה לצופן כזה היא Threefish.