סרפנט (צופן)

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

סרפנט (Serpent) הוא צופן בלוקים סימטרי שפותח ב-1998 על ידי רוס אנדרסון - קיימברידג', אלי ביהם - הטכניון ולארס קנודסן - אוניברסיטת ברגן, במטרה להוות מועמד לתקן ההצפנה המתקדם.‏[1] זהו צופן בעל תכנון שמרני ושולי ביטחון הגבוהים ביותר מבין כל המועמדים האחרים שהוצעו במהלך התחרות. בסופו של דבר הגיע למקום השני וריינדל נבחר כאלגוריתם הזוכה. סרפנט משתמש בתיבות החלפה (s-box) דומות ל-DES במבנה חדש המאפשר אפקט כדור השלג מהיר, ניתן ליישום יעיל בטכניקת bitslice[2], קל ופשוט לניתוח, מהיר לפחות כ-DES במחשב אינטל נפוץ ובטוח יותר מ-DES משולש. מימוש ממוטב של הצופן כפי שהוצע לתקן מופץ תחת GPL לשימוש חופשי, למרות שבקוד מצוין אחרת.

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

בשל פילוסופיה שמרנית, נמנעו המפתחים מלהכניס בצופן טכנולוגיות חדשות ובלתי מוכרות, בשל הכוונה לייעדו להצפנת מידע רב בעל חשיבות כמידע פיננסי, בריאותי או ממשלתי. לכן בתחילה הוחלט על שימוש בתיבות ההחלפה של DES שנחקרו לעומק לאורך שנים על ידי מיטב המומחים, אך במבנה ממוטב המתאים יותר למעבדים מודרניים. ההיגיון היה לרכוש את אמון הציבור ובעיקר להוכיח שלא הוכנסה דלת אחורית. ההצעה המקורית פורסמה בסדנה החמישית של Fast Software Encryption שהתקיימה ב-1998 בפריז (כיום בחסות IACR). לאחר מכן עבר האלגוריתם שיפורים אחדים, תיבות ההחלפה הוחלפו בתיבות אחרות שמציעות עמידות טובה יותר כנגד התקפות בעיקר דיפרנציאליות ושונתה פרוצדורת הרחבת המפתח. בשל כך סומנה הגרסה הראשונה Serpent-0, והגרסה המשודרגת שהייתה מועמדת לתקן Serpent-1. עיקר ההשראה לצופן סרפנט מקורה בטכנולוגיה bitslice - שהיא מעין חישוב מקבילי, שפותחה על ידי אלי ביהם עבור DES במטרה לאפשר הצפנה מקבילית של בלוקים כדי לשפר את מהירותו, מאז התגלתה ככלי שימושי למטרות נוספות. סרפנט משיג ביצועים טובים ביישום מעשי בשל המקביליות של טכניקת bitslice.

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

טרנספורמציית הערבוב הלינארית של סרפנט, הסימן \lll מייצג הזזה מעגלית לשמאל במספר פוזיציות לפי הערך שלימינו והסימן \ll מייצג הזזה לשמאל (shift left), הסימן \oplus מייצג XOR

סרפנט (נחש במיתולוגיה) הוא צופן איטרטיבי, הכולל 32 סבבים של רשת החלפה-תמורה (SP-network) על ארבע מילים בגודל 32 סיביות (סך הכול 128 סיביות). כל הערכים בצופן מייצגים מערכי סיביות בסדר בתים קטן (כלומר המילה או הסיבית הנמוכה ביותר - הפחות חשובה, מאוחסנת בכתובת הראשונה בזיכרון המערך). האלגוריתם מצפין 128 סיביות של טקסט קריא P ל-128 סיביות טקסט מוצפן C באמצעות 33 תת-מפתחות בגודל 128 סיביות כל אחד K_0,...,K_{32} המורחבים ממפתח הצופן המסופק על ידי המשתמש. מפתח הצופן יכול להיות 128, 192 או 256 סיביות. תקציר האלגוריתם פשוט, כדלהלן:

  • פרמוטציה ראשונית (Initial Permutaion) החלפה בטבלת תמורה קבועה.
  • 32 סבבים שבכל אחד מהם מערבבים תת-מפתח מתאים עם הקלט באמצעות XOR, את התוצאה מחליפים באמצעות תיבות ההחלפה של סרפנט (להלן) ולמעט בסבב האחרון מוסיפים טרנספורמציה לינארית (להלן). בסבב האחרון מוחלפת הטרנספורמציה הלינארית בערבוב נוסף עם המפתח באמצעות XOR.
  • פרמוטציה מסיימת (Final Permutation) החלפה הופכית שמבטלת את ההחלפה הראשונה.

לטבלאות התמורה IP ו-FP אין חשיבות קריפטוגרפית והן קיימות רק לצורך אופטימיזציה (המרה לפורמט המאפשר יישום bitslice). לצורך תיאור הצופן, ערך הביניים לאחר כל סבב נקרא הווקטור B_i. הקלט לסבב הראשון הוא B_1 לשני B_2 וכן הלאה (המציין i מתייחס למספר הסבב). הפעולה העיקרית המתרחשת בלב הצופן המסומנת R_i משתמשת בכל סבב בתיבת החלפה אחת משמונה תיבות ההחלפה כשהיא מוכפלת 32 פעמים, כל עותק מחליף ארבע סיביות אחרות של הקלט B_i. בגרסה הממוטבת ההחלפה מתרחשת במקביל. כך יוצא שכל אחת מהתיבות מנוצלת ארבע פעמים במהלך ההצפנה. לאחר ההחלפה מתבצעת הטרנספורמציה הלינארית.

ובניסוח פורמלי:

  1. B_0=\mbox{IP}(P)
  2. \mbox{For }i=0\mbox{ to }30\mbox{ do:}
    1. B_{i+1}=R_i(B_i)
  3. C=\mbox{FP}(B_{32})

למעט בסבב האחרון הטרנספורמציה R_i(X) כוללת שילוב מפתח, החלפה בטבלה והעברה בפונקציה הלניארית L והיא מוגדרת:

R_i(X)=\mbox{L}(S_{i\bmod 8}(X\oplus K_i))

ואילו בסבב האחרון מתבצע חיבור נוסף עם חלק המפתח המתאים במקום הפונקציה הלינארית:

R_{31}(X)=S_7(B_{31}\oplus K_{31})\oplus K_{32}.

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

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

תיבות ההחלפה של סרפנט הן תמורה של ארבע סיביות בעלת תכונות דיפרנציאליות ולינאריות המותאמות במיוחד כנגד ההתקפות הידועות. ערכי התיבות המקוריות (בגרסה Serpent-0) חושבו בתהליך הבא; תחילה נבנתה מטריצה בגודל 32 על 16 שבה הועתקו 32 השורות מתיבות ההחלפה של DES ואז בוצעו החלפות בין כניסות בשורה r לפי ערכים משורה r+1 ולפי מחרוזת קבועה המייצגת מפתח. אם התוצאה מפגינה תכונות לינאריות ודיפרנציאליות טובות, נשמרת כתיבת החלפה של סרפנט. על תהליך זה חוזרים מספר פעמים עד שמשלימים את כל התיבות. באופן פורמלי; תחילה מכינים מערך \mbox{serpent}[\cdot] המכיל את ארבעת הסיביות הנמוכות של כל האותיות במחרוזת "sboxesforserpent" ומערך דו ממדי \mbox{S}[\cdot][\cdot] בגודל 32x16 המכיל את 32 השורות של תיבות ההחלפה של DES כאשר \mbox{S}[r][\cdot] מייצג שורה r, המהלך מתואר בפסאודו קוד הבא:

  1. index=0
  2. \mbox{Repeat:}
c = index \ \bmod\ 32
\mbox{For }i = 0\mbox{ to }15\mbox{ do:}
j = \mbox{S}[(c + 1) \ \bmod\ 32][\mbox{serpent}[i]]
\mbox{SwapEntries(S}[c][i],\mbox{S}[c][j])
\mbox{If S}[c][\cdot]\mbox{ has the desired properties save it.}
index = index + 1
\mbox{Until 8 S-box have been generated.}

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

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

הווקטור B_i מחולק תחילה לארבע מילים בגודל 32 סיביות X_0,...,X_3 ואז מעורבב לינארית כדלהלן:

  1. X_0=X_0\lll 13
  2. X_2=X_2\lll 3
  3. X_1=X_1\oplus X_0\oplus X_2
  4. X_3=X_3\oplus X_2\oplus (X_0 \ll 3)
  5. X_1=X_1\lll 1
  6. X_3=X_3\lll 7
  7. X_0=X_0\oplus X_1\oplus X_3
  8. X_2=X_2\oplus X_3\oplus (X_1 \ll 7)
  9. X_0=X_0\lll 5
  10. X_2=X_2\lll 22

התוצאה מומרת לוקטור B_{i+1} שהוא הקלט לסבב הבא. הסמל "\lll" מייצג הזזה מעגלית (Rotate left) לפי מספר פוזיציות המופיע מימין לסימן. הסמל "\ll" מייצג אופרטור הזזה בסיביות (Shift left). והסימן \oplus הוא XOR. אפשר לראות שהטרנספורמציה המתוארת משיגה ערבוב גבוה בתוך מספר קצר של סבבים. סיבה נוספת לבחירה בטרנספורמציה זו, הפעולות המתוארות פשוטות ברמה כזו שביישום במעבד מודרני לא יווצרו בועות בצינור עיבוד הנתונים. ביישום מעשי מקודדים את הטרנספורמציה כטבלה קבועה.

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

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

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

כאמור הצופן זקוק ל-132 מילים של 'חומר-מפתח' כל אחת בגודל 32 סיביות. אם מפתח הצופן קטן מ-256 סיביות, תחילה מרפדים את המפתח בסיבית '1' ולאחריה אפסים לפי הצורך עד לקבלת מחרוזת של 256 סיביות. ואז מרחיבים אותו ל-33 תת-מפתחות בגודל 128 סיביות כדלהלן: משתמשים במערך עזר של שמונה מילים בגודל 32 סיביות w_{-8},...,w_{-1} אותו מרחיבים לפי הנוסחה:

w_i=(w_{i-8}\oplus w_{i-5}\oplus w_{i-3} \oplus w_{i-1} \oplus \phi \oplus i)\lll 11

כאשר i=0,...,132. הערך \phi=(\sqrt 5 +1)/2 מייצג את יחס הזהב או בהקסדצימלית 9E3779B9. שים לב שהפולינום ברקע x^8+x^7+x^5+x^3+1 פרימיטיבי. הפולינום יחד עם הזזה מעגלית לפי אינדקס הסבב, מבטיחים פיזור אחיד של סיביות המפתח כדי לסכל מפתחות הצפנה חלשים. שים לב שביישום מעשי במרבית שפות התכנות אין אינדקס שלילי במערך, אם מבצעים את הצופן בגרסה הרשמית והלא ממוטבת יש צורך לעקוף בעיה זו בדרך כלשהי. מפתחות הסבב מחושבים מתוך המערך w באופן כזה שכל ארבעה אלמנטים w_i,...,w_{i+4} מועברים בתיבות ההחלפה והתוצאה תהיה הכניסה הבאה של 128 סיביות של מפתח מורחב K_i. כגון:

\{k_0,k_1,k_2,k_3\}=S_3(w_0,w_1,w_2,w_3)

לאחר מכן הקבוצה 4-7, 8-11 וכן הלאה. כאשר תיבות ההחלפה נבחרות לפי הנוסחה (r + 3 - i)\mbox{ modulo }r ו-i=0,...,r. כאשר הצופן מיושם בשיטה הקונבנציונלית מחשבים בסוף כל סבב את התמורה K_i=\mbox{IP}(K_i).

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

בהגדרה המקורית של הצופן בהתחשב בעובדה שהוא מבוסס על התכונות הידועות של תיבות ההחלפה של DES ההתקפה הטובה ביותר האפשרית מוערכת יותר מ-2^{100}. בגרסה המשופרת Serpent-1 שהוצעה במהלך בחירת התקן תיבות ההחלפה החדשות הפגינו תכונות טובות יותר והערכת המפתחים היא שלא קיימת התקפה טובה יותר מחיפוש ממצה (ניסוי פענוח עם כל המפתחות האפשריים) ולכן ההתקפה הטובה ביותר האפשרית גם בניתוח דיפרנציאלי או לינארי תהיה בסיבוכיות של 2^k (k הוא גודל המפתח). במקרה של מפתח 256 סיביות כמות כזו של טקסטים פשוט לא קיימת. לכל מפתח נתון צפויים דיפרנציאלים בהסתברות 2^{-120}. נתון זה צפוי בכל המועמדים לתקן החדש. לא ידוע על התקפה יעילה יותר כנגד סרפנט וכן צריך לזכור שללא תלות בצופן שבשימוש, לא מומלץ להצפין עם אותו מפתח 2^{64} בלוקים. התקפה לינארית בגרסת 11 סבבים של הצופן אפשרית בסיבוכיות של 2^{118} בזמן של 2^{89}[3].

ב-2011 קריפטואנליזה של סרפנט במספר מצומצם של סבבים הראתה שאפשר לשבור את הצופן עם המפתח 128 ב-11 סבבים עם 2^{116} טקסטים ידועים ובזמן 2^{107.5} ו-2^{104} זיכרון‏[4]. ועם מפתח 256 ההתקפה הטובה ביותר על 12 סבבים הייתה של 2^{118} טקסטים ידועים 2^{228} זיכרון וזמן של 2^{228}. כזכור בצופן 32 סבבים.

יישום יעיל (Bit-slice)[עריכת קוד מקור | עריכה]

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

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


קישורים חיצוניים[עריכת קוד מקור | עריכה]


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