단계별 Bcrypt

게시물Bcrypt Step by Step은 Qvault에 처음 등장했습니다.

Bcrypt는 느린key derivation function으로 생각할 수 있는 hash function 입니다. 그 목적은 입력 데이터 조각을 고정된 크기의 결정적이며 예측할 수 없는 출력으로 천천히 변환하는 것입니다. 일반적인 사용 사례는 암호를 안전한 인증에 사용할 수 있는 n비트 암호화 키로 변환하는 것입니다.

여기Qvault,에서 우리는 보안 시스템에서 Bcrypt를 사용합니다. Bcrypt는 매우 인기 있는 암호 해싱 기능이므로 현재 Practical Cryptography 과정에서 구현을 가르치는 해시 기능입니다.

Bcrypt의 모습

비밀번호 myPassword123에 Bcrypt를 사용하면 다음과 같이 생성됩니다.

**_myPassword123_** ->$2y$12$vUw4OU4EAl4w4vC6/lA33OtDSYGhiIdekdT9iOoSs9/ckwrffaEui

해당 출력은 원본 데이터가 일치하는지 확인하기 위해 향후 해시와 비교하는 데 사용할 수 있습니다.

암호를 직접 비교하지 않는 이유는 무엇입니까?

웹 개발에서 사용자의 암호를 일반 텍스트로 저장하는 것은 안전하지 않습니다. 공격자가 서버의 데이터베이스에 대한 액세스 권한을 얻으면 원시 이메일/비밀번호 조합을 찾아 다른 사이트에서 동일한 사용자를 공격하는 데 사용할 수 있습니다.

적어도 우리는 사용자의 암호를 해시해야 하지만 SHA-2 및 MD5와 같은 해시 함수는 너무 빠르기 때문에 안전하지 않습니다. Bcrypt와 같은 KDF를 사용하면 계산 비용이 많이 들고 느리기 때문에 빠른 해시보다 보안상의 이점이 있습니다. 공격자가 빠른 알고리즘으로 만든 암호 해시 데이터베이스에 대한 액세스 권한을 얻으면 다른 입력을 추측하고 출력이 일치하는지 확인하여 해시를 "역전"하기 쉽습니다.

예를 들어 공격자가 데이터베이스에서 다음 항목을 찾았다고 가정해 보겠습니다.

[email protected] 5906ac361a137e2d286465cd6588ebb5ac3f5ae955001100bc41577c3d751764

다음과 같은 일반적인 암호를 해싱할 수 있습니다.

password1 ->0b14d501a594442a01c6859541bcb3e8164d183d32937b851835442f69d5c94epassword2 ->6cf615d5bcaac778352a8f1f3360d23f02f34ec182e259897fd6ce485d7870d4password3 -> 5906ac361a137e2d286465cd6588ebb5ac3f5ae955001100bc41577c3d751764

암호password3는 일치하는 해시를 생성했습니다! 이제 공격자는 [email protected]가 다른 사이트에서 암호password3를 사용할 가능성이 있음을 알고 다른 계정을 해킹할 수 있습니다. 이는 공격자가 초당 많은 해시를 빠르게 계산하고 수백만 개의 잠재적 암호를 추측할 수 있기 때문에 가능합니다.

Bcrypt와 같은 느린 KDF는 이 문제를 해결합니다.

Bcrypt 출력 형식

$2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy\_\_\_/\_\_/\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_/\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_/Alg Cost Salt Hash

2a : 해시 알고리즘 식별자(Bcrypt)

10 : 비용 요소(210 = 키 확장 1,024회)

N9qo8uLOickgx2ZMRZoMye : 16바이트(128비트) 솔트, base64가 22자로 인코딩됨

IjZAgcfl7p92ldGxad68LJZdL17lhWy : 24바이트(192비트) 해시, base64가 31자로 인코딩됨

Wikipedia에서 직접

Bcrypt 단계별 설명

Bcrypt는 다음과 같은 Go 유사 의사 코드로 시각화할 수 있습니다.

func bcrypt(cost int, salt [16]byte, password [72]byte) (hash string) {
    // Initialize Blowfish state with expensive key setup algorithm
    // This is the slow part of the algorithm
    pEighteenSubkeys, sFourSubBoxes := expensiveBlowfishSetup(cost, salt, password)

    // Repeatedly encrypt the text "OrpheanBeholderScryDoubt" 64 times
    // 24 bytes = three 64-bit blocks
    ctext := "OrpheanBeholderScryDoubt"
    for i := 0; i < 64; i++ {
        // Encrypt using standard Blowfish in ECB mode
        ctext = encryptECB(pEighteenSubkeys, sFourSubBoxes, ctext)
    }

    // return the version, cost, salt, and ctext in the proper format
    return "$2a${cost}${salt}{ctext}"
}

보시다시피 Bcrypt는 Blowfish 암호에 크게 의존합니다. 간단히 말해서 Bcrypt는 Blowfish 암호화와 결합된 값비싼 키 확장입니다.
expensiveBlowfishSetup 함수는 다음 의사 코드로 이해할 수 있습니다.

// pEighteenSubkeys: array of 18 subkeys
// sFourSubBoxes: Four substitution boxes
// Each S-Box is a 256-length array of uint32
func expensiveBlowfishSetup(cost int, salt [16]byte, password [72]byte) (pEighteenSubkeys [18]uint32, sFourSubBoxes [4][256]uint32) {
    // Initialize arrays
    pEighteenSubkeys := [18]uint32
    sFourSubBoxes := [4][256]uint32

    // Fill pEighteenSubkeys and sFourSubBoxes with the hex digits of pi 
    // This initial state works as in the original Blowfish algorithm
    // it populates the P-array and S-box entries with the fractional part of pi in hexadecimal
    pEighteenSubkeys = fillWithPi(pEighteenSubkeys)
    sFourSubBoxes = fillWithPi(sFourSubBoxes)

    // Permutate P and S based on the password and salt
    pEighteenSubkeys, sFourSubBoxes = expandKey(pEighteenSubkeys, sFourSubBoxes, salt, password)

    // This is the "Expensive" part of the "Expensive Key Setup"
    // Otherwise the key setup would be identical to Blowfish
    // Expand the key an exponentially increasing number of times
    // depending on the cost factor
    for i := 0; i < math.Pow(2, cost); i++ {
        pEighteenSubkeys, sFourSubBoxes = expandKey(pEighteenSubkeys, sFourSubBoxes, 0, password)
        pEighteenSubkeys, sFourSubBoxes = expandKey(pEighteenSubkeys, sFourSubBoxes, 0, salt)
    }

    return pEighteenSubkeys, sFourSubBoxes
}

The expandKey function는 cost 매개변수의 값에 따라 기하급수적으로 증가하는 횟수로 실행됩니다. expandKey 함수는 다음 의사 코드로 설명됩니다.

func expandKey(pEighteenSubkeys [18]uint32, sFourSubBoxes [4][256]uint32, salt [16]byte, password [72]byte) (
    pEighteenSubkeys [18]uint32, sFourSubBoxes [4][256]uint32
    ) {

    // Mix password into the pEighteenSubkeys array
    // by XORing password with subkeys
    for i := 0; i < 18; i++{
        // treat the password as cyclic, XOR 32 bit chunks of password with subkeys
        pEighteenSubkeys[i] ^= password[i % 18]
    }

   // Treat the 128-bit salt as two 64-bit halves 
   saltHalf[0] = salt[0:63]
   saltHalf[1] = salt[64:127]

   // Initialize an 8-byte (64-bit) buffer with all zeros.
   block := [8]byte

   // Mix internal state into P-boxes   
   for i := 0; i < 9; i++ {
      // XOR 64-bit block with a 64-bit salt half
      // Each iteration alternating between saltHalf[0], and saltHalf[1]
      block ^= saltHalf[(i-1) mod 2]

      // Encrypt block using current key schedule with blowfish block encryption
      block = Encrypt(pEighteenSubkeys, sFourSubBoxes, block)

      // Split block and use as new subkeys
      pEighteenSubkeys[2*i] = block[0:31]
      pEighteenSubkeys[2*i + 1] = block[32:63]
   }

   // Mix encrypted state into the internal S-boxes of state
   for i := 0; i < 4; i ++ {
      for j := 0; j < 127; j++ {
        // Encrypt block using blowfish block encryption
        // where salt[i] is 64 bit chunks
        block = Encrypt(pEighteenSubkeys, sFourSubBoxes, block ^ salt[i])
        sFourSubBoxes[2*i] = block[0:31]
        sFourSubBoxes[2*i + 1] = block[32:63]
      }
    }
    return pEighteenSubkeys, sFourSubBoxes
}

Go와 같은 보다 "실제"프로그래밍 구문을 사용하여 의사 코드의 세부 사항을 시각화하는 데 도움이 됩니다. 그래도 도움이 되지 않으면 여기Wikipedia 페이지의 코드를 살펴보십시오.

읽어 주셔서 감사합니다!

질문이나 의견이 있으면 Twitter에서 팔로우하세요.

Qvault Classroom에서 게임 같은 코딩 과정을 수강하세요.

Subscribe 더 교육적인 기사를 보려면 뉴스레터로