balloon.go

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