1 // balloon -- Balloon password hashing function
2 // Copyright (C) 2016-2024 Sergey Matveev <stargrave@stargrave.org>
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU Lesser General Public License as
6 // the Free Software Foundation, version 3 of the License.
8 // This program is distributed in the hope that it will be useful,
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 // GNU Lesser General Public License for more details.
13 // You should have received a copy of the GNU Lesser General Public
14 // License along with this program. If not, see
15 // <http://www.gnu.org/licenses/>.
17 // Balloon password hashing.
19 // Look https://crypto.stanford.edu/balloon/ for more description.
30 // This function takes hash, password, salt, space cost (buffer size,
31 // number of hash-output sized blocks), time cost (number of rounds) and
32 // performs the following:
34 // # Expand input into buffer.
35 // buf[0] = hash(cnt++ || passwd || salt)
36 // for m from 1 to sCost-1:
37 // buf[m] = hash(cnt++ || buf[m-1])
38 // # Mix buffer contents.
39 // for t from 0 to tCost-1:
40 // for m from 0 to sCost-1:
41 // # Hash last and current blocks.
42 // prev = buf[(m-1) mod sCost]
43 // buf[m] = hash(cnt++ || prev || buf[m])
44 // # Hash in pseudorandomly chosen blocks.
45 // for i from 0 to delta-1:
46 // other = to_int(hash(cnt++ || salt || t || m || i)) mod sCost
47 // buf[m] = hash(cnt++ || buf[m] || buf[other])
48 // # Extract output from buffer.
49 // return buf[sCost-1]
50 func B(h hash.Hash, passwd, salt []byte, sCost, tCost uint64) []byte {
52 intBuf := make([]byte, 8)
53 hSize := uint64(h.Size())
54 buf := make([]byte, 0, sCost*hSize)
55 // Expand input into buffer
56 binary.LittleEndian.PutUint64(intBuf, cnt)
63 for m = 1; m < sCost; m++ {
64 binary.LittleEndian.PutUint64(intBuf, cnt)
68 h.Write(buf[(m-1)*hSize : m*hSize])
71 // Mix buffer contents
76 bs := big.NewInt(int64(sCost))
77 biBuf := make([]byte, 0, h.Size())
78 for t := uint64(0); t < tCost; t++ {
79 for m = 0; m < sCost; m++ {
80 // Hash last and current blocks
82 prev = buf[(sCost-1)*hSize:]
84 prev = buf[(m-1)*hSize : m*hSize]
86 binary.LittleEndian.PutUint64(intBuf, cnt)
91 h.Write(buf[m*hSize : (m+1)*hSize])
92 buf = h.Sum(buf[:m*hSize])
94 // Hash in pseudorandomly chosen blocks
95 for i = 0; i < delta; i++ {
97 binary.LittleEndian.PutUint64(intBuf, t)
99 binary.LittleEndian.PutUint64(intBuf, m)
101 binary.LittleEndian.PutUint64(intBuf, i)
103 biBuf = h.Sum(biBuf[:0])
104 binary.LittleEndian.PutUint64(intBuf, cnt)
110 biBuf = h.Sum(biBuf[:0])
111 for i, j := 0, len(biBuf)-1; i < j; i, j = i+1, j-1 {
112 biBuf[i], biBuf[j] = biBuf[j], biBuf[i]
116 binary.LittleEndian.PutUint64(intBuf, cnt)
120 h.Write(buf[m*hSize : (m+1)*hSize])
122 h.Write(buf[neigh*hSize : (neigh+1)*hSize])
123 buf = h.Sum(buf[:m*hSize])
127 // Extract output from buffer
128 return buf[(sCost-1)*hSize:]
131 // This function adds additional functionality over pure B(): ability to
132 // run several hashers (jobs) simultaneously and second-preimage resistant
133 // password double hashing.
135 // H(p, s, jobs) = hash(p || s || (
136 // B(p, s || "1") XOR
137 // B(p, s || "2") XOR
140 func H(hasher func() hash.Hash, passwd, salt []byte, sCost, tCost int, jobs int) []byte {
142 results := make(chan []byte)
143 for ; i < jobs; i++ {
145 saltBuf := make([]byte, len(salt)+8)
147 binary.LittleEndian.PutUint64(saltBuf[len(salt):], uint64(i))
148 results <- B(hasher(), passwd, saltBuf, uint64(sCost), uint64(tCost))
154 result := make([]byte, h.Size())
155 for i = 0; i < jobs; i++ {
156 for n, e := range <-results {
162 return h.Sum(result[:0])