리라2

Lyra2

Lyra2는 KDF(Key Delection Function)로도 사용할 수 있는 PHS(Password Hashing Scheme)입니다.2015년 7월 Argon2가 수상한 Password Hashing 대회에서 특별한 인정을 받았습니다.[1]본래의 목적으로 사용되는 것 외에 Lyra2와 같은 작업 증명 알고리즘의 핵심이기도 합니다.Vertcoin,[3][4] MonaCoin이 채택한 Rev2는 [2]다른 암호화[5] 화폐 Lyra2가 Marcos A가 설계했다.심플리시오 주니어, 레오나르도 C.알메이다, 에워튼 R.안드라데, 파울로 C에스코라 폴리티케치니카 다 유니버시다데 데 상파울루의 [6]F. dos Santos와 Paulo S. L. M. Barreto.이것은 이전에 같은 저자가 제안한 [7][8]Lyra에 비해 개선된 것입니다.Lyra2는 (1) 알고리즘에서 사용하는 메모리 용량, 처리 시간 및 병렬 처리를 구성하는 기능, (2) 스크립트에서 얻은 처리 시간과 동일한 처리 시간으로 높은 메모리 사용량을 제공하는 기능 등 이전 모델의 보안, 효율성 및 유연성을 유지합니다.또한 이전 [9]버전과 비교하여 다음과 같은 개선 사항이 있습니다.

  • 타임메모리 트레이드오프를 수반하는 공격 장소에 대한 고도의 보안 수준을 실현합니다.
  • 정규 사용자는 자신의 플랫폼의 병렬 처리 기능을 통해 보다 효과적으로 혜택을 받을 수 있습니다.
  • 알고리즘을 공격하기 위한 전용 하드웨어 구축과 관련된 비용을 증가시키기 위한 조정을 포함합니다.
  • 저렴한(따라서 속도가 느린) 스토리지 디바이스에 의존하는 측면 채널의 위협 및 공격에 대한 저항의 균형을 유지합니다.
  • Lyra2는 퍼블릭 도메인으로 출시되며 다음 두 가지 주요 [10]확장을 제공합니다.
  • Lyra2-timeout을 통해 알고리즘의 대역폭 사용률을 보다 효율적으로 제어할 수 있습니다.
  • Lyra2p는 정규 사용자 플랫폼에서 병렬 처리 기능을 활용합니다.

이 알고리즘은 [10]다음 관점에서 파라미터화를 활성화합니다.

  • 실행 시간(시간 T T
  • 필요한 메모리( 수및 수
  • 병렬도( p p
  • 기본 치환 함수(주 암호 프리미티브로 볼 수 있음)
  • 기본 순열 함수에 사용되는 블록 수(비트레이트)
  • 치환 기능에 대해 수행된 라운드 수( {\
  • 시 사용되는 비트 수( \ \)
  • 출력길이

힘

알고리즘의 주요 강점은 다음과 같습니다.[5][10]

  • 프로세싱과 메모리의 트레이드오프에 대한 높은 저항성: 메모리 사용량이 적은 공격의 예상 프로세싱 비용은 재계산으로 인한 시간 비용과 함께 기하급수적으로 증가하는 요인이 됩니다.
  • 메모리와 시간 비용을 분리하여 리소스 사용을 미세 조정할 수 있습니다.
  • 알고리즘의 코어에 축소된 원형 스펀지 기능을 사용하여 고속화
  • 원하는 길이의 출력을 제공할 수 있으며, 키 파생 함수(KDF)로 작동합니다.
  • 사이드 채널 공격(셋업 단계 전체)과 저비용(즉 저속) 메모리 디바이스 공격에 대한 내성을 조합한 설계로 이러한 모순되는 요건을 균형 있게 조정할 수 있습니다.
  • 다음과 같은 다양한 구성을 검토하여 정규 플랫폼에서의 실행을 최적화하면서 공격 플랫폼으로부터 보호합니다.
    • GPU 기반 공격에 큰 이점을 주지 않고 멀티코어 플랫폼 병렬화 지원
    • 대상 플랫폼에 따라 다른 기본 스폰지 기능을 사용하는 기능(예를 들어 소프트웨어 구현의 경우 BLAK2b, 하드웨어 구현의 경우 Kecak, 하드웨어 플랫폼에 대한 추가 저항의 경우 BlaMka 등)
    • 알고리즘의 메모리 대역폭 사용률을 높이는 기능(주의: 원래 사양은 현재 머신의 대역폭을 최대화할 것으로 예상되지만, 이 기능은 향후 하드웨어에 도움이 될 수 있음)

설계.

모든 PHS와 마찬가지로 Lyra2는 솔트와 패스워드를 입력으로 사용하여 암호 알고리즘의 주요 자료 또는 인증 [11][failed verification][citation needed]문자열로 사용할 수 있는 의사 난수 출력을 만듭니다.

내부적으로 스킴의 메모리는 전체 패스워드 해싱 프로세스 동안 메모리에 남아 있을 것으로 예상되는 매트릭스로 구성되어 있습니다.스킴의 셀은 반복적으로 읽고 쓰기 때문에 메모리를 절약하기 위해 셀을 폐기하면 마지막으로 [5]수정될 때까지 다시 액세스할 때마다 다시 계산해야 합니다.

매트릭스의 구성 및 방문은 기본 스펀지의 흡수, 압착 및 이중화 작동(즉, 내부 상태는 0으로 재설정되지 않음)의 스테이트풀 조합을 사용하여 수행되며 전체 프로세스의 순차적 특성을 보장합니다.

또, 초기화 후에 매트릭스의 셀을 재방문하는 회수를 유저가 정의해, 타겟 플랫폼의 자원에 맞추어 Lyra2의 실행 시간을 미세 조정할 수 있습니다.

함수/기호

[+]Wordwise을 추가하 Concatenate 두 문자열을 Bitwise XOR^ 작업(사이의 단어 즉을 무시하고 carries)%Modulus W대상 기계의 단어 크기(보통, 32또는 64)오메가의 비트에서 사용할 회전(:그 기계의 단어 크기, W배수 추천)>>> 맞아 회전rho의 라운드까지 줄었다. squ스펀지의 블록 사이즈(바이트 단위)를 H 또는 H_i 스펀지의 블록 사이즈(바이트 단위)로 블렌징하고 입력 H.squeeze(렌) 스펀지의 스퀴즈(렌) 스퀴즈(렌) 스퀴즈(렌) 스펀지의 스퀴즈(렌) 입력 H.squeeze(렌) 스펀지의 스퀴즈(렌) 스퀴즈(렌) 스퀴즈(렌) 스퀴즈(렌즈)에 대한 스퀴즈(렌즈) 스퀴즈) 스퀴즈(렌즈) 스퀴즈(렌즈)의 스퀴즈(렌즈)의 스퀴즈g(input,len) 입력 시 스폰지의 듀플렉싱 조작, len 바이트 H.duplexing_{rho}(input,len) 입력 시 스폰지의 듀플렉싱 조작, rho 라운드의 f를 사용하여 len 바이트 패드(string) 생성, blen 바이트의 배수(패딩 규칙: 10*1) lsw(input)에 문자열을 패딩합니다.input len(string) 문자열의 최하위 워드(바이트 단위) syncThreads() Synchronize parallel threads swap(input1,input2) 메모리 매트릭스의 두 입력 C Number of columns(일반적으로 64, 128, 256, 512, 512 또는 1024) P Degreallelassismallelism(P = 1 및 (m) 0%) 값을 바꿉니다.

입력

  • 패스워드
  • 소금.
  • 비용
  • m_cost(비용)
  • 압도하다

병렬이 없는 알고리즘

** 부트스트랩 단계:스펀지의 상태 및 지역 변수 # 입력 파라미터의 바이트 표현(패스워드 추가 가능) = outlen len(패스워드) len(패스워드 추가 가능) t_cost m_cost C # 스펀지의 상태를 초기화합니다(패스워드 덮어쓰기 가능). H.absorb(패드(패스워드 salt parames) # 방문 단계 및 창 초기화간격을 공급하는 첫 번째 행 = 1 stp = 1 wnd = 2 sqrt = 2 prev0 = 2 row1 = 1 prev1 = 0 ** 설정 단계:(m_cost x C) 메모리 매트릭스를 초기화합니다. 블렌바이트 셀을 가진 셀 # col = 0 ~ C-1 M[0] [C-1-col] = 0 ~ C.squeeze_{rho}(blen)에 대해 M[0], M[2]를 초기화합니다.row0에 R은 한줄=3연합 사인사 참모 부장 공화국 랜드)H.duplexing_ᆼ(M[row1][콜][+]M[prev0][콜][+]M[prev1][콜], blen)M[row0][C-1-col])M[prev0][콜]^ rand M[row1][콜])M[row1][콜]^#Rows 다음 루프 prev0에서 재검토할에(공화국 랜드>>>omega)ro을 돌봅니다에#기둥 루프:M[row0]과 M[row1]콜의 업데이트된 것이다.)초기화됩니다 0m_cost-1.w0 prev1= row1 = (row1 + stp) % wnd # (row1 = 0) # 창이 두 번이면 완전히 다시 방문되고 wnd = 2 * wnd stp = sqrt + 간격 = -gap # 다른 반복마다 sqrt를 두 번 조정합니다(갭 = -1) sqrt = 2 * sqrt 방황 단계:Iteratively)마리아 방문 루프:(2*m_cost*t_cost)줄 의사 난수의 패션에wCount=0에((m_cost*t_cost)에 되돌아 본 기억을 기질의pseudorandom 세포들을 덮어쓰-1)#Picks pseudorandom줄 row0=lsw(란드)%m_cost row1)lsw(공화국 랜드>>>omega)%m_cost)기둥 루프:업데이트 모두 M[row0]과 M[row1]에 콜=0에 C1#Picks pseudorandom 기둥 col0)lsw((rand>>>omega)>>>omega#%Ccol1)lsw(((공화국 랜드>>>omega)>>>omega)>>>omega#%C공화국 랜드)H.duplexing_ᆼ(M[row0][콜][+]M[row1][콜][+]M[prev0][col0][+]M[prev1][col1], blen)M[row0][콜])M[row0][콜]^ rand M[row1][콜])M는 경우.Row1][콜]^(공화국 랜드>>>omega))다음 iter.가장 최근에 업데이트된 행 prev0 = row0 prev1 = row1 ** rowup phase: 출력 계산 # 풀 라운드 스폰지 H.absorb(M[row0][0]) # 풀 라운드 스폰지 출력 = H.squeeze(len) # 출력으로 출력된 마지막 열을 흡수합니다.

병렬 알고리즘

[0..]의 각 i에 대해P] ** 부트스트랩 단계:스펀지 상태 및 지역 변수 # 입력 파라미터의 바이트 표현(패스워드 추가 가능) = outlen len(패스워드) len(패스워드 추가 가능) t_cost m_cost C Pi # 스펀지 상태 초기화(패스워드 덮어쓰기 가능) H_i.abs(패스워드 salt params) # 방문 초기화간격을 공급하는 단계, 창 및 첫 번째 행에서 = 1 stp = 1 wnd = 2 sqrt = 2 sync = 4 j = i prev0 = 2 rowP = 1 prevP = 0 ** 설정 단계:(m_cost x C) 메모리 매트릭스를 초기화합니다. blen 바이트 셀 # M_i[0], M_i[1] 및 M_i[2]를 초기화합니다(col = 0 ~ C-1 M_i[0] = H_isquee_{hoen} col = 0)에 대해.잉 루프:row0에=3에((/Pm_cost)-1)#기둥 루프:M_i[row0]과 M_j[row1]콜의 업데이트된가 초기화되다)0연합 사인사 참모 부장 공화국 랜드)H_i.duplexing_ᆼ(M_j[rowP][콜][+]M_i[prev0][콜][+]M_j[prevP][콜], blen)M_i[row0][C-1-col])M_i[prev0][콜]^ rand M_j[rowP][콜])M_j[rowP][콜]^(rand &g 나머지 열 초기화합니다.밀폐된<>>오메가)#Rows 다음 루프 prev0에서 재검토할에 row0 prevP = rowP rowP)(rowP+stp)%wnd)창호 만약(rowP)0)# 더블즈 창을 조정할 때 완전히 재검토 wnd=2*wnd stp)sqrt+격차 공간 -gap)더블즈 sqrt 모든 다른 반복 만약(공간))sqrt=2*sqrt#동기화 지점 i.f(row0 = sync) sync = sync + (syncrt / 2) j = (j + 1) % P syncThreads() syncThreads() ** 방황 단계:메모리 매트릭스 wnd = m_cost / (2 * P) sync = sqrt off0 =0 offP =0 offP = wnd # 방문루프: (2 * m _ cost * t _ cost / P ) 행을 반복적으로 덮어씁니다.wCount = 0 ~ ( m _ cost - p / ) 。P+(lsw(rand>>>omega)%wnd)j)lsw((rand>>>omega)>>>omega#%P#기둥 루프:콜에 M_i[row0]를 업데이트)0에 연합 사인사 참모 부장#Picks 의사 난수의 칼럼 col0)lsw(((공화국 랜드>>>omega)>>>omega)>>>omega#%C공화국 랜드)H_i.duplexing_{로}(M_i[row0][콜][+]M_i[prev0]-LSB- cOl0][+]M_j[rowP][콜], blen)M_i[row0][콜])M_i.[row0][col] ^ rand # 다음 반복에서는 (wCount = sync) sync = sqrt swap(off0,offP) syncThreads() syncThreads() syncThreads()의 경우 가장 최근에 업데이트된 행 prev0 = row0 # 동기화 포인트를 다시 살펴봅니다.full-round sponge output_i = H_i.squee(outlen) # 출력 반환 출력_0 ^ ...으로 outlen-long 비트스트링을 제공합니다.^ 출력_{P-1}

보안 분석

Lyra2에 대해 정규 사용자가 사용하는 메모리 용량중 /+ 2({1/를 한 공격의 처리비용은 O와 O( 일 것으로 예상됩니다.er 메모리의 이O일 때 얻을 수 O 대신 n1(\ n1)의 . 여기서 T는 처리 시간을 정의하는 사용자 정의 파라미터입니다.

이는 메모리 사용량이O(1[12]일 때 O2 O2})의 비용을 표시하는 스크립트 및 일반적으로 OT + O[7][13][14][15]의 결과를 문헌의 다른 솔루션과 비교해도 손색이 없습니다.

다만, 실제로는, 이러한 솔루션에는, 같은 처리 [16][17][18][19][20]시간에 Lyra2로 얻을 수 있는 값보다 낮은 R)이 필요하게 됩니다.

성능

최소 파라미터로 SSE 지원 스크립트 및 메모리 하드 PHC 최종 후보와 비교하여 C = 256, c = 1, p = 1의 경우 SSE 지원 Lyra2의 성능 및 다양한 T 및 R 설정.

SSE 싱글코어 Lyra2의 실장에 의해 얻을 수 있는 처리 시간을 그림으로 나타냅니다.이 수치는 PHC [16][17][18][19][20]컨텍스트에서 수행된 서드파티 벤치마크에서 [9]추출한 수치이며, 이와 매우 유사합니다.

표시된 결과는 C {C = { \ 、 b （ b 768 ） 구성된 Lyra2의 평균 실행 시간(즉, 내부 상태에는 256비트)과 T { Tyle T 및의 설정에 대응합니다.파라미터의 가능한 조합과 대응하는 자원 사용의 ea.

이 그림에서 보듯이 Lyra2는 최대 400 MB( 2 ({ R = 2^ { 및 5 (R 4.2 10 2 4（ T =） ) )또는 최대 1 GB의 메모리( 4 4.2 、 약 4 （ display R ） cd ^ 4 ） ^ 2 를 사용할 때 1초 이내에 실행할 수 있습니다.GB(R R= T T})의 경우)

모든 테스트는 48GB의 DRAM을 탑재한 Ubuntu 14.04 LTS 64비트를 실행하고 있는 인텔 Xeon E5-2430 (2.20GHz, 12코어, 64비트)에서 실행되었으며 소스 코드는 gcc 4.9.[9]2를 사용하여 컴파일되었습니다.

레퍼런스

  1. ^ "Password Hashing Competition". password-hashing.net. Retrieved 2016-03-22.
  2. ^ "Lyra2REv2". eprint.iacr.org. Retrieved 2016-03-22.
  3. ^ "Vertcoin". vertcoin.org. Retrieved 2019-10-08.
  4. ^ "MonaCoin". monacoin.org. Retrieved 2019-10-08.
  5. ^ a b c van Beirendonck, M.; Trudeau, L.; Giard, P.; Balatsoukas-Stimming, A. (2019-05-29). A Lyra2 FPGA Core for Lyra2REv2-Based Cryptocurrencies. IEEE International Symposium on Circuits and Systems (ISCAS). Sapporo, Japan: IEEE. pp. 1–5. arXiv:1807.05764. doi:10.1109/ISCAS.2019.8702498.
  6. ^ "Cryptology ePrint Archive: Report 2015/136". eprint.iacr.org. Retrieved 2016-03-22.
  7. ^ a b Almeida, Leonardo C.; Andrade, Ewerton R.; Barreto, Paulo S. L. M.; Simplicio Jr, Marcos A. (2014-01-04). "Lyra: password-based key derivation with tunable memory and processing costs". Journal of Cryptographic Engineering. 4 (2): 75–89. CiteSeerX 10.1.1.642.8519. doi:10.1007/s13389-013-0063-5. ISSN 2190-8508.
  8. ^ "Cryptology ePrint Archive: Report 2014/030". eprint.iacr.org. Retrieved 2016-03-22.
  9. ^ a b c Andrade, E.; Simplicio Jr, M.; Barreto, P.; Santos, P. (2016-01-01). "Lyra2: efficient password hashing with high security against time-memory trade-offs". IEEE Transactions on Computers. PP (99): 3096–3108. doi:10.1109/TC.2016.2516011. ISSN 0018-9340.
  10. ^ a b c Simplicio Jr, Marcos A.; Almeida, Leonardo C.; Andrade, Ewerton R.; Santos, Paulo C.; Barreto, Paulo S. L. M. "The Lyra2 reference guide" (PDF). PHC. The Password Hashing Competition.
  11. ^ Chen, Lily (2009). "Recommendation for Key Derivation Using Pseudorandom Functions (Revised)" (PDF). Computer Security. NIST. doi:10.6028/NIST.SP.800-108.
  12. ^ Percival, Colin. "Stronger Key Derivation via Sequential Memory-Hard Functions" (PDF). TARSNAP. The Technical BSD Conference.
  13. ^ "Cryptology ePrint Archive: Report 2013/525". eprint.iacr.org. Retrieved 2016-03-22.
  14. ^ Schmidt, Sascha. "Implementation of the Catena Password-Scrambling Framework" (PDF). Bauhaus-Universität Weimar. Faculty of Media.
  15. ^ "P-H-C/phc-winner-argon2" (PDF). GitHub. Retrieved 2016-03-22.
  16. ^ a b "Gmane -- Another PHC candidates mechanical tests". article.gmane.org. Retrieved 2016-03-22.
  17. ^ a b "Gmane -- A review per day Lyra2". article.gmane.org. Retrieved 2016-03-22.
  18. ^ a b "Gmane -- Lyra2 initial review". article.gmane.org. Retrieved 2016-03-22.
  19. ^ a b "Gmane -- Memory performance and ASIC attacks". article.gmane.org. Retrieved 2016-03-22.
  20. ^ a b "Gmane -- Quick analysis of Argon". article.gmane.org. Retrieved 2016-03-22.

외부 링크