Scrypt

Scrypt (מבוטא אס-קריפט) בקריפטוגרפיה היא פונקציית ייצור מפתחות (Key derivation function) מבוססת סיסמה שנוצרה על ידי קולין פרסיבל, במקור עבור שירות הגיבוי המקוון Tarsnap‏. האלגוריתם תוכנן כך שיהיה "יקר" (מבחינת ביצועים, ולכן קשה מעשית) לבצע התקפות חומרה על ידי כך שנדרשת עבורו כמות זיכרון גדולה. בשנת 2016, האלגוריתם פורסם על ידי ה IETF כ-RFC 7914.

גרסה פשוטה יותר של Scrypt משמשת למערכת הוכחת עבודה בכמה מטבעות מבוזרים, בתחילה על ידי מפתח אנונימי בשם ArtForz עבור Tenebrix, ומיד אחר כך עבור Fairbrix ו Litecoin‏.

תיאור

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

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

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

האלגוריתם

האלגוריתם כולל את הפרמטרים הבאים:

• Passphrase - מחרוזת לגיבוב.
• Salt - מחרוזת אשר משנה את הגיבוב, כדי להגן מ"התקפת טבלת קשת" (Rainbow table attacks)
• N - "עלות" מעבד/זיכרון.
• p - פרמטר מיקבול; מספר שלם חיובי המקיים: p ≤ (2³²− 1) * hLen / MFLen.
• dkLen - מיועד לאורך הפלט (octets) של המפתח הנוצר ; מספר שלם חיובי המקיים dkLen ≤ (2³²− 1) * hLen.
• r - גדול בלוק, כוונון של גודל קריאת זיכרון רציפה וביצועים (נפוץ להשתמש ב-8).
• hLen - אורך (octets) של פונקציית הגיבוב של (32 עבור SHA256).
• MFlen - אורך (octets) של הפלט של פונקציית ה"ערבול" (SMix למטה). מוגדר כ r * 128 ב RFC7914.

Function scrypt
Inputs:
Passphrase: Bytes string of characters to be hashed
Salt: Bytes random Salt
CostFactor (N): Integer CPU/memory cost parameter
BlockSizeFactor (r): Integer blocksize parameter (8 is commonly used)
ParallelizationFactor (p): Integer Parallelization parameter. (1..232-1 * hLen/MFlen)
DesiredKeyLen: Integer Desired key length in bytes
Output:
DerivedKey: Bytes array of bytes, DesiredKeyLen long

Step 1. Generate expensive salt
blockSize ← 128*BlockSizeFactor //Length (in bytes) of the SMix mixing function output (e.g. 128*8 = 1024 bytes)

Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data (e.g. 128*8*3 = 3072 bytes)
Treat the result as an array of p elements, each entry being blocksize bytes (e.g. 3 elements, each 1024 bytes)
 [B0...Bp−1] ← PBKDF2HMAC-SHA256(Passphrase, Salt, 1, blockSize*ParallelizationFactor)

Mix each block in B 2CostFactor times using ROMix function (each block can be mixed in parallel)
for i ← 0 to p-1 do
Bi ← ROMix(Bi, 2CostFactor)

All the elements of B is our new "expensive" salt
expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1 //where ∥ is concatenation

Step 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generated
return PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);

Function ROMix(Block, Iterations)

Create Iterations copies of X
X ← Block
for i ← 0 to Iterations−1 do
Vi ← X
X ← BlockMix(X)

for i ← 0 to Iterations−1 do
//Convert first 8-bytes of the last 64-byte block of X to a UInt64, assuming little endian (Intel) format
j ← Integerify(X) mod N
X ← BlockMix(X xor Vj)

return X

כאשר Integerify היא פונקציית bijective מתוך {0, 1}^k עד {0,...,2^k− 1}.

Function BlockMix(B):

The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)
r ← Length(B) / 128;

Treat B as an array of 2r 64-byte chucks
 [B0...B2r-1] ← B

X ← B2r−1
for i ← 0 to 2r−1 do
X ← Salsa20/8(X xor Bi) //Salsa20/8 hashes from 64-bytes to 64-bytes
Yi ← X

return ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1

כאשר Salsa20/8 היא גירסת 8-סיבובים של Salsa20.

הערות שוליים

הערך באדיבות ויקיפדיה האנגלית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0