צופן זרם
מתוך ויקיפדיה, האנציקלופדיה החופשית
צופן זרם (Stream Cipher) מהווה משפחה חשובה של צופנים סימטריים, המצפינים יחידות מידע קטנות (בדרך כלל סיביות או בתים) בזה אחר זה, תוך שימוש בטרנספורמציית מפתח דינמית, המשתנה תוך כדי תהליך ההצפנה. בניגוד לצופן בלוקים, המצפין גושי מידע גדולים (גם במקביל) ובטרנספורמציית מפתח קבועה. בחומרה, צופן זרם מהיר יותר ומכיל מעגלים פחות מורכבים. שימושי במיוחד באפליקציות תקשורת נתונים, בהם הזכרון מוגבל או לא קיים כלל. או כאשר יש צורך בהצפנה ושידור של יחידות מידע קטנות בכל פעם, כאשר אורך המסר אינו ידוע מראש. לצופן זרם יש יתרון ברור על פני צופן בלוקים גם במקרים בהם כשל בשידור, עלול לקרות בתדירות גבוהה כגון בתקשורת אלחוטית, מאחר ואינו מכיל כשל מצטבר.
תוכן עניינים |
[עריכה] מאפייני צופן זרם
צופני זרם קיימים מזה שנים רבות ושימשו בעיקר בתקשורת אלחוטית, במיוחד למטרות צבאיות. כבר במלחמת העולם הראשונה יושמו צופני זרם במכונות פרימיטיביות מבוססות רוטור כמו המכונה הגרמנית לורנץ שהשתמש בה הצבא הגרמני במלחמת העולם השנייה. צבאות בעלות הברית השתמשו אף הם באופן נרחב, בצופן זרם לתקשורת נתונים בין הפיקוד לבין היחידות הפועלות בשטח. צופני זרם מהירים מאוד בחומרה ומאפשרים שימוש במעגלים פשוטים וקלים לתפעול ותחזוקה. חלק ממכונות ההצפנה הפרימיטיביות שיישמו צופני זרם בזמן המלחמה היו טובות למדי, אולם כשלים במילוי הוראות בטיחות הקלו על מנתחי הצפנים של סוכנויות מודיעין בפיצוח הצופנים. ידוע למשל כי, רשלנות במילוי אחר הוראות בטיחות מצד מפעילי האניגמה, סייעה בידי מנתחי הצפנים בבלצ'לי פארק לפענח את התשדורות המוצפנות שנעשו על יזה.
מרבית צופני הזרם, מוגנים בזכויות יוצרים ובדרך כלל גם סודיים. בשל עובדות אלו, מטבע הדברים, קיים תיעוד דל יחסית, אודות אלגוריתמים של צופני זרם, שהם נחלת הציבור.
ניתן ליישם צופן זרם בעזרת הצפנה סימטרית וגם אסימטרית. ההבחנה העקרית בין צופן זרם לצופן בלוקים מלבד גודל הגושים, הוא באופן הטיפול במפתח. צופן זרם משנה את המפתח תוך כדי תהליך ההצפנה, לא רק בהתבסס על המסר או המפתח, אלא גם על פי מה שמכונה "מצב" (state) הזרם הנוכחי, לעיתים תוך שימוש ביחידות זמן מוגדרות.
למרות התכונות הטובות של צופני זרם, השימוש בהם מחייב זהירות רבה, בשל רגישותם לסוגי התקפות שונות כמו התקפות המבוססות על נתונים סטטיסטיים של הזרם האקראי של המחולל, במיוחד כאשר המסר המקורי ידוע לתוקף וכן התקפת קורלציה.
[עריכה] פנקס חד פעמי
צופן זרם בסיסי מיושם באופן פשוט ביותר. זרם-הנתונים מחובר בחיבור בינארי (XOR) עם זרם-מפתח סודי אקראי. כאשר בטיחות הצופן תלויה באקראיות זרם המפתח. עיקר העבודה בצופן זרם היא יצירת זרם המפתח. הדוגמה הקלאסית לצופן זרם נקראת One-time pad (פנקס חד פעמי), הרעיון מבוסס על צופן ורנם (Vernam), צופן המוגדר מעל אלפבית בינארי, כדלהלן: עבור תו ה-i במסר m בצע:
. אם זרם המפתח
מיוצר באופן אקראי (אמיתי), ללא תלות במסר כלל ואם אורך המפתח זהה לאורך המסר, אזי צופן זה מוגדר כצופן מושלם והוא בטוח לחלוטין. עובדה שהוכחה מתמטית על ידי קלוד שנון. אולם בשל הקושי שבהכנה מוקדמת של זרם מפתח אקראי באורך המסר, צופני זרם משתמשים במחולל אקראי יעיל ומהיר, המייצר זרם-מפתח פסאודו-אקראי (מדומה) באורך זרם הנתונים, מתוך מפתח קצר כגון 128 סיביות. אולם עקב כך, בטיחותו אינה עוד מוכחת כפנקס חד-פעמי, מאחר וזרם המפתח אינו אקראי אמיתי ובטיחות הצופן תלויה במידת אקראיות המפתח.
[עריכה] סוגי צופן זרם
ניתן להבחין בשני סוגי צופן זרם עיקריים:
- צופן זרם סינכרוני
- צופן זרם בו זרם המפתח מופק באופן עצמאי, ללא תלות בזרם הנתונים והצופן ורק לאחר מכן משולב עם זרם הנתונים בחיבור בינארי, כמו בפנקס חד-פעמי. בשיטה זו נדרש תזמון מדויק בין המשדר לבין המקבל, אם סיביות מסוימות בזרם הצופן חסרות, הפענוח יהיה משובש ויהיה צורך בהפעלת תהליך סינכרוניזציה.
- צופן זרם א-סינכרוני
- צופן זרם (שמוגן בפטנט) בו זרם המפתח הוא פונקציה של המפתח עצמו ומספר קבוע של תווי צופן קודמים, או "מצבים" קודמים. יתרונו בכך שבמקרה של כשל בשידור, הצופן יסתנכרן לבד לאחר מספר קבוע של תווי צופן.
[עריכה] LFSR
דרך נפוצה להפקת זרם מפתח בעל תכונות אקראיות טובות, היא בעזרת מה שקרוי Feedback shift register, במיוחד הגרסה הלינארית שנקראת LFSR. הסיבות לשימוש ב-LFSR הן: נוחות יישום בחומרה, מחזוריות גבוהה, תוכנות אקראיות טובות וקלות ניתוח ובדיקה בעזרת טכניקות אלגבריות. מחולל LFSR הוא מעגל אלקטרוני המתנהג כמכונת מצבים, שמייצר זרם סיביות באורך מוגדר, הנראה לעין כאקראי.
אוגר הזזה LFSR פשוט מורכב ממספר שלבים או יחידות, שכל אחד מהם מסוגל לאחסן סיבית אחת בלבד, לקלוט סיבית אחת ולפלוט סיבית אחת. מעל שלבים אלו שולטת יחידת בקרה, או שעון עצר. ובכל מחזור זמן מתבצעים המהלכים הבאים:
- תכולת השלב התחתון (הסיבית הנמוכה), מהווה חלק מזרם הפלט.
- תכולת כל השלבים מוזזת, כלפי מטה שלב אחד (Shift).
- והתכולה החדשה של השלב העליון, היא סיבית ההזנה המחושבת בעזרת פעולה לינארית כלשהי, כמו חיבור בינארי מודולו 2 (XOR) של תכולת מספר קבוע של שלבים קודמים, לא בהכרח עוקבים.
סוג אחר Nonlinear Feedback shift register הגרסה הלא לינארית של המחולל, דומה לקודמת מלבד זאת שבכל מחזור זמן, תכולת השלב העליון היא תוצאה של מה שקרוי Feedback function, פונקציה בוליאנית לא-לינארית, המקבלת כקלט מספר קבוע של שלבים קודמים, לא בהכרח עוקבים ומחזירה סיבית אחת.
[עריכה] יישומי צופן זרם באמצעות LFSR
כיוון ש-LFSR לינארי במהותו, הוא קל לניתוח ולבדיקה, ישנם אלגוריתמים לבדיקת מחזוריות, סיבוכיות לינארית ונתונים סטטיסטיים אחרים אודות המחולל. אולם בשל כך, אין להשתמש בזרם LFSR יחיד, כמפתח הצפנה. כדי למנוע מתקפה על הצופן, כאשר זרם הנתונים ידוע מראש. ביישומים מעשיים, צופן זרם משלב בדרך כלל, כמה יחידות LFSR יחדיו באופן כזה שמסיר את לינאריות המחולל. כגון, שילוב מספר יחידות LFSR בקומבינציה לא לינארית כלשהי. או שימוש בפילטר לא לינארי על פלט LFSR יחיד בכך פעולת המחולל אינה קבועה. למשל אפשר לעצור את פעולת יחידת LFSR אחת, על פי תוצאת מחולל LFSR אחר, במקרה שתוצאת המחולל הראשון היא אפס, הפלט יהיה חזרה על מצב קודם של ה-LFSR הראשון שיטה זו מכונה Stop/go. או בשיטה המכונה Shrinking Generator, המיישמת מחוללי LFSR באופן כזה, אם תוצאת מחולל אחד היא 1, תוצאת המחולל השני תהווה חלק מזרם הפלט, אם תוצאתו 0, אז מתעלמים מתוצאת המחולל השני, במצב כזה אף סיבית אינה נפלטת (שיטה זו יושמה בצופן זרם המכונה FISH). שיטה זו סובלת מפגיעות למתקפת תזמון על המחולל השני, כיוון שקצב התקדמות המחולל הראשון תלוי בסיביות 1 של המחולל השני.
צופני זרם מודרניים עושים שימוש בכמה יחידות LFSR ובשיטות שילוב לא לינארית כלשהן. דוגמה לצופן זרם מודרני היא אלגוריתם A5/1 שיושם בעבר בטכנולוגיית GSM במכשירי טלפון ניידים. A5/1 הוא צופן זרם המייצר זרם מפתח באמצעות מחולל המורכב משלושה יחידות LFSR באורך שונה ומשתמש בטכניקה Stop/go האמורה. המחולל מאותחל בעזרת מפתח בגודל 64 סיביות. תוצאת המחולל בכל מחזור זמן, היא XOR של הסיבית הנמוכה של שלושת יחידות ה-LFSR, בהתבסס על סיבית תזמון, הממוקמת בכל יחידה במיקום שונה. כאשר התוצאה נקבעת לפי "החלטת" רוב סיביות התזמון.
צופן זה התגלה כלא בטוח בתחילה עם עבודתו של גוליק ב-1997, המבוססת על פתרון מערכת משוואות לינאריות, התקפה שלא הייתה יעילה במיוחד. לאחר מכן הורחבה ושופרה על ידי פרופסור עדי שמיר, אלכס ביריוקוב ודויד וגנר בשנת 2000, הם הורידו את סיבוכיות ההתקפה על הצופן, באמצעות חישוב מוקדם של כ-300 גיגה-בית של נתונים. מייד לאחריהם הציעו פרופסור אלי ביהם ואור דונקלמן התקפה משופרת יותר המסתמכת על זרם של 220 נתונים (קריאים), ידוע מראש. בשנים 2003 ו-2004 נמצאו שיטת פיצוח אף טובות יותר על ידי אקדהל, יוהנסון ומקסימוב בעזרתם אפשר לפצח את הצופן בתוך מספר דקות בהסתמך על מספר שניות של זרם נתונים ידוע.
[עריכה] בטיחות
מחולל LFSR הוא מחזורי. כלומר לאחר מספר סופי של סיביות פלט, המחולל מתחיל לחזור על עצמו. במקרה כזה נוצרת חפיפה, כאשר חלק מזרם הנתונים מוצפן בעזרת אותם סיביות מפתח. קיימות טכניקות בעזרתם ניתן לחלץ בקלות רבה, את זרם הנתונים מתך הצופן במקרה של חפיפה. לדוגמה, מחזוריות של 232 נחשבת קטנה מדי ברוב היישומים. להשגת מחזוריות מרבית, הערך הראשוני של האוגר חשוב. אפשר לראות את LFSR כפולינום מעל השדה המורחב
שמקדמיו הם 0 או 1, כאן המקדמים הם סיביות המחולל, שחלקם משמשים כמקדמים לחישוב סיבית ההזנה בשלב העליון. ה-LFSR מקסימלי (כלומר מייצר רצף בעל מחזוריות מקסימלית) רק אם הפולינום האמור פרימיטיבי ומספר הסיביות במחולל זוגי.
[עריכה] צופני זרם בתוכנה
בעקרון יישומים של LFSR יעילים בחומרה ולא בתוכנה. לאחרונה, פותחו מספר צופני זרם המעוצבים במיוחד עבור תוכנה. ביניהם אפשר למנות את RC4 של רונלד ריבסט צופן הזרם הראשון שעוצב במיוחד לתוכנה וכן SEAL. צופן בלוקים מיושם לעיתים במצבי הפעלה המדמים צופן זרם. למשל במצב OFB אפשר ליישם צופן בלוקים כמו AES באופן כזה שפלט הצופן מתנהג כצופן זרם לכל דבר.
[עריכה] eSTREAM
eSTREAM הוא פרויקט בחירת צופן זרם בעל פוטנציאל להפצה בקנה מידה גדול שהוקם על ידי הארגון האירופאי European Network of Excellence for Cryptology. הפרויקט החל ב-2004 ואמור להמשך עד 2008 כאשר במהלכו נבדקים אלגוריתמים לצופן זרם בשני מסלולים מקבילים, צופן זרם המיושם בחומרה (עם משאבים ויכולת אחסון מוגבלים). וצופן זרם המיושם בתוכנה עם קצב העברה גבוה.
[עריכה] קישורים חיצוניים
- מאמר טכני על צופני זרם, מעבדות RSA יולי 1995.

