balloon.go

   1 /*
   2 balloon -- Balloon password hashing function
   3 Copyright (C) 2016 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 General Public License as published by
   7 the Free Software Foundation, either version 3 of the License, or
   8 (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 General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 // Balloon password hashing.
  20 //
  21 // Look https://crypto.stanford.edu/balloon/ for more description.
  22 package balloon
  23
  24 import (
  25         "encoding/binary"
  26         "hash"
  27         "math/big"
  28 )
  29
  30 const (
  31         delta = 3
  32 )
  33
  34 // This function takes hash, password, salt, space cost (buffer size,
  35 // number of hash-output sized blocks), time cost (number of rounds) and
  36 // performs the following:
  37 //
  38 //    # Expand input into buffer.
  39 //    buf[0] = hash(cnt++ || passwd || salt)
  40 //    for m from 1 to sCost-1:
  41 //        buf[m] = hash(cnt++ || buf[m-1])
  42 //    # Mix buffer contents.
  43 //    for t from 0 to tCost-1:
  44 //        for m from 0 to sCost-1:
  45 //            # Hash last and current blocks.
  46 //            prev = buf[(m-1) mod sCost]
  47 //            buf[m] = hash(cnt++ || prev || buf[m])
  48 //            # Hash in pseudorandomly chosen blocks.
  49 //            for i from 0 to delta-1:
  50 //                other = to_int(hash(cnt++ || salt || t || m || i)) mod sCost
  51 //                buf[m] = hash(cnt++ || buf[m] || buf[other])
  52 //    # Extract output from buffer.
  53 //    return buf[sCost-1]
  54 func B(h hash.Hash, passwd, salt []byte, sCost, tCost int) []byte {
  55         var cnt uint64
  56         intBuf := make([]byte, 8)
  57         buf := make([][]byte, sCost)
  58         // Expand input into buffer
  59         binary.BigEndian.PutUint64(intBuf, cnt)
  60         cnt++
  61         h.Write(intBuf)
  62         h.Write(passwd)
  63         h.Write(salt)
  64         buf[0] = h.Sum(nil)
  65         var m int
  66         for m = 1; m < sCost; m++ {
  67                 binary.BigEndian.PutUint64(intBuf, cnt)
  68                 cnt++
  69                 h.Reset()
  70                 h.Write(intBuf)
  71                 h.Write(buf[m-1])
  72                 buf[m] = h.Sum(nil)
  73         }
  74         // Mix buffer contents
  75         var prev []byte
  76         var i int
  77         bi := big.NewInt(0)
  78         bs := big.NewInt(int64(sCost))
  79         biBuf := make([]byte, 0, h.Size())
  80         var other int
  81         for t := 0; t < tCost; t++ {
  82                 for m = 0; m < sCost; m++ {
  83                         // Hash last and current blocks
  84                         if m == 0 {
  85                                 prev = buf[len(buf)-1]
  86                         } else {
  87                                 prev = buf[m-1]
  88                         }
  89                         binary.BigEndian.PutUint64(intBuf, cnt)
  90                         cnt++
  91                         h.Reset()
  92                         h.Write(intBuf)
  93                         h.Write(prev)
  94                         h.Write(buf[m])
  95                         buf[m] = h.Sum(buf[m][:0])
  96
  97                         // Hash in pseudorandomly chosen blocks
  98                         for i = 0; i < delta; i++ {
  99                                 binary.BigEndian.PutUint64(intBuf, cnt)
 100                                 cnt++
 101                                 h.Reset()
 102                                 h.Write(intBuf)
 103                                 h.Write(salt)
 104                                 binary.BigEndian.PutUint64(intBuf, uint64(t))
 105                                 h.Write(intBuf)
 106                                 binary.BigEndian.PutUint64(intBuf, uint64(m))
 107                                 h.Write(intBuf)
 108                                 binary.BigEndian.PutUint64(intBuf, uint64(i))
 109                                 h.Write(intBuf)
 110                                 biBuf = h.Sum(biBuf[:0])
 111                                 bi.SetBytes(biBuf)
 112                                 bi.Mod(bi, bs)
 113                                 other = int(bi.Uint64())
 114                                 binary.BigEndian.PutUint64(intBuf, cnt)
 115                                 cnt++
 116                                 h.Reset()
 117                                 h.Write(intBuf)
 118                                 h.Write(buf[m])
 119                                 h.Write(buf[other])
 120                                 buf[m] = h.Sum(buf[m][:0])
 121                         }
 122                 }
 123         }
 124         // Extract output from buffer
 125         return buf[sCost-1]
 126 }
 127
 128 // This function adds additional functionality over pure B(): ability to
 129 // run several hashers (jobs) simultaneously and second-preimage resistant
 130 // password double hashing.
 131 //
 132 //     H(p, s, jobs) = hash(p || s || (
 133 //         B(p, s || "1") XOR
 134 //         B(p, s || "2") XOR
 135 //         B(p, s || jobs)
 136 //     ))
 137 func H(hasher func() hash.Hash, passwd, salt []byte, sCost, tCost int, jobs int) []byte {
 138         var i int
 139         results := make(chan []byte)
 140         for ; i < jobs; i++ {
 141                 go func(i int) {
 142                         saltBuf := make([]byte, 8)
 143                         binary.BigEndian.PutUint64(saltBuf, uint64(i))
 144                         results <- B(hasher(), passwd, append(salt, saltBuf...), sCost, tCost)
 145                 }(i)
 146         }
 147         h := hasher()
 148         h.Write(passwd)
 149         h.Write(salt)
 150         result := make([]byte, h.Size())
 151         for i = 0; i < jobs; i++ {
 152                 for n, e := range <-results {
 153                         result[n] ^= e
 154                 }
 155         }
 156         close(results)
 157         h.Write(result)
 158         return h.Sum(result[:0])
 159 }