비밀의

bcrypt
bcrypt 파일 암호화 유틸리티에 대한 내용은 Blowfish(암호)를 참조하십시오.
비밀의
일반
디자이너닐스 프로보스, 데이비드 마제르
초간출판1999
파생된 위치복어(암호)
디테일
다이제스트 크기184비트
라운드비용 매개 변수를 통해 가변적

bcrypt는 Niels Provos와 David Mazieres가 Blowfish 암호를 기반으로 설계한 암호 해싱 기능으로 1999년 USENIX에서 제시되었다.[1] 비크립트는 무지개 테이블 공격으로부터 보호하기 위해 소금을 통합하는 것 외에도 적응 기능이다. 시간이 지남에 따라 반복 횟수를 증가시켜 더 느리게 만들 수 있기 때문에 계산력이 증가하더라도 무차별적인 검색 공격에 대한 내성을 유지한다.

bcrypt 함수는 OpenBSD의[2] 기본 암호 해시 알고리즘이며 SUSE Linux와 같은 일부 Linux 배포의 경우 기본값이었다.[3]

C, C++, C#, Embarcadero Delphi, Elixir,[4] Go,[5] Java,[6][7] JavaScript,[8] Perl, PHP, Python,[9] Ruby 및 기타 언어에 대한 BCrypt의 구현이 있다.

배경

복어는 값비싼 키 설정 단계로 블록 암호 중 눈에 띈다. 표준 상태의 하위 키로 시작한 다음 이 상태를 사용하여 키의 일부를 사용하여 블록 암호화를 수행하고, 암호화의 결과(해싱에서 더 정확함)를 사용하여 일부 하위 키를 대체한다. 그런 다음 이 수정된 상태를 사용하여 키의 다른 부분을 암호화하고 결과를 사용하여 더 많은 하위 키를 대체한다. 모든 하위 키가 설정될 때까지 키를 해시하고 상태 비트를 교체하기 위해 점진적으로 수정된 상태를 사용하여 이 방식으로 진행한다.

프로보스와 마제르스는 이것을 이용하여, 더 나아가서 그것을 이용했다. 그들은 블로피쉬를 위한 새로운 키 설정 알고리즘을 개발했고, 결과 암호 "익스블루피쉬" ("비용키스케줄 블로피쉬")를 더빙했다. 키 설정은 모든 하위 키를 설정하기 위해 소금과 암호를 모두 사용하는 표준 복어 키 설정의 수정된 형태로 시작한다. 그런 다음 이전 라운드의 서브키 상태로 시작하는 각 라운드를 대신하여 소금과 암호를 키로 사용하여 표준 블로피쉬 키잉 알고리즘을 적용하는 여러 라운드가 있다. 이론적으로, 이것은 표준 복어 키 스케줄보다 강하지는 않지만, 재키핑 횟수는 구성할 수 있다. 따라서 이 과정은 임의로 느리게 만들어질 수 있으며, 이것은 해시나 소금에 대한 무차별적인 공격을 저지하는 데 도움이 된다.

설명

bcrypt 함수에 대한 입력은 암호 문자열, 숫자 비용 및 16바이트(128비트) 소금 값이다. 소금은 전형적으로 임의의 값이다. bcrypt 함수는 이러한 입력을 사용하여 24바이트(192비트) 해시를 계산한다. bcrypt 함수의 최종 출력은 다음과 같은 형식의 문자열이다. 

$2<a/b/x/y>$[cost]$[22 문자 salt][31 문자 해시]

예를 들어, 입력 암호 사용 abc123xyz, 비용 12, 그리고 임의의 소금, bcrypt의 출력은 끈이다. 

$2a$12$R9h/cIPz0gi.URNNX3kh2OPST9/PgBkqquzi.Ss7KIUGO2t0jWMUW \_/ \_________________________________/ 알그 코스트 솔트 해시

위치:

  • $2a$: 해시 알고리즘 식별자(BCrypt)
  • 12: 투입원가(2회12, 4096회차)
  • R9h/cIPz0gi.URNNX3kh2O: 입력 소금에 대한 radix-64 인코딩
  • PST9/PgBkqquzi.Ss7KIUgO2t0jWMUW: 계산된 해시의 radix-64 인코딩

BCrypt의 radix-64 인코딩은 표를 사용한다. ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789,[10]와는 다른. RFC4648Base64 인코딩.

버전 기록

$2$ (1999)

원본 BCrypt 규격은 다음의 접두사를 정의했다. $2$이는 OpenBSD 암호 파일에 암호를 저장할 때 사용되는 모듈식 암호화 형식에[11] 따른다.

  • $1$: MD5 기반 암호화('md5crypt')
  • $2$: 복어 기반 암호('bcrypt')
  • $sha1$: SHA-1 기반 암호화('sha1crypt')
  • $5$: SHA-256 기반 암호화('sha256crypt')
  • $6$: SHA-512 기반 암호화('sha512 crypt')

$2a$

원래 규격에서 비 ASC 처리 방법이 정의되지 않음II 문자, 또는 null 터미네이터를 처리하는 방법. 해싱 문자열을 지정할 때 다음을 지정하도록 사양이 수정되었다.

  • 문자열은 UTF-8로 인코딩되어야 한다.
  • null 터미네이터가 포함되어야 함

이 변경과 함께 버전이 로 변경되었다. $2a$[12]

$2x$, $2y$(2011년 6월)

2011년 6월, bcrypt의 PHP 구현인 crypt_blowfish에서 버그가 발견되었다. 여덟 번째 비트 세트로 문자를 잘못 처리한 것이었다.[13] 그들은 시스템 관리자가 기존 암호 데이터베이스를 업데이트하고 교체할 것을 제안했다. $2a$ 와 함께 $2x$, 이러한 해시가 나쁘다는 것을 나타내기 위해(그리고 오래된 고장난 알고리즘을 사용해야 한다). 그들은 또한 크립트블루피쉬를 방출하는 아이디어를 제안했다. $2y$ 고정 알고리즘에 의해 생성된 해시용.

표준 오픈BSD를 포함한 그 누구도 2x/2y의 아이디어를 채택하지 않았다. 이 버전 표식기 변경은 crypt_blowfish로 제한되었다.

$2b$ (2014년 2월)

OpenB에서 버그가 발견되었다.비크립트의 SD 구현. 그들은 문자열 길이를 서명되지 않은 문자(즉, 8비트)에 저장하고 있었다. Byte.[12] 비밀번호가 255자보다 길면 넘쳐서 255자로 싸진다.[14]

비밀번호는 OpenBSD를 위해 만들어졌다. 그들이 도서관에 버그가 생겼을 때, 그들은 버전 번호를 입력하기로 결정했다.

알고리즘.

비크립트 알고리즘은 블로피쉬를 이용해 '오르페안베어드스크리두트'라는 텍스트를 64회 암호화한 결과다. BCrypt에서는 일반적인 Blowfish 키 설정 기능이 값비싼 키 설정(EksBlowfishSetup) 기능으로 대체된다. 

함수 암호 입력: 비용:     번호 (4..)31) 로그2(이중)예:12==>, 212)4,096 반복 소금:Bytes의 배열(16바이트)무작위로 소금 암호:Bytes의 배열(1..72 바이트)UTF-8암호 출력 인코딩된:해시:Bytes의 배열(24바이트)//InitializeBlowfish 상태로 비싼 키 설정 알고리즘 //P:배열의 18하위 키(UInt32[18])//S:4substit.utioN, 상자적 S0(S-boxes)...S3이다. 각 S-box은 1,024바이트(UInt32[256])PS← EksBlowfishSetup(비용, 소금, 암호)//Repeatedly은 텍스트 암호화하"OrpheanBeholderScryDoubt"64배ctext ←"OrpheanBeholderScryDoubt"//24 바이트 ==>, 3가지의 64비트 블록 EncryptECB(P, S, ctext)← ECB모드에서 표준 조리를 사용하여 //encrypt(64)ctext을 반복한다. //24바이트 ctext에서 암호 해시 반환 연결(cost, salt, ctext)

값비싼 키 설정

BCrypt 알고리즘은 다음과 같이 실행되는 "Eksblowfish" 키 설정 알고리즘에 크게 의존한다. 

함수 EksBlowfishSetup 입력: 암호: 바이트 배열(1..72바이트) UTF-8 인코딩 암호 소금: 바이트 배열(16바이트) 랜덤 소금 비용:     번호 (4..)31) 로그2(이중) 예: 12 ==> 212 = 4,096 반복 출력: P: 라운드당 18개의 하위 키로 구성된1 UInt32 배열의 배열 S."E의 S4:4SBoxes의UInt32 배열의 배열이고, 파이 P의 육각 숫자, S← InitialState()//Permutate P와 S는 비밀 번호와 소금 P점을 바탕으로 각 SBox는 256UInt32(즉 각 SBox는 1KiB)//Initialize P(Subkeys), S(치환 상자), S← ExpandKey(P, S, 소금, 암호) 암호는" 비싼"부분xpositive Key Setup" //그렇지 않으면 키 설정이 Blowfish와 동일하다. 반복한다cost (2) P, S ← ExpandKey(P, S, 0, 암호) P, S ← ExpandKey(P, S, 0, salt) 리턴 P, S

InitialState는 원래 Blowfish 알고리즘에서와 같이 작동하여 P-array 및 S-box 항목을 {\}의 부분 부분으로 16진수로 채운다.

키 확장

ExpandKey 기능은 다음을 수행한다. 

함수 확장키 입력: 암호: 바이트 배열(1..72바이트) UTF-8 인코딩 암호 소금: 바이트[16] 임의 소금 P: 18 하위 키 S의1 UInt32 어레이 배열.S4: UInt32[1024] 4개의 1KB SBoxes 출력: P: 18개의 라운드당 하위 키 S로1 구성된 UInt32 Array 어레이.S4: UInt32[1024] n ← 1 ~ 18의 P 서브키 어레이에 4개의 1KB SBox //Mix 암호 입력 Pn ← Xorn 암호[32(n-1)]32n-1] //암호를 주기적인 것으로 처리 ///128비트 소금을 64비트 반쪽 두 개(복어 블록 크기)로 처리한다.    소금 반[0] ← 소금[0..63] //낮은 64비트 소금 반[1] ← 소금[64].127]  //Upper 64-bits of salt //Initialize an 8-byte (64-bit) buffer with all zeros.    block ← 0     //Mix internal state into P-boxes for n ← 1 to 9 do //xor 64-bit block with a 64-bit salt half block ← block xor saltHalf[(n-1) mod 2] //each iteration alternating between saltHalf[0], and saltHalf[1] //encrypt block using current key schedule block ← Encrypt(P, S, block)        P2n ← block[0..31]      //lower 32-bits of block       P2n+1 ← block[32..63]  //upper 32-bits block //Mix encrypted state into the internal S-boxes of state for i ← 1 to 4 do for n ← 0 to 127 do block ← Encrypt(state, block xor salt[64(n-1)..64n-1]) //Si[2n] 위의 as 블록[0..31] //하위 32비트 Si[2n+1] ← 블록[32..63] //상위 32비트 반환 상태

그러므로, ExpandKey(state, 0, key) 소금 값이 0인 XOR는 모두 유효하지 않기 때문에 일반 복어 키 스케줄과 동일하다. ExpandKey(state, 0, salt) 비슷하지만 소금을 128비트 키로 사용한다.

사용자 입력

많은 비밀번호가 OpenB에 이어 처음 72바이트로 단축됨SD 구현.

수학 알고리즘 자체는 18개의 32비트 하위 키로 초기화해야 한다(72옥텟/바이트와 동일). 원래 bcrypt의 규격은 사용자랜드의 텍스트 기반 암호를 알고리즘의 숫자 값으로 매핑하기 위한 특정한 한 가지 방법을 의무화하지 않는다. 텍스트에서 간단한 코멘트는 문자열의 ASCII 인코딩 값을 단순히 사용할 가능성을 언급하지만 의무화하지는 않는다: "마침내, 키 인수는 비밀 암호 키로, 최대 56바이트(키 ASCII 문자열일 때 종료되는 0바이트 포함)의 사용자-초센 암호일 수 있다."[1]

위의 인용문은 알고리즘 자체가 72바이트 초기값을 사용함에도 불구하고 "최대 56바이트"의 비밀번호를 언급하고 있다는 점에 유의한다. 프로보스와 마제르는 비록 더 짧은 제한의 이유를 명시하지는 않지만, 브루스 슈나이어의 원래 복어 규격인 "키 크기에 대한 448 비트 제한은 모든 서브키의 모든 비트(bit)가 키의 모든 비트(bit)에 의존하도록 보장한다"[15]는 다음과 같은 진술에 의욕을 느꼈을 것이다.

때때로 비 ASC를 포함하는 암호의 강도를 줄이는 등 비밀번호를 초기 숫자 값으로 변환하는 접근방식이 다양했다.II 문자.[16]

다른 암호 해싱 알고리즘과 비교

비크립트는 KDF(키 디리버레이션 함수)가 아니라는 점에 유의해야 한다. 예를 들어 암호에서 512비트 키를 추출하는 데 bcrypt를 사용할 수 없다. 동시에 pbkdf2, 스크립트, 아르곤2와 같은 알고리즘은 암호 기반 키 파생 함수로서, 여기서 출력은 키 파생만이 아닌 암호 해싱의 목적으로 사용된다.

암호 해싱은 일반적으로 1000ms를 완료해야 한다. 이 시나리오에서 bcrypt는 pbkdf2, 스크립트, 아르곤2보다 강하다.

  • PBKDF2: PBkdf2는 BCrypt보다 약하다. 일반적으로 사용되는 SHA2 해싱 알고리즘은 메모리 하드가 아니다. SHA2는 경량 기기(예: 스마트 카드)에서 구동할 수 있도록 초경량 설계됐다.[17] 이것은[18] PBKDF2가 초당 수조 개의 해시를 수행할 수 있는 범용 SHA-2 해싱 하드웨어를 구입할 수 있기 때문에 암호 저장에는 매우 취약하다는 것을 의미한다.
  • 스크립트: 스크립트는 4MB 미만의 메모리 요구사항의 경우 BCrypt보다 약하다. 스크립트는 (암호 저장용) GPU 기반 공격에 대해 동등한 수준의 방어력을 얻기 위해 약 1000배의 비크립트 메모리가 필요하다.
  • 아르곤2: 아르곤2는 1초 미만의 런타임에 대해 BCrypt보다 약하다. (즉, 암호 인증) Argon2는 >= ~1000ms 런타임까지 BCrypt의 강도와 일치하거나 능가하지 않는다(암호 해싱에는 적합하지 않지만 키 분리에 대해서는 완벽하게 허용됨)
  • 복어2는 비크립트의 고정된 4KB 메모리 풋프린트가 아닌 조절 가능한 메모리 풋프린트(스크립트, 아르곤2)를 사용하는 비크립트의 진화다. 스크립트나 아르곤2와 비슷하게 복어2는 더 많은 메모리를 사용함으로써 어려움을 얻는다. 스크립트나 아르곤2와는 달리 복어2는 CPU 코어의 L2 캐시에서만 작동한다. 스크립트와 아르곤2는 많은 RAM에 랜덤하게 액세스하여 메모리 경도를 얻는 반면, 복어2는 CPU 코어가 사용할 수 있는 전용 L2 캐시로 스스로를 제한한다. 이 때문에 스크립트나 아르곤2보다 커스텀 하드웨어에서 구현하기가 더욱 어려워진다. 복어2의 이상적인 메모리 설치 공간은 코어에 사용할 수 있는 캐시 크기(예: Intel Alder Lake의[20] 경우 1.25MB)이다. 이것은 복어2를 GPU나 ASIC에 훨씬 더 내성을 갖게 한다.

비평

최대 암호 길이

bcrypt는 최대 암호 길이가 72바이트 입니다. 이 최대값은 다음과 같은 ExpandKey 함수의 첫 번째 작동에서 나온다. xor's 암호와 함께 18개의 4바이트 하위 키(P): 

P1..P18 ← P1..P18 xor 암호바이트

암호(UTF-8 인코딩)는 72바이트 길이까지 반복된다. 예를 들어, 다음 의 암호:

correct horse battery staple␀ (29바이트)

라운드당 18 P 하위 키의 72바이트와 일치할 때까지 반복한다.

correct horse battery staple␀correct horse battery staple␀correct horse (72바이트)

이것은 또한 암호가 72바이트 UTF-8로 인코딩된 경우 암호가 잘리게 된다는 것을 의미한다. 일부 문자는 UTF-8 인코딩 시 4바이트를 요구할 수 있다. 이는 최악의 경우 암호를 18자로 제한할 수 있다는 것을 의미한다.

𐑜𐑝𐑟𐑥𐑷𐑻𐑽𐑾𐑿𐑿𐑰𐑩𐑛𐑙𐑘𐑙𐑒𐑔 (18자, 72바이트)

72바이트 암호의 이 제한(하위 키 18개 *각각 4바이트)은 다음과 같은 여러 가지 방법으로 해결할 수 있었다.

솔루션 1 - 하위 키 수 증가

사용되는 P 하위 키의 수를 늘릴 수 있으므로 사용 가능한 최대 암호 길이를 늘릴 수 있다. Blowfish의 원작자인 Bruce Schneier는 사람들이 더 많은 라운드를 추가하면서 놀 수 있고,[21] 이것은 더 많은 하위키를 필요로 하며, 이것은 비밀번호가 최대 길이를 증가시킬 것이라고 언급했다. 이것의 단점은 최대 길이가 아니라 최대 암호 길이가 여전히 있다는 것이다.

솔루션 2 - 계속해서 키 바이트를 P 하위 키 어레이에 혼합하십시오.

암호 혼합은 P1...까지만 계속된다.P18. P에18 도달했는데도 여전히 처리되지 않은 암호 바이트가 있으면 P에서1 xor 프로세스를 계속하십시오. 이 접근 방식의 단점은 계산 시간이 암호 길이(측면 채널 정보 누출)를 누설한다는 점이다.

솔루션 3 - 사전 해시 암호

긴 암호는 다른 암호 해싱 기능으로 미리 해싱할 수 있다. 이 함수는 항상 고정된 크기의 다이제스트를 출력한다. 결과 소화가 72바이트 미만인 한: 끊기지 않고 비크립트로 먹을 수 있다. 이것은 드롭박스[22] 등이 취한 접근법이다. 예를 들어 암호를 고려하십시오.

ਤੇਜ਼ ਭੂਰੇ ਲੂੰਬੜ ਨੇ ਆਲਸੀ ਕੁੱਤੇ ਉੱਤੇ ਛਾਲ ਮਾਰ ਦਿੱਤੀ (32자, 126바이트)

HMAC를SHA-256 사용하여 이 암호를 해싱하면 다음과 같은 256비트(32바이트) 다이제스트가 생성된다. 

A7 B2 AA 86 CB 57 D3 08 EA 54 9F 34 E5 91 7E 8C 06 9B D0 0D 34 28 B1 CA 8D 71 B2 E 84 DA C0 F8

Base64 인코딩 다이제스트의 문자열은 44자로 일관된다.

p7KqhstX0wjqVJ805ZF+jAab0A00KLHKjXGyLoTawPg= (44자, 44바이트)

그리고 항상 72바이트의 암호 해독 한계에 맞을 것이다.

이는 비크립트의 캐시 하드 진화인 퍼퍼피쉬2가 HMAC를SHA-512 사용하여 암호를 고정 길이 64바이트(512비트) 키로 변환하는 접근법과 유사하다.

암호 해시 잘라내기

BCrypt 알고리즘은 24바이트 텍스트의 반복적인 암호화를 포함한다.

OrpheanBeholderScryDoubt (24-180)

이렇게 하면 24바이트의 암호문이 생성된다. 예를 들어,

85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9 a4 (24-180)

그러면 radix-64를 32-charactor로 인코딩해야 한다.

hSCvnwM9s4wIX9JeLapehKK5YdLxKcmk (32-1993)

하지만 정식 오픈B는SD 구현을 통해 암호 해시를 23바이트로 잘라냄:

85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9 a4 (23-180)

그 결과 base-64 인코딩된 텍스트는 일반적으로 다음과 같다. 

hSCvnwM9s4wIX9JeLapehKK5YdLxKck=

후행 = 제거됨, 해시: 

hSCvnwM9s4wIX9JeLapehKK5YdLxKck

정식 구현으로 인해 암호 해시로부터 8비트를 삭제하는 이유는 명확하지 않다.

비표준 base64 인코딩 사용

표준 OpenB에서 사용하는 Base64 인코딩SD 구현은 거의 모든 언어와 플랫폼에서 사용할 수 있는 것과 다른 인코딩 사전을 사용한다. 그 인코딩은 암호와 호환된다. 이는 인코딩이 RFC 4648과 호환되지 않음을 의미한다.[citation needed]

참고 항목

참조

  1. ^ a b Provos, Niels; Mazières, David; Talan Jason Sutton 2012 (1999). "A Future-Adaptable Password Scheme". Proceedings of 1999 USENIX Annual Technical Conference: 81–92.
  2. ^ "Commit of first work to repo". 13 Feb 1997.
  3. ^ "SUSE Security Announcement: (SUSE-SA:2011:035)". 23 August 2011. Archived from the original on 4 March 2016. Retrieved 20 August 2015. SUSE's crypt() implementation supports the blowfish password hashing function (id $2a) and system logins by default also use this method.
  4. ^ Whitlock, David (21 September 2021). "Bcrypt Elixir: bcrypt password hashing algorithm for Elixir". GitHub. riverrun.
  5. ^ "Package bcrypt". godoc.org.
  6. ^ "jBCrypt - strong password hashing for Java". www.mindrot.org. Retrieved 2017-03-11.
  7. ^ "bcrypt - A Java standalone implementation of the bcrypt password hash function". github.com. Retrieved 2018-07-19.
  8. ^ "bcryptjs". npm.
  9. ^ Stufft, Donald (14 October 2021). "bcrypt: Modern password hashing for your software and your servers" – via PyPI.
  10. ^ Provos, Niels (13 February 1997). "bcrypt.c source code, lines 57-58". Retrieved 29 January 2022.
  11. ^ "Modular Crypt Format — Passlib v1.7.1 Documentation". passlib.readthedocs.io.
  12. ^ a b "bcrypt password hash bugs fixed, version changes and consequences". undeadly.org.
  13. ^ Designer, Solar. "oss-sec: CVE request: crypt_blowfish 8-bit character mishandling". seclists.org.
  14. ^ "'bcrypt version changes' - MARC". marc.info.
  15. ^ Schneier, Bruce (1994). "Fast Software Encryption, Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)". Cambridge Security Workshop Proceedings (December 1993). Springer-Verlag: 191–204.
  16. ^ "jBCrypt security advisory". 1 February 2010. 그리고
  17. ^ https://csrc.nist.gov/csrc/media/publications/fips/180/2/archive/2002-08-01/documents/fips180-2.pdf
  18. ^ https://www.asicminervalue.com/miners/goldshell/kd6
  19. ^ https://blog.ircmaxell.com/2014/03/why-i-dont-recommend-scrypt.html#Putting-It-In-Perspective
  20. ^ https://ark.intel.com/content/www/us/en/ark/products/134586/intel-core-i512400-processor-18m-cache-up-to-4-40-ghz.html
  21. ^ "Schneier on Security: The Blowfish Encryption Algorithm".
  22. ^ "How Dropbox securely stores your passwords".
  23. ^ http://bcrypt.sourceforge.net bcrypt 파일 암호화 프로그램 홈페이지
  24. ^ "bcrypt APK for Android - free download on Droid Informer". droidinformer.org.
  25. ^ "T2 package - trunk - bcrypt - A utility to encrypt files". t2sde.org.
  26. ^ "Oracle GoldenGateのライセンス". docs.oracle.com.

외부 링크