SNOW

בקריפטוגרפיה, SNOW היא משפחה של צפני זרם סינכרוניים הפועלים ברמה של מילים ומותאמים לתוכנה. הגרסה הראשונה שכעת נקראת SNOW 1.0 פותחה בשנת 2000 על ידי Thomas Johansson ו-Patrik Ekdahl מאוניברסיטת לונד שוודיה. הצופן מקבל מפתח הצפנה בשני אורכים אפשריים, 128 או 256 סיביות ומפיק בכל פעימה מילה פסאודו-אקראית אחת באורך 32 סיביות המהווה חלק מזרם המפתח. את המפתח מחברים עם זרם המידע בדרך כלל ב-XOR לקבלת זרם מוצפן. SNOW יכול להפיק לכל היותר  מילים פסאודו אקראיות עם מפתח סודי אחד.
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 הושם דגש על עמידות נגד התקפת קורלציה שהיא התקפה גנרית אפקטיבית נגד כל צופן זרם שעושה שימוש ב-LFSR והיא מסתמכת על רמת מתאם מסוימת בין פלט המחולל למצב הפנימי בזמן נתון. למיטב ידיעת המפתחים כמות הזיכרון לצורך התקפה מעין זו נגד SNOW היא מעבר ליכולת הטכנולוגית הקיימת. התקפה נוספת שהצליחה במיוחד נגד A5/1 היא התקפת איזון זמן/זיכרון והיא אינה אפשרית נגד SNOW בשל העובדה שהמצב הפנימי גדול מדי. התקפה אפשרית אחרת היא מסוג Guess and Determine שאיתה הצליחו לפרוץ בין היתר את A5/1. היא פועלת בעיקרון כך; מנחשים חלק מהערכים הפנימיים ומנסים למצוא קשר או יחס כלשהו עם ערכים פנימיים אחרים בעיקר בפונקציית ההיזון. ההתקפה מצליחה אם מצליחים לנחש נכונה את כל המצב הפנימי. בפברואר 2002 פרסמו Hawkes ו-Rose התקפת ניחוש קריפטוגרפית כזו נגד SNOW בסיבוכיות מקום של  מילים ובסיבוכיות זמן של  פעולות. אף על פי שההתקפה תאורטית היא מצביעה על חולשה מסוימת כיוון שהוכח שניתן לפרוץ את הצופן בזמן נמוך מכוח גס כפי שנטען על ידי המפתחים. בין היתר ההתקפה ניצלה את העובדה שמכונת המצבים מקבלת קלט יחיד. התקפה אחרת מ-2002 של Coppersmith, Halevi, Jutla שהיא סוג של התקפת הבחנה גנרית נגד צופן זרם הכולל מיסוך אי-ליניארי מצליחה לשבור את הצופן בזמן של  פעולות ועם  מילות פלט של הצופן. ההתקפה מבוססת על ההבחנה שקיימת קורלציה בפולינום ההזנה וגם היא כמובן תאורטית. בגרסה השנייה המפתחים ניסו לפתור את הבעיות הללו.

ביטחון

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

SNOW 3G

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

LFSR ו-FSM

אוגר ה-LFSR מורכב מ-16 מצבים  כל אחד מכיל 32 סיביות. מכונת המצבים FSM מכילה שלושה אוגרי 32 סיביות הנקראים . פונקציות ההחלפה  ו- משמשות לעדכון האוגרים  ו- בהתאמה (כמתואר בתרשים משמאל). תיבות ההחלפה ממפות קלט באורך 32 סיביות לפלט באורך 32 סיביות. הקלט מחולק לארבעה בתים  כאשר  הוא הבית הכי פחות משמעותי (LSB).

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

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

ביטחון

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

קוד לדוגמה של צופן 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 
            }
        }