SOSEMANUK

SOSEMANUK הוא צופן זרם סינכרוני שפותח ב-2005 בתמיכת משרד החינוך הצרפתי ומשרדים אחרים, על ידי Côme Berbain ועמיתיו ואשר נבחר על ידי eSTREAM^[1] יחד עם שלושה אלגוריתמים נוספים כמועמד מועדף לתקן הצפנת זרם בפרופיל 1 (קטגוריית תוכנה). SOSEMANUK הוא שיפור של צופן הזרם SNOW ומבוסס גם על צופן בלוקים סרפנט. הצופן מקבל מפתח ההצפנה בטווח אורכים של 128-256 סיביות (הביטחון המושג הוא לכל היותר ברמה של 128 סיביות) וכן וקטור אתחול בגודל 128 סיביות ומפיק בכל צעד פלט של ארבע מילים של זרם מפתח (בסך הכול 128 סיביות), הצפנת טקסט-המקור מתבצעת ברמת מילים, ארבע מילים בכל פעימה, באמצעות חיבור XOR עם זרם הפתח. SOSEMANUK בטוח יותר ובעל ביצועים טובים יותר מ-SNOW 2.0, במיוחד שלב הכנת וקטור האתחול מהיר יותר ומצבו הפנימי (internal state) מצומצם בגודלו בסך הכול 384 סיביות, מה שמאפשר ביצועים טובים יותר.

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

סרפנט

ערך מורחב – סרפנט (צופן)

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

Serpent1 מתאר סבב אחד של סרפנט ממנו הופשטו שלב הוספת המפתח והטרנספורמציה הליניארית והוא כולל רק את תיבת ההחלפה (S-box) השלישית. הפונקציה Serpent1 מקבלת רביעייה של מילים בגודל 32 סיביות ומחזירה פלט של ארבע מילים בגודל זהה לאחר ערבוב עם תיבת ההחלפה במצב bitslice (ראה צופן סרפנט). התפקיד של Serpent1 הוא לשמש כפונקציה אי-ליניארית על ערכי הביניים של המצב הפנימי.

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

${\displaystyle R_{23}(X)=L(S_{23}(X\oplus K_{23}))\oplus K_{24}}$

ולמעשה משתמש רק ב-25 תת-מפתחות ${\displaystyle K_{0},...,K_{24}}$ הנוצרים בתהליך הרחבת המפתח של צופן סרפנט. הפונקציה Serpent24 נדרשת רק לצורך שלב האתחול והכנת המפתח של SOSEMANUK (להלן).

תיאור האלגוריתם

תיאור כללי של צופן SOSEMANUK, הסמלים ${\displaystyle \odot }$ ו-${\displaystyle \boxplus }$ מייצגים כפל וחיבור אלמנטים בשדה ${\displaystyle \mathbb {F} _{2^{8}}}$.

המצב הפנימי (internal state) של צופן הזרם SOSEMANUK מנוהל על ידי אוגר זיזה המכיל עשרה אלמנטים בגודל 32 סיביות ואוטומט סופי המכיל זיכרון בגודל שתי מילים. בסך הכול 12 מילים. להלן תיאור רכיבי הצופן.

LFSR

הצופן כולל אוגר זיזה יחיד מסוג LFSR המכיל עשרה אלמנטים מהשדה המורחב ${\displaystyle F_{2^{32}}}$. כל אלמנט מיוצג על ידי הווקטור ${\displaystyle (\alpha ^{3},\alpha ^{2},\alpha ,1)}$ כאשר ${\displaystyle \alpha }$ הוא אלמנט מהשדה ${\displaystyle F_{2^{8}}}$ בגודל בית אחד. כאשר השדה ${\displaystyle F_{2^{8}}}$ מוגדר על ידי הפולינום הפרימיטיבי ${\displaystyle q(x)=x^{8}+x^{7}+x^{5}+x^{3}+1}$. פעולות חיבור וכפל סגורות מודולו 256. הייצוג המקובל הוא הקסדצימלי למשל האלמנט ${\displaystyle \beta ^{23}}$ מיוצג על ידי "${\displaystyle {\text{0xE1}}}$". האלמנטים של השדה ${\displaystyle F_{2^{32}}}$ נוצרים על ידי הפולינום הפרימיטיבי:

${\displaystyle p(x)=x^{4}+\beta ^{23}x^{3}+\beta ^{245}x^{2}+\beta ^{48}x+\beta ^{239}}$

וכל אלמנט ${\displaystyle y\in F_{2^{32}}}$ מזוהה על ידי ${\displaystyle \textstyle \sum _{i=0}^{3}y_{i}\alpha ^{i}}$. היתרון של מבנה זה ברור, פעולת חיבור בין שני אלמנטים בשדה היא בעצם XOR (המסומן כאן בקיצור ${\displaystyle \oplus }$) שהיא פעולה מהירה במונחי מחשוב ופעולות כפל וחילוק מתורגמות להזזות (shift) בסיביות. כלומר כפל ב-${\displaystyle \alpha }$ הוא הזזה לשמאל של סיביות האופרנד 8 פוזיציות ולאחריה חיסור מותנה (חיבור וחיסור זהים בשדה זה) שהוא בעצם פעולת XOR עם הפולינום הקבוע ${\displaystyle p(x)}$, רק אם הסיבית העליונה שנפלטת כתוצאה מההזזה היא '1'. חילוק מתבצע בדרך דומה, ההזזה היא לימין במקום לשמאל ומשתמשים בקבוע אחר (ההופכי של ${\displaystyle p(x)}$) לחילוק אם וכאשר הסיבית התחתונה (שנפלטה) היא '1'. בדרך זו אפשר לבצע ביעילות כפל בכל חזקה של ${\displaystyle \alpha }$ על ידי איטרציה.

מעשית מאיצים את פעולות הכפל והחילוק ב-${\displaystyle \alpha }$ על ידי שימוש בטבלאות חיפוש table lookup המקודדות מראש. לדוגמה אם נתונות טבלאות ${\displaystyle T_{1},T_{2}}$ המכילות את כל 256 האפשרויות של בית אחד עבור כפל וחילוק בהתאמה, הכפל יהיה ${\displaystyle \alpha \cdot x=(x\ll 8)\oplus T_{1}[x\gg 24]}$ והחילוק הוא ${\displaystyle \alpha ^{-1}\cdot x=(x\gg 8)\oplus T_{2}[1^{st}{\text{ byte of }}x]}$

בכל מחזור זמן, מחושב ערך חדש מהאלמנטים ${\displaystyle s_{1},...,s_{10}}$ של LFSR לפי נוסחת הנסיגה ${\displaystyle s_{t+10}=s_{t+9}\oplus \alpha ^{-1}s_{t+3}\oplus \alpha s_{t}}$ עבור ${\displaystyle t>0}$ ותכולת האוגר כולו מוזזת (shift). מעשית פעולת ההזזה מתבצעת בשיטת חלון על ידי ניהול מצביעים במקום העתקה פיזית של כל ערכי התאים.

הפולינום ${\displaystyle \pi (x)=\alpha x^{10}+\alpha ^{-1}x^{7}+x+1}$ הוא פונקציית ההיזון של ה-LFSR. כיוון ש-${\displaystyle \pi (x)}$ פרימיטיבי מחזוריות האוגר מקסימלית והיא ${\displaystyle 2^{320}-1}$.

אוטומט סופי

הצופן כולל אוטומט סופי בקיצור FSM שהוא רכיב המכיל זיכרון פנימי בגודל 64 סיביות המחולק לשני אוגרים ${\displaystyle R_{1},R_{2}}$. ובכל צעד מקבל את המילים 1, 8 ו-9 מאוגר ה-LSFR, מעדכן את הזיכרון הפנימי ומחזיר מילה אחת:

${\displaystyle {\boldsymbol {\mathbf {FSM} _{t}:(R1_{t-1},R2_{t-1},s_{t+1},s_{t+8}s_{t+9})\mapsto (R1_{t},R2_{t},f_{t})}}}$

1. ${\displaystyle R1_{t}=(R2_{t-1}+{\text{mux}}({\text{lsb}}(R1_{t-1}),s_{t+1},s_{t+1}\oplus s_{t+8})){\text{ mod }}2^{32}}$
2. ${\displaystyle R2_{t}={\text{Trans}}(R1_{t-1})}$
3. ${\displaystyle f_{t}=(s_{t+9}+R1_{t}{\text{ mod }}2^{32})\oplus R2_{t}}$

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

${\displaystyle {\text{Trans}}(z)=(M\times z{\text{ mod }}2^{32})\lll 7}$.

הפונקציה ${\displaystyle {\text{lsb}}(x)}$ היא הסיבית הפחות משמעותית של ${\displaystyle x}$. הפונקציה ${\displaystyle {\text{mux}}(c,x,y)}$ שווה ל-${\displaystyle x}$ אם ${\displaystyle c=0}$ או ל-${\displaystyle y}$ אם ${\displaystyle c=1}$. הקבוע ${\displaystyle M}$ הוא ${\displaystyle {\text{0x54655307}}}$ (ייצוג הקסדצימלי של עשר הספרות הראשונות של פאי). הסימן ${\displaystyle \lll 7}$ מייצג הזזה מעגלית של מילה בגודל 32 סיביות בשבע סיביות.

המצב הפנימי

הפלט של האוטומט FSM ופלט האוגר LFSR משמשים יחד לעדכון המצב הפנימי. בכל מחזור זמן ${\displaystyle t}$ תוצאות אוגר הזיזה (LFSR) והאוטומט (FSM) נאספות בחוצץ פנימי ומשולבות יחד כדי לייצר פלט ${\displaystyle z_{i}}$ של המצב הפנימי. כאשר ${\displaystyle t=0}$ זהו המצב הראשוני של הצופן והפלט הראשון שלו הוא ${\displaystyle z_{1}}$. בכל מחזור זמן ${\displaystyle t\geq 1}$ הפעולות הבאות מתבצעות:

• FSM מתעדכן: האוגרים ${\displaystyle R1_{t},R2_{t}}$ וערך הביניים ${\displaystyle f_{t}}$ מחושבים לפי ${\displaystyle R1_{t-1},R2_{t-1},s_{t+1},s_{t+8},s_{t+9}}$. הערך ${\displaystyle f_{t}}$ מאוחסן בחוצץ הפנימי.
• LFSR מתעדכן: ${\displaystyle s_{t+10}}$ מחושב מהערכים ${\displaystyle s_{t},s_{t+3},s_{t+9}}$. הערך ${\displaystyle s_{t}}$ מהווה חלק מפלט האוגר ומאוחסן בחוצץ פנימי ותכולת האוגר מוזזת.

ואחת לארבעה מחזורי זמן מופקים ארבעה ערכי פלט ${\displaystyle z_{t},z_{t+1},z_{t+2}}$ ו-${\displaystyle z_{t+3}}$ המחושבים מערכי הביניים שנאספו ${\displaystyle f_{t},f_{t+1},f_{t+2}}$ ו-${\displaystyle f_{t+3}}$ ופלטי האוגר ${\displaystyle s_{t},s_{t+1},s_{t+2}}$ ו-${\displaystyle s_{t+3}}$.

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

${\displaystyle (z_{t+3},z_{t+2},z_{t+1},z_{t})={\text{Serpent1}}(f_{t+3},f_{t+2},f_{t+1},f_{t})\oplus (s_{t+3},s_{t+2},s_{t+1},s_{t})}$

כאשר ${\displaystyle f_{i}}$ הם פלט האוטומט ו-${\displaystyle s_{i}}$ הם פלט האוגר. המצב הפנימי בזמן ${\displaystyle t+4}$ הוא ${\displaystyle (z_{t+3},z_{t+2},z_{t+1},z_{t})}$.

הכנת מפתח והוספת וקטור האתחול

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

לאחר הכנת המפתח המורחב הפרוצדורה Serpent24 משמשת כרגיל כצופן בלוקים להצפנת וקטור האתחול המסופק על ידי המשתמש. מתוך 24 הסבבים של הפרוצדורה רק פלט הסבבים 12, 18 ו-24 מנוצלים. כל אחד מהם בגודל ארבע מילים. כאשר בסבב ה-24 הפלט הוא רק לאחר XOR עם תת-מפתח סרפנט ה-25. לצורך המחשה פלט סבב 12 מסומן בקיצור ${\displaystyle Y_{3}^{12},Y_{2}^{12},Y_{1}^{12},Y_{0}^{12}}$ וכן לגבי היתר. בסך הכול 12 מילים המשמשים לאתחול המצב הפנימי של SOSEMANUK כדלהלן:

${\displaystyle (s_{7},s_{8},s_{9},s_{10})=(Y_{3}^{12},Y_{2}^{12},Y_{1}^{12},Y_{0}^{12})}$

${\displaystyle (s_{5},s_{6})=(Y_{1}^{18},Y_{3}^{18})}$

${\displaystyle (s_{1},s_{2},s_{3},s_{4})=(Y_{3}^{24},Y_{2}^{24},Y_{1}^{24},Y_{0}^{24})}$

${\displaystyle R1_{0}=Y_{0}^{18}}$

${\displaystyle R2_{0}=Y_{2}^{18}}$

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

• בצעד הראשון ${\displaystyle R1_{1},R2_{1}}$ ו-${\displaystyle f_{1}}$ מחושבים מהערכים ההתחלתיים ${\displaystyle R1_{0},R2_{0},s_{2},s_{9}}$ ו-${\displaystyle s_{10}}$.
• ערכי הביניים ${\displaystyle s_{1},f_{1}}$ מאוחסנים בחוצץ הפנימי.
• המילה ${\displaystyle s_{11}}$ מחושבת על ידי פונקציית ההיזון מהאלמנטים ${\displaystyle s_{10},s_{4}}$ ו-${\displaystyle s_{1}}$ והמצב הפנימי של האוגר מתעדכן למצב חדש ${\displaystyle s_{2}}$ עד ${\displaystyle s_{11}}$.
• האוטומט FSM והאוגר LFSR מופעלים שלוש פעמים נוספות עד שמצטברים בחוצץ הפנימי שמונת ערכי הביניים הראשונים ${\displaystyle f_{1},f_{2},f_{3},f_{4}}$ וכן ${\displaystyle s_{1},s_{2},s_{3},s_{4}}$.
• ארבעת הפלטים הראשונים של הצופן ${\displaystyle z_{1},z_{2},z_{3}}$ ו-${\displaystyle z_{4}}$ מועברים פעם אחת ב-Serpent1 והפלט מחובר ב-XOR עם ${\displaystyle s_{4},s_{3},s_{2},s_{1}}$ בהתאמה, לקבלת הפלט הסופי.

תיבות החלפה

תיבות ההחלפה של SOSEMANUK הן שמונה תיבות ההחלפה של סרפנט, ${\displaystyle 4\times 16}$ סיביות כל אחת, המוגדרות כתמורה מעל ${\displaystyle Z_{16}}$:

      0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
S0 : 03, 08, 15, 01, 10, 06, 05, 11, 14, 13, 04, 02, 07, 00, 09, 12
S1 : 15, 12, 02, 07, 09, 00, 05, 10, 01, 11, 14, 08, 06, 13, 03, 04
S2 : 08, 06, 07, 09, 03, 12, 10, 15, 13, 01, 14, 04, 00, 11, 05, 02
S3 : 00, 15, 11, 08, 12, 09, 06, 03, 13, 01, 02, 04, 10, 07, 05, 14
S4 : 01, 15, 08, 03, 12, 00, 11, 06, 02, 05, 04, 10, 09, 14, 07, 13
S5 : 15, 05, 02, 11, 04, 10, 09, 12, 00, 03, 14, 08, 13, 06, 07, 01
S6 : 07, 02, 12, 05, 08, 04, 06, 11, 14, 09, 01, 15, 13, 03, 10, 00
S7 : 01, 13, 15, 00, 14, 08, 02, 11, 07, 04, 12, 10, 09, 03, 05, 06

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

פונקציה ליניארית

הפונקציה הליניארית פועלת על ארבע מילים באורך 32 סיביות כל אחת המסומנות ${\displaystyle X_{0},X_{1},X_{2},X_{3}}$ כאשר ${\displaystyle X_{0}}$ היא המילה הפחות משמעותית (LSW) והיא מוגדרת כך:

${\displaystyle X_{0}=X_{0}\lll 13,X_{2}=X_{2}\lll 3}$

${\displaystyle X_{1}=X_{1}\oplus X_{0}\oplus X_{2}}$

${\displaystyle X_{3}=X_{3}\oplus X_{2}\oplus (X_{0}\lll 3)}$

${\displaystyle X_{1}=X_{1}\lll 1,X_{3}=X_{3}\lll 7}$

${\displaystyle X_{0}=X_{0}\oplus X_{1}\oplus X_{3}}$

${\displaystyle X_{2}=X_{2}\oplus X_{3}\oplus (X_{1}\lll 7)}$

${\displaystyle X_{0}=X_{0}\lll 5,X_{2}=X_{2}\lll 22}$

ביטחון ויעילות

לפי תקן eSTREAM הצופן הוכרז בטוח לשימוש נכון לשנת 2008. SOSEMANUK נבדק היטב על ידי קריפטוגרפים רבים, לא ידוע על התקפות יעילות כנגד הצופן ולהערכת המפתחים ביטחונו הוא ${\displaystyle 2^{128}}$. ב-2006^[2] פותחה התקפה שנקראת Guess-and-determine כנגד הצופן שבה אפשר לשחזר את מצבו הפנימי המלא של הצופן לאחר האתחול, בסך הכול 384 סיביות בסיבוכיות זמן של ${\displaystyle 2^{224}}$. צריך לזכור שגם ניחוש מצבו הפנימי של הצופן אינו חושף את מפתח ההצפנה כיוון שלשם כך צריך לפרוץ גם את Serpent24 שמהווה חלק מהכנת המפתח. ב-ASIACRYPT-2008^[3] הוצגה התקפה כנגד SOSEMANUK שבעזרתה אפשר לשבור את הצופן על ידי שחזור המצב הפנימי בזמן של ${\displaystyle 2^{148}}$ ולאחר מכן הוצג שיפור^[4] של אותה התקפה בפקטור של ${\displaystyle 2^{10}}$. התקפה חדשה שפורסמה ב-2010^[5] שהיא סוג של Guess-and-determine דהיינו ניחוש המצב הפנימי של הצופן מגיעה לזמן של ${\displaystyle 2^{176}}$.

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

קוד לדוגמה

להלן קוד ב-C++‎ של צופן SOSEMANUK לפי המלצת התקן. הקוד עושה שימוש בתיבות החלפה ממוטבות חלקית לפי שיטת Bitslice.

#define rotl(x,n) (((x) << (n)) | ((x) >> (32 - (n))))
typedef struct
{
  unsigned int r[2];
  unsigned int s[10];
  unsigned char t;
} sosemanuk_state;

typedef struct
{
  unsigned int k[100];
} sosemanuk_master_state;

//Partially optimized Serpent S Box in Bitslice mode
#define sb0(a,b,c,d,e,f,g,h)	\
	t1 = a ^ d;		t2 = a & d;		t3 = c ^ t1;	t4 = b ^ t3;	\
	h = t2 ^ t4;	t6 = b & t1;	t7 = a ^ t6;	t8 = c | t7;	\
	g = t4 ^ t8;	t10 = ~t3;		t11 = t3 ^ t7;	t12 = h & t11;	\
	f = t10 ^ t12;	t14 = ~t7;		e = t12 ^ t14

#define sb1(a,b,c,d,e,f,g,h)	\
	t1 = ~a;		t2 = b ^ t1;	t3 = a | t2;	t4 = d | t2;	\
	t5 = c ^ t3;	g = d ^ t5;		t7 = b ^ t4;	t8 = t2 ^ g;	\
	t9 = t5 & t7;	h = t8 ^ t9;	t11 = t5 ^ t7;	f = h ^ t11;	\
	t13 = t8 & t11;	e = t5 ^ t13

#define sb2(a,b,c,d,e,f,g,h)	\
    t1 = ~a;		t2 = b ^ d;     t3 = c & t1;    e = t2 ^ t3;    \
    t5 = c ^ t1;    t6 = c ^ e;     t7 = b & t6;    h = t5 ^ t7;    \
    t9 = d | t7;    t10 = e | t5;   t11 = t9 & t10;	g = a ^ t11;    \
    t13 = d | t1;   t14 = t2 ^ h;   t15 = g ^ t13;  f = t14 ^ t15

#define sb3(a,b,c,d,e,f,g,h)	\
	t1 = a ^ b;		t2 = a & c;		t3 = a | d;		t4 = c ^ d;		\
	t5 = t1 & t3;	t6 = t2 | t5;	g = t4 ^ t6;	t8 = b ^ t3;	\
	t9 = t6 ^ t8;	t10 = t4 & t9;	e = t1 ^ t10;	t12 = g & e;	\
	f = t9 ^ t12;	t14 = b | d;	t15 = t4 ^ t12;	h = t14 ^ t15

#define sb4(a,b,c,d,e,f,g,h)	\
	t1 = a ^ d;		t2 = d & t1;	t3 = c ^ t2;	t4 = b | t3;	\
	h = t1 ^ t4;	t6 = ~b;		t7 = t1 | t6;	e = t3 ^ t7;	\
	t9 = a & e;		t10 = t1 ^ t6;	t11 = t4 & t10;	g = t9 ^ t11;	\
	t13 = a ^ t3;	t14 = t10 & g;	f = t13 ^ t14

#define sb5(a,b,c,d,e,f,g,h)	\
	t1 = ~a;		t2 = a ^ b;		t3 = a ^ d;		t4 = c ^ t1;	\
	t5 = t2 | t3;	e = t4 ^ t5;	t7 = d & e;		t8 = t2 ^ e;	\
	f = t7 ^ t8;	t10 = t1 | e;	t11 = t2 | t7;	t12 = t3 ^ t10;	\
	g = t11 ^ t12;	t14 = b ^ t7;	t15 = f & t12;	h = t14 ^ t15

#define sb6(a,b,c,d,e,f,g,h)	\
	t1 = ~a;		t2 = a ^ d;		t3 = b ^ t2;	t4 = t1 | t2;	\
	t5 = c ^ t4;	f = b ^ t5;		t7 = t2 | f;	t8 = d ^ t7;	\
	t9 = t5 & t8;	g = t3 ^ t9;	t11 = t5 ^ t8;	e = g ^ t11;	\
	t13 = ~t5;		t14 = t3 & t11;	h = t13 ^ t14

#define sb7(a,b,c,d,e,f,g,h)	\
	t1 = b ^ c;		t2 = c & t1;	t3 = d ^ t2;	t4 = a ^ t3;	\
	t5 = d | t1;	t6 = t4 & t5;	f = b ^ t6;		t8 = t3 | f;	\
	t9 = a & t4;	h = t1 ^ t9;	t11 = t4 ^ t8;	t12 = h & t11;	\
	g = t3 ^ t12;	t14 = ~t11;		t15 = h & g;	e = t14 ^ t15

// Multiplication by alpha: alpha * x = T32(x << 8) ^ mul_a[x >> 24]
static unsigned int mul_a[] = {
  0x00000000, 0xE19FCF13, 0x6B973726, 0x8A08F835, 0xD6876E4C, 0x3718A15F, 0xBD10596A, 0x5C8F9679,
  0x05A7DC98, 0xE438138B, 0x6E30EBBE, 0x8FAF24AD, 0xD320B2D4, 0x32BF7DC7, 0xB8B785F2, 0x59284AE1,
  0x0AE71199, 0xEB78DE8A, 0x617026BF, 0x80EFE9AC, 0xDC607FD5, 0x3DFFB0C6, 0xB7F748F3, 0x566887E0,
  0x0F40CD01, 0xEEDF0212, 0x64D7FA27, 0x85483534, 0xD9C7A34D, 0x38586C5E, 0xB250946B, 0x53CF5B78,
  0x1467229B, 0xF5F8ED88, 0x7FF015BD, 0x9E6FDAAE, 0xC2E04CD7, 0x237F83C4, 0xA9777BF1, 0x48E8B4E2,
  0x11C0FE03, 0xF05F3110, 0x7A57C925, 0x9BC80636, 0xC747904F, 0x26D85F5C, 0xACD0A769, 0x4D4F687A,
  0x1E803302, 0xFF1FFC11, 0x75170424, 0x9488CB37, 0xC8075D4E, 0x2998925D, 0xA3906A68, 0x420FA57B,
  0x1B27EF9A, 0xFAB82089, 0x70B0D8BC, 0x912F17AF, 0xCDA081D6, 0x2C3F4EC5, 0xA637B6F0, 0x47A879E3,
  0x28CE449F, 0xC9518B8C, 0x435973B9, 0xA2C6BCAA, 0xFE492AD3, 0x1FD6E5C0, 0x95DE1DF5, 0x7441D2E6,
  0x2D699807, 0xCCF65714, 0x46FEAF21, 0xA7616032, 0xFBEEF64B, 0x1A713958, 0x9079C16D, 0x71E60E7E,
  0x22295506, 0xC3B69A15, 0x49BE6220, 0xA821AD33, 0xF4AE3B4A, 0x1531F459, 0x9F390C6C, 0x7EA6C37F,
  0x278E899E, 0xC611468D, 0x4C19BEB8, 0xAD8671AB, 0xF109E7D2, 0x109628C1, 0x9A9ED0F4, 0x7B011FE7,
  0x3CA96604, 0xDD36A917, 0x573E5122, 0xB6A19E31, 0xEA2E0848, 0x0BB1C75B, 0x81B93F6E, 0x6026F07D,
  0x390EBA9C, 0xD891758F, 0x52998DBA, 0xB30642A9, 0xEF89D4D0, 0x0E161BC3, 0x841EE3F6, 0x65812CE5,
  0x364E779D, 0xD7D1B88E, 0x5DD940BB, 0xBC468FA8, 0xE0C919D1, 0x0156D6C2, 0x8B5E2EF7, 0x6AC1E1E4,
  0x33E9AB05, 0xD2766416, 0x587E9C23, 0xB9E15330, 0xE56EC549, 0x04F10A5A, 0x8EF9F26F, 0x6F663D7C,
  0x50358897, 0xB1AA4784, 0x3BA2BFB1, 0xDA3D70A2, 0x86B2E6DB, 0x672D29C8, 0xED25D1FD, 0x0CBA1EEE,
  0x5592540F, 0xB40D9B1C, 0x3E056329, 0xDF9AAC3A, 0x83153A43, 0x628AF550, 0xE8820D65, 0x091DC276,
  0x5AD2990E, 0xBB4D561D, 0x3145AE28, 0xD0DA613B, 0x8C55F742, 0x6DCA3851, 0xE7C2C064, 0x065D0F77,
  0x5F754596, 0xBEEA8A85, 0x34E272B0, 0xD57DBDA3, 0x89F22BDA, 0x686DE4C9, 0xE2651CFC, 0x03FAD3EF,
  0x4452AA0C, 0xA5CD651F, 0x2FC59D2A, 0xCE5A5239, 0x92D5C440, 0x734A0B53, 0xF942F366, 0x18DD3C75,
  0x41F57694, 0xA06AB987, 0x2A6241B2, 0xCBFD8EA1, 0x977218D8, 0x76EDD7CB, 0xFCE52FFE, 0x1D7AE0ED,
  0x4EB5BB95, 0xAF2A7486, 0x25228CB3, 0xC4BD43A0, 0x9832D5D9, 0x79AD1ACA, 0xF3A5E2FF, 0x123A2DEC,
  0x4B12670D, 0xAA8DA81E, 0x2085502B, 0xC11A9F38, 0x9D950941, 0x7C0AC652, 0xF6023E67, 0x179DF174,
  0x78FBCC08, 0x9964031B, 0x136CFB2E, 0xF2F3343D, 0xAE7CA244, 0x4FE36D57, 0xC5EB9562, 0x24745A71,
  0x7D5C1090, 0x9CC3DF83, 0x16CB27B6, 0xF754E8A5, 0xABDB7EDC, 0x4A44B1CF, 0xC04C49FA, 0x21D386E9,
  0x721CDD91, 0x93831282, 0x198BEAB7, 0xF81425A4, 0xA49BB3DD, 0x45047CCE, 0xCF0C84FB, 0x2E934BE8,
  0x77BB0109, 0x9624CE1A, 0x1C2C362F, 0xFDB3F93C, 0xA13C6F45, 0x40A3A056, 0xCAAB5863, 0x2B349770,
  0x6C9CEE93, 0x8D032180, 0x070BD9B5, 0xE69416A6, 0xBA1B80DF, 0x5B844FCC, 0xD18CB7F9, 0x301378EA,
  0x693B320B, 0x88A4FD18, 0x02AC052D, 0xE333CA3E, 0xBFBC5C47, 0x5E239354, 0xD42B6B61, 0x35B4A472,
  0x667BFF0A, 0x87E43019, 0x0DECC82C, 0xEC73073F, 0xB0FC9146, 0x51635E55, 0xDB6BA660, 0x3AF46973,
  0x63DC2392, 0x8243EC81, 0x084B14B4, 0xE9D4DBA7, 0xB55B4DDE, 0x54C482CD, 0xDECC7AF8, 0x3F53B5EB
};

// Division by alpha: x / alpha = (x >> 8) ^ div_a[x & 0xFF] 
static unsigned int div_a[] = {
  0x00000000, 0x180F40CD, 0x301E8033, 0x2811C0FE, 0x603CA966, 0x7833E9AB, 0x50222955, 0x482D6998,
  0xC078FBCC, 0xD877BB01, 0xF0667BFF, 0xE8693B32, 0xA04452AA, 0xB84B1267, 0x905AD299, 0x88559254,
  0x29F05F31, 0x31FF1FFC, 0x19EEDF02, 0x01E19FCF, 0x49CCF657, 0x51C3B69A, 0x79D27664, 0x61DD36A9,
  0xE988A4FD, 0xF187E430, 0xD99624CE, 0xC1996403, 0x89B40D9B, 0x91BB4D56, 0xB9AA8DA8, 0xA1A5CD65,
  0x5249BE62, 0x4A46FEAF, 0x62573E51, 0x7A587E9C, 0x32751704, 0x2A7A57C9, 0x026B9737, 0x1A64D7FA,
  0x923145AE, 0x8A3E0563, 0xA22FC59D, 0xBA208550, 0xF20DECC8, 0xEA02AC05, 0xC2136CFB, 0xDA1C2C36,
  0x7BB9E153, 0x63B6A19E, 0x4BA76160, 0x53A821AD, 0x1B854835, 0x038A08F8, 0x2B9BC806, 0x339488CB,
  0xBBC11A9F, 0xA3CE5A52, 0x8BDF9AAC, 0x93D0DA61, 0xDBFDB3F9, 0xC3F2F334, 0xEBE333CA, 0xF3EC7307,
  0xA492D5C4, 0xBC9D9509, 0x948C55F7, 0x8C83153A, 0xC4AE7CA2, 0xDCA13C6F, 0xF4B0FC91, 0xECBFBC5C,
  0x64EA2E08, 0x7CE56EC5, 0x54F4AE3B, 0x4CFBEEF6, 0x04D6876E, 0x1CD9C7A3, 0x34C8075D, 0x2CC74790,
  0x8D628AF5, 0x956DCA38, 0xBD7C0AC6, 0xA5734A0B, 0xED5E2393, 0xF551635E, 0xDD40A3A0, 0xC54FE36D,
  0x4D1A7139, 0x551531F4, 0x7D04F10A, 0x650BB1C7, 0x2D26D85F, 0x35299892, 0x1D38586C, 0x053718A1,
  0xF6DB6BA6, 0xEED42B6B, 0xC6C5EB95, 0xDECAAB58, 0x96E7C2C0, 0x8EE8820D, 0xA6F942F3, 0xBEF6023E,
  0x36A3906A, 0x2EACD0A7, 0x06BD1059, 0x1EB25094, 0x569F390C, 0x4E9079C1, 0x6681B93F, 0x7E8EF9F2,
  0xDF2B3497, 0xC724745A, 0xEF35B4A4, 0xF73AF469, 0xBF179DF1, 0xA718DD3C, 0x8F091DC2, 0x97065D0F,
  0x1F53CF5B, 0x075C8F96, 0x2F4D4F68, 0x37420FA5, 0x7F6F663D, 0x676026F0, 0x4F71E60E, 0x577EA6C3,
  0xE18D0321, 0xF98243EC, 0xD1938312, 0xC99CC3DF, 0x81B1AA47, 0x99BEEA8A, 0xB1AF2A74, 0xA9A06AB9,
  0x21F5F8ED, 0x39FAB820, 0x11EB78DE, 0x09E43813, 0x41C9518B, 0x59C61146, 0x71D7D1B8, 0x69D89175,
  0xC87D5C10, 0xD0721CDD, 0xF863DC23, 0xE06C9CEE, 0xA841F576, 0xB04EB5BB, 0x985F7545, 0x80503588,
  0x0805A7DC, 0x100AE711, 0x381B27EF, 0x20146722, 0x68390EBA, 0x70364E77, 0x58278E89, 0x4028CE44,
  0xB3C4BD43, 0xABCBFD8E, 0x83DA3D70, 0x9BD57DBD, 0xD3F81425, 0xCBF754E8, 0xE3E69416, 0xFBE9D4DB,
  0x73BC468F, 0x6BB30642, 0x43A2C6BC, 0x5BAD8671, 0x1380EFE9, 0x0B8FAF24, 0x239E6FDA, 0x3B912F17,
  0x9A34E272, 0x823BA2BF, 0xAA2A6241, 0xB225228C, 0xFA084B14, 0xE2070BD9, 0xCA16CB27, 0xD2198BEA,
  0x5A4C19BE, 0x42435973, 0x6A52998D, 0x725DD940, 0x3A70B0D8, 0x227FF015, 0x0A6E30EB, 0x12617026,
  0x451FD6E5, 0x5D109628, 0x750156D6, 0x6D0E161B, 0x25237F83, 0x3D2C3F4E, 0x153DFFB0, 0x0D32BF7D,
  0x85672D29, 0x9D686DE4, 0xB579AD1A, 0xAD76EDD7, 0xE55B844F, 0xFD54C482, 0xD545047C, 0xCD4A44B1,
  0x6CEF89D4, 0x74E0C919, 0x5CF109E7, 0x44FE492A, 0x0CD320B2, 0x14DC607F, 0x3CCDA081, 0x24C2E04C,
  0xAC977218, 0xB49832D5, 0x9C89F22B, 0x8486B2E6, 0xCCABDB7E, 0xD4A49BB3, 0xFCB55B4D, 0xE4BA1B80,
  0x17566887, 0x0F59284A, 0x2748E8B4, 0x3F47A879, 0x776AC1E1, 0x6F65812C, 0x477441D2, 0x5F7B011F,
  0xD72E934B, 0xCF21D386, 0xE7301378, 0xFF3F53B5, 0xB7123A2D, 0xAF1D7AE0, 0x870CBA1E, 0x9F03FAD3,
  0x3EA637B6, 0x26A9777B, 0x0EB8B785, 0x16B7F748, 0x5E9A9ED0, 0x4695DE1D, 0x6E841EE3, 0x768B5E2E,
  0xFEDECC7A, 0xE6D18CB7, 0xCEC04C49, 0xD6CF0C84, 0x9EE2651C, 0x86ED25D1, 0xAEFCE52F, 0xB6F3A5E2
};

static unsigned int automaton_step(sosemanuk_state *state)
{
  unsigned int *r = state->r;
  unsigned int *s = state->s;
  unsigned int r0_prev = r[0];
  unsigned char t = state->t;

  r[0] = r[1] + ((r0_prev & 1u) ? s[(t+1)%10] ^ s[(t+8)%10] : s[(t+1)%10]);
  r[1] = rotl(r0_prev * 0x54655307, 7);

  return (s[(t+9)%10] + r[0]) ^ r[1];
}

static unsigned int lfsr_step(sosemanuk_state *state)
{
  unsigned int *s = state->s;
  unsigned char t = state->t;

  unsigned int st0 = s[t];
  unsigned int st3 = s[(t+3)%10];

  s[t] = s[(t+9)%10] ^ (st3 >> 8) ^ div_a[st3 & 0xff] ^ (st0 << 8) ^ mul_a[st0 >> 24];

  state->t = (t+1) % 10;
  return st0;
}

static inline void sbox_apply(unsigned char sbox_idx, unsigned int *in, unsigned int *out)
{
  register unsigned int t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11, t12, t13, t14, t15;
  switch(sbox_idx) 
    {
    case 0: sb0(in[0], in[1], in[2], in[3], out[0], out[1], out[2], out[3]); break;
    case 1: sb1(in[0], in[1], in[2], in[3], out[0], out[1], out[2], out[3]); break;
    case 2:	sb2(in[0], in[1], in[2], in[3], out[0], out[1], out[2], out[3]); break;
    case 3: sb3(in[0], in[1], in[2], in[3], out[0], out[1], out[2], out[3]); break;
    case 4:	sb4(in[0], in[1], in[2], in[3], out[0], out[1], out[2], out[3]); break;
    case 5:	sb5(in[0], in[1], in[2], in[3], out[0], out[1], out[2], out[3]); break;
    case 6:	sb6(in[0], in[1], in[2], in[3], out[0], out[1], out[2], out[3]); break;
    case 7:	sb7(in[0], in[1], in[2], in[3], out[0], out[1], out[2], out[3]); break;
    }
}

void sosemanuk_init_key(sosemanuk_master_state *state, const unsigned char *key, size_t bitlength)
{
  unsigned int w[108];

  unsigned int i;
  int fullwords = bitlength / 32;
  for(i = 0; i < fullwords; ++i)
     w[i] = *((unsigned int*)(key + (i*4)));

  int partial = bitlength % 32;
  if(partial)
    {
      unsigned int tmp = 0;

      int j;
      int fullbytes = partial / 8;
      for(j = 0; j < fullbytes; ++j)
	     tmp |= (unsigned int)key[i*4 + j] << (j*8);

      int bitpartial = partial % 8;
      if(bitpartial)
	  {
	     unsigned char extra_bit = 1u << bitpartial;
	     tmp |= (unsigned int)((key[i*4 + j] & (extra_bit - 1)) | extra_bit) << (j*8);
	  } else {
	     tmp |= 1u << partial;
	  }
	  w[i++] = tmp;
    }
    else if(bitlength < 256)
       w[i++] = 1u;

    for(; i < 8; ++i)
       w[i] = 0;

    for(; i < 108; ++i)
       w[i] = rotl(w[i - 8] ^ w[i - 5] ^ w[i - 3] ^ w[i - 1] ^ 0x9e3779b9u ^ (i-8), 11);

    for(i = 0; i < 8; ++i)
    {
      unsigned char sbox_idx = 7 - (i+4) % 8;
      int j;
      for(j = i; j < 25; j += 8)
	  sbox_apply(sbox_idx, &w[8 + j*4], &state->k[j*4]);
    }
}

static void serpent_round(const sosemanuk_master_state *master, int idx, unsigned int *data)
{
  int i;
  unsigned int tmp[4];

  for(i = 0; i < 4; ++i)
    tmp[i] = data[i] ^ master->k[idx*4 + i];
  sbox_apply(idx % 8, tmp, data);

  data[0] = rotl(data[0], 13);
  data[2] = rotl(data[2], 3);
  data[1] = data[1] ^ data[0] ^ data[2];
  data[3] = data[3] ^ data[2] ^ (data[0] << 3);
  data[1] = rotl(data[1], 1);
  data[3] = rotl(data[3], 7);
  data[0] = data[0] ^ data[1] ^ data[3];
  data[2] = data[2] ^ data[3] ^ (data[1] << 7);
  data[0] = rotl(data[0], 5);
  data[2] = rotl(data[2], 22);
}

void sosemanuk_init_iv(sosemanuk_state *iv_state, const sosemanuk_master_state *master,  const unsigned char *iv)
{
  int i;

  unsigned int *s = iv_state->s;
  unsigned int *r = iv_state->r;
  iv_state->t = 0;

  unsigned int data[4];

  for(i = 0; i < 4; ++i)
    data[i] = *((unsigned int*)(iv + (i * 4)));

  for(i = 0; i < 12; ++i)
    serpent_round(master, i, data);

  s[9] = data[0];
  s[8] = data[1];
  s[7] = data[2];
  s[6] = data[3];

  for(; i < 18; ++i)
    serpent_round(master, i, data);

  r[0] = data[0];
  r[1] = data[2];

  s[5] = data[3];
  s[4] = data[1];

  for(; i < 24; ++i)
    serpent_round(master, i, data);

  const unsigned int *sk = master->k;

  s[3] = data[0] ^ sk[96];
  s[2] = data[1] ^ sk[97];
  s[1] = data[2] ^ sk[98];
  s[0] = data[3] ^ sk[99];
}

void sosemanuk_extract(sosemanuk_state *state, unsigned char *stream)
{
  unsigned int f[4];
  unsigned int s[4];

  for(int i = 0; i < 4; ++i)
  {
      f[i] = automaton_step(state);
      s[i] = lfsr_step(state);
  }

  unsigned int *stream32 = (unsigned int*)stream;
  sbox_apply(2, f, stream32);

  for(int i = 0; i < 4; ++i)
  {
      *((unsigned int*)(stream + (i*4))) = stream32[i] ^ s[i];
  }
}

ראו גם

• צופן זרם
• סרפנט

הערות שוליים

1. SOSEMANUK
2. http://www.ecrypt.eu.org/stream/papersdir/2006/009.pdf
3. http://link.springer.com/chapter/10.1007%2F978-3-540-89255-7_32
4. http://link.springer.com/chapter/10.1007%2F978-3-642-14423-3_8
5. http://link.springer.com/chapter/10.1007%2F978-3-642-17373-8_9