צופן זרם

בקריפטוגרפיה, צופן זרם (באנגלית: Stream Cipher) הוא סוג של צופן סימטרי שמצפין זרם באורך משתנה של יחידות מידע (המיוצגות על ידי סיביות, בתים או מילים), תוך שימוש בטרנספורמציה המייצרת מפתח לפי 'מצב פנימי' (internal state) של הצופן. צופן זרם מתפקד כמו מחולל פסידו-אקראי ש'מותח' את מפתח ההצפנה המסופק על ידי המשתמש ומייצר ממנו זרם מפתח פסידו-אקראי כאורך הקלט המיועד להצפנה. לקבלת הטקסט המוצפן זרם המפתח מחובר עם הקלט הקריא בחיבור בינארי (XOR) או בפעולה אחרת ובלבד שתהיה הפיכה.
ההבחנה העיקרית בין צופן זרם לצופן בלוקים היא אופן יצירת מפתח ההצפנה. בהגדרת צופן זרם מתכוונים למחולל הפנימי (keystream generator) המייצר זרם-המפתח פסידו-אקראי. המחולל מתבסס על זיכרון פנימי ופועל בצורה של פעימות (clocking), מסיבה זו אומרים שלצופן זרם יש 'זיכרון', זאת בניגוד לצופן בלוקים שכאשר הוא מופעל בצורה ישירה, אינו מכיל זיכרון כלל. למשל AES מצפין בלוק בגודל 128 סיביות באמצעות פונקציה קבועה שאינה עושה שימוש במידע מהצפנה קודמת. צופן זרם הוא פרימיטיב קריפטוגרפי (כלי בסיסי) ואינו מהווה כשלעצמו מערכת הצפנה שלמה.
אם צופן זרם מיושם בחומרה הוא מהיר מאוד, מנצל מעגלים פשוטים וקלים לתפעול ותחזוקה, לכן מתאים במיוחד להתקני תקשורת בהם הזיכרון מוגבל או כאשר יש צורך בהצפנה ושידור של מנות מידע קטנות בכל פעם או כאשר אורך המידע אינו ידוע מראש. לצופן זרם יתרון מסוים במקרים בהם כשל בשידור עלול להתרחש בתדירות גבוהה כגון בתקשורת אלחוטית. צפני זרם ישנים פעלו בעיקר על סיביות ויועדו לחומרה. צפני זרם מודרניים מותאמים בחלקם גם לתוכנה תוך ניצול יכולות המעבד המודרני להשגת ביצועים גבוהים, תוך התחשבות בגבולות מילה.

היסטוריה

לצפני זרם היסטוריה עשירה. הם קיימים מזה שנים רבות ושימשו בתקשורת אלחוטית במיוחד למטרות צבאיות. כבר במלחמת העולם הראשונה יושמו צפני זרם במכונות פרימיטיביות מבוססות רוטור. המכונה הגרמנית לורנץ ששימשה את הצבא הגרמני במלחמת העולם השנייה לתקשורת מאובטחת פעלה על עיקרון צופן זרם שכונה בפי מומחי ההצפנה הבריטיים בבלצ'לי פארק בשם "FISH". צבאות בעלות הברית השתמשו אף הן באופן נרחב בצופן זרם לתקשורת. חלק ממכונות ההצפנה הפרימיטיביות שיישמו צפני זרם בזמן המלחמה היו טובות ולעיתים רק אי מילוי הוראות ביטחון גרמו לפרצות שהקלו על מנתחי הצפנים בפיצוחן.
בעבר רבים מצפני הזרם נחשבו לסודות צבאיים ולכן קיים מטבע הדברים תיעוד דל יחסית אודותם. כיום קיים מגוון רחב של צפני זרם מודרניים המתאימים להצפנה מאסיבית הן בחומרה והן בתוכנה. RC4 הוא דוגמה לצופן זרם מודרני המיועד לתוכנה והיה בשימוש נרחב מאז המצאתו למרות שכיום אינו מומלץ לשימוש.

צופן זרם א-סינכרוני

צופן זרם בעל סינכרון עצמי (באנגלית Self-Synchronizing Stream Cipher) או צופן זרם א-סינכרוני המסומן בקיצור SSSC פותר את בעיית הסינכרון בדרך אחרת. בצופן זרם בעל סינכרון עצמי זרם המפתח הוא פונקציה של המפתח הסודי  ומספר מוגבל של סמלים מהטקסט המוצפן שהופקו עד כה. המצב הפנימי של הצופן ניתן לשחזור באופן מלא בעזרת מספר סמלים קודמים של הטקסט המוצפן, לכן כאשר המקבל מנסה לפענח את הטקסט המוצפן, אם חסר סמל או נוסף סמל כתוצאה משיבושים בשידור, הדבר ישפיע רק על מספר מוגבל של סמלים, לאחריהם הסינכרון יחודש מעצמו והטקסט המוצפן יהיה לאחר מכן תקין. בניסוח פורמלי, כמתואר בתרשים משמאל, ההבדל בין צופן זרם זה לצופן זרם סינכרוני הוא שהסמל הבא של זרם המפתח  הוא תוצאה של הפונקציה . כאשר  מייצג את מספר הסמלים שהפונקציה  צריכה לקבל מתוך הטקסט המוצפן שהתקבל עד כה, כדי לייצר את הסמל החדש.
יחסית צפני זרם מסוג זה נפוצים פחות. הבולטים שבהם הם מצב הפעלה CFB של צופן בלוקים הפועל למעשה כצופן זרם בעל סינכרון עצמי וכן SSS ו-Moustique.

צופן A5/1

דוגמה לצופן זרם מודרני המיישם LFSR היא אלגוריתם A5/1 שיושם בעבר בטכנולוגיית GSM במכשירי טלפון ניידים. A5/1 הוא צופן זרם המייצר זרם מפתח באמצעות מחולל המורכב משלוש יחידות LFSR באורך שונה (ראו תרשים) ומשתמש בטכניקה Stop/go. המחולל מאותחל בעזרת מפתח בגודל 64 סיביות. הפלט בכל מחזור זמן הוא XOR של הסיבית הנמוכה של שלוש יחידות ה-LFSR. עדכון המצב הפנימי מבוסס על סיביות תזמון, הממוקמות בכל יחידה במיקום שונה. כאשר התוצאה נקבעת לפי "החלטת" רוב סיביות התזמון.
צופן זה התגלה כלא בטוח בתחילה עם עבודתו של גוליק ב-1997, המבוססת על פתרון מערכת משוואות ליניאריות, התקפה שלא הייתה יעילה במיוחד. לאחר מכן הורחבה ושופרה ההתקפה על ידי פרופסור עדי שמיר, אלכס ביריוקוב ודויד וגנר בשנת 2000. הם הורידו את סיבוכיות ההתקפה על הצופן, באמצעות חישוב מוקדם של כ-300 גיגה-בית של נתונים. מיד לאחריהם הציעו פרופסור אלי ביהם ואור דונקלמן התקפה משופרת יותר המסתמכת על זרם של  נתונים (קריאים), ידוע מראש. בשנים 2003 ו-2004 נמצאו שיטות פיצוח טובות אף יותר על ידי אקדהל, יוהנסון ומקסימוב, בעזרתן אפשר לפצח את הצופן בתוך מספר דקות בהסתמך על מספר שניות של זרם נתונים ידוע.

ביטחון

המחולל הפנימי של צופן זרם מתנהג כאוטומט סופי. כלומר בכל נקודת זמן מצבו הפנימי הנוכחי מתעדכן על פי המצב הקודם ובד בבד נוצר חלק מזרם המפתח. בשל העובדה שמספר המצבים האפשריים סופי, לאחר זמן מצב כלשהו יופיע שוב והיות וכל מצב תלוי במצבים קודמים, למעשה מנקודה זו ואילך המחולל יחזור על עצמו בהעתק מדויק. לתכונה זו קוראים מחזוריות (period). אם מחזוריות המחולל קצרה מדי נוצרת חפיפה, חלקים שונים מזרם המסר יוצפנו באמצעות סיביות מפתח זהות. במצב כזה הצופן פרוץ לחלוטין, כיוון שבידיעת חלק קטן מהמסר המקורי ניתן לשחזר חלקים מזרם המפתח ואיתם לפענח את יתר חלקי הטקסט המוצפן. גם אם המסר המקורי אינו ידוע, אם משלבים קטעים שונים של זרם מוצפן שידוע כי הוצפנו עם מפתח זהה, מתקבל זרם סיביות המכיל שילוב של חלקי מסר מקוריים. במילים אחרות מסירים למעשה את זרם המפתח מפלט הצופן וחושפים את האופי הסטטיסטי של חלקי המסרים המקוריים. ניתוח סטטיסטי פשוט של השפה מאפשר להפרידם זה מזה בקלות.
במהלך מלחמת העולם השנייה, שימשה מכונת ההצפנה הגרמנית לורנץ להצפנת מסרים שהועברו בין המפקדה הנאצית לבין עמדות הפיקוד של הצבא הגרמני. מנתחי הצופן של בעלות הברית נהנו מהעובדה שמפעיל רדיו גרמני כשל פעם אחת והשתמש בטעות במפתח הצפנה זהה כדי להצפין שתי תשדורות שונות, עקב כך הושגה פריצת דרך בשבירת צופן המכונה על ידי חיקוי המבנה הפנימי שלה וניתוח מבנה הצופן.
דרך אחרת לבחון ביטחון צופן זרם היא לבדוק את מידת האקראיות של המחולל הפנימי שלו. היות שזרם המפתח מתנהג כרצף אקראי, אפשר לעשות שימוש בכלים סטטיסטיים ידועים כדי לבחון את מידת אקראיות הפלט. העבודה הראשונה בתחום נעשתה על ידי סולומון גולומב שהגדיר שלושה כללים לקביעת טיב אקראיות המחולל. קיימות שיטות שונות לבדיקת אקראיות (ראו מחולל מספרים אקראיים).

סיבוכיות לנארית

כל מחרוזת סיביות ניתנת לייצוג על ידי נוסחת נסיגה רקורסיבית כלשהי של מחרוזת סיביות קצרה יותר. כלומר אפשר לבטא כל סיבית ברצף כצירוף ליניארי כלשהו של מספר סיביות קודמות. הצירוף הקצר ביותר איתו ניתן לבטא מחרוזת סיביות נתונה נקרא הסיבוכיות הליניארית של המחרוזת. אלגוריתם ברלקמפ-מסי (Berlekamp-Massey) יעיל בחישוב נוסחת הנסיגה של מחרוזת סיביות מעל שדה בינארי וכתוצאה מכך בחישוב הסיבוכיות הליניארית שלה. סיבוכיות ליניארית חשובה בניתוח צופן זרם המבוסס על LFSR כיוון שכדי להשיג מחזוריות מרבית, הערך הראשוני של האוגר חשוב. אפשר לראות את LFSR כפולינום מעל השדה המורחב  שמקדמיו הם 0 או 1, המקדמים הם סיביות המחולל, שחלקם משמשים כמקדמים לחישוב סיבית ההזנה בשלב העליון. ה-LFSR מקסימלי (כלומר מייצר רצף בעל מחזוריות מקסימלית) רק אם הפולינום המייצג אותו פרימיטיבי ומספר הסיביות במחולל זוגי.
כיום מקובל שמחזוריות של  נחשבת קטנה מדי ברוב היישומים. מקובל שתהיה מחזוריות של לפחות .

צפני זרם בתוכנה

בעקרון יישום LFSR יעיל יותר בחומרה. ב-1987 פותח RC4 של רונלד ריבסט, צופן הזרם הראשון שעוצב במיוחד לתוכנה. ב-1994 הוצג לציבור צופן SEAL. צפנים אילו אינם עושים שימוש ב-LFSR אלא פועלים על עיקרון של תמורה פסאודו-אקראית. למעט RC4, צופן זרם מודרני כולל שימוש בווקטור אתחול, הנקרא גם Nonce. מטרתו היא לאפשר שימוש באותו מפתח הצפנה להצפנת טקסטים רבים ללא חשש. בדרך כלל החלפת מפתח הצפנה דורשת פעולת הכנה מסוימת ואילו החלפת Nonce קלה ביותר. צופן בלוקים מיושם לעיתים במצבי הפעלה המדמים צופן זרם. למשל במצב OFB אפשר ליישם צופן בלוקים כמו AES באופן כזה שפלט הצופן מתנהג כצופן זרם לכל דבר, אך פחות יעיל כיוון שבכל סבב שבו מופעל הצופן רק מספר קטן של סיביות מוצפנות. ב-2005 פותח צופן זרם Salsa20 שהוא מהיר יותר מ-AES, מתאים לתוכנה ולחומרה והומלץ לשימוש בעיקר בתוכנה.
צופני זרם מודרניים שמנצלים LFSR משתמשים ביחידות גדולות עם מצב פנימי בגודל 160 סיביות ומעלה ובשיטות שילוב לא ליניאריות בדומה לצופן בלוקים. לדוגמה SOSEMANUK הוא צופן זרם מודרני שמנצל טכניקות מתקדמות ממספר אלגוריתמים ידועים כמו סרפנט ו-SNOW וכולל מצב פנימי שמנוהל על ידי LFSR בעל עשר יחידות בגודל  ומכונת מצבים בגודל 64 סיביות.