MARS

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

MARS הוא צופן בלוקים סימטרי שפותח ב-1998 בחברת IBM על ידי צוות מפתחים בראשות דון קופרשמידט[1] שהיה מעורב בפיתוח DES כמועמד לתקן ההצפנה המתקדם. MARS הגיע למקום האחרון מבין חמשת המועמדים המובילים (אחרי RC6). הצופן קומפקטי, מתאים ליישום בתוכנה ובחומרה, מנצל את יכולות המעבד המודרני להשגת מהירות, יעילות וביטחון טובים יותר לעומת אלגוריתמים מדור קודם כמו DES או IDEA ונועד להצפנה מסיבית. MARS פועל על בלוקים בגודל 128 סיביות ומפתח הצפנה בטווח גדלים של [128 - 400] סיביות. כיתר המועמדים המובילים שעלו לגמר הוכרז במהלך התחרות שלא התגלו התקפות מעשיות שמסכנות את ביטחונו. IBM התירה את השימוש בו ומימוש שלו ברישיון חופשי במגבלות מסוימות, למרות היותו מוגן בפטנט וזכויות יוצרים.

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

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

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

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

  • חיבור, חיסור ו-XOR, בעיקר לערבוב ערכי קלט עם ערכי מפתח (פעולות אילו לא נועדו להשגת ביטחון).
  • טבלת חיפוש (Table lookup) הנקראת גם תיבות החלפה (s-box), המספקות את הביטחון העיקרי של הצופן. MARS משתמש בטבלה בגודל 512 כניסות של מילים בגודל 32 סיביות. תיבות ההחלפה תוכננו להשגת אפקט מפולת מהיר ונבחרו בקפידה כדי לעמוד בפני התקפות דיפרנציאליות ולינאריות. חסרונן העיקרי שנדרשות שלוש פקודות מכונה לכל החלפה וכן צריכת זיכרון - מה שעשוי להיות קריטי במעבד קטן.
  • הזזה מעגלית (rotation) קבועה או דינאמית התלויה בקלט. בפעולה זו הסיביות הנפלטות מצד אחד מוחזרות לצד השני. שימוש מסיבי בהזזה מעגלית קיים באלגוריתמים מודרניים אחרים כמו RC6. חסרונן העיקרי שלעתים תוצאת הזזה אינה מושפעת מכל סיביות האופרנדים מה שמוביל לחולשה מסוימת. לדוגמה אם מספר הפוזיציות להזזה מיוצג על ידי משתנה count בגודל 32 סיביות, הרי שלכל היותר נדרשות שש סיביות מתוכו כדי לייצג את ההזזה (הייצוג הבינארי של הזזה מקסימלית - 32 פוזיציות), ליתר הסיביות אין השפעה. הפתרון אפשרי הוא שילוב עם פעולת כפל.
  • פעולת כפל שלמים מודולו כאשר מתייחס לגודל מילה בסיביות. כמו בצופן IDEA פעולות אילו מניבים פיזור גבוה ותכונות דיפרנציאליות טובות. בארכיטקטורת מעבדים מודרניים חל צמצום ניכר במספר מחזורי שעון לפעולת כפל. לכן השימוש בהן הופך אטרקטיבי.

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

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

  • חיבור מפתח.
  • שמונה סבבים של ערבוב לפנים ללא מפתח.
  • שמונה סבבים של ערבוב לפנים עם מפתח.
  • שמונה סבבים של ערבוב לאחור עם מפתח.
  • שמונה סבבים של ערבוב לאחור ללא מפתח.
  • חיסור מפתח.

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

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

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

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

בבניית תיבות ההחלפה (s-box) הכניסות חושבו בסגנון פסאודו-ראנדומלי ונבדקו שלהם תכונות דיפרנציאליות ולינאריות טובות כדלהלן; עבור הכניסה מחושבת על ידי הפעלת פונקציית הגיבוב הקריפטוגרפית SHA-1 שמחזירה 4 מילים של 32 סיביות:

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

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

תרשים ערבוב לפנים של צופן מארס

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

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

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

Phase (I) השלב הפותח שנקרא ערבוב לפנים

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


ערבוב לאחור של הצפנת צופן מארס, כל הפעולות הפוכות לפעולות שבוצעו בערבוב הפותח

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

קלט: בגודל 32 סיביות כל אחד. שים לב שהביטוי מתייחס לאינדקס בגודל 9 סיביות לטבלה המאוחדת מ- ו-

הפלט הוא .

Phase (II) גרעין קריפטוגרפי

Phase (III) השלב המסיים המשלים של השלב הפותח שנקרא ערבוב לאחור.


פלט הצופן הוא ארבע המילים .

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

Phase (I)

Phase (II)

Phase (III)

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

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

בקוד המתואר נקרא מסכת סיביות (bit mask) כאשר הסיביות מחושבות לפי ערכי . וגודל המסכה הוא לכל היותר . הסמל הוא האופרטור OR והסמל הוא האופרטור AND.

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

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

ועדת המחקר של האיחוד האירופי לבחירת תקן ההצפנה אירופאי הנקראת NESSIE (מקבילה של NIST) ביקרה את כל המועמדים המובילים לתקן AES בשנים 2000-2003 וציינה מספר בעיות בקשר ל-MARS[2]. לדעת הוועדה, טענת המפתחים לגבי ביטחון הצופן מכילה מספר שגיאות ואין בהירות מספקת לגבי תרומתו של המבנה המיוחד (תוספת הסבבים ללא המפתח) לביטחונו, אם כי אין מספיק מידע כדי לפתח התקפה מעשית. קיימות למעשה התקפות תאורטיות (של ביהם ושנייר) על מספר סבבים מצומצם של הצופן שמלמדות שאין הוכחה ברורה ליתרון זה. ניתוח תהליך הרחבת המפתח מאוד איטי ואינו מעיד בהכרח על ביטחונו. במיוחד העובדה ששתי הסיביות הנמוכות של חלקים מהמפתח המשתתפים בכפל שנקבעו ל-"11", משליכה שתמיד יהיו שני קלטים שלא ישתנו בשלב הכפל בלי התחשבות במפתח. המבקרים מסכמים שמבנה MARS היה מורכב מדי להערכה בזמן הקצר של התחרות ואין ביטחון שלא יתגלו חולשות.

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

ההתקפה הטובה ביותר הידועה (נכון לשנת 2000) כנגד צופן MARS היא התקפה דיפרנציאלית של ג'ון קלסי, ברוס שנייר וטדיושי קונו[3]. ההתקפה שנקראת 'בומרנג' מצליחה לפרוץ את MARS באחד-עשר סבבים של הגרעין הקריפטוגרפי בסיבוכיות של טקסטים גלויים נבחרים עם זיכרון ו- ניסיונות (הצפנה חלקית - ללא שכבת הערבוב).

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

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