From: Sergey Matveev Date: Mon, 10 Jun 2019 10:01:45 +0000 (+0300) Subject: MGM mode X-Git-Tag: 3.0~15 X-Git-Url: http://www.git.cypherpunks.ru/?p=gogost.git;a=commitdiff_plain;h=8d16c661d91aab1db9341fd1e41216b4fc4af50f MGM mode --- diff --git a/README b/README index a5eeb17..a92b6eb 100644 --- a/README +++ b/README @@ -16,6 +16,7 @@ GOST is GOvernment STandard of Russian Federation (and Soviet Union). * GOST R 34.12-2015 128-bit block cipher Кузнечик (Kuznechik) (RFC 7801) * GOST R 34.12-2015 64-bit block cipher Магма (Magma) * GOST R 34.13-2015 padding methods +* MGM AEAD mode for 64 and 128 bit ciphers Known problems: diff --git a/VERSION b/VERSION index cd5ac03..879b416 100644 --- a/VERSION +++ b/VERSION @@ -1 +1 @@ -2.0 +2.1 diff --git a/src/cypherpunks.ru/gogost/mgm/mode.go b/src/cypherpunks.ru/gogost/mgm/mode.go new file mode 100644 index 0000000..f8db796 --- /dev/null +++ b/src/cypherpunks.ru/gogost/mgm/mode.go @@ -0,0 +1,249 @@ +// GoGOST -- Pure Go GOST cryptographic functions library +// Copyright (C) 2015-2019 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 . + +// Multilinear Galois Mode (MGM) block cipher mode. +package mgm + +import ( + "crypto/cipher" + "crypto/hmac" + "encoding/binary" + "errors" + "math/big" +) + +var ( + R64 *big.Int = big.NewInt(0) + R128 *big.Int = big.NewInt(0) +) + +func init() { + R64.SetBytes([]byte{ + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1b, + }) + R128.SetBytes([]byte{ + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x87, + }) +} + +type MGM struct { + maxSize uint64 + cipher cipher.Block + blockSize int + tagSize int + icn []byte + bufP []byte + bufC []byte + padded []byte + sum []byte + + x *big.Int + y *big.Int + z *big.Int + maxBit int + r *big.Int + mulBuf []byte +} + +func NewMGM(cipher cipher.Block, tagSize int) (cipher.AEAD, error) { + blockSize := cipher.BlockSize() + if !(blockSize == 8 || blockSize == 16) { + return nil, errors.New("MGM supports only 64/128 blocksizes") + } + if tagSize < 4 || tagSize > 16 || tagSize > blockSize { + return nil, errors.New("invalid tag size") + } + mgm := MGM{ + maxSize: uint64(1< 0 { + panic("nonce must not have higher bit set") + } +} + +func (mgm *MGM) validateSizes(text, additionalData []byte) { + if len(text) == 0 && len(additionalData) == 0 { + panic("at least either *text or additionalData must be provided") + } + if uint64(len(additionalData)) > mgm.maxSize { + panic("additionalData is too big") + } + if uint64(len(text)+len(additionalData)) > mgm.maxSize { + panic("*text with additionalData are too big") + } +} + +func (mgm *MGM) auth(out, text, ad []byte) { + for i := 0; i < mgm.blockSize; i++ { + mgm.sum[i] = 0 + } + adLen := len(ad) * 8 + textLen := len(text) * 8 + mgm.icn[0] |= 0x80 + mgm.cipher.Encrypt(mgm.bufP, mgm.icn) // Z_1 = E_K(1 || ICN) + for len(ad) >= mgm.blockSize { + mgm.cipher.Encrypt(mgm.bufC, mgm.bufP) // H_i = E_K(Z_i) + xor( // sum (xor)= H_i (x) A_i + mgm.sum, + mgm.sum, + mgm.mul(mgm.bufC, ad[:mgm.blockSize]), + ) + incr(mgm.bufP[:mgm.blockSize/2]) // Z_{i+1} = incr_l(Z_i) + ad = ad[mgm.blockSize:] + } + if len(ad) > 0 { + copy(mgm.padded, ad) + for i := len(ad); i < mgm.blockSize; i++ { + mgm.padded[i] = 0 + } + mgm.cipher.Encrypt(mgm.bufC, mgm.bufP) + xor(mgm.sum, mgm.sum, mgm.mul(mgm.bufC, mgm.padded)) + incr(mgm.bufP[:mgm.blockSize/2]) + } + + for len(text) >= mgm.blockSize { + mgm.cipher.Encrypt(mgm.bufC, mgm.bufP) // H_{h+j} = E_K(Z_{h+j}) + xor( // sum (xor)= H_{h+j} (x) C_j + mgm.sum, + mgm.sum, + mgm.mul(mgm.bufC, text[:mgm.blockSize]), + ) + incr(mgm.bufP[:mgm.blockSize/2]) // Z_{h+j+1} = incr_l(Z_{h+j}) + text = text[mgm.blockSize:] + } + if len(text) > 0 { + copy(mgm.padded, text) + for i := len(text); i < mgm.blockSize; i++ { + mgm.padded[i] = 0 + } + mgm.cipher.Encrypt(mgm.bufC, mgm.bufP) + xor(mgm.sum, mgm.sum, mgm.mul(mgm.bufC, mgm.padded)) + incr(mgm.bufP[:mgm.blockSize/2]) + } + + mgm.cipher.Encrypt(mgm.bufP, mgm.bufP) // H_{h+q+1} = E_K(Z_{h+q+1}) + // len(A) || len(C) + if mgm.blockSize == 8 { + binary.BigEndian.PutUint32(mgm.bufC, uint32(adLen)) + binary.BigEndian.PutUint32(mgm.bufC[mgm.blockSize/2:], uint32(textLen)) + } else { + binary.BigEndian.PutUint64(mgm.bufC, uint64(adLen)) + binary.BigEndian.PutUint64(mgm.bufC[mgm.blockSize/2:], uint64(textLen)) + } + // sum (xor)= H_{h+q+1} (x) (len(A) || len(C)) + xor(mgm.sum, mgm.sum, mgm.mul(mgm.bufP, mgm.bufC)) + mgm.cipher.Encrypt(mgm.bufP, mgm.sum) // E_K(sum) + copy(out, mgm.bufP[:mgm.tagSize]) // MSB_S(E_K(sum)) +} + +func (mgm *MGM) crypt(out, in []byte) { + mgm.icn[0] &= 0x7F + mgm.cipher.Encrypt(mgm.bufP, mgm.icn) // Y_1 = E_K(0 || ICN) + for len(in) >= mgm.blockSize { + mgm.cipher.Encrypt(mgm.bufC, mgm.bufP) // E_K(Y_i) + xor(out, mgm.bufC, in) // C_i = P_i (xor) E_K(Y_i) + incr(mgm.bufP[mgm.blockSize/2:]) // Y_i = incr_r(Y_{i-1}) + out = out[mgm.blockSize:] + in = in[mgm.blockSize:] + } + if len(in) > 0 { + mgm.cipher.Encrypt(mgm.bufC, mgm.bufP) + xor(out, in, mgm.bufC) + } +} + +func (mgm *MGM) Seal(dst, nonce, plaintext, additionalData []byte) []byte { + mgm.validateNonce(nonce) + mgm.validateSizes(plaintext, additionalData) + if uint64(len(plaintext)) > mgm.maxSize { + panic("plaintext is too big") + } + ret, out := sliceForAppend(dst, len(plaintext)+mgm.tagSize) + copy(mgm.icn, nonce) + mgm.crypt(out, plaintext) + mgm.auth( + out[len(plaintext):len(plaintext)+mgm.tagSize], + out[:len(plaintext)], + additionalData, + ) + return ret +} + +func (mgm *MGM) Open(dst, nonce, ciphertext, additionalData []byte) ([]byte, error) { + mgm.validateNonce(nonce) + mgm.validateSizes(ciphertext, additionalData) + if uint64(len(ciphertext)-mgm.tagSize) > mgm.maxSize { + panic("ciphertext is too big") + } + ret, out := sliceForAppend(dst, len(ciphertext)-mgm.tagSize) + ct := ciphertext[:len(ciphertext)-mgm.tagSize] + copy(mgm.icn, nonce) + mgm.auth(mgm.sum, ct, additionalData) + if !hmac.Equal(mgm.sum[:mgm.tagSize], ciphertext[len(ciphertext)-mgm.tagSize:]) { + return nil, errors.New("invalid authentication tag") + } + mgm.crypt(out, ct) + return ret, nil +} diff --git a/src/cypherpunks.ru/gogost/mgm/mode_test.go b/src/cypherpunks.ru/gogost/mgm/mode_test.go new file mode 100644 index 0000000..84f0ef1 --- /dev/null +++ b/src/cypherpunks.ru/gogost/mgm/mode_test.go @@ -0,0 +1,148 @@ +// GoGOST -- Pure Go GOST cryptographic functions library +// Copyright (C) 2015-2019 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 mgm + +import ( + "bytes" + "crypto/cipher" + "crypto/rand" + "testing" + "testing/quick" + + "cypherpunks.ru/gogost/gost3412128" + "cypherpunks.ru/gogost/gost341264" +) + +func TestVector(t *testing.T) { + key := [gost3412128.KeySize]byte{ + 0x88, 0x99, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF, + 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, + 0xFE, 0xDC, 0xBA, 0x98, 0x76, 0x54, 0x32, 0x10, + 0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF, + } + additionalData := []byte{ + 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, + 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, + 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, + 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, + 0xEA, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, + 0x05, + } + plaintext := []byte{ + 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x00, + 0xFF, 0xEE, 0xDD, 0xCC, 0xBB, 0xAA, 0x99, 0x88, + 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, + 0x88, 0x99, 0xAA, 0xBB, 0xCC, 0xEE, 0xFF, 0x0A, + 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, + 0x99, 0xAA, 0xBB, 0xCC, 0xEE, 0xFF, 0x0A, 0x00, + 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 0x99, + 0xAA, 0xBB, 0xCC, 0xEE, 0xFF, 0x0A, 0x00, 0x11, + 0xAA, 0xBB, 0xCC, + } + c := gost3412128.NewCipher(key) + nonce := plaintext[:16] + aead, _ := NewMGM(c, 16) + sealed := aead.Seal(nil, nonce, plaintext, additionalData) + if bytes.Compare(sealed[:len(plaintext)], []byte{ + 0xA9, 0x75, 0x7B, 0x81, 0x47, 0x95, 0x6E, 0x90, + 0x55, 0xB8, 0xA3, 0x3D, 0xE8, 0x9F, 0x42, 0xFC, + 0x80, 0x75, 0xD2, 0x21, 0x2B, 0xF9, 0xFD, 0x5B, + 0xD3, 0xF7, 0x06, 0x9A, 0xAD, 0xC1, 0x6B, 0x39, + 0x49, 0x7A, 0xB1, 0x59, 0x15, 0xA6, 0xBA, 0x85, + 0x93, 0x6B, 0x5D, 0x0E, 0xA9, 0xF6, 0x85, 0x1C, + 0xC6, 0x0C, 0x14, 0xD4, 0xD3, 0xF8, 0x83, 0xD0, + 0xAB, 0x94, 0x42, 0x06, 0x95, 0xC7, 0x6D, 0xEB, + 0x2C, 0x75, 0x52, + }) != 0 { + t.FailNow() + } + if bytes.Compare(sealed[len(plaintext):], []byte{ + 0xCF, 0x5D, 0x65, 0x6F, 0x40, 0xC3, 0x4F, 0x5C, + 0x46, 0xE8, 0xBB, 0x0E, 0x29, 0xFC, 0xDB, 0x4C, + }) != 0 { + t.FailNow() + } + _, err := aead.Open(sealed[:0], nonce, sealed, additionalData) + if err != nil { + t.FailNow() + } + if bytes.Compare(sealed[:len(plaintext)], plaintext) != 0 { + t.FailNow() + } +} + +func TestSymmetric(t *testing.T) { + sym := func(keySize, blockSize int, c cipher.Block, nonce []byte) { + f := func( + plaintext, additionalData []byte, + initials [][]byte, + tagSize uint8, + ) bool { + if len(plaintext) == 0 && len(additionalData) == 0 { + return true + } + tagSize = 4 + tagSize%uint8(blockSize-4) + aead, err := NewMGM(c, int(tagSize)) + if err != nil { + return false + } + for _, initial := range initials { + sealed := aead.Seal(initial, nonce, plaintext, additionalData) + if bytes.Compare(sealed[:len(initial)], initial) != 0 { + return false + } + pt, err := aead.Open( + sealed[:0], + nonce, + sealed[len(initial):], + additionalData, + ) + if err != nil || bytes.Compare(pt, plaintext) != 0 { + return false + } + } + return true + } + if err := quick.Check(f, nil); err != nil { + t.Error(err) + } + } + + key128 := new([gost3412128.KeySize]byte) + if _, err := rand.Read(key128[:]); err != nil { + panic(err) + } + nonce := make([]byte, gost3412128.BlockSize) + if _, err := rand.Read(key128[1:]); err != nil { + panic(err) + } + sym( + gost3412128.KeySize, + gost3412128.BlockSize, + gost3412128.NewCipher(*key128), + nonce[:gost3412128.BlockSize], + ) + + key64 := new([gost341264.KeySize]byte) + copy(key64[:], key128[:]) + sym( + gost341264.KeySize, + gost341264.BlockSize, + gost341264.NewCipher(*key64), + nonce[:gost341264.BlockSize], + ) +} diff --git a/src/cypherpunks.ru/gogost/mgm/mul.go b/src/cypherpunks.ru/gogost/mgm/mul.go new file mode 100644 index 0000000..3401232 --- /dev/null +++ b/src/cypherpunks.ru/gogost/mgm/mul.go @@ -0,0 +1,44 @@ +// GoGOST -- Pure Go GOST cryptographic functions library +// Copyright (C) 2015-2019 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 mgm + +func (mgm *MGM) mul(xBuf, yBuf []byte) []byte { + mgm.x.SetBytes(xBuf) + mgm.y.SetBytes(yBuf) + mgm.z.SetInt64(0) + var i int + for mgm.y.BitLen() != 0 { + if mgm.y.Bit(0) == 1 { + mgm.z.Xor(mgm.z, mgm.x) + } + if mgm.x.Bit(mgm.maxBit) == 1 { + mgm.x.SetBit(mgm.x, mgm.maxBit, 0) + mgm.x.Lsh(mgm.x, 1) + mgm.x.Xor(mgm.x, mgm.r) + } else { + mgm.x.Lsh(mgm.x, 1) + } + mgm.y.Rsh(mgm.y, 1) + } + zBytes := mgm.z.Bytes() + rem := len(xBuf) - len(zBytes) + for i = 0; i < rem; i++ { + mgm.mulBuf[i] = 0 + } + copy(mgm.mulBuf[rem:], zBytes) + return mgm.mulBuf +} diff --git a/src/cypherpunks.ru/gogost/mgm/mul_test.go b/src/cypherpunks.ru/gogost/mgm/mul_test.go new file mode 100644 index 0000000..7985ebb --- /dev/null +++ b/src/cypherpunks.ru/gogost/mgm/mul_test.go @@ -0,0 +1,64 @@ +// GoGOST -- Pure Go GOST cryptographic functions library +// Copyright (C) 2015-2019 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 mgm + +import ( + "crypto/rand" + "math/big" + "testing" + + "cypherpunks.ru/gogost/gost3412128" + "cypherpunks.ru/gogost/gost341264" +) + +func BenchmarkMul64(b *testing.B) { + x := make([]byte, gost341264.BlockSize) + y := make([]byte, gost341264.BlockSize) + rand.Read(x) + rand.Read(y) + mgm := MGM{ + x: big.NewInt(0), + y: big.NewInt(0), + z: big.NewInt(0), + maxBit: 64 - 1, + r: R64, + mulBuf: make([]byte, gost341264.BlockSize), + } + b.ResetTimer() + for i := 0; i < b.N; i++ { + mgm.mul(x, y) + } +} + +func BenchmarkMul128(b *testing.B) { + x := make([]byte, gost3412128.BlockSize) + y := make([]byte, gost3412128.BlockSize) + rand.Read(x) + rand.Read(y) + mgm := MGM{ + x: big.NewInt(0), + y: big.NewInt(0), + z: big.NewInt(0), + maxBit: 128 - 1, + r: R128, + mulBuf: make([]byte, gost3412128.BlockSize), + } + b.ResetTimer() + for i := 0; i < b.N; i++ { + mgm.mul(x, y) + } +} diff --git a/src/cypherpunks.ru/gogost/mgm/slice.go b/src/cypherpunks.ru/gogost/mgm/slice.go new file mode 100644 index 0000000..d2086cc --- /dev/null +++ b/src/cypherpunks.ru/gogost/mgm/slice.go @@ -0,0 +1,13 @@ +package mgm + +// Taken from go/src/crypto/cipher/gcm.go +func sliceForAppend(in []byte, n int) (head, tail []byte) { + if total := len(in) + n; cap(in) >= total { + head = in[:total] + } else { + head = make([]byte, total) + copy(head, in) + } + tail = head[len(in):] + return +}