שידור מוצפן
ויקיפדיה האנציקלופדיה encyclopedia
בקריפטוגרפיה, סכימת שידור מוצפן (באנגלית: Broadcast Encryption) היא טכניקה לשידור יעיל של תוכן מוצפן לקבוצה דינאמית של משתמשים מורשים באופן שרק הם יוכלו לפענחו. כלומר כל המשתמשים שברשותם מקלט מתאים מסוגלים לקלוט את התוכן המשודר, אך רק קבוצה של משתמשים מורשים תוכל ליהנות ממנו, בעוד שהיתר אמורים לראות תוכן בלתי קריא. לעיתים נוח להתייחס לזה כאל 'סכימת ביטול' שמטפלת בצורך למנוע ממקלט אחד או יותר מלקלוט שידור מסוים.
שידור מוצפן לעיתים משולב עם "מנגנון מעקב" שמאפשר להתחקות אחר חשיפת תוכן בלתי חוקית או הפרת זכויות. במיוחד איתור וזיהוי מקור החשיפה, כך שהמערכת תוכל להגיב בהתאם. בדרך זו אפשר להתגונן מפני העתקה בלתי חוקית או שימוש בהתקנים לא חוקיים כמו מפענח פיראטי. יישומים אפשריים של שידור מוצפן כוללים:
- שלם וצפה; שיטות שידור בתשלום של תוכן אחיד למשתמשים מרובים.
- רב-נתיב; פרוטוקול תקשורת לניתוב מידע יחיד לנקודות מרובות.
- וידאו על פי דרישה; שירות אינטראקטיבי להעברת תכנים לפי דרישה.
- הזרמת מדיה; טכניקות העברת מדיה רציפה ומתמשכת על ידי ספקי תוכן.
- זכויות יוצרים; הגבלת גישה והגנה מפני העתקה פיראטית של מדיה דיגיטלית כמו תקן Advanced Access Content System.
- שימוש אפשרי נוסף הוא אבטחת שיתוף מידע במחשוב ענן.
היישומים השונים מכתיבים גישות שונות לניהול ועדכון רשימת המשתמשים הלגיטימיים. משתמשים מוסרים מהרשימה עקב אי תשלום, תפוגה של מנוי או שימוש בלתי הולם. מקרה מיוחד של הבעיה נקרא "State-less", כלומר משתמש לגיטימי לא יוכל להקליט את היסטוריית התכנים שקיבל כדי לשנות את מעמדו באופן שיאפשר לו לראות תכנים בלתי מורשים. במקרה זה ההחלטה האם משתמש רשאי לקבל תוכן מבוקש מתבססת רק על השידור הנוכחי והקונפיגורציה הראשונית שלו. 'משתמש חסר מעמד' נחוץ במקרים בהם השידור מופץ להתקנים שאינם בהכרח מקוונים, כגון נגן DVD במקרה זה ה"שידור" הוא בעצם התקליטור.
הבעיה הכללית שנקראת בעיית שידור מוצפן מתעוררת בתרחישים שונים כמו העברת תכנים בסגנון שלם וצפה והיא כדלהלן: שרת מרכזי מעוניין לשדר תוכן רב לקבוצה גדולה של מקלטים, כך שרק תת-קבוצה מוגדרת מראש תוכל לפענח את התוכן המשודר. דרך נאיבית לפתור את הבעיה היא להפיץ מראש לכל המשתמשים הרשומים במערכת מפתחות הצפנה סודיים, כל משתמש מקבל מפתח שונה. את המפתח הסודי אפשר להעביר בדרך בטוחה כלשהי או להטמיעו בתוך חומרת המקלט באופן בטוח. זה לא מעשי להצפין ולשדר את התוכן עצמו מספר מרובה של פעמים עם מפתח אחר בכל פעם אלא במקום זאת, השרת מכין תחילה מפתח שיחה, מצפין את גוף התוכן, מצפין את המפתח איתו השתמש במספר הפעמים הדרוש עבור כל משתמש מורשה (עם המפתח הסודי המשותף לו ולשרת) ואז משדר את כל המפתחות המוצפנים יחד עם התוכן המוצפן, רק המשתמשים המחזיקים במפתחות המתאימים יוכלו לחלץ את מפתח ההצפנה מהמידע הנלווה ולפענח את התוכן. דרך זו אינה יעילה במיוחד בעיקר ברשת מרובת משתתפים כי נפח המידע שהשרת צריך לשדר מלבד התוכן גדל משמעותית, כלומר גודל המפתחות המוצפנים כפול מספר המשתמשים.
אפשר לחלק את המשתמשים הרשומים לתת-קבוצות (למשל תת-קבוצה אפשרית היא כל המשתמשים שהזמינו תוכן מסוים) ולהקצות מראש לכל תת-קבוצה אפשרית מפתח הצפנה מתאים, כך שהשרת צריך להצפין ולשדר את התוכן רק פעם אחת עבור תת-הקבוצה המתאימה ואינו נדרש לשדר מלבד התוכן שום דבר. אולם במקרה כזה כל משתמש רשום יאלץ להחזיק בכמות עצומה של מפתחות (מפתח אחד עבור כל תת-קבוצה אפשרית שהוא עשוי להיות חבר בה). המטרות הן למצוא דרך מאוזנת שבה כמות המפתחות שמשתמש בודד צריך להחזיק תהיה המינימלית האפשרית, שתעבורת הרשת לא תגדל משמעותית עקב התרחבות המידע המוצפן וכן כמות העבודה שתידרש מכל משתמש כדי לפענח את התוכן שיקבל לא תהיה גבוהה. בכללות התכונות המינימליות הדרושות ממערכת שידור מוצפן הן:
- רוחב פס נמוך; כלומר התרחבות מינימלית של התוכן עקב ההצפנה.
- דרישות אחסון נמוכות; שכל משתמש יאלץ להחזיק בכמות נמוכה ביותר האפשרית של מידע פרטי כמו מפתחות הצפנה.
- זמינות; אפשרות למצב של שידור "חסר מעמד" כך שהמשתמש אינו נדרש להיות מקוון כמו תקליטור.
- עמידות; תכונה חשובה של שידור מוצפן היא היכולת להתנגד לשיתוף פעולה או "קואליציה" של מספר משתמשים כנגד המערכת על מנת לקבל מידע בלתי מורשה.
בדרך כלל יש איזון בין הצורך בביטחון לעומת נוחות. לפעמים מתפשרים בביטחון השידור המוצפן על מנת להבטיח תעבורה גבוהה או תקורה נמוכה. על מנת להעריך או להשוות בין שיטות שידור מוצפן, צריך להגדיר מספר פרמטרים. קבוצת כל המשתמשים הרשומים במערכת מסומנת ב- ומכילה חברים. הקבוצה היא תת-קבוצה המכילה משתמשים בלתי מורשים (Revoked) שיש לבטל את תקפות מפתחות ההצפנה שלהם ולא לאפשר להם ליהנות מהתוכן (כגון, אם לא שילמו עבורו). מייצג את התוכן המיועד לשידור במצבו הגלוי, אותו השרת צריך להצפין ולשדר באופן כזה שרק תת-הקבוצה (המורשים פחות המבוטלים) תוכל לפענחו, בעוד שקואליציה של או פחות משתמשים החברים ב- לא תוכל. אם אחד מהמשתמשים המורשים משתתף בקואליציה לא ניתן להגן על סודיות התוכן. מקרה כזה מוגדר כ'בגידה' והטיפול בה נעשה באמצעות מנגנון מעקב (Traitor tracing) להלן. מערכת שידור מוצפן כוללת שלושה מרכיבים עיקריים:
- סכימת הקצאת מפתח. שהיא שיטת אתחול המייצרת ומפיצה מפתחות הצפנה סודיים לכל המשתמשים הרשומים.
- אלגוריתם שידור. בהינתן תוכן וקבוצה בלתי מורשית מפיק ומשדר את לכל המשתמשים הרשומים.
- אלגוריתם פענוח. משתמש לגיטימי שאינו נכלל בקבוצה המקבל את משחזר את התוכן המקורי באמצעות המפתח הסודי שברשותו משלב 1.
נושא הצפנה משודרת הועלה כבר ב-1991 על ידי שמשון ברקוביץ שהציע שימוש בחלוקת סוד[1] כדי לפתור את הבעיה. הגדרה הפורמלית ראשונה וניתוח יסודי של הבעיה ניתנו ב-1993 על ידי עמוס פיאט ומוני נאור[2]. הם הציעו אלגוריתם המבוסס על עץ בינארי שמאפשר למנוע מכל מספר של משתמשים מלקבל תוכן כל עוד לא יותר מ- מהם משתפים פעולה נגד המערכת. כמות המפתחות המוצפנים היא בסדר גודל של וכל משתמש צריך לאחסן מספר מפתחות שהוא ביחס לוגריתמי ל-. כמות העבודה הנדרשת מכל משתמש היא פענוחים. כמו כן הפרוטוקול תומך בסביבת Stateless ואינו דורש נוכחות (בלתי מקוון).
רעיון השימוש בלוגיקה של עץ היררכי הומצא בנפרד ב-1990 על ידי וולנר (Wallner)[3] וונג (Wong) שפיתחו שיטות לתקשורת בטוחה בתרחיש רב-נתיב (multicast) במצב מקוון. בשיטה זו שנקראת בקיצור LKH (להלן) יש צורך לשדר מפתחות בכל פעם שמעדכנים את הרשימה (מבטלים משתמש), כל משתמש נדרש לאחסן מפתחות וכן כמות העבודה שכל משתמש נדרש לבצע היא פעולות פענוח (בממוצע רק 1). הפרוטוקול בטוח ללא תלות ב- אך כמות המידע המשודר היא שזה יחסית גבוה אלא אם כן כל משתמש יאחסן יותר מידע. הנושא נחקר על ידי רבים אחרים.
השיטה subset difference (להלן) שהוצעה ב-2002 על ידי נאור ולוצפיץ'[4] היא הטובה ביותר למצב Statesless. לפי שיטה זו התוכן המשודר דורש רק הצפנות במקרה הממוצע כדי לבטל משתמשים, כמות האחסון של כל מקבל היא מפתחות. אין הגבלה על וכן תהליך הקצאת המפתח הוא חישובי ולא מסתמך על תורת האינפורמציה. שמיר הלוי ואחרים הציעו שיפור לשיטה זו שנקרא LSD כמות האחסון מצטמצמת לפיה ל- וכמות התוכן היא בפקטור , כאשר יכול 2.
להלן פירוט שלוש שיטות בסיסיות לפתרון בעיית שידור מוצפן שהמכנה המשותף שלהן בתהליך הקצאת המפתחות הוא השימוש במבנה דמוי עץ. מקצים מפתח ראשי לשורש העץ ולכל יתר הצמתים והעלים מקצים מפתחות בשיטת GGM שהוצעה על ידי גולדרייך, גולדווסר ומיקאלי שהיא סוג של פונקציה פסאודו-אקראית.
הבסיס התאורטי למשפחת האלגוריתמים Subset-Cover מתחיל במושג שהגו לראשונה פיאט ונאור[5] שנקרא סכימת ביטול "k-resilient" הפועלת כך שבהינתן קבוצה של חברים, הסכימה תהיה עמידה כנגד קואליציה של עד חברים. לשם כך מקצים מפתחות הצפנה סודיים ונפרדים עבור כל תת-קבוצה אפשרית כאשר , אותו מעבירים לכל משתמש (לכל המשתמשים החברים ב- אך אינם נמנים עם ). אפשר לדמות זאת באנלוגיה למצב שבו המפתחות נרשמים על גבי מצחם של כל המשתמשים, כל אחד יכול לראות את המפתחות של כולם למעט המפתח הרשום על מצחו. אם הקבוצה היא אוסף חברים מורשים, מפתח ההצפנה הסודי עבורם הוא XOR של כל המפתחות כאשר . כל קואליציה של חברים תחסר את המפתח (המשויך להם) ולכן לא תוכל לחלץ את המפתח של בתנאי שמתקיים .
הסכימה המתוארת הוכחה בטוחה מהיבט תאורטי אך אינה יעילה, כדי לכסות את כל האפשרויות, כל משתמש נדרש לאחסן מפתחות (לדוגמה; עבור עשרה משתמשים שמתוכם חמישה מבוטלים, כל משתמש נדרש לאחסן 638 מפתחות). במקרה הפרטי שבו (כלומר רק משתמש אחד מבוטל) מספר המפתחות שכל אחד נדרש לשמור הוא . אפשר לשפר את הסכימה על ידי הסתמכות על פונקציה חד-כיוונית ואז הביטחון אינו אבסולוטי אלא חישובי. מדמים את רשימת המשתמשים לעץ בינארי שכל עלה בו מתאים למשתמש אחד. מקצים מפתח אקראי לשורש העץ ולכל צומת מקצים רקורסיבית מפתח מתאים על ידי פונקציה פסאודו-אקראית שמקבלת קלט מפתח של צומת אב ומפיקה פלט כפול באורכו, מחצית אחת מקצים לבן השמאלי והמחצית השנייה לבן הימני. היתרון שבשיטת בנייה זו הוא שכעת כל משתמש נדרש לדעת בעיקרון רק מפתח של אב קדום כלשהו שלו, כי המפתח שלו הוא תוצאה של הפעלת הפונקציה הפסאודו-אקראית באופן רקורסיבי במסלול מהשורש ועד לעלה שלו. כעת כדי לבטל עלים מסוימים מסירים את המסלולים המקשרים ביניהם לבין שורש העץ, כך למעשה נוצר "יער" של תת-עצים, כל משתמש צריך לקבל כעת את מפתחות של כל שורשי תת-העצים. כעת אם המדיה מוצפנת עם XOR של כל המפתחות המשויכים למשתמשים שהוסרו, כל משתמש יכול לחשב כל מפתח מלבד המפתח המשויך אליו ולכן אינו יכול לחלץ את המפתח לתוכן. המשתמשים המורשים לעומת זאת מקבלים את המפתח כשהוא מוצפן עם המפתח הפרטי שהם משתפים עם השרת.
דרך אחרת היא לבסס את הסכימה על בעיה מתורת המספרים דוגמת RSA. השרת מכין מפתח שורש שהוא , כפולה של שני ראשוניים גדולים, בוחר יוצר מסדר גבוה וכל משתמש מקבל את כאשר כל זרים הדדית. המפתח המשותף לקבוצה הוא כאשר ואז המשתמש מחלץ את המפתח המשותף על ידי כלומר חזקה של כל המפתחות למעט המפתח שלו. הוכח שהסכימה הזו בטוחה בהנחה שפירוק לגורמים היא בעיה קשה וכל מה שנדרש לאחסן הוא רק מפתח אחד.
בשתי הסכימות השרת אינו נדרש לשדר כלל מידע נלווה לתוכן המוצפן, כיוון שהמפתחות הוקצו מראש ובידי המשתמשים המידע הדרוש לחילוץ מפתח השיחה. אולם שיתוף פעולה של שני משתמשים מאפשר להם לשבור בקלות את המערכת. אלגוריתם Complete Subset Cover מרחיב את הרעיון הבסיסי לעמידות כנגד מבוטלים וכן מצמצם את דרישות האחסון ברמת משתמש במחיר שהשרת ישדר לפני כל תוכן מוצפן מידע מסוים שנקרא "כותר". בכללות הוא מגדיר אוסף של תת-קבוצות כאשר . מקצים מפתח סודי ארוך טווח (קבוע) לכל ולכל מקצים מידע פרטי איתו הוא אמור לשחזר את . בהינתן קבוצה של משתמשים מבוטלים יתר המשתמשים מחולקים לתת-קבוצות זרות כך שמתקיים:
- .
מוצפן פעמים עם המפתחות בהתאמה.
לצורך כך יש להגדיר שני פרימיטיבים קריפטוגרפיים: (1) צופן מהצורה להצפנת התוכן עם שצריך להיות חדש עבור כל תוכן. הצופן צריך להיות מהיר ולא אמור לגרום להתנפחות התוכן עקב ההצפנה. הוא יכול להיות צופן זרם בטוח כמו Salsa20. וכן (2) צופן מהצורה עם מפתח ארוך-טווח שהמרכז משתף עם כל משתמש בנפרד. יכול להיות צופן בלוקים כמו AES. מסיבות של יעילות רצוי ש- יהיה קצר (להגנה על זכויות יוצרים אין צורך בהצפנה כבדה) ורק המפתח ארוך הטווח צריך להיות באורך מלא (בדרך כלל 128 סיביות). מפני שאורך הכותר תלוי בגודל הבלוק של צופן הבלוקים, אפשר להשתמש בחלופה חסכונית כך; במקום בלוק מלא. כאשר הביטוי פירושו הסיביות הראשונות של הערך וכן הוא מחרוזת אקראית כלשהי באורך בלוק מלא.
תיאור הסכימה
1. אלגוריתם אתחול
כל משמש מקבל מידע סודי באופן כזה שעבור כל כאשר , מאפשר לו לחלץ את המפתח לקבוצה שלו . את אפשר להכין בשתי דרכים, בחירה אקראית (אמיתית) ונפרדת עבור כל מפתח, מה שמספק ביטחון אבסולוטי מהיבט של תורת האינפורמציה כמו פנקס חד-פעמי או כפונקציה של מידע סודי אחר שאז ביטחונו נשען על הפונקציה הפסאודו-אקראית מה שמספק ביטחון חישובי.
2. אלגוריתם שידור
מרכז שמעוניין לשדר או להפיץ תוכן מוצפן פועל כדלהלן;
- 1. בוחר מפתח שיחה אקראי .
- 2. בהינתן קבוצה של משתמשים מבוטלים, המרכז מפריד את כל המשתמשים הבלתי מבוטלים ל- תת-קבוצות זרות ומקצה להם מפתחות סודיים בהתאמה.
- 3. המרכז מצפין את מפתח השיחה פעמים עם כל המפתחות ומשדר את התוכן כדלהלן:
- החלק שמופיע בסוגריים המרובעות נקרא "כותר" והחלק האחרון הוא גוף התוכן.
3. אלגוריתם פענוח
מקבל מורשה הקולט את השידור: פועל כדלהלן:
- 1. מוצא את כך שמתקיים (תת-הקבוצה אליה הוא שייך) במקרה שהוא נמנה עם הקבוצה התוצאה היא null.
- 2. מחלץ את המפתח המתאים באמצעות .
- 3. מפענח את מפתח השיחה: .
- 4. מפענח את התוכן: .
עיקר העבודה ביישום הסכימה האמורה היא (1) הכנת אוסף של כל תת-הקבוצות האפשריות של המשתמשים הרשומים (2) הקצאת מפתח לכל תת-קבוצה אפשרית באוסף, (3) "כיסוי" כל המשתמשים הלגיטימיים פחות המבוטלים בתת-קבוצות נפרדות ו-(4) הגדרת שיטה שבה כל משתמש יוכל למצוא את המפתח המתאים לקבוצה שלו. אלגוריתם Subset-Cover ניתן למימוש באופן הבא: אוסף הקבוצות מתאים לכל תת-העצים בעץ בינארי מלא בעל עלים, כל עלה כנגד משתמש אחד. סך הכול עלים וצמתים הוא . כל צומת מייצג תת-עץ בעץ הכללי, כל משתמש נמנה עם תת-הקבוצה אך ורק אם שורש תת-הקבוצה הוא אב קדום שלו. לכל צומת מוקצה מפתח וכל משתמש מקבל מפתחות המשויכים לכל הצמתים במסלול המקשר מהעלה שלו לשורש העץ. אם אוסף המשתמשים שייכים לקבוצה , מפרידים את יתר העלים בעץ לתת-קבוצות נפרדות על ידי הכנת "עץ שטיינר" מכוון, בקיצור ( שהוא עץ פורש מינימלי הנוצר על ידי העלים המקושרים לשורש העץ באמצעות תוספת קשתות המינימלית האפשרית. כעת תת-הקבוצות האחרות הן למעשה כל תת-העצים "התלויים", כלומר העצים אשר שורשיהם סמוכים לצמתים בעץ בעלי דרגה 1, אך אינם נמצאים בו. אוסף הקבוצות הללו נקרא "כיסוי" ומספרם הוא בערך . ישנן כמה דרכים כדי למצוא במהירות וביעילות חברות באחת מהקבוצות של משתמש נתון , אפשר להשתמש למשל בטבלת גיבוב או בקוד תיקון שגיאות. רצוי שהמידע בכותר יהיה דחוס ככל האפשר. עם אופטימיזציה אפשר להגיע לתצורה שבה החיפוש נעשה בסיבוכיות של השוואות. כמות המפתחות שכל משתמש יאחסן תעמוד על , מספר המפתחות המוצפנים שהשרת משדר ואילו התוכן מוצפן רק פעם אחת.