2 balloon -- Balloon password hashing function
3 Copyright (C) 2016-2019 Sergey Matveev <stargrave@stargrave.org>
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation, either version 3 of the
8 License, or (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with this program. If not, see
17 <http://www.gnu.org/licenses/>.
20 // Balloon password hashing.
22 // Look https://crypto.stanford.edu/balloon/ for more description.
35 // This function takes hash, password, salt, space cost (buffer size,
36 // number of hash-output sized blocks), time cost (number of rounds) and
37 // performs the following:
39 // # Expand input into buffer.
40 // buf[0] = hash(cnt++ || passwd || salt)
41 // for m from 1 to sCost-1:
42 // buf[m] = hash(cnt++ || buf[m-1])
43 // # Mix buffer contents.
44 // for t from 0 to tCost-1:
45 // for m from 0 to sCost-1:
46 // # Hash last and current blocks.
47 // prev = buf[(m-1) mod sCost]
48 // buf[m] = hash(cnt++ || prev || buf[m])
49 // # Hash in pseudorandomly chosen blocks.
50 // for i from 0 to delta-1:
51 // other = to_int(hash(cnt++ || salt || t || m || i)) mod sCost
52 // buf[m] = hash(cnt++ || buf[m] || buf[other])
53 // # Extract output from buffer.
54 // return buf[sCost-1]
55 func B(h hash.Hash, passwd, salt []byte, sCost, tCost uint64) []byte {
57 intBuf := make([]byte, 8)
58 hSize := uint64(h.Size())
59 buf := make([]byte, 0, sCost*hSize)
60 // Expand input into buffer
61 binary.BigEndian.PutUint64(intBuf, cnt)
68 for m = 1; m < sCost; m++ {
69 binary.BigEndian.PutUint64(intBuf, cnt)
73 h.Write(buf[(m-1)*hSize : m*hSize])
76 // Mix buffer contents
81 bs := big.NewInt(int64(sCost))
82 biBuf := make([]byte, 0, h.Size())
83 for t := uint64(0); t < tCost; t++ {
84 for m = 0; m < sCost; m++ {
85 // Hash last and current blocks
87 prev = buf[(sCost-1)*hSize:]
89 prev = buf[(m-1)*hSize : m*hSize]
91 binary.BigEndian.PutUint64(intBuf, cnt)
96 h.Write(buf[m*hSize : (m+1)*hSize])
97 buf = h.Sum(buf[:m*hSize])
99 // Hash in pseudorandomly chosen blocks
100 for i = 0; i < delta; i++ {
101 binary.BigEndian.PutUint64(intBuf, cnt)
106 binary.BigEndian.PutUint64(intBuf, t)
108 binary.BigEndian.PutUint64(intBuf, m)
110 binary.BigEndian.PutUint64(intBuf, i)
112 biBuf = h.Sum(biBuf[:0])
115 binary.BigEndian.PutUint64(intBuf, cnt)
119 h.Write(buf[m*hSize : (m+1)*hSize])
121 h.Write(buf[neigh*hSize : (neigh+1)*hSize])
122 buf = h.Sum(buf[:m*hSize])
126 // Extract output from buffer
127 return buf[(sCost-1)*hSize:]
130 // This function adds additional functionality over pure B(): ability to
131 // run several hashers (jobs) simultaneously and second-preimage resistant
132 // password double hashing.
134 // H(p, s, jobs) = hash(p || s || (
135 // B(p, s || "1") XOR
136 // B(p, s || "2") XOR
139 func H(hasher func() hash.Hash, passwd, salt []byte, sCost, tCost int, jobs int) []byte {
141 results := make(chan []byte)
142 for ; i < jobs; i++ {
144 saltBuf := make([]byte, 8)
145 binary.BigEndian.PutUint64(saltBuf, uint64(i))
146 results <- B(hasher(), passwd, append(salt, saltBuf...), sCost, tCost)
152 result := make([]byte, h.Size())
153 for i = 0; i < jobs; i++ {
154 for n, e := range <-results {
160 return h.Sum(result[:0])