balloon.go

   1 // balloon -- Balloon password hashing function
   2 // Copyright (C) 2016-2024 Sergey Matveev <stargrave@stargrave.org>
   3 //
   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.
   7 //
   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.
  12 //
  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/>.
  16
  17 // Balloon password hashing.
  18 //
  19 // Look https://crypto.stanford.edu/balloon/ for more description.
  20 package balloon
  21
  22 import (
  23         "encoding/binary"
  24         "hash"
  25         "math/big"
  26 )
  27
  28 const delta = 3
  29
  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:
  33 //
  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 {
  51         var cnt uint64
  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)
  57         cnt++
  58         h.Write(intBuf)
  59         h.Write(passwd)
  60         h.Write(salt)
  61         buf = h.Sum(buf)
  62         var m uint64
  63         for m = 1; m < sCost; m++ {
  64                 binary.LittleEndian.PutUint64(intBuf, cnt)
  65                 cnt++
  66                 h.Reset()
  67                 h.Write(intBuf)
  68                 h.Write(buf[(m-1)*hSize : m*hSize])
  69                 buf = h.Sum(buf)
  70         }
  71         // Mix buffer contents
  72         var prev []byte
  73         var i uint64
  74         var neigh uint64
  75         bi := big.NewInt(0)
  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
  81                         if m == 0 {
  82                                 prev = buf[(sCost-1)*hSize:]
  83                         } else {
  84                                 prev = buf[(m-1)*hSize : m*hSize]
  85                         }
  86                         binary.LittleEndian.PutUint64(intBuf, cnt)
  87                         cnt++
  88                         h.Reset()
  89                         h.Write(intBuf)
  90                         h.Write(prev)
  91                         h.Write(buf[m*hSize : (m+1)*hSize])
  92                         buf = h.Sum(buf[:m*hSize])
  93
  94                         // Hash in pseudorandomly chosen blocks
  95                         for i = 0; i < delta; i++ {
  96                                 h.Reset()
  97                                 binary.LittleEndian.PutUint64(intBuf, t)
  98                                 h.Write(intBuf)
  99                                 binary.LittleEndian.PutUint64(intBuf, m)
 100                                 h.Write(intBuf)
 101                                 binary.LittleEndian.PutUint64(intBuf, i)
 102                                 h.Write(intBuf)
 103                                 biBuf = h.Sum(biBuf[:0])
 104                                 binary.LittleEndian.PutUint64(intBuf, cnt)
 105                                 cnt++
 106                                 h.Reset()
 107                                 h.Write(intBuf)
 108                                 h.Write(salt)
 109                                 h.Write(biBuf)
 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]
 113                                 }
 114                                 bi.SetBytes(biBuf)
 115                                 bi.Mod(bi, bs)
 116                                 binary.LittleEndian.PutUint64(intBuf, cnt)
 117                                 cnt++
 118                                 h.Reset()
 119                                 h.Write(intBuf)
 120                                 h.Write(buf[m*hSize : (m+1)*hSize])
 121                                 neigh = bi.Uint64()
 122                                 h.Write(buf[neigh*hSize : (neigh+1)*hSize])
 123                                 buf = h.Sum(buf[:m*hSize])
 124                         }
 125                 }
 126         }
 127         // Extract output from buffer
 128         return buf[(sCost-1)*hSize:]
 129 }
 130
 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.
 134 //
 135 //      H(p, s, jobs) = hash(p || s || (
 136 //          B(p, s || "1") XOR
 137 //          B(p, s || "2") XOR
 138 //          B(p, s || jobs)
 139 //      ))
 140 func H(hasher func() hash.Hash, passwd, salt []byte, sCost, tCost int, jobs int) []byte {
 141         var i int
 142         results := make(chan []byte)
 143         for ; i < jobs; i++ {
 144                 go func(i int) {
 145                         saltBuf := make([]byte, len(salt)+8)
 146                         copy(saltBuf, salt)
 147                         binary.LittleEndian.PutUint64(saltBuf[len(salt):], uint64(i))
 148                         results <- B(hasher(), passwd, saltBuf, uint64(sCost), uint64(tCost))
 149                 }(i)
 150         }
 151         h := hasher()
 152         h.Write(passwd)
 153         h.Write(salt)
 154         result := make([]byte, h.Size())
 155         for i = 0; i < jobs; i++ {
 156                 for n, e := range <-results {
 157                         result[n] ^= e
 158                 }
 159         }
 160         close(results)
 161         h.Write(result)
 162         return h.Sum(result[:0])
 163 }