2 GoVPN -- simple secure free software virtual private network daemon
3 Copyright (C) 2014-2019 Sergey Matveev <stargrave@stargrave.org>
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.
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.
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/>.
19 // Chaffing-and-Winnowing.
21 // This package implements Chaffing-and-Winnowing technology
22 // (http://people.csail.mit.edu/rivest/chaffing-980701.txt).
24 // It outputs two Poly1305 MACs for each bit of input data: one valid,
25 // and other is not. MACs sequence is following:
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
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".
37 // Poly1305 uses 256-bit one-time key. We generate it using ChaCha20 for
38 // for the whole byte at once (16 MACs).
40 // MACKey1, MACKey2, ... = ChaCha20(authKey, nonce, 0x00...)
41 // nonce = prefix || big endian byte number
50 "golang.org/x/crypto/poly1305"
54 EnlargeFactor = 16 * poly1305.TagSize
57 func zero(in []byte) {
58 for i := 0; i < len(in); i++ {
63 // Chaff the data. noncePrfx is 64-bit nonce. Output data will be much
64 // larger: 256 bytes for each input byte.
65 func Chaff(authKey *[32]byte, noncePrfx, in []byte) []byte {
66 out := make([]byte, len(in)*EnlargeFactor)
67 keys := make([]byte, 8*64)
68 nonce := new([16]byte)
69 copy(nonce[:8], noncePrfx)
73 macKey := new([32]byte)
74 for n, b := range in {
75 binary.BigEndian.PutUint64(nonce[8:], uint64(n))
76 chacha20.XORKeyStream(keys, keys, nonce, authKey)
77 for i = 0; i < 8; i++ {
78 v = (b >> uint8(i)) & 1
79 copy(macKey[:], keys[64*i:64*i+32])
81 poly1305.Sum(tag, []byte("1"), macKey)
83 poly1305.Sum(tag, []byte("0"), macKey)
85 copy(out[16*(n*16+i*2):], tag[:])
86 copy(macKey[:], keys[64*i+32:64*i+64])
88 poly1305.Sum(tag, []byte("1"), macKey)
90 poly1305.Sum(tag, []byte("0"), macKey)
92 copy(out[16*(n*16+i*2+1):], tag[:])
101 func Winnow(authKey *[32]byte, noncePrfx, in []byte) ([]byte, error) {
102 if len(in)%EnlargeFactor != 0 {
103 return nil, errors.New("Invalid data size")
105 out := make([]byte, len(in)/EnlargeFactor)
106 keys := make([]byte, 8*64)
107 nonce := new([16]byte)
108 copy(nonce[:8], noncePrfx)
112 macKey := new([32]byte)
113 defer zero(macKey[:])
118 for n := 0; n < len(out); n++ {
119 binary.BigEndian.PutUint64(nonce[8:], uint64(n))
120 chacha20.XORKeyStream(keys, keys, nonce, authKey)
122 for i = 0; i < 8; i++ {
123 copy(macKey[:], keys[64*i:64*i+32])
124 poly1305.Sum(tag, []byte("1"), macKey)
125 is01 = subtle.ConstantTimeCompare(
127 in[16*(n*16+i*2):16*(n*16+i*2+1)],
129 poly1305.Sum(tag, []byte("0"), macKey)
130 is00 = subtle.ConstantTimeCompare(
132 in[16*(n*16+i*2):16*(n*16+i*2+1)],
134 copy(macKey[:], keys[64*i+32:64*i+64])
135 poly1305.Sum(tag, []byte("1"), macKey)
136 is11 = subtle.ConstantTimeCompare(
138 in[16*(n*16+i*2+1):16*(n*16+i*2+2)],
140 poly1305.Sum(tag, []byte("0"), macKey)
141 is10 = subtle.ConstantTimeCompare(
143 in[16*(n*16+i*2+1):16*(n*16+i*2+2)],
145 if !((is01 && is10) || (is00 && is11)) {
147 return nil, errors.New("Invalid authenticator received")