ไลร่า2

Lyra2เป็นระบบแฮชรหัสผ่าน (PHS) ที่สามารถทำหน้าที่เป็นฟังก์ชันการสร้างคีย์ (KDF) ได้ด้วย ได้รับการยอมรับในระหว่างการแข่งขันแฮชรหัสผ่านในเดือนกรกฎาคม 2558 ^{[ 1 ]} ซึ่ง Argon2เป็นผู้ชนะนอกจากนี้ยังใช้ในอัลกอริธึมพิสูจน์การทำงาน เช่น Lyra2REv2 ^{[ 2 ]}ซึ่ง Vertcoin ^{[ 3 ]}และ MonaCoin ^{[ 4 ]} นำมาใช้ ในสกุลเงินดิจิทัลอื่นๆ^{[ 5 ]}

Lyra2 ได้รับการออกแบบโดย Marcos A. Simplicio Jr., Leonardo C. Almeida, Ewerton R. Andrade, Paulo CF dos Santos และPaulo SLM BarretoจากEscola Politécnica da Universidade de São Paulo ^{[ 6 ]}มันขึ้นอยู่กับไลรา^{[ 7 ] [ 8 ]}ซึ่งถูกสร้างขึ้นโดยทีมเดียวกัน Lyra2 ประกอบด้วย:

• ความสามารถในการกำหนดค่าปริมาณหน่วยความจำ เวลาประมวลผล และการทำงานแบบขนานตามที่ต้องการสำหรับอัลกอริทึม
• มีการ ใช้หน่วยความจำสูงและใช้เวลาประมวลผลใกล้เคียงกับscrypt

นอกจากนี้ ยังมี: ^{[ 9 ]}

• ช่วยเพิ่มความปลอดภัยในการป้องกันข้อจำกัดด้านเวลาและหน่วยความจำ
• ช่วยให้ผู้ใช้ที่ได้รับอนุญาตสามารถใช้ประโยชน์จากความสามารถในการประมวลผลแบบขนานของแพลตฟอร์มของตนเองได้ดียิ่งขึ้น
• ทำให้ต้นทุนในการสร้างฮาร์ดแวร์เฉพาะเพื่อโจมตีอัลกอริทึมเพิ่มสูงขึ้น
• สร้างสมดุลในการต้านทานภัยคุกคามและการโจมตีจากช่องทางด้านข้างโดยใช้หน่วยเก็บข้อมูลราคาถูกและช้ากว่า

Lyra2 ได้ถูกปล่อยสู่สาธารณะแล้ว

เช่นเดียวกับ PHS อื่นๆ Lyra2 รับค่าsaltและรหัสผ่านเป็นอินพุต สร้าง เอาต์พุต แบบสุ่มเทียมที่สามารถใช้เป็นวัสดุสำคัญสำหรับอัลกอริธึมการเข้ารหัสหรือเป็นสตริงการตรวจสอบความถูกต้องได้^{[ 10 ]}

ภายในระบบ หน่วยความจำของแผนการนี้ถูกจัดระเบียบเป็นเมทริกซ์ซึ่งคาดว่าจะคงอยู่ในหน่วยความจำตลอดกระบวนการแฮชรหัสผ่านทั้งหมด เนื่องจากเซลล์ของเมทริกซ์นี้จะถูกอ่านและเขียนซ้ำๆ การทิ้งเซลล์เพื่อประหยัดหน่วยความจำจึงทำให้จำเป็นต้องคำนวณเซลล์นั้นใหม่ทุกครั้งที่มีการเข้าถึงอีกครั้ง จนกว่าจะถึงจุดที่มีการแก้ไขครั้งล่าสุด^{[ 5 ]}

การสร้างและการเยี่ยมชมเมทริกซ์นั้นกระทำโดยใช้การผสมผสานสถานะของการดูดซับ การบีบอัด และการทำสำเนาของฟองน้ำ พื้นฐาน (กล่าวคือ สถานะภายในของมันจะไม่ถูกรีเซ็ตเป็นศูนย์) ซึ่งทำให้มั่นใจได้ถึงลักษณะที่เป็นลำดับของกระบวนการทั้งหมด

นอกจากนี้ จำนวนครั้งที่เซลล์ของเมทริกซ์จะถูกตรวจสอบซ้ำหลังจากเริ่มต้นการทำงานจะถูกกำหนดโดยผู้ใช้ ซึ่งช่วยให้สามารถปรับแต่งเวลาในการทำงานของ Lyra2 ให้เหมาะสมกับทรัพยากรของแพลตฟอร์มเป้าหมายได้

• รหัสผ่าน
• เกลือ
• t_cost - เวลาในการดำเนินการ
• m_cost - หน่วยความจำที่ต้องการ
• เอาท์เลน

นอกจากนี้ อัลกอริทึมยังช่วยให้สามารถกำหนดพารามิเตอร์ได้ในแง่ของ: ^{[ 11 ]}

• ระดับของการทำงานแบบขนาน (จำนวนเธรด )${\displaystyle p}$
• ฟังก์ชันการเรียงสับเปลี่ยนพื้นฐาน (สามารถมองได้ว่าเป็นองค์ประกอบพื้นฐานหลักของการเข้ารหัส)
• จำนวนบล็อกที่ใช้โดยฟังก์ชันการเรียงสับเปลี่ยนพื้นฐาน ( บิตเรต )
• จำนวนรอบที่ดำเนินการสำหรับฟังก์ชันการเรียงสับเปลี่ยนพื้นฐาน ( )${\displaystyle \rho }$
• จำนวนบิตที่จะใช้ในการหมุน ( )${\displaystyle \omega }$
• ความยาวเอาต์พุต( )${\displaystyle \kappa }$

||

รวมสตริงสองสตริงเข้าด้วยกัน

^

XOR แบบบิตไวส์

[+]

การดำเนินการบวกแบบคำต่อคำ (เช่น การไม่สนใจตัวทดระหว่างคำ)

%

โมดูลัส

W

ขนาดคำของเครื่องเป้าหมาย (โดยปกติคือ 32 หรือ 64)

omega

จำนวนบิตที่จะใช้ในการหมุน (แนะนำ: ควรเป็นจำนวนเท่าของขนาดคำ (W) ของเครื่อง)

>>>

การหมุนขวา

rho

จำนวนรอบสำหรับการบีบอัดที่ลดลงหรือการทำงานแบบดูเพล็กซ์

blen

ขนาดบล็อกของ Sponge ในหน่วยไบต์

H or H_i

ฟองน้ำที่มีขนาดบล็อก blen (เป็นไบต์) และการเรียงสับเปลี่ยนพื้นฐาน f

H.absorb(input)

การดูดซับของฟองน้ำเมื่อได้รับอินพุต

H.squeeze(len)

การบีบอัดของ Sponge ที่ใช้ len ไบต์

H.squeeze_{rho}(len)

การบีบอัดข้อมูลของ Sponge โดยใช้ไบต์ len จำนวน n รอบของ f

H.duplexing(input,len)

การดำเนินการแบบดูเพล็กซ์ของ Sponge บนข้อมูลขาเข้า ทำให้ได้ข้อมูลขนาด len ไบต์

H.duplexing_{rho}(input,len)

การดำเนินการแบบดูเพล็กซ์ของ Sponge บนอินพุต โดยใช้ f จำนวน rho รอบ ทำให้ได้ข้อมูลขนาด len ไบต์

pad(string)

เติมช่องว่างให้กับสตริงให้มีจำนวนไบต์เป็นจำนวนเท่าของ blen (กฎการเติมช่องว่าง: 10*1)

lsw(input)

คำที่มีความสำคัญน้อยที่สุดในการป้อนข้อมูล

len(string)

ความยาวของสตริง (หน่วยเป็นไบต์)

syncThreads()

ซิงโครไนซ์เธรดคู่ขนาน

swap(input1,input2)

สลับค่าของอินพุตสองตัว

C

จำนวนคอลัมน์ในเมทริกซ์หน่วยความจำ (โดยทั่วไปคือ 64, 128, 256, 512 หรือ 1024)

P

ระดับความขนาน ( P >= 1และ(m_cost/2) % P == 0)

**ขั้นตอนการบูตสแตรป: เริ่มต้นสถานะและตัวแปรภายในของฟองน้ำ** # การแสดงผลแบบไบต์ของพารามิเตอร์อินพุต (สามารถเพิ่มพารามิเตอร์อื่นๆ ได้) params = outlen || len(password) || len(salt) || t_cost || m_cost || C # เริ่มต้นสถานะของฟองน้ำ (หลังจากนั้น สามารถเขียนทับรหัสผ่านได้) H.absorb( pad(password || salt || params) ) # เริ่มต้นขั้นตอนการเยี่ยมชม ช่วงเวลา และแถวแรกที่จะใช้ในการป้อนข้อมูล ช่องว่าง = 1 stp = 1 wnd = 2 รากที่สอง = 2 prev0 = 2 แถวที่ 1 = 1 prev1 = 0 **ขั้นตอนการตั้งค่า: เริ่มต้นเมทริกซ์หน่วยความจำขนาด (m_cost x C) โดยที่เซลล์ในเมทริกซ์มีขนาด 1/2 ไบต์ # เริ่มต้นค่า M[0], M[1] และ M[2] สำหรับ col = 0 ถึง C-1 M[0][C-1-col] = H.squeeze_{rho}(blen) สำหรับ col = 0 ถึง C-1 M[1][C-1-col] = H.duplexing_{rho}( M[0][col], เบลน) สำหรับ col = 0 ถึง C-1 M[2][C-1-col] = H.duplexing_{rho}( M[1][col], เบลน) # ลูปการเติม: เริ่มต้นแถวที่เหลือ สำหรับแถวที่ 0 = 3 ถึง m_cost-1 # ลูปคอลัมน์: M[row0] ถูกกำหนดค่าเริ่มต้น และ M[row1] ถูกอัปเดต สำหรับ col = 0 ถึง C-1 rand = H.duplexing_{rho}( M[row1][col] [+] M[prev0][col] [+] M[prev1][col], เบลน) M[row0][C-1-col] = M[prev0][col] ^ rand M[row1][col] = M[row1][col] ^ ( rand >>> omega ) # แถวที่จะกลับมาตรวจสอบอีกครั้งในลูปถัดไป prev0 = แถวที่ 0 prev1 = แถวที่ 1 row1 = (row1 + stp) % wnd # กลับมาดูหน้าต่างกันอีกครั้งอย่างเต็มรูปแบบ ถ้า (row1 = 0) # เพิ่มหน้าต่างเป็นสองเท่าและปรับขั้นตอน wnd = 2 * wnd stp = sqrt + gap ช่องว่าง = -ช่องว่าง # คูณรากที่สองทุกๆ สองรอบ ถ้า (ช่องว่าง = -1) รากที่สอง = 2 * รากที่สอง **ขั้นตอนการเคลื่อนที่: เขียนทับเซลล์แบบสุ่มเทียมของเมทริกซ์หน่วยความจำซ้ำๆ** # ลูปการเยี่ยมชม: เยี่ยมชมแถว (2 * m_cost * t_cost) แถวซ้ำในลักษณะสุ่มเทียม สำหรับ wCount = 0 ถึง ( (m_cost * t_cost) - 1) # เลือกแถวแบบสุ่มเทียม row0 = lsw(rand) % m_cost row1 = lsw( rand >>> omega ) % m_cost # ลูปคอลัมน์: อัปเดตทั้ง M[row0] และ M[row1] สำหรับ col = 0 ถึง C-1 # เลือกคอลัมน์แบบสุ่มเทียม col0 = lsw( ( แรนด์ >>> โอเมก้า ) >>> โอเมก้า ) % C col1 = lsw( ( ( แรนด์ >>> โอเมก้า ) >>> โอเมก้า ) >>> โอเมก้า ) % C rand = H.duplexing_{rho}( M[row0][col] [+] M[row1][col] [+] M[prev0][col0] [+] M[prev1][col1], เบลน) M[row0][col] = M[row0][col] ^ rand M[row1][col] = M[row1][col] ^ ( rand >>> omega ) # การวนซ้ำครั้งต่อไปจะตรวจสอบแถวที่มีการอัปเดตล่าสุดอีกครั้ง prev0 = แถวที่ 0 prev1 = แถวที่ 1 **ขั้นตอนสรุป: การคำนวณผลลัพธ์** # ดูดซับคอลัมน์สุดท้ายด้วยฟองน้ำทรงกลมเต็มรูปแบบ H.absorb( M[row0][0] ) # บีบเอาเศษอาหารส่วนเกินออกด้วยฟองน้ำทรงกลม output = H.squeeze(outlen) # ให้ผลลัพธ์เป็นสตริงบิตความยาว outlen-long ส่งคืนผลลัพธ์

สำหรับแต่ละ i ในช่วง [0..P] **ขั้นตอนการบูตสแตรป: เริ่มต้นสถานะและตัวแปรภายในของฟองน้ำ** # การแสดงผลแบบไบต์ของพารามิเตอร์อินพุต (สามารถเพิ่มพารามิเตอร์อื่นๆ ได้) params = outlen || len(password) || len(salt) || t_cost || m_cost || C || P || i # เริ่มต้นสถานะของฟองน้ำ (หลังจากนั้น สามารถเขียนทับรหัสผ่านได้) H_i.absorb( pad(password || salt || params) ) # เริ่มต้นขั้นตอนการเยี่ยมชม ช่วงเวลา และแถวแรกที่จะใช้ในการป้อนข้อมูล ช่องว่าง = 1 stp = 1 wnd = 2 รากที่สอง = 2 ซิงค์ = 4 j = i prev0 = 2 rowP = 1 prevP = 0 **ขั้นตอนการตั้งค่า: เริ่มต้นเมทริกซ์หน่วยความจำขนาด (m_cost x C) โดยที่เซลล์ในเมทริกซ์มีขนาด 1/2 ไบต์ # เริ่มต้นค่า M_i[0], M_i[1] และ M_i[2] สำหรับ col = 0 ถึง C-1 M_i[0][C-1-col] = H_i.squeeze_{rho}(blen) สำหรับ col = 0 ถึง C-1 M_i[1][C-1-col] = H_i.duplexing_{rho}( M_i[0][col], blen) สำหรับ col = 0 ถึง C-1 M_i[2][C-1-col] = H_i.duplexing_{rho}( M_i[1][col], blen) # ลูปการเติม: เริ่มต้นแถวที่เหลือ สำหรับแถวที่ 0 = 3 ถึง ( (m_cost / P) - 1 ) # ลูปคอลัมน์: M_i[row0] ถูกกำหนดค่าเริ่มต้น และ M_j[row1] ถูกอัปเดต สำหรับ col = 0 ถึง C-1 rand = H_i.duplexing_{rho}( M_j[rowP][col] [+] M_i[prev0][col] [+] M_j[prevP][col], เบลน) M_i[row0][C-1-col] = M_i[prev0][col] ^ rand M_j[rowP][col] = M_j[rowP][col] ^ ( rand >>> omega ) # แถวที่จะกลับมาตรวจสอบอีกครั้งในลูปถัดไป prev0 = แถวที่ 0 prevP = rowP rowP = (rowP + stp) % wnd # กลับมาดูหน้าต่างกันอีกครั้งอย่างเต็มรูปแบบ ถ้า (rowP = 0) # เพิ่มหน้าต่างเป็นสองเท่าและปรับขั้นตอน wnd = 2 * wnd stp = sqrt + gap ช่องว่าง = -ช่องว่าง # คูณรากที่สองทุกๆ สองรอบ ถ้า (ช่องว่าง = -1) รากที่สอง = 2 * รากที่สอง # จุดซิงโครไนซ์ ถ้า (แถวที่ 0 = ซิงค์) sync = sync + (sqrt / 2) j = (j + 1) % P syncThreads() syncThreads() **ขั้นตอนการเคลื่อนที่: เขียนทับเซลล์แบบสุ่มเทียมของเมทริกซ์หน่วยความจำซ้ำๆ** wnd = m_cost / (2 * P) ซิงค์ = รากที่สอง off0 = 0 offP = wnd # วงวนการเยี่ยมชม: เยี่ยมชมแถว (2 * m_cost * t_cost / P) แถวซ้ำในลักษณะสุ่มเทียม สำหรับ wCount = 0 ถึง ( ( (m_cost * t_cost) / P) - 1) # เลือกแถวและส่วนแบบสุ่มเทียม (j) row0 = off0 + (lsw (แรนด์) % wnd) rowP = offP + (lsw( rand >>> omega ) % wnd) j = lsw( ( แรนด์ >>> โอเมก้า ) >>> โอเมก้า ) % P # ลูปคอลัมน์: อัปเดต M_i[row0] สำหรับ col = 0 ถึง C-1 # เลือกคอลัมน์แบบสุ่มเทียม col0 = lsw( ( ( แรนด์ >>> โอเมก้า ) >>> โอเมก้า ) >>> โอเมก้า ) % C rand = H_i.duplexing_{rho}( M_i[row0][col] [+] M_i[prev0][col0] [+] M_j[rowP][col], blen) M_i[row0][col] = M_i[row0][col] ^ rand # การวนซ้ำครั้งต่อไปจะตรวจสอบแถวที่มีการอัปเดตล่าสุดอีกครั้ง prev0 = แถวที่ 0 # จุดซิงโครไนซ์ ถ้า (wCount = sync) ซิงค์ = ซิงค์ + รากที่สอง สลับ(ปิด0,ปิดP) syncThreads() syncThreads() **ขั้นตอนสรุป: การคำนวณผลลัพธ์** # ดูดซับคอลัมน์สุดท้ายด้วยฟองน้ำทรงกลมเต็มรูปแบบ H_i.absorb( M_i[row0][0] ) # บีบเอาเศษอาหารส่วนเกินออกด้วยฟองน้ำทรงกลม output_i = H_i.squeeze(outlen) # ให้ผลลัพธ์เป็นสตริงบิตความยาว outlen-long คืนค่า output_0 ^ ... ^ output_{P-1} 

เมื่อเปรียบเทียบกับ Lyra2 ต้นทุนการประมวลผลของการโจมตีโดยใช้ปริมาณหน่วยความจำที่ผู้ใช้ที่ถูกต้องใช้นั้น คาดว่าจะอยู่ระหว่างและโดยค่าหลังเป็นค่าประมาณที่ดีกว่าสำหรับแทนที่จะเป็นค่าที่ได้เมื่อปริมาณหน่วยความจำคือโดยที่เป็นพารามิเตอร์ที่ผู้ใช้กำหนดเพื่อกำหนดเวลาในการประมวลผล ${\displaystyle 1/2^{n+2}}$${\displaystyle O(2^{2nT}R^{3})}$${\displaystyle O(2^{2nT}R^{n+2})}$${\displaystyle n\gg 1}$${\displaystyle O(R)}$${\displaystyle O(R)}$${\displaystyle T}$

เปรียบเทียบได้ดีกับScryptซึ่งแสดงต้นทุนเมื่อการใช้หน่วยความจำสูง[ ^{12 ]}และกับโซลูชันอื่นๆ ในเอกสาร ซึ่งผลลัพธ์มัก^จะเป็น^{[ 7 ] [ 13 ] [ 14 ] [ 15 ]}${\displaystyle O(R^{2})}$${\displaystyle O(1)}$${\displaystyle O(R^{T+1})}$

อย่างไรก็ตาม ในทางปฏิบัติ โซลูชันเหล่านี้มักจะมีค่า(การใช้หน่วยความจำ) ต่ำกว่าที่ได้จาก Lyra2 สำหรับเวลาประมวลผลเดียวกัน^{[ 16 ] [ 17 ] [ 18 ] [ 19 ] [ 20 ]}${\displaystyle R}$

เวลาประมวลผลที่ได้จากการใช้งาน Lyra2 แบบแกนเดี่ยว SSE แสดงอยู่ในรูปที่แสดงไว้ที่นี่ รูปนี้ดึงมาจาก^{[ 9 ]}และคล้ายคลึงกับเกณฑ์มาตรฐานของบุคคลที่สามที่ดำเนินการในบริบท PHC มาก^{[ 16 ] [ 17 ] [ 18 ] [ 19 ] [ 20 ]}

ผลลัพธ์ที่แสดงสอดคล้องกับเวลาการทำงานเฉลี่ยของ Lyra2 ที่กำหนดค่าด้วย บิต , , (กล่าวคือ สถานะภายในมี 256 บิต) และ การตั้งค่า และ ที่แตกต่างกัน ซึ่งให้ภาพรวมของชุดค่าผสมที่เป็นไปได้ของพารามิเตอร์และการใช้ทรัพยากรที่เกี่ยวข้อง ${\displaystyle C=256}$${\displaystyle \rho =1}$${\displaystyle b=768}$${\displaystyle T}$${\displaystyle R}$

ดังแสดงในรูปนี้ Lyra2 สามารถทำงานได้ในเวลา: น้อยกว่า 1 วินาที โดยใช้หน่วยความจำสูงสุด 400 MB (พร้อมและ) หรือสูงสุด 1 GB (พร้อมและ); หรือน้อยกว่า 5 วินาที โดยใช้หน่วยความจำ 1.6 GB (พร้อมและ) ${\displaystyle R=2^{14}}$${\displaystyle T=5}$${\displaystyle R\approx 4.2\cdot 10^{4}}$${\displaystyle T=1}$${\displaystyle R=2^{16}}$${\displaystyle T=6}$

การทดสอบทั้งหมดดำเนินการบนIntel Xeon E5-2430 (2.20 GHz พร้อม 12 คอร์ 64 บิต) ที่ติดตั้งDRAM ขนาด 48 GB โดยใช้Ubuntu 14.04 LTS 64 บิต และโค้ดต้นฉบับถูกคอมไพล์โดยใช้GCC 4.9.2 ^{[ 9 ]}

Lyra มีส่วนขยายหลักสองส่วน: ^{[ 11 ]}

• Lyra2- δ : ช่วยให้ควบคุมการใช้งานแบนด์วิดท์ของอัลกอริทึมได้มากขึ้น
• Lyra2 p : ใช้ประโยชน์จาก ความสามารถ ในการประมวลผลแบบขนานบนแพลตฟอร์มของผู้ใช้

• เข้ารหัส (C)
• เยสคริปต์
• การเข้ารหัสรหัสผ่าน
• การแข่งขันแฮชรหัสผ่าน

• เว็บไซต์ของ Lyra2
• แหล่งเก็บซอร์สโค้ดของ Lyra2 บน Github