Salsa20

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

Salsa20 הוא צופן זרם שפותח ב-2005 על ידי דניאל ברנשטיין באוניברסיטת אילינוי בשיקגו[1] והוצע עבור פרויקט eSTREAM[2] האירופאי. ב-2008 נבחר על ידי eSTREAM בסיבוב השלישי (Phase 3), כאחד מארבעת האלגוריתמים המובילים במסגרת פרופיל 1 בקטגוריית צופן זרם בתוכנה. הגרעין של Salsa20 הוא פונקציה פסאודו-אקראית הפועלת על קלט ופלט בגודל 64 בתים ומיושמת כצופן זרם במצב מונה. הפונקציה מקבלת מפתח הצפנה סודי באורך 128 או 256 סיביות, ערך ייחודי חד-פעמי באורך 64 סיביות הנקרא Nonce ומשמש כוקטור אתחול, מונה המייצג את מספר הבלוק באורך 64 סיביות וקבועים נוספים. על ידי גיבוב הערכים הללו כשהם משולבים יחד, מייצרת פלט פסאודו-אקראי באורך 64 בתים, אותו מחברים בחיבור בינארי עם בלוק טקסט קריא לקבלת טקסט מוצפן. אפשר להצפין עם מפתח אחד עד 2^{70} בתים של מידע. המבנה הזה מעניק לצופן יתרון ביכולת לשחזר כל בלוק ספציפי מהטקסט המוצפן בזמן קבוע. מימוש ממוטב של צופן Salsa יכול להגיע ליעילות בסדר גודל של כמעט 14 מחזורי שעון לבית או כ-643 מגה לשנייה (לעומת RC4 שמגיע לסדר גודל של 200 מגה לשנייה בקירוב). נכון לשנת 2014 נחשב Salsa לצופן בטוח ולא ידוע על התקפה יעילה נגדו.

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

Salsa20 הוא צופן זרם סינכרוני (שבו המפתח מופק ללא תלות בטקסט הקריא או המוצפן), הפועל על יחידת מידע בגודל 64 בתים. השלד העיקרי מורכב מפונקציית גיבוב הכוללת שילוב של שלוש פעולות אריתמטיות פשוטות; חיבור מודולו 2^{32} המבוצע במילים בגודל 32 סיביות, חיבור מודולו 2 (המסומן XOR) והזזה מעגלית (rotation) על מילים (הזזה של כל סיביות המילה שמאלה או ימינה במספר פוזיציות לפי פרמטר, כאשר הסיביות הקיצוניות שנפלטות מצד אחד מוחזרות מהצד השני). ומפיקה פלט בגודל 64 בתים פסאודו-אקראיים שמרכיבים את 'המצב הפנימי' של הצופן. פונקציית הגיבוב הופכת לפונקציית הצפנה בשיטת ורנם, שבה תוצאת הגיבוב הופכת למפתח הצפנה מורחב בגודל 16 מילים. בלוק הטקסט הקריא בגודל 16 מילים מוצפן מילה אחר מילה, בדרך זו: c_i=m_i\oplus k_i. הפענוח זהה, כיוון ש-XOR הופכי של עצמו. סדר הפעולות הוא "או-מוציא של חיבור לאחר הזזה מעגלית" בקיצור ARX (ראשי תיבות של שלוש הפעולות לפי הסדר האמור). שילוב זה הוכח כבטוח כנגד התקפה דיפרנציאלית (ראה להלן) וכן מבטיח עמידות כנגד התקפת תזמון (timing attack).

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

את המצב ההתחלתי (initial state) של פונקציית הגיבוב של Salsa מאתחלים בערכים הבאים:

  1. 8 מילות מפתח. מפתח ההצפנה המסופק על ידי המשתמש בסך הכול 256 סיביות, מחולק לשמונה מילים של 32 סיביות. במקרה של מפתח 128 סיביות מכפילים פעמיים לקבלת 8 מילים.
  2. 2 מילות מונה. קידוד של מספר שלם בגודל 64 סיביות המזהה את מספר הבלוק הנוכחי, מתחיל באפס ומקודם באחד לאחר כל הצפנה של בלוק, כך שבכל הצפנה מתקבל מפתח אחר. המונה מאפשר לשחזר את זרם המפתח ששימש להצפנת בלוק נתון ובכך לפענחו ללא תלות בבלוקים האחרים.
  3. 2 מילות Nonce. ערך ייחודי בגודל 64 סיביות המשמש פעם אחת בלבד עבור מסר נתון (המכיל בלוק אחד או יותר) ואינו בהכרח סודי. בדרך כלל בוחרים מספר פסאודו-אקראי או מספר רץ. בתקן eSTREAM הוא מכונה וקטור אתחול (iv). ערך זה מבטיח שלא יהיו שני מסרים שונים שיוצפנו באותו מפתח. ייחודיותו של ערך זה באחריות המשתמש.
  4. 4 מילים קבועות. שהם (16 בתים) של קידוד המחרוזת "expand 32-byte k" (כולל רווחים) במקרה של מפתח 256 סיביות או המחרוזת "expand 16-byte k" במקרה של מפתח 128 סיביות.

את הערכים המתוארים פורסים לתוך מצב הראשוני ב-64 בתים לפי הסדר הבא. אם המפתח הוא בגודל 256 סיביות (לפי ההמלצה של המַפַתֵּח דניאל ברנשטיין), תחילה ממירים את מחרוזות הטקסט הקבועות לארבע מילים לפי סדר בתים קטן, סך הכול ארבע אותיות במילה. למשל קוד האסקי של "e" הוא 101 ובייצוג הקסדצימלי \mbox{0x65}, של "x" הוא \mbox{0x78} ושל "p" \mbox{0x70} וכן הלאה. אחרי המרה של המחרוזת למילים בייצוג הקסדצימלי מתקבל:

\sigma_0=(\text{65,78,70,61}), \sigma_1=(\text{6E,64,20,33}), \sigma_2=(\text{32,2D,62,79}), \sigma_3=(\text{74,65,20,6B})

וקטור האיתחול מיוצג על ידי v ומונה הבלוקים מיוצג על ידי i. אם המפתח בגודל 256 סיביות מחלקים אותו לשני מקטעים בני 16 בתים כל אחד k_0,k_1 ומשרשרים את כל החלקים יחד במבנה הבא:

1 2 3 4 5 6 7 8
בתים 1-4 5-20 21-24 25-32 33-40 41-44 45-60 61-64
ערך \sigma_0 k_0 \sigma_1 v i \sigma_2 k_1 \sigma_3

עבור מפתח 128 סיביות קיים רק מפתח k אחד בגודל 16 בתים וערכי המחרוזת "expand 16-byte k" בחלוקה למילים הם:

\tau_0=(\text{65,78,70,61}), \tau_1=(\text{6E,64,20,31}), \tau_2=(\text{36,2D,62,79}), \tau_3=(\text{74,65,20,6B})

והמבנה המתקבל הוא:

1 2 3 4 5 6 7 8
בתים 1-4 5-20 21-24 25-32 33-40 41-44 45-60 61-64
ערך \tau_0 k \tau_1 v i \tau_2 k \tau_3


תיאור הפונקציה הפנימית QuarterRound של צופן Salsa

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

הפונקציה השוכנת בליבו של צופן סלסה z_0,...,z_3=\mbox{QuarterRound}(y_0,...,y_3) (ראה תרשים), היא פונקציה הפיכה המקבלת 4 מילים ומפיקה פלט של 4 מילים כדלהלן:

z_1=y_1\oplus ((y_0\boxplus y_3)\lll_7)
z_2=y_2\oplus ((z_1\boxplus y_0)\lll_9)
z_3=y_3\oplus ((z_2\boxplus z_1)\lll_{13})
z_0=y_0\oplus ((z_3\boxplus z_2)\lll_{18})

הסימן \boxplus מייצג חיבור מודולו 2^{32}, הסימן \lll מייצג הזזה מעגלית שמאלה במספר פוזיציות לפי הערך שלימינו והסימן \oplus מייצג XOR. לדוגמה בייצוג הקסדצימלי בחישוב \mbox{QuarterRound}(1,0,0,0) מתקבל: (z_0=\text{0x8008145},z_1=\mbox{0x80},z_2=\text{0x10200},z_3=\text{0x20500000})

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

הפונקציה RowRound מפעילה את הפונקציה QuarterRound על 16 מילים y_0,...,y_{15} באופן הבא:

(z_0, z_1, z_2, z_3) = \mbox{QuarterRound}(y_0, y_1, y_2, y_3)
(z_5, z_6, z_7, z_4) = \mbox{QuarterRound}(y_5, y_6, y_7, y_4)
(z_{10}, z_{11}, z_8, z_9) = \mbox{QuarterRound}(y_{10}, y_{11}, y_8; y_9)
(z_{15}, z_{12}, z_{13}, z_{14}) = \mbox{QuarterRound}(y_{15}, y_{12}, y_{13}, y_{14})

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

\begin{pmatrix} x_0 & x_1 & x_2 & x_3 \\ x_4 & x_5 & x_6 & x_7 \\ x_8 & x_9 & x_{10} & x_{11} \\ x_{12} & x_{13} & x_{14} & x_{15}  \end{pmatrix}

אם מדמיינים את 16 הבתים לעיל, כמטריצה ריבועית 4x4 מילים (ראה תרשים), הפונקציה ColumnRound דומה לקודמת מלבד זאת שהיא מפעילה את QurterRound על עמודות המטריצה במקום שורות, כדלהלן:

(y_0, y_4, y_8, y_{12}) = \mbox{QuarterRound}(x_0, x_4, x_8, x_{12})
(y_5, y_9, y_{13}, y_1) = \mbox{QuarterRound}(x_5, x_9, x_{13}, x_1)
(y_{10}, y_{14}, y_2, y_6) = \mbox{QuarterRound}(x_{10}, x_{14}, x_2, x_6)
(y_{15}, y_3, y_7, y_{11}) = \mbox{QuarterRound}(x_{15}, x_3, x_7, x_{11})

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

שתי הפונקציות המתוארות כשהן משולבות יחד נקראות DoubleRound דהיינו כל מילה מעובדת פעמיים, פעם אחת כחלק משורות במטריצה ופעם אחת כעמודות, בניסוח פורמלי: \mbox{DoubleRound}(x_0,...,x_{15})=\mbox{RowRound}(\mbox{ColumnRound}(x_0,...,x_{15})).

כמו כן, לצורך הפעולות האריתמטיות, המעבר ממערך של ארבעה בתים למילה אחת הוא לפי סדר בתים קטן שאומר שהבית הראשון מייצג את הספרות הפחות משמעותיות של המילה, לכן במחשב עם סדר בתים גדול, יש צורך בפונקציית המרה כדי להמיר מבתים למילים ובחזרה לפי הנוסחה: b_0+2^8b_1+2^{16}b_2+2^{24}b_3. לדוגמה אם נתון מערך הבתים: \{ b_0=86,b_1=75,b_2=30,b_3=9 \} בהמרה למילה בת 32 סיביות לפי סדר בתים קטן, יתקבל הערך 152,980,310 (לפי סדר בתים גדול מתקבל 1,447,763,456).

אם מסכמים את כל הפעולות יחד, מימוש הפונקציה DoubleRound ייראה כך:

ColumnRound RowRound

x_{4} = x_{4} \oplus \mbox{ROTL}_{7}(x_{0} \boxplus x_{12})

x_{8} = x_{8} \oplus \mbox{ROTL}_{9}(x_{4} \boxplus x_{0})

x_{12} = x_{12} \oplus \mbox{ROTL}_{13}(x_{8} \boxplus x_{4})

x_{0} = x_{0} \oplus \mbox{ROTL}_{18}(x_{12} \boxplus x_{8})

x_{9} = x_{9} \oplus \mbox{ROTL}_{7}(x_{5} \boxplus x_{1})

x_{13} = x_{13} \oplus \mbox{ROTL}_{9}(x_{9} \boxplus x_{5})

x_{1} = x_{1} \oplus \mbox{ROTL}_{13}(x_{13} \boxplus x_{9})

x_{5} = x_{5} \oplus \mbox{ROTL}_{18}(x_{1} \boxplus x_{13})

x_{14} = x_{14} \oplus \mbox{ROTL}_{7}(x_{10} \boxplus x_{6})

x_{2} = x_{2} \oplus \mbox{ROTL}_{9}(x_{14} \boxplus x_{10})

x_{6} = x_{6} \oplus \mbox{ROTL}_{13}(x_{2} \boxplus x_{14})

x_{10} = x_{10} \oplus \mbox{ROTL}_{18}(x_{6} \boxplus x_{2})

x_{3} = x_{3} \oplus \mbox{ROTL}_{7}(x_{15} \boxplus x_{11})

x_{7} = x_{7} \oplus \mbox{ROTL}_{9}(x_{3} \boxplus x_{15})

x_{11} = x_{11} \oplus \mbox{ROTL}_{13}(x_{7} \boxplus x_{3})

x_{15} = x_{15} \oplus \mbox{ROTL}_{18}(x_{11} \boxplus x_{7})

x_{1} = x_{1} \oplus \mbox{ROTL}_{7}(x_{0} \boxplus x_{3})

x_{2} = x_{2} \oplus \mbox{ROTL}_{9}(x_{1} \boxplus x_{0})

x_{3} = x_{3} \oplus \mbox{ROTL}_{13}(x_{2} \boxplus x_{1})

x_{0} = x_{0} \oplus \mbox{ROTL}_{18}(x_{3} \boxplus x_{2})

x_{6} = x_{6} \oplus \mbox{ROTL}_{7}(x_{5} \boxplus x_{4})

x_{7} = x_{7} \oplus \mbox{ROTL}_{9}(x_{6} \boxplus x_{5})

x_{4} = x_{4} \oplus \mbox{ROTL}_{13}(x_{7} \boxplus x_{6})

x_{5} = x_{5} \oplus \mbox{ROTL}_{18}(x_{4} \boxplus x_{7})

x_{11} = x_{11} \oplus \mbox{ROTL}_{7}(x_{10} \boxplus x_{9})

x_{8} = x_{8} \oplus \mbox{ROTL}_{9}(x_{11} \boxplus x_{10})

x_{9} = x_{9} \oplus \mbox{ROTL}_{13}(x_{8} \boxplus x_{11})

x_{10} = x_{10} \oplus \mbox{ROTL}_{18}(x_{9} \boxplus x_{8})

x_{12} = x_{12} \oplus \mbox{ROTL}_{7}(x_{15} \boxplus x_{14})

x_{13} = x_{13} \oplus \mbox{ROTL}_{9}(x_{12} \boxplus x_{15})

x_{14} = x_{14} \oplus \mbox{ROTL}_{13}(x_{13} \boxplus x_{12})

x_{15} = x_{15} \oplus \mbox{ROTL}_{18}(x_{14} \boxplus x_{13})

הפונקציה \mbox{ROTL} היא פונקציית הזזה מעגלית לשמאל והמספר התחתי מציין את מספר הפוזיציות שיש להזיז. הזזה מעגלית ניתנת ליישום בתוכנה בקריאה לפונקציית ספרייה או באמצעות הזזות Shift ו-OR המובנות ברוב שפות התיכנות, למשל הביטוי: (value << count) | (value >> (32 - count)) מבצע הזזה מעגלית של value במספר פוזיציות לפי count.

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

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

\mbox{Salsa20}(x_0,...,x_{15})=(x_0,...,x_{15})+\mbox{DoubleRound}^{10}(x_0,...,x_{15}).

כלומר מחלקים את הקלט x ל-16 מילים x_0 עד x_{15}, אותם מחשבים באמצעות פונקציית DoubleRound עשר פעמים. ופלט הפונקציה הוא תוצאת החיבור מודולו 2^{32} עם מילות המצב הראשוני x_0 עד x_{15}. המציין מעל הפונקציה DoubleRound מייצג את מספר החזרות. כיוון שהפונקציה הפנימית מבוצעת פעמיים (בשורות ובעמודות) מסומן הצופן בקיצור Salsa20, כלומר ביצוע \mbox{DoubleRound}^{10}, נחשב כ-20 סבבים.

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

עם פלט פונקציית הגיבוב Slasa20 המתוארת, אפשר להצפין מסר m באורך מקסימלי של 2^{70} בתים כשהוא מחולק לבלוקים בגודל 64 בתים, עם וקטור האתחול v, המונה i כאשר 0 \le i \le 2^{64}-1 והמפתח k באופן הבא:

c_i=\mbox{Salsa20}_k(v,i)\oplus m_i.

לאחר הצפנת 2^{70} בתים יש לאתחל את הצופן עם וקטור איתחול חדש ולהתחיל את המונה מאפס או להחליף מפתח. כאמור v לא חייב להיות סודי אך חייב להיות ייחודי. מעשית יכול להיות מונה כלשהו. לפענוח פועלים באופן זהה לחלוטין:

m_i=\mbox{Salsa20}_k(v,i)\oplus c_i.

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

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

ב-2005 דווח על סוג של ההתקפה דיפרנציאלית נגד גרסה מצומצמת של סלסה בחמשה סבבים, מסומן בקיצור Salsa20/5 בסיבוכיות זמן של 2^{165} בקירוב. מפתח ההתקפה זכה באלף דולר מאת דניאל ברנשטיין שהבטיח את הפרס לכל מי שיצליח להציג "קריפטואנליזה הכי מעניינת של סלסה"‏[3]. ב-2006 הצליחו מספר חוקרים לפתח התקפה כנגד Salsa20/6 בסיבוכיות זמן של 2^{177} וכן התקפת Related key על Salsa20/7 בזמן של 2^{217}[4]. ב-2007 פותחה התקפה על Salsa20/8 בזמן של 2^{255} עם 2^{11.37} מפתחות‏[5]. ב-2008 פותחה התקפה נגד Salsa20/7 בזמן של 2^{153} וכן התקפה על Salsa20/8 בזמן של 2^{251}. ב-2012 התקפה של אמסון ושי כנגד Salsa20/8 הצליחה לשבור את הצופן בזמן של 2^{109} או בזמן של 2^{250} במקרה של מפתח 256 סיביות עם 8 סבבים‏[6]. ב-2013 פורסמה הוכחה‏[7] שצופן סלסה מעל 15 סבבים בטוח כנגד התקפה דיפרנציאלית, כלומר לא נמצאו מאפיינים דיפרנציאליים בהסתברות גבוהה מ-2^{-130} כך שהיא אינה יעילה מכוח גס.

ראו גם[עריכת קוד מקור | עריכה]

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

  1. ^ Snuffle 2005: the Salsa20 encryption function
  2. ^ eSTREAM: the ECRYPT Stream Cipher Project
  3. ^ Truncated differential cryptanalysis of five rounds of Salsa20
  4. ^ Simon Fischer, Willi Meier, Côme Berbain, Jean-Francois Biasse, Matt Robshaw, Non-Randomness in eSTREAM Candidates Salsa20 and TSC-4, Indocrypt 2006
  5. ^ Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki and Hiroki Nakashima (2007-01-02)
  6. ^ Zhenqing Shi, Bin Zhang, Dengguo Feng, Wenling Wu (2012): „Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha“. Information Security and Cryptology – ICISC 2012. Springer Verlag, 2013, pp. 337-351
  7. ^ Nicky Mouha, Bart Preneel (2013)