סרפנט

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

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

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

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

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

לטבלאות התמורה IP ו-FP אין חשיבות קריפטוגרפית והן קיימות רק לצורך אופטימיזציה (המרה לפורמט המאפשר יישום bitslice). לצורך תיאור הצופן, ערך הביניים לאחר כל סבב נקרא הווקטור ${\displaystyle B_{i}}$. הקלט לסבב הראשון הוא ${\displaystyle B_{1}}$ לשני ${\displaystyle B_{2}}$ וכן הלאה (המציין ${\displaystyle i}$ מתייחס למספר הסבב). הפעולה העיקרית המתרחשת בלב הצופן המסומנת ${\displaystyle R_{i}}$ משתמשת בכל סבב בתיבת החלפה אחת משמונה תיבות ההחלפה כשהיא מוכפלת 32 פעמים, כל עותק מחליף ארבע סיביות אחרות של הקלט ${\displaystyle B_{i}}$. בגרסה הממוטבת ההחלפה מתרחשת במקביל. כך יוצא שכל אחת מהתיבות מנוצלת ארבע פעמים במהלך ההצפנה. לאחר ההחלפה מתבצעת ההעתקה הליניארית.

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

למעט בסבב האחרון הטרנספורמציה ${\displaystyle R_{i}(X)}$ כוללת שילוב מפתח, החלפה בטבלה והעברה בפונקציה הלניארית ${\displaystyle L}$ והיא מוגדרת:

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

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

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

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

הווקטור ${\displaystyle B_{i}}$ מחולק תחילה לארבע מילים בגודל 32 סיביות ${\displaystyle X_{0},...,X_{3}}$ ואז מעורבב ליניארית כדלהלן:

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

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

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

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

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

${\displaystyle \{k_{0},k_{1},k_{2},k_{3}\}=S_{3}(w_{0},w_{1},w_{2},w_{3})}$

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

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

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

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

• DES
• AES

• אתר האינטרנט הרשמי של סרפנט
• אלי ביהם, Serpent - A New Block Cipher Proposal for AES