צופן זרם

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

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

היסטוריה

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

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

פנקס חד פעמי

ערך מורחב – פנקס חד-פעמי

צופן זרם באופן הבסיסי ביותר פשוט מאוד. זרם-הנתונים מחובר בדרך כלל בחיבור בינארי מודולו 2 (XOR) סיבית אחר סיבית עם זרם-מפתח סודי וחד פעמי. בטיחות הצופן תלויה במידת אקראיות זרם המפתח. עיקר העבודה היא יצירת זרם המפתח שאמור להיות קשה לניחוש. הדוגמה הקלאסית לצופן זרם נקראת One-time pad (פנקס חד פעמי), הרעיון מבוסס על צופן ורנם המוגדר מעל אלפבית בינארי כדלהלן: עבור התו ה-$\ i$ במסר $\ m$ בצע: $\ c_{i}=m_{i}\oplus k_{i}$. אם זרם המפתח $\ k_{1},k_{2},k_{3},...$ מיוצר באופן אקראי (אמיתי), ללא תלות במסר כלל וכן אם אורך המפתח זהה לאורך המסר, אזי צופן זה מוגדר כצופן מושלם והוא בטוח לחלוטין. עובדה שהוכחה מתמטית על ידי קלוד שנון. אולם בשל הקושי המעשי שבהכנה מוקדמת של זרם מפתח אקראי ארוך, צופני זרם מסתייעים במחולל אקראי מובנה, המייצר זרם-מפתח פסבדו-אקראי באורך זרם הנתונים, מתוך מפתח קצר יותר כגון 128 סיביות. אולם כתוצאה מכך, בטיחותו אינה מוחלטת כפנקס חד-פעמי, מאחר שזרם המפתח אינו באמת אקראי. כיוון שבטיחות הצופן תלויה באקראיות זרם המפתח, יש קשר הדוק בין צופן זרם למספרים אקראיים.

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

סוגי צופן זרם

מבנה צופן זרם ניתן להצגה כמכונת מצבים (FSM) עם מצב פנימי (IS) ופונקציית עדכון (UF). מבחינה קריפטוגרפית חוזקו של כל צופן זרם מבוסס על הממצאים של קלוד שאנון בנוגע לביטחון פנקס חד-פעמי. צופן זרם טיפוסי מקבל מפתח סודי $K$ ווקטור אתחול $IV$ ומייצר זרם מפתח ארוך $z$ הנקרא גם רצף פסאודו-אקראי. בניסוח פורמלי:

כל צופן זרם הפועל מעל אלפבית ${\mathcal {A}}$ מייצר את הרצף $z$ המכיל $n$ סמלים: $z_{1},z_{2},...,z_{n}$, מתוך אותו אלפבית:

$z^{n}=z_{1},z_{2},...,z_{n},\ \ z_{i}\in {\mathcal {A}},\ \ i=1,2,...,n$.

זרם המפתח מחובר עם הטקסט המיועד להצפנה וממנו נוצר טקסט מוצפן, שלב זה של הצופן דומה לפנקס חד-פעמי.

$c_{i}=m_{i}\oplus z_{i},\ \ i=1,2,3,...,n$

הפונקציה המחברת את הטקסט הקריא עם זרם המפתח היא בדרך כלל פעולת XOR פשוטה של הטקסט המקורי עם המפתח סמל אחר סמל. זאת משום שהיא פעולה הופכית של עצמה. בפענוח כל מה שנדרש לעשות זה לחזור בדיוק על אותה פעולה כמובן עם הפרמטרים המתאימים. למעשה אפשר לבחור בפעולה מתמטית אחרת, העיקר שתהיה לה פעולה הופכית כך שהטקסט המוצפן ניתן יהיה לשחזור. בפענוח מפעילים את הפונקציה ההופכית. אילו היה זרם המפתח אקראי לגמרי הצופן יהיה בלתי ניתן לשבירה. אולם מצב כזה יכול לקרות רק אם זרם המפתח אקראי אמיתי. למעשה צופן זרם מנסה לדמות ככל האפשר זרם אקראי תוך שימוש בגרעין ההתחלתי הסודי $K$. אפשר לחלק את מרבית צפני הזרם לשתי קטגוריות עיקריות: צופן זרם סינכרוני וצופן זרם א-סינכרוני, למרות שקיימות פרדיגמות אחרות. למשל Helix שייך לקטגוריה אחרת.

תרשים סכמתי של צופן זרם סינכרוני

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

מבנה כללי של צופן זרם סינכרוני (באנגלית Synchronous Stream Cipher) המסומן בקיצור SSC, כמתואר בתרשים משמאל, מורכב ממכונת מצבים (אוטומט סופי) ופונקציית עדכון. מקבל מפתח סודי $K$ וייתכן גם ערך התחלתי כלשהו $IV$ ומפיק זרם מפתח באופן בלתי תלוי בטקסט המקורי או בטקסט המוצפן. בניסוח רשמי הצופן כולל:

• מצב פנימי $\sigma _{t}$ המייצג את תכולת הזיכרון הפנימי של הצופן בזמן $t$. כאשר $t$ הוא מונה המייצג את פעימות הצופן.
• פונקציית אתחול Init שאיתה מאתחלים את המצב הפנימי המיוצג על ידי הסמל $\sigma _{0}$ בזמן $t=0$.
• פונקציית עדכון $f$ האחראית לעדכון המצב הפנימי של מכונת המצבים FSM בהתאם לערכו של המפתח $K$. כלומר $\sigma _{t+1}=f(\sigma _{t},K)$.
• זרם מפתח פונקציה $g$ שהפלט שלה בזמן $t$ הוא סמל אחד מהאלפבית שהוא פונקציה של המצב הפנימי וייתכן גם מפתח ההצפנה $K$. כלומר $z_{t}=g(\sigma _{t},K)$.
• פונקציית פלט $h$ שתפקידה לחבר את הטקסט הקריא המיועד להצפנה עם זרם המפתח לקבלת טקסט מוצפן. בכל פעימה הפונקציה מקבלת את הסמל הבא מתוך הטקסט הקריא ומחזירה את הסמל הבא של הטקסט המוצפן: $c_{t}=h(m_{t},z_{t})$. הפונקציה $h$ יכולה להיות פשוט חיבור XOR שהוא הופכי של עצמו ולכן הוא זהה בהצפנה ובפענוח.

החלק המייצר את זרם המפתח נקרא "מחולל זרם מפתח" בקיצור KSG והוא זהה לחלוטין בשני הצדדים בצד השולח ובצד המקבל. הדרישה היחידה היא שפונקציית הפלט $h$ תהיה הפיכה כמו במקרה של XOR. צופן זרם סינכרוני כשמו, סובל מבעיה מהותית של סינכרוניזציה כאשר יש שיבושים בתקשורת. אם סמל אחד אבד או נוסף במהלך השידור כל הסמלים הבאים אחריו יפוענחו בצורה שגויה מכיוון שאבד הרצף בין זרם המפתח לבין הטקסט המוצפן. בעיה זו ניתנת לפתרון בדרך מאד פשוטה. מחלקים את הטקסט המקורי למקטעים בגודל קבוע הקרויים פריים (frame) או חלונית ומוסיפים "סיביות סינכרון" ביניהם. הטקסט המקורי מוצפן פריים אחר פריים כשכל פריים מקבל מספר סידורי. לאחר כל פריים מבצעים אתחול מפתח הצפנה ווקטור אתחול שיכול להיות פונקציה מוסכמת של מספר הפריים. כך מתגברים באופן עקיף על בעיית הסינכרון. לסיכום: צופן זרם סינכרוני בדרך כלל מכיל פריים וערך אתחול:

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

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

דוגמה טובה לצופן זרם סינכרוני היא צופן A5/1 להלן ששימש בעבר להצפנת שיחות GSM. אורך הפריים היה 228 סיביות ווקטור האתחול נגזר ישירות ממספר הפריים.

תרשים סכמתי של צופן זרם בעל סינכרון עצמי

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

צופן זרם בעל סינכרון עצמי (באנגלית Self-Synchronizing Stream Cipher) או צופן זרם א-סינכרוני המסומן בקיצור SSSC פותר את בעיית הסינכרון בדרך אחרת. בצופן זרם בעל סינכרון עצמי זרם המפתח הוא פונקציה של המפתח הסודי $K$ ומספר מוגבל של סמלים מהטקסט המוצפן שהופקו עד כה. המצב הפנימי של הצופן ניתן לשחזור באופן מלא בעזרת מספר סמלים קודמים של הטקסט המוצפן, לכן כאשר המקבל מנסה לפענח את הטקסט המוצפן, אם חסר סמל או נוסף סמל כתוצאה משיבושים בשידור, הדבר ישפיע רק על מספר מוגבל של סמלים, לאחריהם הסינכרון יחודש מעצמו והטקסט המוצפן יהיה לאחר מכן תקין. בניסוח פורמלי, כמתואר בתרשים משמאל, ההבדל בין צופן זרם זה לצופן זרם סינכרוני הוא שהסמל הבא של זרם המפתח $z_{t}$ הוא תוצאה של הפונקציה $g(c_{t-1},c_{t-2},...,c_{t-d},K)$. כאשר $d$ מייצג את מספר הסמלים שהפונקציה $g$ צריכה לקבל מתוך הטקסט המוצפן שהתקבל עד כה, כדי לייצר את הסמל החדש.

יחסית צפני זרם מסוג זה נפוצים פחות. הבולטים שבהם הם מצב הפעלה CFB של צופן בלוקים הפועל למעשה כצופן זרם בעל סינכרון עצמי וכן SSS ו-Moustique.

תיאור סכמתי של מחולל פסאודו-אקראי בצופן זרם

מחולל פסאודו-אקראי

ערך מורחב – מחולל מספרים פסאודו-אקראיים קריפטוגרפי

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

מחולל פסאודו-אקראי הוא למעשה ניסיון לדמות מחולל אקראי אמיתי. זהו אלגוריתם דטרמיניסטי (מסיבה זו הוא אינו באמת אקראי), שמנסה לייצר רצף של סמלים מתוך האלפבית ${\mathcal {A}}$ באופן שייראה על פניו כאקראי למתבונן מהצד שאינו יודע מהו הגרעין ההתחלתי. יש לציין שבניגוד למחולל אקראי אמיתי פלט PRNG תלוי בערכים ההתחלתיים. כלומר בהינתן אותו גרעין התחלתי הרצף שהוא ייצר יהיה זהה לחלוטין. מבחינה פרקטית פיתוח מחולל פסאודו-אקראי אינו דבר קל. מחולל טוב צריך להכיל את התכונות הבאות:

• מחזוריות מקסימלית. היות שהמחולל פועל כמכונת מצבים, הוא מכיל מספר סופי של מצבים ולכן בשלב כלשהו הוא יחזור על עצמו, כלומר יפיק רצף מספרים זהה לרצף שהופק בעבר ובמעין מעגל אין סופי. למעגל זה קוראים מחזוריות, וביטחון המחולל תלוי באורך המחזוריות.
• תכונות סטטיסטיות. הסמלים שהמחולל מפיק צריכים להיות בהתפלגות אחידה, כלומר עבור מחרוזת בינארית ההסתברות לקבל אחד או אפס צריכה להיות 1/2. יתרה מזו ההתפלגות של רצף סיביות צריכה להיות אחידה גם היא. בנוסף כל צירוף ליניארי של סיביות הפלט צריך להיות בהתפלגות אחידה. קיים מגוון מבחנים שמטרתם היא בדיקת טיב האקראיות של רצף נתון בהשוואה לרצף אקראי אמיתי.

LFSR

ערך מורחב – LFSR

דרך ותיקה וקלה להכין מחולל פסאודו-אקראי בעיקר בחומרה אך גם בתוכנה היא בעזרת אוגר זיזה ממושב Feedback shift register, במיוחד הגרסה הליניארית שנקראת LFSR. הסיבות לשימוש ב-LFSR הן: נוחות יישום בחומרה, מחזוריות גבוהה, תכונות אקראיות טובות וקלות ניתוח ובדיקה בעזרת טכניקות אלגבריות. מחולל LFSR הוא מעגל אלקטרוני המתנהג כאוטומט סופי, שמייצר זרם סיביות באורך מוגדר, הנראה לעין כאקראי.

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

1. תכולת השלב התחתון (הסיבית הנמוכה), מהווה חלק מזרם הפלט.
2. תכולת כל השלבים מוזזת כלפי מטה שלב אחד (Shift). כל שלב מעביר את תכולתו לשלב הבא אחריו.
3. והתכולה החדשה של השלב העליון, היא סיבית ההזנה המחושבת בעזרת פעולה ליניארית כלשהי, כמו חיבור בינארי מודולו 2 (XOR) של תכולת מספר קבוע של שלבים קודמים, לא בהכרח עוקבים.

סוג אחר Nonlinear Feedback shift register הגרסה הלא ליניארית של המחולל, דומה לקודמת מלבד זאת שבכל מחזור זמן, תכולת השלב העליון היא תוצאה של מה שקרוי Feedback function, פונקציה בוליאנית לא-ליניארית, המקבלת כקלט מספר קבוע של שלבים קודמים, לא בהכרח עוקבים ומחזירה סיבית אחת.

יישומי צופן זרם באמצעות LFSR

כיוון ש-LFSR ליניארי במהותו, הוא קל לניתוח ולבדיקה. ישנם אלגוריתמים לבדיקת מחזוריות, סיבוכיות ליניארית ונתונים סטטיסטיים אחרים אודות המחולל. בשל כך לא נהוג להשתמש בזרם LFSR יחיד כמפתח הצפנה. זאת כדי למנוע התקפה על הצופן כאשר חלק מזרם הנתונים ידוע מראש. ביישומים מעשיים צופן זרם מסתמך גם על פונקציה לא ליניארית כלשהי, או משלב כמה יחידות LFSR בקומבינציה לא ליניארית, באופן כזה שמסיר את ליניאריות המחולל. למשל אפשר לעצור זמנית פעולת יחידת LFSR אחת, על פי תוצאת יחידת LFSR אחרת. דהיינו במקרה שתוצאת היחידה הראשונה היא אפס, פלט המחולל יהיה חזרה על מצב קודם של ה-LFSR הראשון. שיטה זו מכונה Stop/go. שיטה אחרת הנקראת Shrinking Generator מיישמת מחוללי LFSR באופן כזה: אם תוצאת יחידה אחת היא "1" תוצאת היחידה השנייה תהווה חלק מפלט המחולל, אם התוצאה היא "0" מתעלמים מתוצאת היחידה השנייה. כלומר אף סיבית אינה נפלטת. כתוצאה מכך פלט המחולל מתכווץ (ומכאן שמו). שיטה זו יושמה בצופן זרם המכונה FISH, אך סובלת מפגיעות למתקפת תזמון, כיוון שקצב התקדמות היחידה הראשונה תלוי בסיביות "1" של היחידה השנייה.

ישנן שלוש שיטות ידועות ליישום LFSR בצופן זרם:

• סינון פלט של LFSR אחד או יותר על ידי פונקציית בוליאנית אי-ליניארית של מצבים מסוימים מתוך האוגרים.
• תזמון הפעימות של LFSR אחד על ידי הפלט של LFSR אחר או NFSR.
• סינון פלט LFSR אחד או יותר דרך מכונת מצבים.

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

צופן A5/1

צופן A5/1

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

צופן זה התגלה כלא בטוח בתחילה עם עבודתו של גוליק ב-1997, המבוססת על פתרון מערכת משוואות ליניאריות, התקפה שלא הייתה יעילה במיוחד. לאחר מכן הורחבה ושופרה ההתקפה על ידי פרופסור עדי שמיר, אלכס ביריוקוב ודויד וגנר בשנת 2000. הם הורידו את סיבוכיות ההתקפה על הצופן, באמצעות חישוב מוקדם של כ-300 גיגה-בית של נתונים. מיד לאחריהם הציעו פרופסור אלי ביהם ואור דונקלמן התקפה משופרת יותר המסתמכת על זרם של $2^{20}$ נתונים (קריאים), ידוע מראש. בשנים 2003 ו-2004 נמצאו שיטות פיצוח טובות אף יותר על ידי אקדהל, יוהנסון ומקסימוב, בעזרתן אפשר לפצח את הצופן בתוך מספר דקות בהסתמך על מספר שניות של זרם נתונים ידוע.

צופן E0

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

E0 הוא צופן זרם סינכרוני ששימש בעבר לאבטחת פרוטוקול התקשורת של רשת בלוטות'. הוא מבוסס על צופן זרם חיבורי מעל שדה סופי $GF(2^{n})$ של רופל ומסי מ-1986. הצופן פועל עם מפתח הצפנה בגודל 128 סיביות. המחולל הפנימי מייצר 'זרם מפתח' פסאודו-אקראי באורך הרצוי שמחובר על ידי אופרטור XOR עם חבילות המידע סיבית אחר סיבית ומסונכרן מחדש אחרי כל חבילה. הפענוח פועל בדיוק כמו ההצפנה. המחולל הפנימי מייצר סיבית מפתח אחת בכל אות שעון באמצעות ארבעה אוגרי זיזה ממושבים (LFSR) בגדלים שונים; 25, 31, 33 ו-39 סיביות בהתאמה, בסך הכול 128 סיביות וכולל בנוסף יחידת חיבור (summation combiner) ויחידת מיזוג אי-ליניארית (blend machine) שיחד מהווים אוטומט סופי עם זיכרון של ארבע סיביות המייצגות בסך הכול 16 מצבים שונים. 128 הסיביות הראשוניות של מצבו הפנימי של הצופן נגזרות מהמחולל עצמו. דהיינו הפעלת המחולל עם מצב ראשוני המכיל את מפתח ההצפנה המסופק על ידי המשתמש, 48-סיביות כתובת ההתקן, מונה חבילה שנקרא master clock בגודל 26 סיביות וכן מספר אקראי בגודל 128 סיביות. סיביות הפלט הללו משמשות לאתחול תהליך ההצפנה. כל הפולינומים המשמשים להזנה פרימיטיביים ומשקלם הבינארי הוא 5 (הם מכילים רק חמשה אחדות בייצוגם הבינארי). הפולינומים הם:

$f_{1}(t)=t^{25}+t^{20}+t^{12}+t^{8}+1$

$f_{2}(t)=t^{31}+t^{24}+t^{16}+t^{12}+1$

$f_{3}(t)=t^{33}+t^{28}+t^{24}+t^{4}+1$

$f_{4}(t)=t^{39}+t^{36}+t^{28}+t^{4}+1$

בכל מחזור זמן תכולת האוגרים מוזזת בסיבית אחת כלפי מטה (ימינה כמתואר בתרשים), הסיבית העליונה מתעדכנת בהתאם לפונקציית ההיזון המתאימה, למשל באוגר הראשון הסיביות 25, 20, 12, 8 ו-1 מחוברות ב-XOR והתוצאה מוזנת בסיבית העליונה. הסיביות במיקומים 24, 24, 32 ו-32 מארבעת האוגרים בהתאמה מחוברים ב-XOR עם סיבית הפלט של האוטומט הסופי כשהתוצאה היא חלק מזרם המפתח. האוטומט הסופי מתעדכן על ידי סכום סיביות הפלט של ארבעת האוגרים.

E0 התגלה כלא בטוח, אפשר לפרוץ את הצופן בפחות מ-$2^{64}$ צעדים בשיטת הפרד ומשול. למרות זאת הוא עדיין נמצא בשימוש.

ביטחון

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

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

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

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

כל מחרוזת סיביות ניתנת לייצוג על ידי נוסחת נסיגה רקורסיבית כלשהי של מחרוזת סיביות קצרה יותר. כלומר אפשר לבטא כל סיבית ברצף כצירוף ליניארי כלשהו של מספר סיביות קודמות. הצירוף הקצר ביותר איתו ניתן לבטא מחרוזת סיביות נתונה נקרא הסיבוכיות הליניארית של המחרוזת. אלגוריתם ברלקמפ-מסי (Berlekamp-Massey) יעיל בחישוב נוסחת הנסיגה של מחרוזת סיביות מעל שדה בינארי וכתוצאה מכך בחישוב הסיבוכיות הליניארית שלה. סיבוכיות ליניארית חשובה בניתוח בטיחות צופן זרם המבוסס על LFSR כיוון שכדי להשיג מחזוריות מרבית, הערך הראשוני של האוגר חשוב. אפשר לראות את LFSR כפולינום מעל השדה המורחב $\ {\boldsymbol {F}}_{2^{n}}$ שמקדמיו הם 0 או 1, המקדמים הם סיביות המחולל, שחלקם משמשים כמקדמים לחישוב סיבית ההזנה בשלב העליון. ה-LFSR מקסימלי (כלומר מייצר רצף בעל מחזוריות מקסימלית) רק אם הפולינום המייצג אותו פרימיטיבי ומספר הסיביות במחולל זוגי.

כיום מקובל שמחזוריות של $2^{32}$ נחשבת קטנה מדי ברוב היישומים. מקובל שתהיה מחזוריות של לפחות $2^{64}$.

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

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

צופני זרם מודרניים שמנצלים LFSR משתמשים ביחידות גדולות עם מצב פנימי בגודל 160 סיביות ומעלה ובשיטות שילוב לא ליניאריות בדומה לצופן בלוקים. לדוגמה SOSEMANUK הוא צופן זרם מודרני שמנצל טכניקות מתקדמות ממספר אלגוריתמים ידועים כמו סרפנט ו-SNOW וכולל מצב פנימי שמנוהל על ידי LFSR בעל עשר יחידות בגודל $2^{32}$ ומכונת מצבים בגודל 64 סיביות.

eSTREAM

ערך מורחב – eSTREAM

eSTREAM הוא פרויקט אירופאי לתיקנון צופן זרם בעל פוטנציאל להפצה בקנה מידה גדול שהוקם על ידי הארגון European Network of Excellence for Cryptology. הפרויקט החל ב-2004 והסתיים ב-2008 כאשר במהלכו נבדקו אלגוריתמים לצופן זרם בשני מסלולים מקבילים, פרופיל 1 - צופן זרם המיושם בתוכנה עם קצב העברה גבוה. פרופיל 2 - צופן זרם המיושם בחומרה (עם משאבים ויכולת אחסון מוגבלים).

להלן רשימת האלגוריתמים המובילים:

פרופיל 1 - תוכנה	פרופיל 2 - חומרה
HC-128	Grain
Rabbit	MICKEY
Salsa20	Trivium
SOSEMANUK	-

קישורים חיצוניים

• מאמר טכני על צופני זרם, מעבדות RSA יולי 1995.

• הספר Handbook of Applied Cryptography

הערות שוליים

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