לדלג לתוכן

צופן בלוקים

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

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

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

DES שפותח על ידי IBM בשיתוף עם NSA ופורסם ב-1977 הוא דוגמה לאחד מצפני הבלוקים הראשונים והמשפיעים ביותר בקריפטוגרפיה המודרנית. הצופן התבסס על טכניקות שפיתח מהנדס יבם, האמריקאי-גרמני הורסט פייסטל, שאותם יישם תחילה בצופן שלו לוציפר. ממשיכו של DES הקרוי AES שאומץ כתקן הצפנה רשמי ב-2001, נמצא כיום בשימוש מאסיבי ומהווה מרכיב בסיסי וחשוב כמעט בכל מערכת אבטחת מידע מודרנית.

הגדרה פורמלית

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

צופן בלוקים בהגדרה פורמלית הוא תמורה פסידו-אקראית עם מפתח, המסומנת בקיצור PRP, מהצורה:

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

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

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

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

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

היסטוריה והתפתחות

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

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

את היסודות לצופן הבלוקים המודרני הניח קלוד שאנון אבי תורת האינפורמציה. במאמר חשוב[1] מ-1949, הסביר את עקרונות השיטה מהיבט של תורת האינפורמציה וסיפק הוכחות מתמטיות. הוא הגה לראשונה את רעיון ההרכבה של צופן החלפה (שיכול) עם צופן העתקה (טרנספוזיציה), כדי לקבל פונקציית הצפנה חזקה. הוא כינה זאת שילוב של פיזור (diffusion) וערבוב (confusion), הפיזור נועד להבטיח שהמפתח והטקסט הקריא ישפיעו על כל סיביות הצופן במידה שווה וערבוב נועד לגרום לקשר בין הצופן למקור או המפתח להיות רחוק ככל האפשר. כמו כן הגה את רעיון האיטרציה, כלומר מפעילים פונקציה פנימית כלשהי במספר חזרות, כאשר פלט סבב אחד הופך קלט לסבב הבא וכן הלאה. המטרה של האיטרציה היא יצירת אפקט כדור השלג או אפקט מפולת, כלומר לאחר מספר חזרות של פונקציות הערבוב/פיזור כל שינוי של סיבית בודדת בקלט יגרום לשינוי גדול בפלט, במקרה הממוצע לפחות מחצית מסיביות הפלט. מְפַתֵּח הצופן קובע את מספר הסבבים כדי להגיע לרמת ביטחון רצויה. אפשר ליצור צופן חזק יותר על ידי ביצוע מספר גדול מאוד של סבבים, אולם יעילותו תפגע בהתאם.

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

להלן מבנה טיפוסי של צופן בלוקים:

שלד בסיסי של צופן בלוקים

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

גודל המפתח

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

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

גודל הבלוק

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

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

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

  • גודל מפתח וגודל בלוק. ערכים אילו קובעים בדרך כלל את הגבול העליון של הביטחון המשוער של הצופן. באופן כללי אורך מפתח משפיע על סיבוכיות זמן ואורך הבלוק על סיבוכיות מקום.
  • ביטחון. הערכת ביטחון המסתמכת על ניסיונות אינטנסיביים מצד אנליסטים רבים לתקוף את הצופן עם מיטב ההתקפות הקריפטוגרפיות הידועות. בראשן קריפטואנליזה דיפרנציאלית, קריפטואנליזה ליניארית, התקפת ערוץ צדדי ועוד.
  • יעילות בתוכנה. סיבוכיות יישום הצופן בתוכנה, יעילות ומורכבות הקוד, צריכת זיכרון, שימוש בתת-בלוקים המתאימים לגודל מילה במעבד, סיבוכיות פעולות אלגבריות וכדומה.
  • יעילות בחומרה. יצרנים שואפים להטמיע צופן בלוקים בחומרה ייעודית כדי לשפר ביצועים. יכולת הטמעה בחומרה נמדדת במספר השערים המינימלי הדרוש ליישומו, אפשרות למקביליות, צריכת אנרגיה, מורכבות קוד ופשטות פעולות האלגוריתם.
  • ביצועים. תפוקת האלגוריתם נמדדת במספר הבתים שניתן להצפין בשנייה על מגוון פלטפורמות, כמו מעבד 64 סיביות או 8 סיביות. השאיפה כיום היא להגיע למהירויות של 10Gbps.
  • גמישות. גמישות נמדדת ביכולת להתאימו למגוון רמות של ביטחון או מגוון אופני שימוש. כמו שימוש במפתח הצפנה קטן יותר, או הרתמתו לצורך פונקציית גיבוב או קוד אימות מסרים.
  • פשטות וקלות ניתוח. האלגוריתם צריך להיות פשוט וקל להבנה באופן שמאפשר ניתוח ובדיקה על ידי מיטב המומחים. למשל אחת הטכניקות הידועות לניתוח צופן בלוקים היא בדיקה של מידת הביטחון שלו עם מספר מצומצם של סבבים, פחות ממה שהצהירו המפתחים. בדרך זו קל יותר לאמוד את חוסנו כמו גם לגלות פרצות ונקודות חולשה.
  • זכויות יוצרים ופטנטים. זכויות יוצרים לעיתים מעכבים או מונעים תיקנון הצופן בקנה מידה גדול. גופי תקינה מעדיפים בדרך כלל אלגוריתמים חופשיים.

תיבות החלפה

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

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

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

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

דוגמה לפעולת החלפה עם חלק מתיבות ההחלפה של AES

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

תיבות תמורה

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

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

מראה רשת פייסטל בסיסית. הסימן מייצג XOR ו- היא טרנספורמציה כלשהי שהיא הליבה של הצופן, שילוב של מספר פעולות אלגבריות ופעולות אי-ליניאריות

רשת פייסטל

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

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

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

מראה רשת החלפה תמורה, מייצגים תיבות החלפה (מפורטים בהמשך), היא תיבת תמורה (permutation)

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

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

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

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

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

רשת אינוולוציה

[עריכת קוד מקור | עריכה]
מבנה רשת אינוולוציה של צופן IDEA כאשר MA הוא קיצור של Multiplication-Addition זהו ליבת הצופן המורכבת שילוב פעולות כפל וחיבור בשדות אלגבריים שונים

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

דרך ידועה להוספת "אי-ליניאריות" לצופן היא שילוב של פעולות אלגבריות פשוטות בשדות סופיים שונים כמו חיבור מודולרי, פעולת XOR והזזה מעגלית ויושמה בצפנים מודרניים רבים ביניהם Salsa20 ,Threefish, בפונקציית הגיבוב SipHash ועוד. בדרך כלל משלבים בין חיבור מודולו שלם כלשהו כמו 32 או 64 סיביות (לצורך יעילות), הזזה מעגלית בהיסטים קבועים או דינאמיים ופעולת XOR ששקולה לחיבור מודולו 2, המבוצעות במבנה הנקרא בקיצור ARX דהיינו "או-מוציא של חיבור לאחר הזזה מעגלית" כאשר סדר הפעולות אינו חשוב. מבנה זה אינו עושה שימוש בתיבות החלפה והוכח כבטוח כנגד התקפה דיפרנציאלית וכן עמיד כנגד התקפת תזמון וכן התקפות קריפטוגרפיות אחרות כמו התקפת גלישה והתקפת הזזה מעגלית[2]. חסרונו העיקרי הוא שבגלל פשטותו הרבה יש צורך במספר גבוה יותר של סבבים כדי להשיג שולי ביטחון טובים. במבנה זה נעשה שימוש בצפנים רבים. דוגמה לשימוש כזה היא הפונקציה MIX מצופן Threefish:

מחברים תחילה את מודולו ואז הוא תוצאת XOR של עם לאחר הזזה מעגלית לפי קבוע כלשהו .

מבנה MIX שנעשה בו שימוש בצופן Threefish

אופני הפעלה

[עריכת קוד מקור | עריכה]
ערך מורחב – אופן הפעלה של צופן בלוקים

צופן בלוקים בהגדרה נועד להבטחת סודיות של בלוק בגודל קבוע. אך בדרך כלל המידע המיועד להצפנה עולה עשרת מונים על גודל הבלוק. לכן יש צורך לחלקו לבלוקים בגודל המתאים ולהצפינם בזה אחר זה. אם צופן הבלוקים דטרמיניסטי הפעלת פונקציית ההצפנה על בלוק נתון פעם נוספת עם מפתח זהה תניב בלוק צופן זהה. במקרים מסוימים עובדה זו עלולה להוות נקודת תורפה, כיוון שמידע על שכיחות בלוקים זהים עשוי לעזור למתקיף הצופן בחשיפת מידע אודות המערכת. כדי להתגבר על חיסרון זה מיישמים את הצופן במה שקרוי סגנון הפעלה (Mode of operation) בטוח. השיטה הפשוטה ביותר היא פיצול מסר גדול לחלקים נפרדים, כל אחד בגודל הבלוק והצפנתם בנפרד ללא תלות זה בזה. שיטה זו נקראת electronic codebook. בשיטות אחרות כל בלוק מוצפן אחרת. צופן זרם אינו סובל מבעיה זו כיוון שהוא מכיל 'זיכרון', כלומר כל יחידת מידע מוצפנת בהתבסס על מצב פנימי המורכב מתוצאה של הצפנת יחידה קודמת. אפשר לדמות התנהגות צופן זרם גם בצופן בלוקים כך שכל בלוק מוצפן עם מפתח אחר, וגם אם יוצפנו שני בלוקים זהים התוצאה תהיה שונה. בשילוב עם וקטור אתחול אפשר להצפין כמויות גדולות של מידע באופן כזה שלעולם לא יוצפנו שני בלוקים זהים עם מפתח זהה, תופעה זו נקראת הצפנה הסתברותית. השיטות הבסיסיות שעונות להגדרה זו כוללות את CBC ,CFB ,OFB ו-CTR. בשיטות אילו שמים דגש בעיקר על ביטחון ההצפנה ועל התאוששות במצב של שגיאת שידור, אך הן אינן מספקות הגנה מפני שינוי זדוני, מה שקרוי אימות והבטחת שלמות. קיימות שיטות המספקות גם הבטחת שלמות בשילוב קוד אימות מסרים, ביניהן ניתן למנות את: OCB,EAX,CWC וכן CCM ו-GCM.

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

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

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

  • קריפטואנליזה ליניארית. שהיא שיטה לניתוח צופן סימטרי (לרוב צופן בלוקים), מסוג התקפת גלוי ידוע שבה התוקף מחפש אחר קירובים ליניאריים אפיניים לפעולת הצופן באמצעות הצבות זוגות רבים של טקסטים ידועים ותוצאת הצפנתם, בשאיפה לגזור מהם ערכי המפתח. השיטה התגלתה ב-1992 על ידי הקריפטוגרף היפאני מיטסורו מאטסוי שניסה אותה לראשונה על הצופן FEAL[3]. כיום היעד בצפנים מודרניים בין היתר הוא עמידות כנגד התקפה ליניארית.
  • קריפטאנליזה דיפרנציאלית היא שיטת אנליזה שעוסקת בניתוח ההשפעה של שינויים בקלט פונקציה קריפטוגרפית על הפלט שלה. מטרתה היא למצוא היכן הצופן מתנהג בצורה שאינה אקראית וכך לגלות את המפתח. הקריפטואנליזה הדיפרנציאלית פותחה ב-1993 על ידי אלי ביהם ועדי שמיר[4]. צפנים מודרניים בדרך כלל עמידים כנגד התקפה זו, בשלבי הפיתוח מוודאים שהצופן לא מכיל מה שקרוי דיפרנציאלים בעלי הסתברות גבוהה.
  • קריפטואנליזה אינטגרלית היא התקפה שמתאימה במיוחד כנגד צופן בלוקים במבנה רשת החלפה-תמורה, בדומה לקריפטואנליזה דיפרנציאלית בשיטה זו בוחנים את תוצאת חיבור XOR של קבוצות של טקסטים גלויים כאשר חלקם קבועים וחלקם משתנים רק בבתים מסוימים שנקראים 'בתים פעילים'. השיטה יושמה לראשונה על ידי לרס קנודסן בהתקפה שנכללה בתיאור הצופן SQUARE[5] שמהווה בסיס לצופן AES. וכן יושמה בווריאציות שונות כנגד צפנים אחרים כמו Twofish.
  • slide attack שפותחה ב-1999 על ידי אלקס בריוקוב[6] ויושמה נגד Blowfish. ההתקפה מתמקדת במפתח ההצפנה ומאתגרת את ההנחה שכל צופן חלש ניתן לחיזוק על ידי מספר מרובה של סבבים.
  • התקפת בומרנג היא התקפה שמבוססת על אנליזה דיפרנציאלית שפותחה ב-1999 על ידי דויד וגנר[7]. ההתקפה סותרת את ההנחה שאם הצופן אינו מכיל דיפרנציאלים בעלי הסתברות גבוהה הוא בטוח לפחות כנגד התקפה דיפרנציאלית. וריאציות של ההתקפה נוסו בהצלחה על צפנים שונים. בכל אופן חמשת האלגוריתמים שעברו את מבחן תקן ההצפנה החדש אינם מושפעים באופן משמעותי מהתקפה זו.

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

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

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

[עריכת קוד מקור | עריכה]
ערך מורחב – צופן בלוקים בר התאמה

המושג צופן בלוקים בר התאמה (Tweakable Block Cipher)[8] הוצע לראשונה ב-2002 על ידי מוזס ליסקוב, רונלד ריבסט ודויד וגנר. הם פיתחו רעיון ל'פרימיטיב קריפטוגרפי' שלו תכונה נוספת הנקראת tweak (התאמה). זהו צופן בלוקים רגיל שמקבל מלבד הקלט הרגיל שהוא בלוק טקסט גלוי ומפתח הצפנה סודי, ערך נוסף המשמש כוקטור אתחול או nonce, ערך ייחודי וחד-פעמי כלשהו שאינו חייב להיות אקראי או סודי. הרעיון של שימוש בוקטור אתחול כבר קיים בסגנונות ההפעלה של צופן בלוקים אבל ברמה גבוהה יותר (כלומר מופרדת מהצופן עצמו). ההצעה שלהם היא להוריד את התוספת לרמה של הצופן ולהפוך אותה לחלק בלתי נפרד ממנו, לטענתם פיתוח צופן בלוקים שמוטמעת בו יכולת התאמה כזו אינו קשה ובמחיר מועט אפשר לקבל צופן בלוקים עם ביטחון מוכח, כך שתוצאת הצפנת שני בלוקים זהים תהיה שונה תמיד גם אם המפתח זהה. הסיבה לפיתוח מבנה זה היא בשל העובדה שבדרך כלל תהליך הכנת המפתח בצופן בלוקים איטי ויקר במונחי מחשוב כיוון שאינו מעוצב להחלפה תדירה של מפתחות, מה שמאלץ את הפעלת צופן הבלוקים באופן הפעלה מתקדם כלשהו כמו EAX שבא על חשבון יעילות. החלפת וקטור אתחול זולה יותר ולכן מועדפת במקרים שבהם זה אפשרי.

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

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

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

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

כאשר היא פונקציית גיבוב כלשהי כמו UHASH.

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

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

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

רשימת צפני בלוקים

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

במרוצת השנים פותחו צפני בלוקים רבים, מהם בטוחים יותר מהם פחות. DES הוא אבן דרך ונקודת ציון חשובה בהתפתחות צופן הבלוקים המודרני. אף על פי שאינו בטוח כיום לשימוש בשל מפתח ההצפנה הקצר, הצופן היה בשימוש מאסיבי ועדיין קיים בשימוש מוגבל בגרסת DES משולש וכן היה לתקן ההצפנה הרשמי הראשון של ממשלת ארצות הברית עד שנת 2001. מספר ניסיונות נעשו כדי להחליפו בהם אפשר למנות את IDEA שפותח ב-1991, RC5 של רונלד ריבסט ו-Blowfish של ברוס שנייר וכן TEA של רוג'ר נידהם ודויד ווילר. תקן ההצפנה המתקדם שהחליף את DES הפך לצופן הפופולרי ביותר כיום והוא בשימוש במרבית מערכות האבטחה המודרניות. למעשה יתר המועמדים המובילים לתקן המתקדם (סרפנט, MARS, Twofish ו-RC6) שלא נבחרו לבסוף, הוערכו כבטוחים לשימוש. להלן רשימה חלקית של צפני בלוקים פופולריים, חלקם עדיין בשימוש כיום וחלקם אף הוכנסו לתקנים הבינלאומיים:

שם הצופן מבנה הצופן תיבות החלפה מספר סבבים גודל בלוק בסיביות גודל מפתח בסיביות מקור שנה
3DES רשת פייסטל 8 תיבות 6x4 16 64 56 IBM בשיתוף עם NSA 1973
3-Way רשת החלפה-תמורה ללא 11 96 96 יוהאן דאמן 1994
AES רשת החלפה-תמורה 16x16 10/12/14 128 128/192/256 יוהאן דאמן ווינסנט ריימן 2000
ARIA רשת החלפה-תמורה אינוולוציונית 8x8 12/14/16 128 128/192/256 KATS 2004
Blowfish רשת פייסטל 8×32 16 64 32-448 ברוס שנייר 1993
Camellia רשת פייסטל 8x8 18 128 128/192/256 מיצורו מצואי ואחרים NTT יפן 1998
CAST-128 רשת פייסטל 8×32 16 64 40-128 Carlisle Adams ו-Stafford Tavares 1996
CAST-256 רשת פייסטל 8×32 48 128 128/160/192/224/256 Carlisle Adams ו-Stafford Tavares 1996
CRYPTON רשת החלפה-תמורה 2 תיבות 8x8 12 128 128/192/256 Chae Hoon Lim 1998
DEAL רשת פייסטל 8 תיבות 6x4 6/8 128 128/192/256 לארס קנודסן 1998
DES רשת פייסטל 8 תיבות 6x4 16 64 56 IBM בשיתוף עם NSA 1973
DFC רשת פייסטל 6×32 8 128 128/192/256 אקול נורמל סופרייר 1998
E2 רשת פייסטל 8x8 12 128 128/192/256 יפן (Nippon Telegraph and Telephone) 1998
FEAL רשת פייסטל אין 32 64 128 NTT 1987
FROG מבנה ייחודי[9] ללא 8 128 128/192/256 TecApro 1998
GOST רשת פייסטל 8 תיבות 4x4 32 64 256 ברית המועצות 1970
Hasty Pudding רשת פייסטל ללא ללא משתנה משתנה Richard Schroeppel 1998
IDEA רשת אינוולוציה ללא 8 64 128 ג'יימס מסי 1991
Lucifer רשת פייסטל 2x16 16 128 1028 הורסט פייסטל ואחרים 1966
MARS רשת פייסטל מסוג 3 512 32 128 128/192/256 דון קופרשמידט ואחרים IBM 1998
RC2 רשת פייסטל ללא 18 64 משתנה[10] רון ריבסט מעבדות RSA 1989
RC5 רשת פייסטל ללא 12 64 128[11] רון ריבסט מעבדות RSA 1994
RC6 רשת פייסטל ללא 20 128 128/192/256 רונלד ריבסט מעבדות RSA 1998
SAFER+‎ רשת החלפה-תמורה 8x32 7/10 128 128/256 Cylink ג'יימס מסי ואחרים 1993
SAFER++‎ רשת החלפה-תמורה 8x32 7/10 128 128/256 Cylink ג'יימס מסי ואחרים 1993
SAFER רשת החלפה-תמורה 8x32 6 64 64 Cylink ג'יימס מסי 1993
SEED רשת פייסטל 2 תיבות 8x8 16 128 128 KISA דרום קוראה 1998
SERPENT רשת החלפה-תמורה 32x16 32 128 128/192/256 רוס אנדרסון ואחרים קיימברידג' 1998
Skipjack רשת פייסטל 8×32 32 64 80 NSA ממשלת ארצות הברית שוחרר לידיעת הציבור ב-1998
Threefish רשת פייסטל ללא 72/80 256/512/1024 256/512/1024 נילס פרגוסון ואחרים[12] 2008
Twofish רשת פייסטל 4 תיבות 8x8[13] 16 128 128/192/256 Counterpane Labs ברוס שנייר ואחרים 2000

צופן בלוקים משקל קל

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

צופן בלוקים משקל קל הוא צופן בלוקים המותאם במיוחד להטמעה בחומרה זעירה עם מספר מינימלי של יחידות GE (תואמי שערים לוגיים), עם צריכת אנרגיה הנמוכה ביותר האפשרית, או בתוכנה המינימלית ביותר האפשרית במונחים של צריכת זיכרון, זאת תוך שמירה על הביטחון הגבוה ביותר שניתן להשיג. לאור הניסיון שהצטבר עם השנים, הסתבר שאפשר לפתח צופן בלוקים בטוח מבלי להשתמש בפונקציות פנימיות מסובכות או טבלאות החלפה גדולות על חשבון מספר גבוה יותר של סבבים, שזה אטרקטיבי במיוחד עבור חומרה זעירה. הצורך בפרימיטיבים קריפטוגרפיים קלילים גבר במיוחד עקב התפתחות טכנולוגיית האינטרנט של הדברים ביניהם: התקני תיוג ובקרה כמו RFID, חיישנים אלחוטיים וביו-רפואיים, מחשוב לביש, כרטיס חכם וכן טכנולוגיות בית חכם כמו שליטה ובקרה מרחוק, מנעול אלקטרוני, תאורה, מיזוג אוויר וטמפרטורה מטעמים של חסכון באנרגיה וידידותיות לסביבה. לשם כך קיימת בין היתר רשת אינטרנט 0 שהיא רשת עמית לעמית איטית אך זולה ופשוטה, הפועלת בסביבה מוגבלת משאבים ומאפשרת לכל מכשיר להתקשר עם מכשיר אחר ישירות. חלקם פועלים על אנרגיה חיצונית וחלקם פועלים על סוללה זעירה שאמורה להחזיק מעמד ללא טעינה במשך זמן רב (אפילו מספר שנים). כל המכשירים האמורים כוללים רכיב תקשורת והם משדרים מידע רגיש בצורה כזו או אחרת. כמו כל רשת חובה להגן על התקשורת הזו מפני גורמים עוינים באמצעות קריפטוגרפיה. עקב כך מומחים רבים התמקדו בפיתוח פרימיטיבים קריפטוגרפיים חדשים; צופן בלוקים, צופן זרם, פונקציית גיבוב וקוד אימות קלי משקל. כמו כן NIST הקים סדנת קריפטוגרפיה קלת משקל[14] על מנת לבדוק אפשרות לפתח תקנים מתאימים.

ההגדרה של "משקל" בהקשר של צופן בלוקים מתייחסת לכמה היבטים; הראשון, משקל האלגוריתם מהיבט של המשאבים הדרושים להרצתו, זיכרון וזמן ביצוע. השני, היבט לא פחות חשוב, צריכת האנרגיה שלו. בתוכנה משקל נמדד באמצעות מספר מחזורי שעון הדרוש לעיבוד בית אחד (cpb) שקובע את מהירות האלגוריתם, זיכרון ה-RAM שהוא צורך וכן תקורה נוספת הנובעת מתהליך הכנת מפתח. בחומרה משקל נמדד ביחידות GE כשכל אחת מהן שקולה לשער NAND אחד. יעילות החומרה נמדדת במונחים של תפוקה בתדר מסוים (בדרך כלל 100Hz) וכן מביאים בחשבון תקורה כמו זמן טעינת מפתח וכיוצא בזה.

תקן איזו ISO/IEC 29192-2[15] קטגורית צופן בלוקים קל משקל כולל את הצפנים PRESENT ו-CLEFIA. להלן רשימה חלקית של צפני בלוקים מודרניים קלי משקל ומאפייניהם[16]:

הצעה מאפיינים קריפטוגרפיים מאפייני יישום
שם מפתחים קישור גודל בלוק גודל מפתח מבנה סבבים קריפטואנליזה טכנולוגיה שטח (GE) תפוקה (Kb/s @ 100kHz) צריכת אנרגיה (µW) פרסום
AES Rijmen et al. AES conference 98 128 128 SPN 10
  • דיפרנציאלים בלתי אפשריים, 7 סבבים AES-128
  • בומרנג עם מפתחות קשורים, AES-192 ו-AES-256
  • Biclique (מלא AES)
0.13µm 3100 80 -- ECRYPT
192 12 -- -- -- -- --
256 14 -- -- -- -- --
Chaskey Cipher Mouha et. al. SAC'14 128 128 ARX 8
  • דיפרנציאלית/ליניארית (6,7 סבבים)
-- -- -- -- --
CLEFIA Shirai et al. FSE 2007 128 128 GFN 18
  • התקפה אינטגרלית (12, 13, 14 סבבים)
  • דיפרנציאלים בלתי אפשריים (13, 14, 15 סבבים)
0.09µm 4950 355.6 -- ECRYPT
192 22 -- -- -- -- חברת סוני
256 26 -- -- -- -- --
DESL Leander et al. FSE 2007 64 184 פייסטל 16 0.18 µm 2168 44.4 1.6 ECRYPT
פאנטומאס Grosso et al. FSE'14 128 128 SPN 12
  • לא ידוע
-- -- -- -- --
GOST2 Poschmann et al. סדנת CHES 10 64 256 פייסטל 32 0.18 µm 651 / 1017 24.24 / 200 -- מפרט
HIGHT Hong et al. סדנת CHES 06 64 128 GFS 32
  • Saturation (22 סבבים)
  • דיפרנציאלים בלתי אפשריים (26 סבבים)
  • התקפת Rectangle עם מפתחות קשורים (מלוא הצופן)
  • Biclique (מלוא הצופן)
0.25µm 3048 188.2 -- ECRYPT
ITUbee Karakoç et al. LightSec'13 80 80 פייסטל 20
  • לא ידוע
-- -- -- -- --
KASUMI ETSI 3GPP std 64 128 פייסטל 8
  • התקפת בומרנג עם מפתחות קשורים (מלוא הצופן)
-- -- -- -- --
KLEIN Gong et al. SaP 12 64 64 SPN 12
  • דיפרנציאלית (KLEIN-64, 8 סבבים)
  • דיפרנציאלים חתוכים (KLEIN-64, מלוא הצופן)
0.18 µm 1360 / 2032 -- -- מפרט
80 16 1530 / 2202 -- --
96 20 1700 / 2372 -- --
KATAN De Cannière et al. CHES 09 32 80 דמוי צופן זרם 254
  • התקפה דיפרנציאלית (KATAN32, 115 סבבים)
  • רב ממדית MitM (175 סבבים KATAN32, 130 סבבים KATAN48 ו- 112 סבבים KATAN64)
  • 3-subsets MitM (מלוא הצופן)
0.13 µm 802 12.5 0.381 ECRYPT
48 -- -- -- -- --
64 0.13 µm 1054 25.1 0.555 ECRYPT
KTANTAN De Cannière et al. CHES 09 32 80 דמוי צופן זרם 254 0.13 µm 462 12.5 0.146 ECRYPT
48 -- -- -- -- --
64 0.13 µm 688 25.1 0.292 ECRYPT
LBlock Wu et al. ACNS 11 64 80 פייסטל 32
  • מפתחות קשורים דיפרנציאלים בלתי אפשריים (22 סבבים)
  • Zero-correlation (22 סבבים)
  • Integral attack (22 סבבים)
  • דיפרנציאלים בלתי אפשריים (21, 23 סבבים)
0.18 µm 1320 200 -- מפרט
LEA Hong et al. WISA 13 128 128 GFN 24
  • התקפת מתאם אפס ליניארית
  • התקפת דיפרנציאלים אוטומטיים
-- -- -- -- --
192 28
256 32
LED Guo et al. CHES 11 64 64 SPN 32
  • אד הוק (12 סבבים של LED-64, ו-32 סבבים של LED-128)
0.18 µm 966 5.1 -- מפרט
128 48 1265 3.4 -- מפרט
MANTIS Beierle et al. CRYPTO 16 64 128+64 (tweak) SPN 14
  • התקפה דיפרנציאלית (10 סבבים)
-- -- -- -- --
mCrypton Lim et al. ISA 06 64 64 SPN 12
  • MitM עם 7 סבבים mCrytpon-64/96/128
  • MitM עם 8 ו- 9 סבבים mCrytpon-128
0.13µm 2420 482.3 -- מפרט
96 2681 -- --
128 2949 -- --
Midori Banik et al. Asiacrypt'15 64 128 SPN 16
  • לא ידוע
0.09µm[18] 1542 -- 60.6[19] מפרט
128 20 2522 -- 89.2
MISTY1 Matsui FSE'97 64 128 פייסטל 8
  • התקפה אינטגרלית על תכונת ההתחלקות (מלוא הצופן)
-- -- -- -- --
Mysterion Journault et al. WCC 15 128 ?[20] SPN 12
  • לא ידוע
-- -- -- -- --
256 ? 16 -- -- -- --
Noekeon Daemen et al. Nessie Workshop 128 128 SPN 16
  • Bit-pattern based integral, 5 סבבים
  • התקפה ליניארית, 12 סבבים
-- -- -- -- --
Piccolo Shibutani et al. CHES 11 64 80 GFN 25
  • Biclique (מלא Piccolo-80; 28-סבבים Piccolo-128)
  • דיפרנציאלים בלתי אפשריים עם מפתחות קשורים, 14 סבבים Piccolo-80, ו-21 סבבים Piccolo-128
-- 683 / 1136 14.8 / 237.04 -- / -- מפרט
128 31 -- 758 / 1196 12.12 / 193.9 -- / --
PRESENT Bogdanov et al. CHES 07 64 80 SPN 31
  • Statistical saturation, up to 24-סבבים
  • Multi-dimensionnal linear, 26-סבבים
  • Truncated differential, 26-סבבים
0.18 µm 1075 / 1570 11.7 / 200 1.4 / 2.78 Poschmann עבודת הדוקטורט של
128 1391 / 1884 11.45 / 200 -- / 3.67
PRIDE Albrecht et al. CRYPTO 14 64 128 SPN 20
  • לא ידוע
-- -- -- -- --
PRINCE Borghoff et al. ASIACRYPT 12 64 128 SPN 12
  • התקפת השתקפות, 6 סבבים
  • Sieve-in-the-Middle, 8 סבבים
  • דיפרנציאלים מרובים, 10 סבבים
0.09 µm / 0.13 µm 3286 / 3491 529.9 / 533.3 4.5 / 5.8 מפרט
RC5 Rivest FSE 95 32 0..2040 ARX 12
  • דיפרנציאלית
  • התקפה ליניארית
-- -- -- --
64
128
Rectangle Zhang et al. Sci China'15 64 80 SPN 25
  • התקפה דיפרנציאלית (18 סבבים)
0.13 µm 1599.5 -- מפרט
128 2063.5 --
RoadRunneR Baysal et. al. LightSec 15 64 80 פייסטל 10
  • לא ידוע
-- -- -- -- --
128 12 -- -- -- --
Robin Grosso et al. FSE'14 128 128 SPN 16
  • מרחב משנה קבוע (מפתחות חלשים, מלוא הסבבים)
-- -- -- -- --
SEA Standaert et al. SCRAA 06 96[21] 96 פייסטל 93
  • לא ידוע
0.13 µm 449 -- 3.218 MSQ07
SKINNY Beierle et al. CRYPTO 16 64 64/128/192[22] SPN 32/36/40
  • לא ידוע
0.18 µm 1223/1696/2183 200.0/177.8/160.0 -- מפרט
128 128/256/384 40/48/56 2391/3312/4268 320.0/266.7/228.6 -- מפרט
SIMECK Yang et al. CHES'15 32 64 פייסטל 32
  • דיפרנציאלית (22/28/35 סבבים SIMECK-32/48/64)
0.13µm 549 / 765 5.6 / 88.9 0.417 / 0.606 מפרט
48 96 36 778 / 1117 5.0 / 120.0 0.576 / 0.875
64 128 44 1005 / 1484 4.2 / 133.3 0.754 / 1.162
SIMON Beaulieu et al. NSA eprint.iacr 2013 32 64 פייסטל ARX 32
  • דיפרנציאלית (עד 21/22/28/35/46 סבבים SIMON-32/48/64/96/128)
  • ליניארית (20 סבבים SIMON-32)
  • דיפרנציאלים בלתי אפשריים (19/20/26 סבבים SIMON-32/48/64)
  • התקפה ליניארית רב ממדית (23/25/31/38/53 סבבים SIMON-32/48/64/96/128)
-- -- -- -- מפרט
48 72 / 96 36 -- / 763 -- / 15.0 --
64 96 / 128 42 / 44 838 / 1000 17.8 / 16.7 --
96 96 / 144 52 / 54 984 / -- 14.8 / -- --
128 128 / 192 / 256 68 / 69 / 72 1317 / -- / -- 22.9 / -- / -- --
SPARX Dinu et al. ASIACRYPT 16 64 128 SPN (ARX) 24
  • לא ידוע
-- -- -- -- --
128 128/256 32/40 -- -- -- --
Speck Beaulieu et al. NSA eprint.iacr 13 32 64 ARX 22
  • דיפרנציאלית (עד 14/15/19/17/19 סבבים SPECK-32/48/64/96/128)
  • Rectangle (11/12/14/16/18 סבבים SPECK-32/48/64/96/128)
-- -- -- -- 2013
48 72 / 96 22 / 23 -- / 884 -- / 12.0 --
64 96 / 128 26 / 27 984 / 1127 14.5 / 13.8 --
96 96 / 144 28 / 29 1134 / -- 13.8 / -- --
128 128 / 192 / 256 32 / 33 / 34 1396 / -- / -- 12.1 / -- / -- --
TWINE Suzaki et al. Workshop on LC 11 64 80 GFN 36
  • Biclique (full cipher)
  • Zero-correlation (23 סבבים)
0.09 µm 1799 178 -- מפרט
128
  • Biclique (מלוא הסבבים)
  • Zero-correlation (25 סבבים)
2285 178 --
XXTEA Needham et al. Note 64 128 פייסטל 64
  • התקפת rectangle מפתחות קשורים 36 סבבים
  • MitM עם 23 סבבים
0.13 µm 3490 57.1 19.5 ECRYPT
Zorro Gérard et al. CHES 13 128 128 SPN 24
  • דיפרנציאלית פנימיים (264 מפתחות חלשים, מלוא הסבבים)
-- -- -- -- --
Hummingbird-2 Daniel Engels et al. Lecture Notes in Computer Science 16 256 מיוחד[23] 4
  • The Differential

Sequence Analysis

-- -- -- -- --

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

  • צופן זרם. אופני הפעלה שונים של צופן בלוקים מדמים צופן זרם כמו OCB או CBC. באופן זה ניתן להצפין מנות מידע קטנות יותר בכל אורך רצוי מבלי להמתין לקבלת בלוק שלם. יתרה מזו צופן בלוקים יכול לשמש מרכיב בסיסי בצופן זרם כמו צופן סרפנט שמהווה חלק אינטגרלי מ-SOSEMANUK.
  • פונקציית גיבוב קריפטוגרפית. ישנן דרכים בטוחות להפיכת צופן בלוקים לפונקציית גיבוב קריפטוגרפית תחת הנחות סטנדרטיות בשל התכונה המובנית של צופן בלוקים שהוא חד-כיווני. בהינתן טקסט מוצפן קשה לנחש את הטקסט המקורי או את המפתח. אולם צופן בלוקים הוא רק חצי חד-כיווני כיוון שאם ידוע המפתח אפשר לשחזר את הטקסט המקורי. מה שדורש פעולות נוספות כדי להבטיח חד-כיווניות מלאה. מסיבה זו ניצול צופן בלוקים לצורך פונקציית גיבוב איטי בהשוואה לפונקציית גיבוב ייעודית.
  • מחולל פסאודו-אקראי. באופן דומה אפשר להכין מחולל פסאודו-אקראי המייצר מספרים פסאודו-אקראיים לכל מטרה, בין היתר לצורך מפתחות הצפנה. תקן NIST הנקרא SP800-90A מפרט דרך בטוחה לשימוש בצופן בלוקים באופן מונה כדי לחולל מספרים אקראיים[24].
  • קוד אימות מסרים. צופן בלוקים מהווה מרכיב בסיסי במספר אלגוריתמים לקוד אימות מסרים. למשל בהצפנה באופן שרשור כמו CBC אפשר להצפין את המסר כולו והתוצאה האחרונה או חלק ממנה מהווה תג אימות. תג האימות מתאים באופן חד חד-ערכי לטקסט המקור, כך שכל שינוי בטקסט המקורי יגרום בסבירות גבוהה לשינוי בתג האימות ועל כן יתגלה.
  • הצפנה מאומתת. הצפנה מאומתת מבצעת הצפנה של המסר באמצעות צופן בלוקים בד בבד עם ייצור תג אימות להבטחת שלמותו ואימות מקורו. ההצפנה והאימות מבוצעים באמצעות צופן בלוקים עם מפתחות שונים.
  • צופן בלוקים בר התאמה הוא מבנה להפעלת צופן בלוקים שמוסיף אקראיות או "גיוון" על ידי הוספת פרמטר מלבד המפתח שמשתנה מבלוק לבלוק אך אינו חייב להיות סודי. הפרמטר הנוסף מתפקד כמו וקטור אתחול. זוהי שיטה יעילה להפעלת צופן בלוקים שמתאימה במיוחד להצפנת דיסקים.

קישורים חיצוניים

[עריכת קוד מקור | עריכה]
ויקישיתוף מדיה וקבצים בנושא צופן בלוקים בוויקישיתוף

הערות שוליים

[עריכת קוד מקור | עריכה]
  1. ^ Claud shannon
  2. ^ Rotational Cryptanalysis of ARX
  3. ^ Matsui, M. and Yamagishi, A. "A new method for known plaintext attack of FEAL cipher". Advances in Cryptology - EUROCRYPT 1992
  4. ^ Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993
  5. ^ SQUARE
  6. ^ Alex Biryukov and David Wagner (March 1999). "Slide Attacks"
  7. ^ Boomerang
  8. ^ Tweakable Block Ciphers
  9. ^ הצופן פועל ברמת בתים ובצופן זה המפתח עצמו משמש כרצף הוראות לעיבוד הקלט, על מנת להסתיר את הפעולות הפנימיות של הצופן
  10. ^ אורך המפתח הוגבל ל-40 סיביות כדי להכשירו למטרת ייצוא
  11. ^ אורך המפתח משתנה בטווח 0–2040 סיביות
  12. ^ צופן זה מהווה חלק מפונקציית הגיבוב Skein
  13. ^ תיבות ההחלפה של Twofish הן דינאמיות ותלויות במפתח הסודי
  14. ^ Lightweight Cryptography
  15. ^ ISO/IEC 29192-2:2012
  16. ^ CryptoLUX Wiki
  17. ^ כיוון שתיבות ההחלפה טובות יותר התקפות על תיבות ההחלפה של DES לא יהיו בהכרח יעילות נגד DESLX. יתרה מזו, לא ידוע כיום על התקפה יעילה נגד מבנה FX של DESLX המלא.
  18. ^ המספרים מתייחסים להצפנה בלבד
  19. ^ בניגוד לאחרים נתון זה מתייחס ל-10 MHz.
  20. ^ הצגת הצופן לא כללה תהליך הכנת מפתח, רק פונקציית סבב ומספר הסבבים
  21. ^ גודל הבלוק של SEA ניתן לבחירה ככפולות של 6, המינימלי הוא 96 סיביות
  22. ^ SKINNY בנוי מהשלד של TWEAKEY שבו אין הבדל גדול בין המפתח לבין ה-tweak לכן גודל המפתח הוא בעצם סכום הגדלים של המפתח וה-tweak.
  23. ^ שילוב של צופן זרם עם צופן בלוקים
  24. ^ SP800-90A