Salsa20

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

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

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

Salsa20 הוא צופן זרם סינכרוני (שבו המפתח מופק ללא תלות בטקסט הקריא או המוצפן), הפועל על יחידת מידע בגודל 64 בתים. השלד העיקרי מורכב מפונקציית גיבוב הכוללת שילוב של שלוש פעולות אריתמטיות פשוטות; חיבור מודולו המבוצע במילים בגודל 32 סיביות, חיבור מודולו 2 (המסומן XOR) והזזה מעגלית (rotation) על מילים (הזזה של כל סיביות המילה שמאלה או ימינה במספר פוזיציות לפי פרמטר, כאשר הסיביות הקיצוניות שנפלטות מצד אחד מוחזרות מהצד השני). ומפיקה פלט בגודל 64 בתים פסאודו-אקראיים שמרכיבים את 'המצב הפנימי' של הצופן. פונקציית הגיבוב הופכת לפונקציית הצפנה בשיטת ורנם, שבה תוצאת הגיבוב הופכת למפתח הצפנה מורחב בגודל 16 מילים. בלוק הטקסט הקריא בגודל 16 מילים מוצפן מילה אחר מילה, בדרך זו: . הפענוח זהה, כיוון ש-XOR הופכי של עצמו. סדר הפעולות בתוך הליבה של Salsa20 הוא "או-מוציא של חיבור לאחר הזזה מעגלית" בקיצור 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" הוא ובייצוג הקסדצימלי , של "x" הוא ושל "p" וכן הלאה. אחרי המרה של המחרוזת למילים בייצוג הקסדצימלי מתקבל:

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

1 2 3 4 5 6 7 8
בתים 1-4 5-20 21-24 25-32 33-40 41-44 45-60 61-64
ערך

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

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

1 2 3 4 5 6 7 8
בתים 1-4 5-20 21-24 25-32 33-40 41-44 45-60 61-64
ערך


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

פונקציית QuarterRound

הפונקציה השוכנת בליבו של צופן סלסה (ראה תרשים), היא פונקציה הפיכה המקבלת 4 מילים ומפיקה פלט של 4 מילים כדלהלן:

הסימן מייצג חיבור מודולו , הסימן מייצג הזזה מעגלית של משתנה באורך 32 סיביות שמאלה במספר פוזיציות לפי הערך שלימינו והסימן מייצג XOR. לדוגמה בייצוג הקסדצימלי בחישוב מתקבל:

פונקציית RowRound

הפונקציה RowRound מפעילה את הפונקציה QuarterRound על 16 מילים באופן הבא:

פונקציית ColumnRound

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

פונקציית DoubleRound

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

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

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

ColumnRound RowRound

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

פונקציית הגיבוב

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

.

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

הצפנה ופענוח

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

.

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

.

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

בטחון ויעילות

ב-2005 דווח על סוג של ההתקפה דיפרנציאלית נגד גרסה מצומצמת של סלסה בחמשה סבבים, מסומן בקיצור Salsa20/5 בסיבוכיות זמן של בקירוב. מפתח ההתקפה זכה באלף דולר מאת דניאל ברנשטיין שהבטיח את הפרס לכל מי שיצליח להציג "קריפטואנליזה הכי מעניינת של סלסה"[3]. ב-2006 הצליחו מספר חוקרים לפתח התקפה כנגד Salsa20/6 בסיבוכיות זמן של וכן התקפת Related key על Salsa20/7 בזמן של [4]. ב-2007 פותחה התקפה על Salsa20/8 בזמן של עם מפתחות[5]. ב-2008 פותחה התקפה נגד Salsa20/7 בזמן של וכן התקפה על Salsa20/8 בזמן של . ב-2012 התקפה של אמסון ושי כנגד Salsa20/8 הצליחה לשבור את הצופן בזמן של או בזמן של במקרה של מפתח 256 סיביות עם 8 סבבים[6]. ב-2013 פורסמה הוכחה[7] שצופן סלסה מעל 15 סבבים בטוח כנגד התקפה דיפרנציאלית, כלומר לא נמצאו מאפיינים דיפרנציאליים בהסתברות גבוהה מ- כך שהיא אינה יעילה מכוח גס.

Salsa20 מהיר יותר מ-AES ובמבחני ביצועים של eSTREAM[8] נמצא שבעשרים סבבים הצופן מסוגל להצפין בקצב של 3.93 מחזורי שעון לבית על Xeon בעל ליבה כפולה 3 גיגה-הרץ. כמו כן קיימות שתי גרסאות של הצופן פחותות סבבים הנקראות Salsa20/8 ו-Salsa20/12 עם שמונה סבבים או 12 סבבים בהתאמה, המיועדים למשתמשים הוראים צורך בצופן יעיל ומוכנים להקריב מעט בביטחונו.

ChaCha

ב-2008 הציע דניאל ברנשטיין את משפחת ChaCha[9] שהיא גרסה משופרת של צפני זרם החולקת אותם עקרונות תכנון עם Salsa20 אך בשינויים קלים שנועדו בעיקר להגברת רמת הפיזור (diffusion) של הצופן. הפיזור הנוסף אינו בא על חשבון ביצועים, כמו ב-Salsa20 בכל סבב מתבצעים 16 פעולות חיבור, XOR והזזה מעגלית בהיסטים קבועים וכן נשמרת אותה רמת מקביליות ואף יותר. ההערכה היא שגרסאות ChaCha מספקות עמידות גבוהה יותר נגד קריפטואנליזה ומשפרות במעט את הביצועים אם כי רק על פלטפורמות מסוימות. בגלל אחידות כמות העבודה בכל סבב, למספר הסבבים השפעה ישירה על ביצועי הצופן. מסיבה זו הוצעו גרסאות מופחתות סבבים לשיפור ביצועים על חשבון בטחון. ChaCha8 מבוסס על Salsa20 עם שמונה סבבים, ChaCha12 על Salsa20 עם 12 סבבים בהתאמה. ההבדלים בין צופן Salsa וצופן ChaCha הם כדלהלן:

פונקציית QuarterRound

פונקציית הסבב הפנימית של ChaCha גם היא מבצעת 4 פעולות חיבור, 4 פעולות XOR ו-4 פעולות הזזה מעגלית על ארבעה משתני המצב הפנימי אך בסדר שונה. ב-Salsa20 כל משתנה מעודכן בפעולה אחת למשל . לעומתו ב-ChaCha כל מילה מעודכנת פעמיים בנפרד, כך שכל מילת קלט משפיעה על מילות קלט אחרות בשני הכיוונים. אפשר לראות על ידי מעקב אחרי כל סיבית כי ב-ChaCha לפחות 12.5 סיביות בממוצע משתנות בכל סבב לעומת רק 8 ב-Salsa20.

בנוסף קיים הבדל פחות משמעותי בערכי ההיסטים הקבועים של ההזזה המעגלית 16,12,8,7 לעומת 7,9,13,18 ב-Salsa20. ההשפעה של הבדל זה על בטחון הצופן זניחה. לעומת זאת קיים שיפור במהירות על פלטפורמות מסוימות.

מטריצת הקלט

בצופן Salsa20 הקלט המורכב מוקטור אתחול ומונה בלוקים וכן שמונה מילות מפתח וארבע מילים קבועות, נטענים לתוך טבלה או מטריצה ראשונית במבנה זה:

קבוע מפתח מפתח מפתח
מפתח קבוע קלט קלט
קלט קלט קבוע מפתח
מפתח מפתח מפתח קבוע

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

קבוע קבוע קבוע קבוע
מפתח קלט מפתח מפתח
קלט מפתח מפתח קלט
מפתח מפתח קלט מפתח

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

קבוע קבוע קבוע קבוע
מפתח מפתח מפתח מפתח
מפתח מפתח מפתח מפתח
קלט קלט קלט קלט

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

ארבעת הרבעים של כל סבב תמיד מסודרים מלמעלה למטה מה שמוסיף מהיבט של מהירות. פונקציית הגיבוב BLAKE הנמנית עם רשימת הפינלסטים של תחרות הגיבוב של NIST וגרסת ההמשך שלה BLAKE2 מבוססים על ChaCha.

שימושים

ב-2014 אימצה גוגל את ChaCha יחד עם קוד אימות מסרים Poly1305 כתחליף ל-RC4 ב-OpenSSL[10]. כמו כן המימוש של גוגל עבור TLS[11] משמש להגנה על תעבורת הרשת (HTTPS) בין דפדפן כרום לאנדרואיד לבין אתרי גוגל. באופן דומה האלגוריתם שולב בפרוטוקול OpenSSH. הצופן ChaCha נכלל גם במערכות ההפעלה OpenBSD ו-NetBSD[12]. וכן הוצע לפרוטוקול IPSec בטיוטה RFC 7539 וטיוטה RFC 7634. פונקציית הגיבוב BLAKE מבוססת על ליבת צופן ChaCha בשינויים מינוריים.

קוד לדוגמה

להלן קוד C++‎ שלם של צופן ChaCha20 המלא (20 סבבים). למען הבהירות הקוד אינו ממוטב והוא תואם את ההמלצה המופיעה באתר המפתח[13]. ההנחה שהמהדר תומך בסדר בתים קטן. הפונקציה ‎_lrotl‎ היא פונקציית הזזה מעגלית לשמאל הכלולה בספרייה הסטנדרטית של VS. אפשר לשנות את מספר הסבבים בפונקציה ChaCha_encrypt בקריאה לפונקציה Salsa20_Rounds בהתאם לצורך, למשל לגרסת שמונה סבבים יש לציין 8 בפרמטר האחרון, ערכים מומלצים הם 8,12 או 20.

typedef unsigned char byte;
typedef unsigned int uint;

#define BYTES_TO_INT(p) (((uint*)(p))[0])
#define INT_TO_BYTES(p, v) (((uint*)(p))[0] = (v))
#define ROTATE(v,c) (_lrotl(v, c))
#define XOR(v,w) ((v) ^ (w))
#define PLUS(v,w) ( (uint)(((v) + (w)) & 0xFFFFFFFF))
#define PLUSONE(v) (PLUS((v),1))

typedef struct
{
   uint input[16];
} ChaCha_Context;

#define QUARTERROUND(a,b,c,d) \
  x[a] = PLUS(x[a],x[b]); x[d] = ROTATE(XOR(x[d],x[a]),16); \
  x[c] = PLUS(x[c],x[d]); x[b] = ROTATE(XOR(x[b],x[c]),12); \
  x[a] = PLUS(x[a],x[b]); x[d] = ROTATE(XOR(x[d],x[a]), 8); \
  x[c] = PLUS(x[c],x[d]); x[b] = ROTATE(XOR(x[b],x[c]), 7);

static const char sigma[] = "expand 32-byte k";
static const char tau[] = "expand 16-byte k";

static void Salsa20_Rounds(byte output[64], const uint input[16], uint nrounds)
{
	uint x[16];

	for (uint i = 0; i < 16; ++i) 
		x[i] = input[i];

	for (uint i = nrounds; i > 0; i -= 2) {
		QUARTERROUND( 0, 4,  8, 12)
		QUARTERROUND( 1, 5,  9, 13)
		QUARTERROUND( 2, 6, 10, 14)
		QUARTERROUND( 3, 7, 11, 15)
		QUARTERROUND( 0, 5, 10, 15)
		QUARTERROUND( 1, 6, 11, 12)
		QUARTERROUND( 2, 7,  8, 13)
		QUARTERROUND( 3, 4,  9, 14)
	}
	for (uint i = 0; i < 16; ++i) 
		x[i] = PLUS(x[i], input[i]);

	for (uint i = 0; i < 16; ++i) 
		INT_TO_BYTES(output + 4 * i, x[i]);
}


void ChaCha_keysetup(ChaCha_Context *ctx, const byte *k, uint kbits, uint ivbits)
{
	const char *constants;

	ctx->input[4] = BYTES_TO_INT(k + 0);
	ctx->input[5] = BYTES_TO_INT(k + 4);
	ctx->input[6] = BYTES_TO_INT(k + 8);
	ctx->input[7] = BYTES_TO_INT(k + 12);

	if (kbits == 256) { // recommended
		k += 16;
		constants = sigma;
	}
	else { // kbits == 128
		constants = tau;
	}
	ctx->input[8] = BYTES_TO_INT(k + 0);
	ctx->input[9] = BYTES_TO_INT(k + 4);
	ctx->input[10] = BYTES_TO_INT(k + 8);
	ctx->input[11] = BYTES_TO_INT(k + 12);
	ctx->input[0] = BYTES_TO_INT(constants + 0);
	ctx->input[1] = BYTES_TO_INT(constants + 4);
	ctx->input[2] = BYTES_TO_INT(constants + 8);
	ctx->input[3] = BYTES_TO_INT(constants + 12);
}

void ChaCha_ivsetup(ChaCha_Context *ctx, const byte *iv)
{
	ctx->input[12] = 0;
	ctx->input[13] = 0;
	ctx->input[14] = BYTES_TO_INT(iv + 0);
	ctx->input[15] = BYTES_TO_INT(iv + 4);
}

void ChaCha_encrypt(ChaCha_Context *ctx, const byte *m, byte *c, uint bytes)
{
	byte output[64];

	if (!bytes) return;
	for (;;) {
		Salsa20_Rounds(output, ctx->input, 20);
		ctx->input[12] = PLUSONE(ctx->input[12]);
		if (!ctx->input[12]) {
			ctx->input[13] = PLUSONE(ctx->input[13]);
			// stopping at 2^70 bytes per nonce is user's responsibility
		}
		if (bytes <= 64) {
			for (uint i = 0; i < bytes; ++i) c[i] = m[i] ^ output[i];
			return;
		}
		for (uint i = 0; i < 64; ++i) c[i] = m[i] ^ output[i];
		bytes -= 64;
		c += 64;
		m += 64;
	}
}

וקטור בדיקה

מפתח (32 בתים):

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

וקטור אתחול (8 בתים):

00 00 00 00 00 00 00 00

מספר סבבים: 20

64 בתים פסאודו אקראיים הראשונים של פלט הצופן בבסיס הקסדצימלי:

76 b8 e0 ad a0 f1 3d 90 40 5d 6a e5 53 86 bd 28
bd d2 19 b8 a0 8d ed 1a a8 36 ef cc 8b 77 0d c7
da 41 59 7c 51 57 48 8d 77 24 e0 3f b8 d8 4a 37
6a 43 b8 f4 15 18 a1 1c c3 87 b6 69 b2 ee 65 86

ראו גם

הערות שוליים