צופן זרם

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

מאפייני צופן זרם[עריכת קוד מקור | עריכה]

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

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


פנקס חד פעמי[עריכת קוד מקור | עריכה]

צופן זרם באופן הבסיסי ביותר פשוט מאוד. זרם-הנתונים מחובר בדרך כלל בחיבור בינארי מודולו 2 (XOR) סיבית אחר סיבית עם זרם-מפתח סודי וחד פעמי. בטיחות הצופן תלויה במידת אקראיות זרם המפתח. עיקר העבודה היא יצירת זרם המפתח שאמור להיות קשה לניחוש. הדוגמה הקלאסית לצופן זרם נקראת One-time pad (פנקס חד פעמי), הרעיון מבוסס על צופן ורנם המוגדר מעל אלפבית בינארי כדלהלן: עבור התו ה-\ i במסר \ m בצע: \ c_i = m_i \oplus k_i. אם זרם המפתח \ k_1, k_2, k_3, ... מיוצר באופן אקראי (אמיתי), ללא תלות במסר כלל וכן אם אורך המפתח זהה לאורך המסר, אזי צופן זה מוגדר כצופן מושלם והוא בטוח לחלוטין. עובדה שהוכחה מתמטית על ידי קלוד שנון. אולם בשל הקושי המעשי שבהכנה מוקדמת של זרם מפתח אקראי ארוך, צופני זרם מסתייעים במחולל אקראי מובנה, המייצר זרם-מפתח פסבדו-אקראי באורך זרם הנתונים, מתוך מפתח קצר יותר כגון 128 סיביות. אולם כתוצאה מכך, בטיחותו אינה מוחלטת כפנקס חד-פעמי, מאחר שזרם המפתח אינו באמת אקראי. כיוון שבטיחות הצופן תלויה באקראיות זרם המפתח, יש קשר הדוק בין צופן זרם למספרים אקראיים.

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

סוגי צופן זרם[עריכת קוד מקור | עריכה]

ניתן להבחין בשני סוגי צופן זרם עיקריים:

SincStream.jpg
צופן זרם סינכרוני
צופן זרם שבו זרם המפתח מופק באופן עצמאי, ללא תלות בזרם הנתונים והצופן ורק לאחר מכן משולב עם זרם הנתונים ב-XOR. יתרונו הוא ששיבוש בשידור סיבית אחת לא משפיע על יתר הסיביות. במילים אחרות לצופן אין כשל מצטבר. לשיטה זו חסרון בכך שאין דרך לאתר תקלות בזמן פענוח ויתרה מזו, לתוקף יש יכולת לשלוט במערכת על ידי ביצוע שינויים בסיביות מסוימות וללמוד את ההשלכות שלהם על התוצאה. כל סיבית שונה תשפיע על הסיבית המקבילה בפלט הצופן. מלבד זאת, נדרש תזמון מדויק בין המשדר לבין המקבל, אם סיבית אחת בזרם הצופן חסרה, הפענוח מנקודה זו ואילך יהיה משובש ויהיה צורך בהפעלת תהליך סינכרוניזציה. עקב כך נהוג לשלב סיביות זוגיות כדי ליצור 'נקודות סינכרון'.
AsincStream.jpg
צופן זרם א-סינכרוני
נקרא גם צופן זרם בעל "סינכרון עצמי", הוא צופן זרם בו זרם המפתח הוא פונקציה של המפתח עצמו ומספר קבוע של סיביות צופן קודמות, או "מצבים" קודמים. אם למשל הצופן תלוי ב-\ c סיביות קודמות אזי לצופן כשל מצטבר מוגבל. כלומר חסרונה של סיבית אחת ישפיע אך ורק על \ c הסיביות הבאות. לאחר מכן הצופן מסתנכרן מעצמו וחוזר להיות תקין. על כן מתאים במיוחד במקרים בהם קשה לשמור על סינכרוניזציה. חסרונו הוא בכך ששינוי סיבית מסוימת משפיע על יותר מסיבית אחת בפלט הצופן. בנוסף, בשל התלות בסיביות קודמות, יש קשר בין פלט הצופן לבין המסר ועל כן יש קושי בניתוח בטיחותו.

LFSR[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – LFSR

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

LFSR 8STAGES.jpg

אוגר הזזה 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" של היחידה השנייה.

צופן A5/1[עריכת קוד מקור | עריכה]

צופן A5/1

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

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

ביטחון[עריכת קוד מקור | עריכה]

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

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

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

סיבוכיות לנארית[עריכת קוד מקור | עריכה]

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

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

צפני זרם מודרניים[עריכת קוד מקור | עריכה]

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

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

eSTREAM[עריכת קוד מקור | עריכה]

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

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]


הערות שוליים[עריכת קוד מקור | עריכה]