SNOW

בקריפטוגרפיה, SNOW היא משפחה של צפני זרם סינכרוניים הפועלים ברמה של מילים ומותאמים לתוכנה. הגרסה הראשונה שכעת נקראת SNOW 1.0 פותחה בשנת 2000 על ידי Thomas Johansson ו-Patrik Ekdahl מאוניברסיטת לונד שוודיה. הצופן מקבל מפתח הצפנה בשני אורכים אפשריים, 128 או 256 סיביות ומפיק בכל פעימה מילה פסאודו-אקראית אחת באורך 32 סיביות המהווה חלק מזרם המפתח. את המפתח מחברים עם זרם המידע בדרך כלל ב-XOR לקבלת זרם מוצפן. SNOW יכול להפיק לכל היותר $2^{50}$ מילים פסאודו אקראיות עם מפתח סודי אחד.

SNOW היה מועמד לתחרות שאורגנה בשנים 2000 - 2003 על ידי NESSIE ובשל העובדה שהייתה דרישה לווקטור אתחול הוסיפו המפתחים אופציה כזו בגרסה נוספת של הצופן עם מצב הפעלה הנקרא מצב IV. בסופו של דבר SNOW 1.0 כמו ששה אלגוריתמים נוספים לא התקבלו בגלל קריפטואנליזה שהעידה על בעיות. ב-2003 פיתחו בתגובה אקדל ויוהנסון את SNOW 2.0 שלא רק יותר בטוח אלא גם יותר מהיר בתוכנה ולמעשה נחשב בין הצפנים המהירים ביותר כיום. הוא היה מועמד לפרויקט eSTREAM ושימש כצופן ייחוס לצורך השוואת ביצועים. אולם בשל חולשות תאורטיות שהתגלו בו לא נכלל בפורטפוליו. SNOW 2.0 נכלל בתקן איזו ISO/IEC 18033-4 לצופן זרם. ב-2006 הוחלט על ידי 3GPP להוסיף צופן חדש לתקן הצפנת שיחות GSM מהדור השלישי ומהדור הרביעי כחלק מהאלגוריתמים UEA2 ו-UIA2 להצפנה מאומתת והוחלט להתבסס על SNOW עם שינויים אחדים שנועדו לחזקו נגד קריפטואנליזה והוא נקרא SNOW 3G. הצופן חופשי לשימוש, אינו מוגן בפטנט ונחשב למהיר יותר מ-AES ולדעת המפתחים בעל רמת בטחון דומה, אם כי מחקרים מראים שהוא פחות בטוח ממה שהוצהר.

רקע תאורטי

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

SNOW 1.0

תיאור סכימתי של צופן SNOW 1.0

באופן כללי SNOW כולל LFSR בעל 16 "מצבים" או תאים (Taps), כל אחד באורך 32 סיביות יחד עם פונקציית היזון מתאימה והפלט שלו משמש להזנת מכונת מצבים, המסומנת בקיצור FSM, המורכבת משני אוגרי 32 סיביות R1 ו-R2 ופונקציות לחישוב הפלט והמצב הבא (כמתואר בתרשים משמאל). תחילה מאתחלים את הצופן עם המפתח הסודי המסופק על ידי המשתמש וטוענים את וקטור האתחול אם ישנו בדרך המפורטת להלן ואז בכל פעימה 32 סיביות פלט הצופן הן תוצאת חיבור XOR של פלט ה-FSM עם כניסה $16$ (האחרונה) של ה-LFSR. ביתר פירוט:

ה-LFSR נוצר על ידי פולינום פרימיטיבי מעל השדה $\mathbb {F} _{2^{32}}$:

$p(x)=x^{16}+x^{13}+x^{7}+\alpha ^{-1}$,

והיוצר של השדה $\mathbb {F} _{2^{32}}$ שנבחר הוא:

$\pi (x)=x^{32}+x^{29}+x^{20}+x^{15}+x^{10}+x+1$ מעל $\mathbb {F} _{2}$. מתקבל שדה בינארי מורחב שכל המקדמים בו הם סיביות.

כאשר $\pi (\alpha )=0$ כלומר $\alpha$ הוא שורש של הפולינום $\pi$. מתייחסים לכניסות האוגר המסומנות על ידי $s_{1},s_{2},...,s_{16}$ כאל מקדמים בייצוג פולינומי לפי בסיס $\alpha$ לדוגמה אם $y\in \mathbb {F} _{2^{32}}$ אזי אפשר לכתוב אותו $(y_{31},y_{30},...,y_{1},y_{0})$ כאשר $y=y_{31}\alpha ^{31}+y_{30}\alpha ^{30}+\cdots +y_{1}\alpha +y_{0}$.

בכל פעימה של הצופן, הכניסה הראשונה ב-LFSR שהיא $s_{1}$ נהיית קלט למכונת המצבים FSM שהפלט שלה הוא:

$FSM_{\text{out}}=(s_{1}\boxplus R_{1})\oplus R_{2}$

פלט ה-FSM מחובר ב-XOR עם הכניסה האחרונה $s_{16}$ וזרם המפתח הוא: $key=FSM_{\text{out}}\oplus s_{16}$.

המצב הפנימי של מכונת המצבים מתעדכן בכל פעימה לפי:

$R1'=((FSM_{\text{out}}\boxplus R2)\lll 7)\oplus R1$

$R2=S(R1),$

$R1=R1'$

הסמל $\boxplus$ הוא חיבור מודולו $2^{32}$, הפעולה $\lll 7$ היא הזזה מעגלית 7 סיביות לשמאל והסמל $\oplus$ הוא XOR. הפונקציה $S$ מייצגת את תהליך ההחלפה המורכב מארבע תיבות ההחלפה בגודל $8\times 8$ סיביות ופרמוטציה. כלומר הקלט מחולק לארבעה בתים, כל אחד עובר מיפוי אי-ליניארי לפי אחת מהתיבות ולאחר מכן התוצאה מוחלפת לפי טבלת התמורה. הקלט לתיבות ההחלפה הוא $w=(w_{7},w_{6},...,w_{0})$ סך הכול שמונה סיביות כאשר $w_{7}$ היא הסיבית המשמעותית ביותר ואילו $w_{0}$ היא הסיבית הכי פחות משמעותית. $w$ נחשב לווקטור המייצג אלמנט בשדה $\mathbb {F} _{2^{8}}$ עם פולינום הבסיס $\{\beta ^{7},...,\beta ,1\}$ שהיוצר שלו הוא פולינום אי-פריק $\pi (x)=x^{8}+x^{5}+x^{3}+x+1$ והמיפוי האי ליניארי הוא:

$r=w^{7}+\beta ^{2}+\beta +1$

כאשר האריתמטיקה היא בשדה $\mathbb {F} _{2^{8}}$. לאחר ההחלפה האמורה מבצעים תמורה לפי הטבלה הבאה:

${\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}31&30&29&28&27&26&25&24&23&22&21&20&19&18&17&16\\\hline 3&10&20&24&0&14&17&29&7&13&18&25&5&12&23&27\end{array}}$

${\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}15&14&13&12&11&10&9&8&7&6&5&4&3&2&1&0\\\hline 1&8&21&26&4&9&19&31&2&11&16&28&6&15&22&30\end{array}}$

הסיבית ה-31 (הסיבית האחרונה כשהספירה מתחילה מאפס) מוחלפת בסיבית במיקום 3 (הרביעית), הסיבית במיקום ה-30 מוחלפת בסיבית ה-10 וכן הלאה.

אתחול הצופן

במקרה של מפתח באורך 128 סיביות המפתח המסופק על ידי המשתמש מחולק לארבע מילים $k_{1},...,k_{4}$, במקרה של מפתח באורך 256 סיביות הוא מחולק לשמונה מילים בהתאמה. וקטור האתחול באורך 64 סיביות מחולק לשתי מילים. את מפתח ההצפנה המסופק על ידי המשתמש יחד עם וקטור האתחול אם ישנו, טוענים לתוך האוגר LFSR כדלהלן:

$s_{1}=k_{1}\oplus IV_{1},s_{2}=k_{2},s_{3}=k_{3},s_{4}=k_{4}\oplus IV_{2}$,

$s_{5}=k_{1}\oplus \mathbf {1} ,s_{6}=k_{2}\oplus \mathbf {1} ,s_{7}=k_{3}\oplus \mathbf {1} ,s_{8}=k_{4}\oplus \mathbf {1}$,

$s_{9}=k_{1},s_{10}=k_{2},s_{11}=k_{3},s_{12}=k_{4}$,

$s_{13}=k_{1}\oplus \mathbf {1} ,s_{14}=k_{2}\oplus \mathbf {1} ,s_{15}=k_{3}\oplus \mathbf {1} ,s_{16}=k_{4}\oplus \mathbf {1}$

כאשר $\mathbf {1}$ מייצג וקטור שכולו אחדים (32 סיביות). חיבור XOR עם וקטור כזה שקול לאופרטור השלילה. אם המפתח הנבחר באורך 256 סיביות טוענים את המפתח ווקטור האתחול כך:

$s_{1}=k_{1}\oplus IV_{1},s_{2}=k_{2},s_{3}=k_{3},s_{4}=k_{4}\oplus IV_{2}$,

$s_{5}=k_{5},s_{6}=k_{6},s_{7}=k_{7},s_{8}=k_{8}$,

$s_{9}=k_{1}\oplus \mathbf {1} ,s_{10}=k_{2}\oplus \mathbf {1} ,s_{11}=k_{3}\oplus \mathbf {1} ,s_{12}=k_{4}\oplus \mathbf {1}$,

$s_{13}=k_{5}\oplus \mathbf {1} ,s_{14}=k_{6}\oplus \mathbf {1} ,s_{15}=k_{7}\oplus \mathbf {1} ,s_{16}=k_{8}\oplus \mathbf {1}$.

אם משתמשים עם הצופן במצב ללא וקטור אתחול ההנחה היא ש-$IV_{1}=IV_{2}=0$. בשלב זה מפעילים את הצופן בדיוק $v$ פעמים ללא שימוש בפלט, במקום זאת הפלט מוזן בחזרה ללולאת ההיזון של ה-LFSR. במצב ההפעלה הרגיל ללא IV המשתנה $v=64$, במקרה של הפעלה עם $IV$ הוא $v=32$. בכל פעימה כל כניסות ה-LFSR מוזזות צעד אחד לימין, כלומר הכניסה השנייה מקבלת את הערך של הכניסה הראשונה, השלישית של השנייה וכן הלאה. בשלב האתחול הערך החדש של הכניסה הראשונה הוא חיבור של הכניסות ה-16, 13 ו-7 יחד עם תוצאת מכונת המצבים:

$s_{1}=\alpha (s_{7}\oplus s_{13}\oplus s_{16}\oplus FSM_{\text{out}})$.

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

$s_{1}=\alpha (s_{7}\oplus s_{13}\oplus s_{16})$.

הצפנה

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

$FSM_{\text{out}}\oplus s_{16}$.

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

בטחון

בפיתוח SNOW הושם דגש על עמידות נגד התקפת קורלציה שהיא התקפה גנרית אפקטיבית נגד כל צופן זרם שעושה שימוש ב-LFSR והיא מסתמכת על רמת מתאם מסוימת בין פלט המחולל למצב הפנימי בזמן נתון. למיטב ידיעת המפתחים כמות הזיכרון לצורך התקפה מעין זו נגד SNOW היא מעבר ליכולת הטכנולוגית הקיימת. התקפה נוספת שהצליחה במיוחד נגד A5/1 היא התקפת איזון זמן/זיכרון והיא אינה אפשרית נגד SNOW בשל העובדה שהמצב הפנימי גדול מדי. התקפה אפשרית אחרת היא מסוג Guess and Determine שאיתה הצליחו לפרוץ בין היתר את A5/1. היא פועלת בעיקרון כך; מנחשים חלק מהערכים הפנימיים ומנסים למצוא קשר או יחס כלשהו עם ערכים פנימיים אחרים בעיקר בפונקציית ההיזון. ההתקפה מצליחה אם מצליחים לנחש נכונה את כל המצב הפנימי. בפברואר 2002 פרסמו Hawkes ו-Rose התקפת ניחוש קריפטוגרפית כזו נגד SNOW בסיבוכיות מקום של $2^{95}$ מילים ובסיבוכיות זמן של $2^{224}$ פעולות. אף על פי שההתקפה תאורטית היא מצביעה על חולשה מסוימת כיוון שהוכח שניתן לפרוץ את הצופן בזמן נמוך מכוח גס כפי שנטען על ידי המפתחים. בין היתר ההתקפה ניצלה את העובדה שמכונת המצבים מקבלת קלט יחיד. התקפה אחרת מ-2002 של Coppersmith, Halevi, Jutla שהיא סוג של התקפת הבחנה גנרית נגד צופן זרם הכולל מיסוך אי-ליניארי מצליחה לשבור את הצופן בזמן של $2^{100}$ פעולות ועם $2^{95}$ מילות פלט של הצופן. ההתקפה מבוססת על ההבחנה שקיימת קורלציה בפולינום ההזנה וגם היא כמובן תאורטית. בגרסה השנייה המפתחים ניסו לפתור את הבעיות הללו.

SNOW 2.0

תיאור סכימתי של צופן SNOW 2.0

מבחינה סכמתית ההבדל בין גרסה 1 לגרסה 2 מינורי (כמתואר בתרשים משמאל). כקודמו ה-LFSR מכיל 16 כניסות באורך 32 סיביות, אך פולינום ההזנה (feedback polynomial) השתנה. כמו כן מכונת המצבים FSM מקבלת שתי מילות קלט במקום אחת. וכמו בקודם, הפלט הוא XOR של פלט ה-FSM עם הכניסה האחרונה של ה-LFSR. פולינום ההזנה כולל כעת שני אלמנטים שונים, $\alpha$ ו-$\alpha ^{-1}$, כאשר הראשון הוא שורש של פולינום פרימיטיבי ממעלה 4 מעל $\mathbb {F} _{2^{8}}$, ביתר פירוט:

$\pi (x)=\alpha x^{16}+x^{14}+\alpha ^{-1}x^{5}+1$ מעל $\mathbb {F} _{2^{32}}$. האלמנט $\alpha$ הוא שורש של $x^{4}+\beta ^{23}x^{3}+\beta ^{245}x^{2}+\beta ^{48}x+\beta ^{239}$ מעל $\mathbb {F} _{2^{8}}$ וכן $\beta$ הוא שורש של $x^{8}+x^{7}+x^{5}+x^{3}+1$ מעל $\mathbb {F} _{2}$.

בשלב האתחול של SNOW 2.0 הפלט של מכונת המצבים $F_{t}$ מחובר עם פונקציית ההיזון של ה-LFSR.

המצב הפנימי בזמן $t$ מיוצג על ידי $s_{t+15},s_{t+14},...,s_{t}$ כאשר $s_{i}\in \mathbb {F} _{2^{32}}$. האלמנט $s_{t}$ הימני ביותר הוא האלמנט הראשון והוא פלט ה-LFSR בכל פעימה. הזמן $t=0$ פירושו הפעימה הראשונה מיד לאחר אתחול המצב הפנימי עם המפתח. הצופן מופעל פעם אחת על ריק לפני שמתחילים לייצר את זרם המפתח, כלומר בזמן $t=1$. פלט הצופן הוא $z_{1},z_{2},z_{3},....$ מכונת המצבים FSM מכילה שני אוגרים המסומנים $R1$ ו-$R2$ כל אחד מהם בעל קיבולת של 32 סיביות. תכולת האוגרים בזמן $t\geq 0$ מסומנת $R1_{t}$, $R2_{t}$ בהתאמה. הקלט ל-FSM נלקח משתי הכניסות $s_{t+15},s_{t+5}$ ב-LFSR ופלט מכונת המצבים בזמן $t$ המיוצג על ידי $F_{t}$ מחושב כדלהלן:

$F_{t}=(s_{t+15}\boxplus R1_{t})\oplus R2_{t}$

פלט הצופן בזמן זה הוא

$z_{t}=F_{t}\oplus s_{t}$ כאשר $t\geq 1$.

פונקציית העדכון של מכונת המצבים פועלת כך:

$R1_{t+1}=s_{t+5}\boxplus R2_{t},R2_{t+1}=S(R1_{t})$ כאשר $S$ מייצג את תיבת ההחלפה.

S-box

תיבות ההחלפה של SNOW 2.0 המסומנות $S(w)$ הן בעצם פרמוטציה המבוססת על פונקציית הסבב של צופן ריינדל כדלהלן; אם $w=(w_{3},w_{2},w_{1},w_{0})$ הוא מילת קלט באורך 32 סיביות המחולקת לארבעה בתים כאשר $w_{3}$ הוא הבית החשוב, אפשר להתייחס אליה כאל וקטור (עמודה). תחילה מיישמים החלפה לפי תיבות ההחלפה של ריינדל ולאחר מכן מבצעים את הפונקציה MixColumn של ריינדל. כלומר מתייחסים למילת הקלט כאל פולינום $y$ ממעלה לכל היותר 3 מעל השדה $\mathbb {F} _{2^{8}}$ המיוצג על ידי פולינום אי-פריק $x^{8}+x^{4}+x^{3}+x+1$ מעל $\mathbb {F} _{2}$ ומכפילים בפולינום קבוע $c(y)=(x+1)y^{3}+y^{2}+y+x$ מעל $\mathbb {F} _{2^{8}}[y]$. הכפל האחרון יכול להתבצע כמו בריינדל על ידי חשבון מטריצות:

${\begin{pmatrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\end{pmatrix}}={\begin{pmatrix}x&x+1&1&1\\1&x&x+1&1\\1&1&x&x+1\\x+1&1&1&x\end{pmatrix}}{\begin{pmatrix}S_{R}(w_{0})\\S_{R}(w_{1})\\S_{R}(w_{2})\\S_{R}(w_{3})\end{pmatrix}}$

התוצאה היא הבתים $r_{0},r_{1},r_{2},r_{3}$. שתי הפעולות יחד ניתנות לביצוע במשולב כמו בפסאודו קוד הבא:

$r_{0}={\text{MULx}}(S_{R}[w_{0}],{\text{0x1b}})\ \ \oplus \ \ S_{R}[w_{1}]\ \ \oplus \ \ S_{R}[w_{2}]\ \ \oplus \ \ {\text{MULx}}(S_{R}[w_{3}],{\text{0x1b}})\ \ \oplus \ \ S_{R}[w_{3}]$

$r_{1}={\text{MULx}}(S_{R}[w_{0}],{\text{0x1b}})\ \ \oplus \ \ S_{R}[w_{0}]\ \ \oplus \ \ {\text{MULx}}(S_{R}[w_{1}],{\text{0x1b}})\ \ \oplus \ \ S_{R}[w_{2}]\ \ \oplus \ \ S_{R}[w_{3}]$

$r_{2}=S_{R}[w_{0}]\ \ \oplus \ \ {\text{MULx}}(S_{R}[w_{1}],{\text{0x1b}})\ \ \oplus \ \ S_{R}[w_{1}]\ \ \oplus \ \ {\text{MULx}}(S_{R}[w_{2}],{\text{0x1b}})\ \ \oplus \ \ S_{R}[w_{3}]$

$r_{3}=S_{R}[w_{0}]\ \ \oplus \ \ S_{R}[w_{1}]\ \ \oplus \ \ {\text{MULx}}(S_{R}[w_{2}],{\text{0x1b}})\ \ \oplus \ \ S_{R}[w_{2}]\ \ \oplus \ \ {\text{MULx}}(S_{R}[w_{3}],{\text{0x1b}})$

כאשר $S_{R}$ מייצגת את תיבות ההחלפה של ריינדל והפונקציה ${\text{MULx}}$ היא פעולת הכפלה של אלמנט בשדה עם אלמנט פרימיטיבי ($x$) שהיא דומה לכפל ב-2, במילים אחרות; פעולת Shift לשמאל סיבית אחת במידה שאין גלישה, או פעולת Shift ו-XOR אחד עם ערך קבוע (${\text{0x1b}}$) אם הייתה גלישה. דהיינו אם הסיבית המשמעותית ביותר הייתה '1' לפני הכפל (הפונקציה מתוארת ביתר פירוט ב-SNOW 3G להלן).

אתחול מפתח

תחילה, אם מפתח ההצפנה באורך 128 סיביות או ארבע מילים $k_{0},...,k_{3}$ באורך 32 סיביות כל אחת, טוענים אותו יחד עם וקטור האתחול $IV$ באורך ארבע מילים $IV_{0},...IV_{3}$ אם ישנו, לתוך ה-LFSR לפי:

$s_{15}=k_{3}\oplus IV_{0},s_{14}=k_{2},s_{13}=k_{1},s_{12}k_{0}\oplus IV_{1}$,

$s_{11}=k_{3}\oplus \mathbf {1} ,s_{10}=k_{2}\oplus \mathbf {1} \oplus IV_{2},s_{9}=k_{1}\oplus \mathbf {1} \oplus IV_{3},s_{8}=k_{0}\oplus \mathbf {1}$

$s_{7}=k_{3},s_{6}=k_{2},s_{5}=k_{1},s_{4}=k-0$,

$s_{3}=k_{3}\oplus \mathbf {1} ,s_{2}=k_{2}\oplus \mathbf {1} ,s_{1}=k_{1}\oplus \mathbf {1} ,s_{0}=k_{0}\oplus \mathbf {1}$

כאשר 1 מייצג וקטור שכולו אחדים (${\text{0xffffffff}}$). אם המפתח הוא 256 סיביות כלומר שמונה מילים $k_{0},...,k_{7}$ אזי הטעינה מתבצעת לפי:

$s_{15}=k_{7}\oplus IV_{0},s_{14}=k_{6},s_{13}=k_{5},s_{12}=k_{4}\oplus IV_{1}$,

$s_{11}=k_{3},s_{10}=k_{2}\oplus IV_{2},s_{9}=k_{1}\oplus IV_{3},s_{8}=k_{0}$,

$s_{7}=k_{7}\oplus \mathbf {1} ,s_{6}=k_{6}\oplus \mathbf {1} ,s_{5}=k_{5}\oplus 1,s_{4}=k_{4}\oplus \mathbf {1} ,s_{3}=k_{3}\oplus \mathbf {1} ,s_{2}=k_{2}\oplus \mathbf {1} ,s_{1}=k_{1}\oplus \mathbf {1} ,s_{0}=k_{0}\oplus \mathbf {1}$.

לאחר מכן מאפסים את R1 ו-R2 ומפעילים את הצופן 32 פעימות (Clocks) מבלי לייצר כל פלט, אלא במקום זאת מזינים את התוצאה בחזרה לפונקציית ההזנה (כמתואר בתרשים), לכן במהלך האתחול האלמנט הבא שמוזן לתוך ה-LFSR הוא:

$s_{t+16}=\alpha ^{-1}s_{t+11}\oplus s_{t+2}\oplus \alpha s_{t}\oplus F_{t}$.

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

$s_{t+16}=\alpha ^{-1}s_{t+11}\oplus s_{t+2}\oplus \alpha s_{t}$.

מכאן ואילך בכל פעימה נוצרת מילה פסאודו אקראית שהיא חלק מזרם המפתח שהצופן מייצר, עד $2^{50}$ מילים כאלה שאז יש צורך להחליף מפתח.

ההבדלים העיקריים בין גרסה 1 לגרסה 2 הם:

• שינוי פולינום ההזנה, בעוד שב-SNOW 1.0 ניתן היה לחשב את לולאת ההזנה עם כפל יחיד ו-XOR אחד מותנה, כך שרוב הזמן בוצע רק Shift הרי שבגרסה 2 מבוצעות שתי הכפלות ו-XOR בלתי מותנה בכל אחת מהן. התוצאה היא פיזור טוב יותר של הסיביות מה שמחזק את הצופן נגד התקפת קורלציה.
• שימוש בשני קבועים שונים בלולאת ההזנה במקום אחד. למיטב ידיעת המפתחים אין אפשרות למניפולציה של פולינום ההזנה כך שנוסחת הנסיגה הליניארית שלו תהיה בעלת משקל נמוך.
• ביצוע XOR באופן קבוע ללא תלות במשתנים האחרים בפולינום ההזנה משפר ביצועים, לעומת הגרסה הקודמת שבה ה-XOR היה מותנה בסיבית המשמעותית.
• ה-FSM של הגרסה השנייה מקבל שני פרמטרים במקום אחד. מה שמקשה על התקפות בסגנון ניחוש ובדיקה, כיוון שפלט R1 תלוי כעת גם בקלט מה-LFSR.
• תיבות ההחלפה החדשות בגרסה 2 הושאלו מצופן ריינדל לעומת גרסה 1. הבחירה הזו משפרת את הפיזור כך שכל סיבית פלט מושפעת מכל סיביות הקלט, בניגוד לגרסה הקודמת.

בטחון

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

SNOW 3G

תיאור סכמתי של צופן SNOW 3G

SNOW 3G מבוסס על SNOW 2.0 והוא שוכן בליבה המבצעת הצפנה מאומתת של תקשורת סלולרית באלגוריתמים UEA2 להצפנה ו-UIA2 לאימות בדור השלישי ובדור הרביעי של GSM. הצופן פועל ברמה של מילים באורך 32 סיביות, מקבל מפתח סודי באורך 128 סיביות וכן וקטור אתחול באורך 128 סיביות. הפלט מחובר עם השיחה או הנתונים מילה אחר מילה ב-XOR והתוצאה משודרת לצד השני. בפענוח הצד המקבל פועל באופן דומה, מפעיל את הצופן עם המפתח הסודי המשותף לקבלת זרם מפתח תואם ואז מחבר שוב עם השיחה המוצפנת כדי להחזירה למצב הגלוי.

SNOW 3G כולל אוגר LFSR אחד בעל 16 כניסות (Taps) באורך 32 סיביות כל אחת, מכונת מצבים אחת הכוללת שלושה אוגרים באורך 32 סיביות ופונקציות עדכון מתאימות לפי הפירוט בהמשך. בתחילת כל שיחה טוענים את המפתח ואת וקטור האתחול לתוך המצב הפנימי והצופן מופעל 32 פעימות ללא שימוש בפלט במקום זאת הפלט מוזן בחזרה לאוגר ולאחר מכן עוברים למצב הפעלה רגיל ומייצרים בכל פעימה 32 סיביות מפתח. בשני מצבי ההפעלה של הצופן (Clocking), מצב האתחול ומצב העבודה משתמשים בשתי הפונקציות הבאות:

הפונקציה MULx

פונקציה להכפלת אלמנטים בשדה $\mathbb {F} _{2^{8}}$ ב-2 (או הפולינום $x$), הנקראת ${\text{MULx}}(V,c)$ מקבלת שני בתים $V,c$ ומחזירה בית אחד:

אם הסיבית המשמעותית ביותר של $V$ היא 1 מבצעים:

${\text{MULx}}(V,c)\longmapsto (V\ll _{8}1)\oplus c$

אחרת מבצעים:

${\text{MULx}}(V,c)\longmapsto V\ll _{8}1$.

הזזה שמאלה (sift left) שהיא פעולה המובנית בכל המעבדים שקולה לכפל בפולינום $x$ (או ב-'02') שהוא אלמנט פרימיטיבי בשדה $\mathbb {F} _{2^{8}}$. אם הסיבית המשמעותית ביותר של $V$ היא '1' תתרחש גלישה לאחר הזזה, במצב זה מתקבל אלמנט שאינו בשדה $\mathbb {F} _{2^{8}}$ ולכן יש צורך לבצע צימצום מודולרי עם הקבוע $c$ ולקחת את השארית. כיוון שהגלישה מאד קטנה אין צורך בביצוע פעולת חילוק ארוכה, לכל היותר יידרש חיסור אחד כדי לקבל את השארית. בהרחבה של שדה בינארי פעולת החיסור זהה לחיבור והיא XOR.

דוגמה במספרים: ${\text{MULx}}({\text{0x96}},{\text{0x1B}})={\text{0x2C}}\oplus {\text{0x1B}}={\text{0x37}}$.

הפונקציה MULxPOW

הפונקציה ${\text{MULxPOW}}$ משתמשת ב-${\text{MULx}}$ באופן רקורסיבי כדי לבצע העלאה בחזקה מודולרית של אלמנטים בשדה. היא מקבלת שני בתים $V,c$ ומעריך $i$ ומחזירה בית אחד כך:

אם $i=0$

מחזירים את $V$

אחרת מבצעים:

${\text{MULxPOW}}(V,i,c)={\text{MULx}}({\text{MULxPOW}}(V,i-1,c),c)$.

הפונקציה MULx מקבילה למעשה להכפלה באיבר פרימיטיבי של ההרחבה ממעלה 8 מעל $GF(2)$. יהי $\beta$ שורש של פולינום אי פריק ממעלה 8 מעל $GF(2)[\beta ]$ אז עבור כל אלמנט $V\in GF(2^{8})$ התוצאה של MULx מקבילה ל-$V\cdot \beta$. כמו כן הפונקציה MULxPOW מקבילה להכפלה בחזקה $i$ של האיבר הפרימיטיבי: $V\cdot \beta ^{i}$.

LFSR ו-FSM

אוגר ה-LFSR מורכב מ-16 מצבים $s_{0},s_{1},...,s_{15}$ כל אחד מכיל 32 סיביות. מכונת המצבים FSM מכילה שלושה אוגרי 32 סיביות הנקראים $R_{1},R_{2},R_{3}$. פונקציות ההחלפה $S_{1}$ ו-$S_{2}$ משמשות לעדכון האוגרים $R_{1}$ ו-$R_{2}$ בהתאמה (כמתואר בתרשים משמאל). תיבות ההחלפה ממפות קלט באורך 32 סיביות לפלט באורך 32 סיביות. הקלט מחולק לארבעה בתים $w=w_{0}\|w_{1}\|w_{2}\|w_{3}$ כאשר $w_{0}$ הוא הבית הכי פחות משמעותי (LSB).

פונקציות החלפה

את פונקציית ההחלפה $S_{1}$ מכינים על ידי הטבלה $S_{R}$ אותה משאילים מצופן ריינדל (בהמשך). הקלט מחולק לארבעה בתים אותם מפרשים כמקדמים של אלמנט בשדה $GF(2^{8})$ המוגדר על ידי הפולינום $x^{8}+x^{4}+x^{3}+x+1$. בנוסף להחלפה לפי ה-S-box של ריינדל מתבצעת הפונקציה MixColumn של ריינדל. שתי הפעולות, ההחלפה וערבוב העמודות מבוצעות במשולב כדלקמן:

$r_{0}={\text{MULx}}(S_{R}(w_{0}),{\text{0x1B}})\oplus S_{R}(w_{1})\oplus S_{R}(w_{2})\oplus {\text{MULx}}(S_{R}(w_{3}),{\text{0x1B}})\oplus S_{R}(w_{3})$,

$r_{1}={\text{MULx}}(S_{R}(w_{0}),{\text{0x1B}})\oplus S_{R}(w_{0})\oplus {\text{MULx}}(S_{R}(w_{1}),{\text{0x1B}})\oplus S_{R}(w_{2})\oplus S_{R}(w_{3})$,

$r_{2}=S_{R}(w_{0})\oplus {\text{MULx}}(S_{R}(w_{1}),{\text{0x1B}})\oplus S_{R}(w_{1})\oplus {\text{MULx}}(S_{R}(w_{2}),{\text{0x1B}})\oplus S_{R}(w_{3})$,

$r_{3}=S_{R}(w_{0})\oplus S_{R}(w_{1})\oplus {\text{MULx}}(S_{R}(w_{2}),{\text{0x1B}})\oplus S_{R}(w_{2})\oplus {\text{MULx}}(S_{R}(w_{3}),{\text{0x1B}})$.

את פונקציית ההחלפה $S_{2}$ מכינים על ידי הטבלה $S_{Q}$ המובאת להלן. ההחלפה מתבצעת כך

$r_{0}={\text{MULx}}(S_{Q}(w_{0}),{\text{0x69}})\oplus S_{Q}(w_{1})\oplus S_{Q}(w_{2})\oplus {\text{MULx}}(S_{Q}(w_{3}),{\text{0x69}})\oplus S_{Q}(w_{3})$,

$r_{1}={\text{MULx}}(S_{Q}(w_{0}),{\text{0x69}})\oplus S_{Q}(w_{0})\oplus {\text{MULx}}(S_{Q}(w_{1}),{\text{0x69}})\oplus S_{Q}(w_{2})\oplus S_{Q}(w_{3})$,

$r_{2}=S_{Q}(w_{0})\oplus {\text{MULx}}(S_{Q}(w_{1}),{\text{0x69}})\oplus S_{Q}(w_{1})\oplus {\text{MULx}}(S_{Q}(w_{2}),{\text{0x69}})\oplus S_{Q}(w_{3})$,

$r_{3}=S_{Q}(w_{0})\oplus S_{Q}(w_{1})\oplus {\text{MULx}}(S_{Q}(w_{2}),{\text{0x69}})\oplus S_{Q}(w_{2})\oplus {\text{MULx}}(S_{Q}(w_{3}),{\text{0x69}})$.

פונקציית ההיזון של ה-LFSR וכן פונקציית העדכון של ה-FSM משתמשות בפונקציות ${\text{MUL}}_{\alpha }$ ו-${\text{DIV}}_{\alpha }$ המוגדרות כך:

${\text{MUL}}_{\alpha }=({\text{MULxPOW}}(c,23,{\text{0xA9}})\ \|$

${\text{MULxPOW}}(c,245,{\text{0xA9}})\ \|$

${\text{MULxPOW}}(c,48,{\text{0xA9}})\ \|$

${\text{MULxPOW}}(c,239,{\text{0xA9}}))$.

${\text{DIV}}_{\alpha }=({\text{MULxPOW}}(c,16,{\text{0xA9}})\ \|$

${\text{MULxPOW}}(c,39,{\text{0xA9}})\ \|$

${\text{MULxPOW}}(c,6,{\text{0xA9}})\ \|$

${\text{MULxPOW}}(c,64,{\text{0xA9}}))$.

תיבות החלפה S-box

הטבלה $S_{R}$ מכילה 256 ערכים אפשריים באורך 8 סיביות (בתים) בבסיס הקסדצימלי מתוך תיבות ההחלפה של צופן ריינדל, כך שמתקיים $S_{R}(x_{0}2^{4}+x_{1})=y_{0}2^{4}+y_{1}$, התא המצוי בשורה $x_{0}$ ועמודה $x_{1}$ מכיל את הערך $y_{0}\|y_{1}$. לדוגמה $S_{R}(42)=S_{R}({\text{0x2A}})={\text{0xE5}}=229$:

   0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
0 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76
1 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0
2 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15
3 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75
4 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84
5 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF
6 D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8
7 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2
8 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73
9 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB
A E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79
B E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08
C BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A
D 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E
E E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF
F 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16

הטבלה $S_{Q}$ מכילה 256 ערכים אפשריים באורך 8 סיביות (בתים) בבסיס הקסדצימלי אותה מכינים על ידי פולינום דיקסון $g_{49}(x)=x\oplus x_{9}\oplus x^{13}\oplus x^{15}\oplus x^{33}\oplus x^{41}\oplus x^{45}\oplus x^{47}\oplus x^{49}$ כך שעבור קלט $x$ באורך 8 סיביות המייצג אלמנט בשדה $GF(2^{8})$ המוגדר על ידי הפולינום $x^{8}+x^{6}+x^{5}+x^{3}+1$ כל כניסה בטבלה מתאימה ל-$g_{49}(x)\oplus {\text{0x25}}$:

   0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
0 25 24 73 67 D7 AE 5C 30 A4 EE 6E CB 7D B5 82 DB
1 E4 8E 48 49 4F 5D 6A 78 70 88 E8 5F 5E 84 65 E2
2 D8 E9 CC ED 40 2F 11 28 57 D2 AC E3 4A 15 1B B9
3 B2 80 85 A6 2E 02 47 29 07 4B 0E C1 51 AA 89 D4
4 CA 01 46 B3 EF DD 44 7B C2 7F BE C3 9F 20 4C 64
5 83 A2 68 42 13 B4 41 CD BA C6 BB 6D 4D 71 21 F4
6 8D B0 E5 93 FE 8F E6 CF 43 45 31 22 37 36 96 FA
7 BC 0F 08 52 1D 55 1A C5 4E 23 69 7A 92 FF 5B 5A
8 EB 9A 1C A9 D1 7E 0D FC 50 8A B6 62 F5 0A F8 DC
9 03 3C 0C 39 F1 B8 F3 3D F2 D5 97 66 81 32 A0 00
A 06 CE F6 EA B7 17 F7 8C 79 D6 A7 BF 8B 3F 1F 53
B 63 75 35 2C 60 FD 27 D3 94 A5 7C A1 05 58 2D BD
C D9 C7 AF 6B 54 0B E0 38 04 C8 9D E7 14 B1 87 9C
D DF 6F F9 DA 2A C4 59 16 74 91 AB 26 61 76 34 2B
E AD 99 FB 72 EC 33 12 DE 98 3B C0 9B 3E 18 10 3A
F 56 E1 77 C9 1E 9E 95 A3 90 19 A8 6C 09 D0 F0 86

מצב אתחול

באתחול הצופן בכל פעימה ה-LFSR מקודם כך שהערך המצוי בכל כניסה מועתק לכניסה הבאה משמאל לימין (כלומר $s_{0}=s_{1},s_{1}=s_{2},s_{2}=s_{3}$ וכן הלאה), הכניסה האחרונה $s_{15}$ מתעדכנת על ידי פונקציית ההיזון לפי הנוסחה הבאה. מתייחסים ל-$s_{0}$ כאל ארבעה בתים $s_{0,0}\|s_{0,1}\|s_{0,2}\|s_{0,3}$ וכן לגבי הכניסה $s_{11}$:

$s_{15}=(s_{0,1}\|s_{0,2}\|s_{0,3}\|{\text{0x00}})\ \ \oplus \ \ {\text{MUL}}_{\alpha }(s_{0,0})\ \ \oplus \ \ s_{2}\ \ \oplus \ \ ({\text{0x00}}\|s_{11,0}\|s_{11,1}\|s_{11,2})\ \ \oplus \ \ {\text{DIV}}_{\alpha }(s_{11,3})\ \ \oplus \ \ F$.

הערך $F$ הוא פלט מכונת המצבים המוגדרת להלן.

מצב הצפנה

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

$s_{15}=(s_{0},1\|s_{0},2\|s_{0},3\|{\text{0x00}})\ \oplus \ {\text{MUL}}_{\alpha }(s_{0,0})\ \oplus \ s_{2}\ \oplus \ ({\text{0x00}}\|s_{11,0}\|s_{11,1}\|s_{11,2})\ \oplus \ {\text{DIV}}_{\alpha }(s_{11,3})$.

בשלב זה לא כוללים את פלט מכונת המצבים בפונקציית ההזנה.

מכונת המצבים

מכונת המצבים FSM מקבלת מה-LFSR שתי מילים מהכניסות $s_{15}$ ו-$s_{5}$ ומייצרת מילה אחת $F$ כדלהלן:

$F=(s_{15}\boxplus (R_{1})\oplus R_{2}$

עדכון מכונת המצבים מתבצע כך:

$r=R_{2}\boxplus (R_{3}\oplus s_{5})$,

$R_{3}=S_{2}(R_{2})$,

$R_{2}=S_{1}(R_{1})$,

$R_{1}=r$.

הכנת מפתח

בשלב הכנת הצופן טוענים את המפתח הסודי באורך 128 סיביות המחולק לארבע מילים $k_{0},...,k_{3}$ ואת וקטור האתחול $IV_{0},...,IV_{3}$ לתוך ה-LFSR כדלהלן:

$s_{15}=k_{3}\oplus IV_{0},s_{14}=k_{2},s_{13}=k_{1},s_{12}=k_{0}\oplus IV_{1}$

$s_{11}=k_{3}\oplus \mathbf {1} ,s_{10}=k_{2}\oplus \mathbf {1} \oplus IV_{2},s_{9}=k_{1}\oplus \mathbf {1} \oplus IV_{3},s_{8}=k_{0}\oplus \mathbf {1}$

$s_{7}=k_{3},s_{6}=k_{2},s_{5}=k_{1},s_{4}=k_{0}$

$s_{3}=k_{3}\oplus \mathbf {1} ,s_{2}=k_{2}\oplus \mathbf {1} ,s_{1}=k_{1}\oplus \mathbf {1} ,s_{0}=k_{0}\oplus \mathbf {1}$

כאן $\mathbf {1}$ מייצג מילה המכילה 32 אחדים (${\text{0xffffffff}}$) כמו כן בשלב האתחול תכולת האוגרים של ה-FSM מאופסת. ואז מריצים את הצופן 32 פעימות ללא שימוש בפלט, אלא במקום זאת הפלט $F$ מחובר לפונקציית ההיזון בחזרה. לאחר מכן מריצים את הצופן פעימה נוספת בה לא משתמשים בפלט כלל ולאחר מכן הצופן מוכן לשימוש.

הצפנה

בכל פעימת הצפנה המהלכים הבאים מתבצעים:

1. מריצים את ה-FSM פעימה אחת ומייצרים את $F$,
2. מכינים מילת מפתח אחת $z_{t}=F\oplus s_{0}$,
3. מריצים את ה-LFSR פעימה אחת.
4. מחברים את מילת המפתח עם מילה אחת מהמסר או השיחה.

חוזרים שוב על התהליך עד להשלמת כל המסר.

בטחון

בעקרון בטחון גרסה זו מבוסס על SNOW 2.0 וקיימת קריפטואנליזה של שתי הגרסאות. מחקרים מראים שקיימת חולשה שנקראת "מפתחות קשורים" (related keys) בשניהם וכן התגלו חולשות באקראיות הצופן. ב-2010 פורסמה התקפת ערוץ צדדי נגד SNOW 3G שמראה שניתן לפרוץ את הצופן בזמן מאד קצר (מספר שניות) אם לתוקף יש אפשרות להשיג מידע תיזמון הקשור במעבר מתיבת החלפה אחת לשנייה. הפתרון שהוצע במקרה כזה שימוש בטכניקה שנקראת BitSlice בדומה לצופן סרפנט.

היבטי יישום

צופן SNOW פותח תוך מתן דגש על יישום מהיר בתוכנה. הפעולות בצופן נפוצות בכל מעבד מצוי; XOR, חיבור שלמים, הזזה ואחזור טבלאות (קריאות זיכרון). אף על פי ש-LFSR הוא רכיב חומרה אפשר ליישמו ביעילות בתוכנה, השדה $\mathbb {F} _{2^{32}}$ הוא הרחבה של $\mathbb {F} _{2^{8}}$ עם $\alpha \in \mathbb {F} _{2^{32}}$ שורש ממעלה 4 של הפולינום

$x^{4}+\beta ^{23}x^{3}+\beta ^{245}x^{2}+\beta ^{48}x+\beta ^{239}\in \mathbb {F} _{2^{8}}[x]$

לכן אפשר לצמצם את המעלה של $\alpha$ כי

$\alpha ^{4}=\beta ^{23}\alpha ^{3}+\beta ^{245}\alpha ^{2}+\beta ^{48}\alpha +\beta ^{239}$

בסיכומו של דבר הכפל ב-$\alpha$ וב-$\alpha ^{-1}$ בלולאת ההזנה ניתנים למימוש בתוכנה בפעולת הזזה (shift) ברמה של בתים. לסיכום זה נראה כך:

$MUL_{\alpha }[c]=(c\beta ^{23},c\beta ^{245},c\beta ^{48},c\beta ^{239})$

$MUL_{\alpha ^{-1}}[c]=(c\beta ^{16},c\beta ^{39},c\beta ^{6},c\beta ^{64})$

המקדמים $c_{i}$ הם בתי הקלט $w$. אפשר לבצע את הכפל והחילוק בשיטה הישירה כמתואר לעיל או באמצעות טבלאות חיפוש מוכנות מראש כמו בפסאודו קוד הבא:

result=(w<<8) ^ MUL_A[w & 0xff];
result=(w>>8) ^ MUL_AINVERSE[w & 0xff];

יישום פעולת ההחלפה של צופן SNOW בתוכנה ניתן להאצה בטכניקה דומה לזו שאומצה בצופן ריינדל. הכפל במטריצות המתואר לעיל ניתן לפיצול כצירוף ליניארי של העמודות תוך שימוש בארבע תיבות המכילות 256 מילים כל אחת. כל טבלה מכילה את כל התוצאות האפשריות של הכפלה בעמודה אחת בהתאם. לסיכום בפסאודו קוד הבא יוצאים מהנחה שקיימות ארבע טבלאות $T0,...,T3$ כאמור:

r=T0[w & 0xff] ^ T1[(w >> 8) & 0xff] ^ T2[(w >> 16) & 0xff] ^ T3[(w >> 24) & 0xff];

כמו כן אפשר ליישם את ה-LFSR בשני אופנים. האחד קל לקריאה והוא מיושם באמצעות מערכים ושימוש בטכניקת חלון, קרי במקום לבצע העתקה בפועל של ערכים מנהלים מעקב באמצעות מצביעים. השני הוא הארד קודינג של מצבי ה-LFSR. היתרון בשיטה האחרונה שבכל קריאה לפרוצדורה להפקת זרם המפתח נוצרות בבת אחת 512 סיביות המקבילות ל-16 פעימות שעון בשיטה הרגילה. בניסוי שערכו המפתחים על פנטיום 4 של אינטל 1.8GHz עם 512 מגה, בגרסה 2 הממוטבת (הארד קודינג) נדרשו 18 מחזורי שעון למילה אחת. שהוא קצב מהיר כמעט פי שניים.

קוד לדוגמה של צופן SNOW 3G

הקוד הבא הוא קוד שלם הכתוב בשפת C#‎ לפי היישום הבסיסי לא ממוטב שהומלץ על ידי התקן לצורך ייחוס והשוואה. הוא משתמש במערך LFSR באורך 16 כניסות בגודל 32 סיביות ומערך FSM עם שלוש כניסות באורך 32 סיביות וכן שתי טבלאות SR ו-SQ המכילות בכל אחת 256 ערכים קבועים:

        uint[] LFSR = new uint[16];
        uint[] FSM = new uint[3];

        byte[] SR = new byte[256] {
           0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
           0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
           0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
           0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
           0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
           0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
           0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
           0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
           0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
           0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
           0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
           0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
           0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
           0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
           0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
           0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16
        };

        byte[] SQ = new byte[256] {
           0x25,0x24,0x73,0x67,0xD7,0xAE,0x5C,0x30,0xA4,0xEE,0x6E,0xCB,0x7D,0xB5,0x82,0xDB,
           0xE4,0x8E,0x48,0x49,0x4F,0x5D,0x6A,0x78,0x70,0x88,0xE8,0x5F,0x5E,0x84,0x65,0xE2,
           0xD8,0xE9,0xCC,0xED,0x40,0x2F,0x11,0x28,0x57,0xD2,0xAC,0xE3,0x4A,0x15,0x1B,0xB9,
           0xB2,0x80,0x85,0xA6,0x2E,0x02,0x47,0x29,0x07,0x4B,0x0E,0xC1,0x51,0xAA,0x89,0xD4,
           0xCA,0x01,0x46,0xB3,0xEF,0xDD,0x44,0x7B,0xC2,0x7F,0xBE,0xC3,0x9F,0x20,0x4C,0x64,
           0x83,0xA2,0x68,0x42,0x13,0xB4,0x41,0xCD,0xBA,0xC6,0xBB,0x6D,0x4D,0x71,0x21,0xF4,
           0x8D,0xB0,0xE5,0x93,0xFE,0x8F,0xE6,0xCF,0x43,0x45,0x31,0x22,0x37,0x36,0x96,0xFA,
           0xBC,0x0F,0x08,0x52,0x1D,0x55,0x1A,0xC5,0x4E,0x23,0x69,0x7A,0x92,0xFF,0x5B,0x5A,
           0xEB,0x9A,0x1C,0xA9,0xD1,0x7E,0x0D,0xFC,0x50,0x8A,0xB6,0x62,0xF5,0x0A,0xF8,0xDC,
           0x03,0x3C,0x0C,0x39,0xF1,0xB8,0xF3,0x3D,0xF2,0xD5,0x97,0x66,0x81,0x32,0xA0,0x00,
           0x06,0xCE,0xF6,0xEA,0xB7,0x17,0xF7,0x8C,0x79,0xD6,0xA7,0xBF,0x8B,0x3F,0x1F,0x53,
           0x63,0x75,0x35,0x2C,0x60,0xFD,0x27,0xD3,0x94,0xA5,0x7C,0xA1,0x05,0x58,0x2D,0xBD,
           0xD9,0xC7,0xAF,0x6B,0x54,0x0B,0xE0,0x38,0x04,0xC8,0x9D,0xE7,0x14,0xB1,0x87,0x9C,
           0xDF,0x6F,0xF9,0xDA,0x2A,0xC4,0x59,0x16,0x74,0x91,0xAB,0x26,0x61,0x76,0x34,0x2B,
           0xAD,0x99,0xFB,0x72,0xEC,0x33,0x12,0xDE,0x98,0x3B,0xC0,0x9B,0x3E,0x18,0x10,0x3A,
           0x56,0xE1,0x77,0xC9,0x1E,0x9E,0x95,0xA3,0x90,0x19,0xA8,0x6C,0x09,0xD0,0xF0,0x86
        };

        byte MULx(byte V, byte c)
        {
            if ((V & 0x80) > 0)
                return (byte)((V << 1) ^ c);
            else
                return (byte)(V << 1);
        }

        byte MULxPOW(byte V, byte i, byte c)
        {
            if (i == 0)
                return V;
            else
                return (byte)MULx(MULxPOW(V, (byte)(i - 1), c), c);
        }

        uint MULalpha(byte c)
        {
            return ((((uint)MULxPOW(c, 23, 0xa9)) << 24) | (((uint)MULxPOW(c, 245, 0xa9)) << 16) |
                    (((uint)MULxPOW(c, 48, 0xa9)) << 8)  | (((uint)MULxPOW(c, 239, 0xa9))));
        }

        uint DIValpha(byte c)
        {
            return ((((uint)MULxPOW(c, 16, 0xa9)) << 24) |  (((uint)MULxPOW(c, 39, 0xa9)) << 16) | 
                    (((uint)MULxPOW(c, 6, 0xa9)) << 8)   |  (((uint)MULxPOW(c, 64, 0xa9))));
        }

        uint S1(uint w)
        {
            byte srw0 = SR[(byte)((w >> 24) & 0xff)];
            byte srw1 = SR[(byte)((w >> 16) & 0xff)];
            byte srw2 = SR[(byte)((w >> 8) & 0xff)];
            byte srw3 = SR[(byte)((w) & 0xff)];
            byte r0 = (byte)((MULx(srw0, 0x1b)) ^ (srw1) ^ (srw2) ^ ((MULx(srw3, 0x1b)) ^ srw3));
            byte r1 = (byte)(((MULx(srw0, 0x1b)) ^ srw0) ^ (MULx(srw1, 0x1b)) ^ (srw2) ^ (srw3));
            byte r2 = (byte)((srw0) ^ ((MULx(srw1, 0x1b)) ^ srw1) ^ (MULx(srw2, 0x1b)) ^ (srw3));
            byte r3 = (byte)((srw0) ^ (srw1) ^ ((MULx(srw2, 0x1b)) ^ srw2) ^ (MULx(srw3, 0x1b)));
            return ((((uint)r0) << 24) | (((uint)r1) << 16) | (((uint)r2) << 8) | (((uint)r3)));
        }
 
        uint S2(uint w)
        {
            byte sqw0 = SQ[(byte)((w >> 24) & 0xff)];
            byte sqw1 = SQ[(byte)((w >> 16) & 0xff)];
            byte sqw2 = SQ[(byte)((w >> 8) & 0xff)];
            byte sqw3 = SQ[(byte)((w) & 0xff)];
            byte r0 = (byte)((MULx(sqw0, 0x69)) ^ (sqw1) ^ (sqw2) ^ ((MULx(sqw3, 0x69)) ^ sqw3));
            byte r1 = (byte)(((MULx(sqw0, 0x69)) ^ sqw0) ^ (MULx(sqw1, 0x69)) ^ (sqw2) ^ (sqw3));
            byte r2 = (byte)((sqw0) ^ ((MULx(sqw1, 0x69)) ^ sqw1) ^ (MULx(sqw2, 0x69)) ^ (sqw3));
            byte r3 = (byte)((sqw0) ^ (sqw1) ^ ((MULx(sqw2, 0x69)) ^ sqw2) ^ (MULx(sqw3, 0x69)));
            return ((((uint)r0) << 24) | (((uint)r1) << 16) | (((uint)r2) << 8) | (((uint)r3)));
        }

        void ClockLFSRInitializationMode(uint F)
        {
            uint v = (((LFSR[0] << 8) & 0xffffff00) ^ (MULalpha((byte)((LFSR[0] >> 24) & 0xff))) ^ (LFSR[2]) ^
                      ((LFSR[11] >> 8) & 0x00ffffff) ^ (DIValpha((byte)((LFSR[11]) & 0xff))) ^ (F));
            for (int i = 0; i < 15; i++)
            {
                LFSR[i] = LFSR[i + 1];
            }
            LFSR[15] = v;
        }

        void ClockLFSRKeyStreamMode()
        {
            uint v = (((LFSR[0] << 8) & 0xffffff00) ^ (MULalpha((byte)((LFSR[0] >> 24) & 0xff))) ^ (LFSR[2]) ^
                      ((LFSR[11] >> 8) & 0x00ffffff) ^ (DIValpha((byte)((LFSR[11]) & 0xff))));
            for (int i = 0; i < 15; i++)
            {
                LFSR[i] = LFSR[i + 1];
            }
            LFSR[15] = v;
        }

        uint ClockFSM()
        {
            uint F = ((LFSR[15] + FSM[0]) & 0xffffffff) ^ FSM[1];
            uint r = (FSM[1] + (FSM[2] ^ LFSR[5])) & 0xffffffff;
            FSM[2] = S2(FSM[1]);
            FSM[1] = S1(FSM[0]);
            FSM[0] = r;
            return F;
        }
 
        void Initialize(uint[] k, uint[] IV)
        {
            byte i = 0;
            uint F = 0x0;
            LFSR[15] = k[3] ^ IV[0];
            LFSR[14] = k[2];
            LFSR[13] = k[1];
            LFSR[12] = k[0] ^ IV[1];
            LFSR[11] = k[3] ^ 0xffffffff;
            LFSR[10] = k[2] ^ 0xffffffff ^ IV[2];
            LFSR[9]  = k[1] ^ 0xffffffff ^ IV[3];
            LFSR[8]  = k[0] ^ 0xffffffff;
            LFSR[7]  = k[3];
            LFSR[6]  = k[2];
            LFSR[5]  = k[1];
            LFSR[4]  = k[0];
            LFSR[3]  = k[3] ^ 0xffffffff;
            LFSR[2]  = k[2] ^ 0xffffffff;
            LFSR[1]  = k[1] ^ 0xffffffff;
            LFSR[0]  = k[0] ^ 0xffffffff;
            for (i = 0; i < 32; i++)
            {
                F = ClockFSM();
                ClockLFSRInitializationMode(F);
            }
        }

        void GenerateKeystream(uint n, uint[] ks)
        {
            ClockFSM();                // Clock FSM once. Discard the output.
            ClockLFSRKeyStreamMode();  // Clock LFSR in keystream mode once.
            for (int t = 0; t < n; t++)
            {
                uint F = ClockFSM();            // STEP 1 
                ks[t] = F ^ LFSR[0];       // STEP 2 
                ClockLFSRKeyStreamMode();  // STEP 3 
            }
        }

ראו גם

• צופן זרם
• GSM
• SOSEMANUK

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

24789608SNOW