src/cypherpunks.ru/govpn/cnw/cnw.go

   1 /*
   2 GoVPN -- simple secure free software virtual private network daemon
   3 Copyright (C) 2014-2017 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 // Package cnw stand for 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 // If bit value is 0, then first MAC is taken over "1" and the second
  34 // one is over "0". If bit value is 1, then first is taken over "0" and
  35 // second is over "1".
  36 //
  37 // Poly1305 uses 256-bit one-time key. We generate it using ChaCha20 for
  38 // for the whole byte at once (16 MACs).
  39 //
  40 //     MACKey1, MACKey2, ... = ChaCha20(authKey, nonce, 0x00...)
  41 //     nonce = prefix || big endian byte number
  42 package cnw
  43
  44 import (
  45         "crypto/subtle"
  46         "encoding/binary"
  47         "errors"
  48
  49         "chacha20"
  50         "golang.org/x/crypto/poly1305"
  51 )
  52
  53 // EnlargeFactor tells how many output bytes will produce single input byte
  54 const EnlargeFactor = 16 * poly1305.TagSize
  55
  56 func zero(in []byte) {
  57         for i := 0; i < len(in); i++ {
  58                 in[i] = 0
  59         }
  60 }
  61
  62 // Chaff the data. noncePrfx is 64-bit nonce. Output data will be much
  63 // larger: 256 bytes for each input byte.
  64 func Chaff(authKey *[32]byte, noncePrfx, in []byte) []byte {
  65         out := make([]byte, len(in)*EnlargeFactor)
  66         keys := make([]byte, 8*64)
  67         nonce := new([16]byte)
  68         copy(nonce[:8], noncePrfx)
  69         var i int
  70         var v byte
  71         tag := new([16]byte)
  72         macKey := new([32]byte)
  73         for n, b := range in {
  74                 binary.BigEndian.PutUint64(nonce[8:], uint64(n))
  75                 chacha20.XORKeyStream(keys, keys, nonce, authKey)
  76                 for i = 0; i < 8; i++ {
  77                         v = (b >> uint8(i)) & 1
  78                         copy(macKey[:], keys[64*i:64*i+32])
  79                         if v == 0 {
  80                                 poly1305.Sum(tag, []byte("1"), macKey)
  81                         } else {
  82                                 poly1305.Sum(tag, []byte("0"), macKey)
  83                         }
  84                         copy(out[16*(n*16+i*2):], tag[:])
  85                         copy(macKey[:], keys[64*i+32:64*i+64])
  86                         if v == 1 {
  87                                 poly1305.Sum(tag, []byte("1"), macKey)
  88                         } else {
  89                                 poly1305.Sum(tag, []byte("0"), macKey)
  90                         }
  91                         copy(out[16*(n*16+i*2+1):], tag[:])
  92                 }
  93                 zero(keys)
  94         }
  95         zero(macKey[:])
  96         return out
  97 }
  98
  99 // Winnow the data.
 100 func Winnow(authKey *[32]byte, noncePrfx, in []byte) ([]byte, error) {
 101         if len(in)%EnlargeFactor != 0 {
 102                 return nil, errors.New("Invalid data size")
 103         }
 104         out := make([]byte, len(in)/EnlargeFactor)
 105         keys := make([]byte, 8*64)
 106         nonce := new([16]byte)
 107         copy(nonce[:8], noncePrfx)
 108         var i int
 109         var v byte
 110         tag := new([16]byte)
 111         macKey := new([32]byte)
 112         defer zero(macKey[:])
 113         var is01 bool
 114         var is00 bool
 115         var is11 bool
 116         var is10 bool
 117         for n := 0; n < len(out); n++ {
 118                 binary.BigEndian.PutUint64(nonce[8:], uint64(n))
 119                 chacha20.XORKeyStream(keys, keys, nonce, authKey)
 120                 v = 0
 121                 for i = 0; i < 8; i++ {
 122                         copy(macKey[:], keys[64*i:64*i+32])
 123                         poly1305.Sum(tag, []byte("1"), macKey)
 124                         is01 = subtle.ConstantTimeCompare(
 125                                 tag[:],
 126                                 in[16*(n*16+i*2):16*(n*16+i*2+1)],
 127                         ) == 1
 128                         poly1305.Sum(tag, []byte("0"), macKey)
 129                         is00 = subtle.ConstantTimeCompare(
 130                                 tag[:],
 131                                 in[16*(n*16+i*2):16*(n*16+i*2+1)],
 132                         ) == 1
 133                         copy(macKey[:], keys[64*i+32:64*i+64])
 134                         poly1305.Sum(tag, []byte("1"), macKey)
 135                         is11 = subtle.ConstantTimeCompare(
 136                                 tag[:],
 137                                 in[16*(n*16+i*2+1):16*(n*16+i*2+2)],
 138                         ) == 1
 139                         poly1305.Sum(tag, []byte("0"), macKey)
 140                         is10 = subtle.ConstantTimeCompare(
 141                                 tag[:],
 142                                 in[16*(n*16+i*2+1):16*(n*16+i*2+2)],
 143                         ) == 1
 144                         if !((is01 && is10) || (is00 && is11)) {
 145                                 zero(keys)
 146                                 return nil, errors.New("Invalid authenticator received")
 147                         }
 148                         if is11 {
 149                                 v = v | 1<<uint8(i)
 150                         }
 151                 }
 152                 out[n] = v
 153                 zero(keys)
 154         }
 155         return out, nil
 156 }