src/govpn/chaffing/chaffing.go

   1 /*
   2 GoVPN -- simple secure free software virtual private network daemon
   3 Copyright (C) 2014-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 // Chaffing-and-Winnowing.
  20 //
  21 // This package implements Chaffing-and-Winnowing technology
  22 // (http://people.csail.mit.edu/rivest/chaffing-980701.txt).
  23 //
  24 // It outputs two Poly1305 MACs for each bit of input data: one valid,
  25 // and other is not. MACs sequence is following:
  26 //
  27 //     MAC of 1st byte, 1st bit, 0 possible value
  28 //     MAC of 1st byte, 1st bit, 1 possible value
  29 //     MAC of 1st byte, 2nd bit, 0 possible value
  30 //     MAC of 1st byte, 2nd bit, 1 possible value
  31 //     ...
  32 //
  33 // MAC is taken over the "V" string for the valid (enabled) bit value
  34 // and over "I" for invalid one.
  35 //
  36 // Poly1305 uses 256-bit one-time key. We generate it using XSalsa20.
  37 //
  38 //     MACKey = XSalsa20(authKey, nonce, 0x00...)
  39 //     nonce = prefix || byte-num || bit-val
  40 //     bit-val = (0x00|0x01) || 0x00... || bit sequence number
  41 //
  42 // 64-bit prefix is explicitly provided during the chaffing. byte-num is
  43 // big-endian 64-bit byte's sequence number. So 24-bit nonces for
  44 // XSalsa20 will be the following:
  45 //
  46 //     prefix || 0x0000000000000000 || 0x0000000000000000
  47 //     prefix || 0x0000000000000000 || 0x0100000000000000
  48 //     prefix || 0x0000000000000000 || 0x0000000000000001
  49 //     prefix || 0x0000000000000000 || 0x0100000000000001
  50 //     prefix || 0x0000000000000000 || 0x0000000000000002
  51 //     prefix || 0x0000000000000000 || 0x0100000000000002
  52 //     ...
  53 //     prefix || 0x0000000000000001 || 0x0000000000000000
  54 //     prefix || 0x0000000000000001 || 0x0100000000000000
  55 package chaffing
  56
  57 import (
  58         "crypto/subtle"
  59         "encoding/binary"
  60         "errors"
  61
  62         "golang.org/x/crypto/poly1305"
  63         "golang.org/x/crypto/salsa20"
  64 )
  65
  66 const (
  67         EnlargeFactor = 16 * poly1305.TagSize
  68 )
  69
  70 var (
  71         markInvld []byte = []byte("I")
  72         markValid []byte = []byte("V")
  73         macZero   []byte = make([]byte, 32)
  74 )
  75
  76 func zero(macKey *[32]byte) {
  77         for i := 0; i < 32; i++ {
  78                 macKey[i] = 0
  79         }
  80 }
  81
  82 // Chaff the data. noncePrfx is 64-bit nonce. Output data will be much
  83 // larger: 256 bytes for each input byte.
  84 func Chaff(authKey *[32]byte, noncePrfx, in []byte) []byte {
  85         out := make([]byte, len(in)*EnlargeFactor)
  86         macKey := new([32]byte)
  87         nonce := make([]byte, 24)
  88         copy(nonce[:8], noncePrfx)
  89         var i int
  90         var v byte
  91         tag := new([16]byte)
  92         for n, b := range in {
  93                 binary.BigEndian.PutUint64(nonce[8:16], uint64(n))
  94                 for i = 0; i < 8; i++ {
  95                         v = b >> uint8(i) & 1
  96                         nonce[23] = byte(i)
  97                         nonce[16] = 0
  98                         salsa20.XORKeyStream(macKey[:], macZero, nonce, authKey)
  99                         if v == 0 {
 100                                 poly1305.Sum(tag, markValid, macKey)
 101                         } else {
 102                                 poly1305.Sum(tag, markInvld, macKey)
 103                         }
 104                         copy(out[poly1305.TagSize*(n*16+i*2):], tag[:])
 105                         nonce[16] = 1
 106                         salsa20.XORKeyStream(macKey[:], macZero, nonce, authKey)
 107                         if v == 1 {
 108                                 poly1305.Sum(tag, markValid, macKey)
 109                         } else {
 110                                 poly1305.Sum(tag, markInvld, macKey)
 111                         }
 112                         copy(out[poly1305.TagSize*(n*16+i*2+1):], tag[:])
 113                 }
 114         }
 115         zero(macKey)
 116         return out
 117 }
 118
 119 // Winnow the data.
 120 func Winnow(authKey *[32]byte, noncePrfx, in []byte) ([]byte, error) {
 121         if len(in)%EnlargeFactor != 0 {
 122                 return nil, errors.New("Invalid data size")
 123         }
 124         out := make([]byte, len(in)/EnlargeFactor)
 125         macKey := new([32]byte)
 126         defer zero(macKey)
 127         nonce := make([]byte, 24)
 128         copy(nonce[:8], noncePrfx)
 129         tag := new([16]byte)
 130         var i int
 131         var is0 bool
 132         var is1 bool
 133         var v byte
 134         for n := 0; n < len(out); n++ {
 135                 binary.BigEndian.PutUint64(nonce[8:16], uint64(n))
 136                 v = 0
 137                 for i = 0; i < 8; i++ {
 138                         is0 = false
 139                         is1 = false
 140                         nonce[23] = byte(i)
 141                         nonce[16] = 0
 142                         salsa20.XORKeyStream(macKey[:], macZero, nonce, authKey)
 143                         poly1305.Sum(tag, markValid, macKey)
 144                         is0 = subtle.ConstantTimeCompare(
 145                                 tag[:],
 146                                 in[poly1305.TagSize*(n*16+i*2):poly1305.TagSize*(n*16+i*2+1)],
 147                         ) == 1
 148                         nonce[16] = 1
 149                         salsa20.XORKeyStream(macKey[:], macZero, nonce, authKey)
 150                         poly1305.Sum(tag, markValid, macKey)
 151                         is1 = subtle.ConstantTimeCompare(
 152                                 tag[:],
 153                                 in[poly1305.TagSize*(n*16+i*2+1):poly1305.TagSize*(n*16+i*2+2)],
 154                         ) == 1
 155                         if is0 == is1 {
 156                                 return nil, errors.New("Invalid authenticator received")
 157                         }
 158                         if is1 {
 159                                 v = v | 1<<uint8(i)
 160                         }
 161                 }
 162                 out[n] = v
 163         }
 164         return out, nil
 165 }