From 020a4f02b6ffe3bffd17ca6fd078278010e53025 Mon Sep 17 00:00:00 2001 From: Sergey Matveev Date: Tue, 5 Jan 2016 12:13:07 +0300 Subject: [PATCH] Add encryptionless confidentiality preserving encoding Signed-off-by: Sergey Matveev --- src/govpn/aont/aont_test.go | 98 +++++++++++++++++ src/govpn/aont/oaep.go | 104 ++++++++++++++++++ src/govpn/chaffing/chaffing.go | 165 ++++++++++++++++++++++++++++ src/govpn/chaffing/chaffing_test.go | 87 +++++++++++++++ src/govpn/encless.go | 71 ++++++++++++ src/govpn/encless_test.go | 77 +++++++++++++ 6 files changed, 602 insertions(+) create mode 100644 src/govpn/aont/aont_test.go create mode 100644 src/govpn/aont/oaep.go create mode 100644 src/govpn/chaffing/chaffing.go create mode 100644 src/govpn/chaffing/chaffing_test.go create mode 100644 src/govpn/encless.go create mode 100644 src/govpn/encless_test.go diff --git a/src/govpn/aont/aont_test.go b/src/govpn/aont/aont_test.go new file mode 100644 index 0000000..93b7db5 --- /dev/null +++ b/src/govpn/aont/aont_test.go @@ -0,0 +1,98 @@ +/* +GoVPN -- simple secure free software virtual private network daemon +Copyright (C) 2014-2016 Sergey Matveev + +This program is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program. If not, see . +*/ + +package aont + +import ( + "bytes" + "crypto/rand" + "testing" + "testing/quick" +) + +var ( + testKey *[16]byte = new([16]byte) +) + +func init() { + rand.Read(testKey[:]) +} + +func TestSymmetric(t *testing.T) { + f := func(data []byte) bool { + encoded, err := Encode(testKey, data) + if err != nil { + return false + } + if len(encoded) != len(data)+16+32 { + return false + } + decoded, err := Decode(encoded) + if err != nil { + return false + } + return bytes.Compare(decoded, data) == 0 + } + if err := quick.Check(f, nil); err != nil { + t.Error(err) + } +} + +func TestSmallSize(t *testing.T) { + _, err := Decode([]byte("foobar")) + if err == nil { + t.Fail() + } +} + +func TestTampered(t *testing.T) { + f := func(data []byte, index int) bool { + if len(data) == 0 { + return true + } + encoded, _ := Encode(testKey, data) + encoded[len(data)%index] ^= byte('a') + _, err := Decode(encoded) + if err == nil { + return false + } + return true + } + if err := quick.Check(f, nil); err != nil { + t.Error(err) + } +} + +func BenchmarkEncode(b *testing.B) { + data := make([]byte, 128) + rand.Read(data) + b.ResetTimer() + for i := 0; i < b.N; i++ { + Encode(testKey, data) + } +} + +func BenchmarkDecode(b *testing.B) { + data := make([]byte, 128) + rand.Read(data) + encoded, _ := Encode(testKey, data) + b.ResetTimer() + for i := 0; i < b.N; i++ { + Decode(encoded) + } +} diff --git a/src/govpn/aont/oaep.go b/src/govpn/aont/oaep.go new file mode 100644 index 0000000..4e13816 --- /dev/null +++ b/src/govpn/aont/oaep.go @@ -0,0 +1,104 @@ +/* +GoVPN -- simple secure free software virtual private network daemon +Copyright (C) 2014-2016 Sergey Matveev + +This program is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program. If not, see . +*/ + +// All-Or-Nothing-Transform, based on OAEP. +// +// This package implements OAEP (Optimal Asymmetric Encryption Padding) +// (http://cseweb.ucsd.edu/~mihir/papers/oaep.html) +// used there as All-Or-Nothing-Transformation +// (http://theory.lcs.mit.edu/~cis/pubs/rivest/fusion.ps). +// We do not fix OAEP parts lengths, instead we add hash-based +// checksum like in SAEP+ +// (http://crypto.stanford.edu/~dabo/abstracts/saep.html). +// +// AONT takes 128-bit random r, data M to be encoded and produce the +// package PKG: +// +// PKG = P1 || P2 +// P1 = HKDF(BLAKE2b, r) XOR (M || BLAKE2b(M || r)) || +// P2 = BLAKE2b(P1) XOR r +package aont + +import ( + "crypto/subtle" + "errors" + + "github.com/dchest/blake2b" + "golang.org/x/crypto/hkdf" +) + +const ( + HSize = 32 + RSize = 16 +) + +// Encode the data, produce AONT package. Data size will be larger than +// the original one for 48 bytes. +func Encode(r *[RSize]byte, in []byte) ([]byte, error) { + out := make([]byte, len(in)+HSize+RSize) + hr := hkdf.New(blake2b.New512, r[:], nil, nil) + if _, err := hr.Read(out[:len(in)+HSize]); err != nil { + return nil, err + } + var i int + for i = 0; i < len(in); i++ { + out[i] ^= in[i] + } + h := blake2b.New256() + h.Write(r[:]) + h.Write(in) + for _, b := range h.Sum(nil) { + out[i] ^= b + i++ + } + h.Reset() + h.Write(out[:i]) + for _, b := range h.Sum(nil)[:RSize] { + out[i] = b ^ r[i-len(in)-HSize] + i++ + } + return out, nil +} + +// Decode the data from AONT package. Data size will be smaller than the +// original one for 48 bytes. +func Decode(in []byte) ([]byte, error) { + if len(in) < HSize+RSize { + return nil, errors.New("Too small input buffer") + } + h := blake2b.New256() + h.Write(in[:len(in)-RSize]) + out := make([]byte, len(in)-RSize) + for i, b := range h.Sum(nil)[:RSize] { + out[i] = b ^ in[len(in)-RSize+i] + } + h.Reset() + h.Write(out[:RSize]) + hr := hkdf.New(blake2b.New512, out[:RSize], nil, nil) + if _, err := hr.Read(out); err != nil { + return nil, err + } + for i := 0; i < len(out); i++ { + out[i] ^= in[i] + } + h.Write(out[:len(out)-HSize]) + if subtle.ConstantTimeCompare(h.Sum(nil), out[len(out)-HSize:]) != 1 { + return nil, errors.New("Invalid checksum") + } + return out[:len(out)-HSize], nil +} diff --git a/src/govpn/chaffing/chaffing.go b/src/govpn/chaffing/chaffing.go new file mode 100644 index 0000000..cee3ea4 --- /dev/null +++ b/src/govpn/chaffing/chaffing.go @@ -0,0 +1,165 @@ +/* +GoVPN -- simple secure free software virtual private network daemon +Copyright (C) 2014-2016 Sergey Matveev + +This program is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program. If not, see . +*/ + +// Chaffing-and-Winnowing. +// +// This package implements Chaffing-and-Winnowing technology +// (http://people.csail.mit.edu/rivest/chaffing-980701.txt). +// +// It outputs two Poly1305 MACs for each bit of input data: one valid, +// and other is not. MACs sequence is following: +// +// MAC of 1st byte, 1st bit, 0 possible value +// MAC of 1st byte, 1st bit, 1 possible value +// MAC of 1st byte, 2nd bit, 0 possible value +// MAC of 1st byte, 2nd bit, 1 possible value +// ... +// +// MAC is taken over the "V" string for the valid (enabled) bit value +// and over "I" for invalid one. +// +// Poly1305 uses 256-bit one-time key. We generate it using XSalsa20. +// +// MACKey = XSalsa20(authKey, nonce, 0x00...) +// nonce = prefix || byte-num || bit-val +// bit-val = (0x00|0x01) || 0x00... || bit sequence number +// +// 64-bit prefix is explicitly provided during the chaffing. byte-num is +// big-endian 64-bit byte's sequence number. So 24-bit nonces for +// XSalsa20 will be the following: +// +// prefix || 0x0000000000000000 || 0x0000000000000000 +// prefix || 0x0000000000000000 || 0x0100000000000000 +// prefix || 0x0000000000000000 || 0x0000000000000001 +// prefix || 0x0000000000000000 || 0x0100000000000001 +// prefix || 0x0000000000000000 || 0x0000000000000002 +// prefix || 0x0000000000000000 || 0x0100000000000002 +// ... +// prefix || 0x0000000000000001 || 0x0000000000000000 +// prefix || 0x0000000000000001 || 0x0100000000000000 +package chaffing + +import ( + "crypto/subtle" + "encoding/binary" + "errors" + + "golang.org/x/crypto/poly1305" + "golang.org/x/crypto/salsa20" +) + +const ( + EnlargeFactor = 16 * poly1305.TagSize +) + +var ( + markInvld []byte = []byte("I") + markValid []byte = []byte("V") + macZero []byte = make([]byte, 32) +) + +func zero(macKey *[32]byte) { + for i := 0; i < 32; i++ { + macKey[i] = 0 + } +} + +// Chaff the data. noncePrfx is 64-bit nonce. Output data will be much +// larger: 256 bytes for each input byte. +func Chaff(authKey *[32]byte, noncePrfx, in []byte) []byte { + out := make([]byte, len(in)*EnlargeFactor) + macKey := new([32]byte) + nonce := make([]byte, 24) + copy(nonce[:8], noncePrfx) + var i int + var v byte + tag := new([16]byte) + for n, b := range in { + binary.BigEndian.PutUint64(nonce[8:16], uint64(n)) + for i = 0; i < 8; i++ { + v = b >> uint8(i) & 1 + nonce[23] = byte(i) + nonce[16] = 0 + salsa20.XORKeyStream(macKey[:], macZero, nonce, authKey) + if v == 0 { + poly1305.Sum(tag, markValid, macKey) + } else { + poly1305.Sum(tag, markInvld, macKey) + } + copy(out[poly1305.TagSize*(n*16+i*2):], tag[:]) + nonce[16] = 1 + salsa20.XORKeyStream(macKey[:], macZero, nonce, authKey) + if v == 1 { + poly1305.Sum(tag, markValid, macKey) + } else { + poly1305.Sum(tag, markInvld, macKey) + } + copy(out[poly1305.TagSize*(n*16+i*2+1):], tag[:]) + } + } + zero(macKey) + return out +} + +// Winnow the data. +func Winnow(authKey *[32]byte, noncePrfx, in []byte) ([]byte, error) { + if len(in)%EnlargeFactor != 0 { + return nil, errors.New("Invalid data size") + } + out := make([]byte, len(in)/EnlargeFactor) + macKey := new([32]byte) + defer zero(macKey) + nonce := make([]byte, 24) + copy(nonce[:8], noncePrfx) + tag := new([16]byte) + var i int + var is0 bool + var is1 bool + var v byte + for n := 0; n < len(out); n++ { + binary.BigEndian.PutUint64(nonce[8:16], uint64(n)) + v = 0 + for i = 0; i < 8; i++ { + is0 = false + is1 = false + nonce[23] = byte(i) + nonce[16] = 0 + salsa20.XORKeyStream(macKey[:], macZero, nonce, authKey) + poly1305.Sum(tag, markValid, macKey) + is0 = subtle.ConstantTimeCompare( + tag[:], + in[poly1305.TagSize*(n*16+i*2):poly1305.TagSize*(n*16+i*2+1)], + ) == 1 + nonce[16] = 1 + salsa20.XORKeyStream(macKey[:], macZero, nonce, authKey) + poly1305.Sum(tag, markValid, macKey) + is1 = subtle.ConstantTimeCompare( + tag[:], + in[poly1305.TagSize*(n*16+i*2+1):poly1305.TagSize*(n*16+i*2+2)], + ) == 1 + if is0 == is1 { + return nil, errors.New("Invalid authenticator received") + } + if is1 { + v = v | 1< + +This program is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program. If not, see . +*/ + +package chaffing + +import ( + "bytes" + "crypto/rand" + "encoding/binary" + "testing" + "testing/quick" +) + +var ( + testKey *[32]byte = new([32]byte) +) + +func init() { + rand.Read(testKey[:]) +} + +func TestSymmetric(t *testing.T) { + nonce := make([]byte, 8) + f := func(data []byte, pktNum uint64) bool { + if len(data) == 0 { + return true + } + binary.BigEndian.PutUint64(nonce, pktNum) + chaffed := Chaff(testKey, nonce, data) + if len(chaffed) != len(data)*EnlargeFactor { + return false + } + decoded, err := Winnow(testKey, nonce, chaffed) + if err != nil { + return false + } + return bytes.Compare(decoded, data) == 0 + } + if err := quick.Check(f, nil); err != nil { + t.Error(err) + } +} + +func TestSmallSize(t *testing.T) { + _, err := Winnow(testKey, []byte("foobar12"), []byte("foobar")) + if err == nil { + t.Fail() + } +} + +func BenchmarkChaff(b *testing.B) { + nonce := make([]byte, 8) + data := make([]byte, 16) + rand.Read(nonce) + rand.Read(data) + b.ResetTimer() + for i := 0; i < b.N; i++ { + Chaff(testKey, nonce, data) + } +} + +func BenchmarkWinnow(b *testing.B) { + nonce := make([]byte, 8) + data := make([]byte, 16) + rand.Read(nonce) + rand.Read(data) + chaffed := Chaff(testKey, nonce, data) + b.ResetTimer() + for i := 0; i < b.N; i++ { + Winnow(testKey, nonce, chaffed) + } +} diff --git a/src/govpn/encless.go b/src/govpn/encless.go new file mode 100644 index 0000000..d29e5d3 --- /dev/null +++ b/src/govpn/encless.go @@ -0,0 +1,71 @@ +/* +GoVPN -- simple secure free software virtual private network daemon +Copyright (C) 2014-2016 Sergey Matveev + +This program is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program. If not, see . +*/ + +package govpn + +import ( + "govpn/aont" + "govpn/chaffing" +) + +const ( + EncLessEnlargeSize = aont.HSize + aont.RSize*chaffing.EnlargeFactor +) + +// Confidentiality preserving (but encryptionless) encoding. +// +// It uses Chaffing-and-Winnowing technology (it is neither +// encryption nor steganography) over All-Or-Nothing-Transformed data. +// nonce is 64-bit nonce. Output data will be EncLessEnlargeSize larger. +// It also consumes 64-bits of entropy. +func EncLessEncode(authKey *[32]byte, nonce, in []byte) ([]byte, error) { + r := new([aont.RSize]byte) + var err error + if _, err = Rand.Read(r[:]); err != nil { + return nil, err + } + aonted, err := aont.Encode(r, in) + if err != nil { + return nil, err + } + out := append( + chaffing.Chaff(authKey, nonce, aonted[:aont.RSize]), + aonted[aont.RSize:]..., + ) + SliceZero(aonted[:aont.RSize]) + return out, nil +} + +// Decode EncLessEncode-ed data. +func EncLessDecode(authKey *[32]byte, nonce, in []byte) ([]byte, error) { + var err error + winnowed, err := chaffing.Winnow( + authKey, nonce, in[:aont.RSize*chaffing.EnlargeFactor], + ) + if err != nil { + return nil, err + } + out, err := aont.Decode(append( + winnowed, in[aont.RSize*chaffing.EnlargeFactor:]..., + )) + SliceZero(winnowed) + if err != nil { + return nil, err + } + return out, nil +} diff --git a/src/govpn/encless_test.go b/src/govpn/encless_test.go new file mode 100644 index 0000000..89d6d59 --- /dev/null +++ b/src/govpn/encless_test.go @@ -0,0 +1,77 @@ +/* +GoVPN -- simple secure free software virtual private network daemon +Copyright (C) 2014-2016 Sergey Matveev + +This program is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program. If not, see . +*/ + +package govpn + +import ( + "bytes" + "crypto/rand" + "encoding/binary" + "testing" + "testing/quick" +) + +var ( + testKey *[32]byte = new([32]byte) +) + +func init() { + rand.Read(testKey[:]) +} + +func TestEncLessSymmetric(t *testing.T) { + nonce := make([]byte, 8) + f := func(pktNum uint64, in []byte) bool { + binary.BigEndian.PutUint64(nonce, pktNum) + encoded, err := EncLessEncode(testKey, nonce, in) + if err != nil { + return false + } + decoded, err := EncLessDecode(testKey, nonce, encoded) + if err != nil { + return false + } + return bytes.Compare(decoded, in) == 0 + } + if err := quick.Check(f, nil); err != nil { + t.Error(err) + } +} + +func BenchmarkEncLessEncode(b *testing.B) { + nonce := make([]byte, 8) + data := make([]byte, 128) + rand.Read(nonce) + rand.Read(data) + b.ResetTimer() + for i := 0; i < b.N; i++ { + EncLessEncode(testKey, nonce, data) + } +} + +func BenchmarkEncLessDecode(b *testing.B) { + nonce := make([]byte, 8) + data := make([]byte, 128) + rand.Read(nonce) + rand.Read(data) + encoded, _ := EncLessEncode(testKey, nonce, data) + b.ResetTimer() + for i := 0; i < b.N; i++ { + EncLessDecode(testKey, nonce, encoded) + } +} -- 2.44.0