frodo.go

Documentation: github.com/cloudflare/circl/kem/frodo/frodo640shake

     1  // Package frodo640shake implements the variant FrodoKEM-640 with SHAKE.
     2  package frodo640shake
     3  
     4  import (
     5  	"bytes"
     6  	cryptoRand "crypto/rand"
     7  	"crypto/subtle"
     8  	"io"
     9  
    10  	"github.com/cloudflare/circl/internal/sha3"
    11  	"github.com/cloudflare/circl/kem"
    12  )
    13  
    14  const (
    15  	paramN = 640
    16  
    17  	// Denoted by 'mbar' in the FrodoKEM spec.
    18  	paramNbar = 8
    19  
    20  	logQ       = 15
    21  	logQMask   = ((1 << logQ) - 1)
    22  	seedASize  = 16
    23  	pkHashSize = 16
    24  
    25  	// Denoted by 'B' in the FrodoKEM spec.
    26  	extractedBits = 2
    27  
    28  	messageSize        = 16
    29  	matrixBpPackedSize = (logQ * (paramN * paramNbar)) / 8
    30  )
    31  
    32  const (
    33  	// Size of seed for NewKeyFromSeed.
    34  	// = len(s) + len(seedSE) + len(z).
    35  	KeySeedSize = SharedKeySize + SharedKeySize + 16
    36  
    37  	// Size of seed for EncapsulateTo.
    38  	EncapsulationSeedSize = 16
    39  
    40  	// Size of the established shared key.
    41  	SharedKeySize = 16
    42  
    43  	// Size of the encapsulated shared key.
    44  	CiphertextSize = 9720
    45  
    46  	// Size of a packed public key.
    47  	PublicKeySize = 9616
    48  
    49  	// Size of a packed private key.
    50  	PrivateKeySize = 19888
    51  )
    52  
    53  // Multi-dimensional arrays are stored in 1-dimensional arrays in
    54  // row-major order.
    55  type (
    56  	nByNU16       [paramN * paramN]uint16
    57  	nByNbarU16    [paramN * paramNbar]uint16
    58  	nbarByNU16    [paramNbar * paramN]uint16
    59  	nbarByNbarU16 [paramNbar * paramNbar]uint16
    60  )
    61  
    62  // Type of a FrodoKEM-640-SHAKE public key
    63  type PublicKey struct {
    64  	seedA   [seedASize]byte
    65  	matrixB nByNbarU16
    66  }
    67  
    68  // Type of a FrodoKEM-640-SHAKE private key
    69  type PrivateKey struct {
    70  	hashInputIfDecapsFail [SharedKeySize]byte
    71  	pk                    *PublicKey
    72  
    73  	// matrixS stores transpose(S)
    74  	matrixS nByNbarU16
    75  
    76  	// H(packed(pk))
    77  	hpk [pkHashSize]byte
    78  }
    79  
    80  // NewKeyFromSeed derives a public/private keypair deterministically
    81  // from the given seed.
    82  //
    83  // Panics if seed is not of length KeySeedSize.
    84  func newKeyFromSeed(seed []byte) (*PublicKey, *PrivateKey) {
    85  	if len(seed) != KeySeedSize {
    86  		panic("seed must be of length KeySeedSize")
    87  	}
    88  
    89  	var sk PrivateKey
    90  	var pk PublicKey
    91  
    92  	var E nByNbarU16
    93  	var byteSE [2 * (len(sk.matrixS) + len(E))]byte
    94  
    95  	var A nByNU16
    96  
    97  	// Generate the secret value s, and the seed for S, E, and A. Add seedA to the public key
    98  	shake128 := sha3.NewShake128()
    99  	_, _ = shake128.Write(seed[2*SharedKeySize:])
   100  	_, _ = shake128.Read(pk.seedA[:])
   101  
   102  	shake128.Reset()
   103  	_, _ = shake128.Write([]byte{0x5F})
   104  	_, _ = shake128.Write(seed[SharedKeySize : 2*SharedKeySize])
   105  	_, _ = shake128.Read(byteSE[:])
   106  
   107  	i := 0
   108  	for i < len(sk.matrixS) {
   109  		sk.matrixS[i] = uint16(byteSE[i*2]) | (uint16(byteSE[(i*2)+1]) << 8)
   110  		i++
   111  	}
   112  	sample(sk.matrixS[:])
   113  
   114  	for j := range E {
   115  		E[j] = uint16(byteSE[i*2]) | (uint16(byteSE[(i*2)+1]) << 8)
   116  		i++
   117  	}
   118  	sample(E[:])
   119  
   120  	expandSeedIntoA(&A, &pk.seedA, &shake128)
   121  	mulAddASPlusE(&pk.matrixB, &A, &sk.matrixS, &E)
   122  
   123  	// Populate the private key
   124  	copy(sk.hashInputIfDecapsFail[:], seed[0:SharedKeySize])
   125  	sk.pk = &pk
   126  
   127  	// Add H(pk) to the private key
   128  	shake128.Reset()
   129  	var ppk [PublicKeySize]byte
   130  	pk.Pack(ppk[:])
   131  	_, _ = shake128.Write(ppk[:])
   132  	_, _ = shake128.Read(sk.hpk[:])
   133  
   134  	return &pk, &sk
   135  }
   136  
   137  // GenerateKeyPair generates public and private keys using entropy from rand.
   138  // If rand is nil, crypto/rand.Reader will be used.
   139  func generateKeyPair(rand io.Reader) (*PublicKey, *PrivateKey, error) {
   140  	var seed [KeySeedSize]byte
   141  	if rand == nil {
   142  		rand = cryptoRand.Reader
   143  	}
   144  	_, err := io.ReadFull(rand, seed[:])
   145  	if err != nil {
   146  		return nil, nil, err
   147  	}
   148  	pk, sk := newKeyFromSeed(seed[:])
   149  	return pk, sk, err
   150  }
   151  
   152  // EncapsulateTo generates a shared key and a ciphertext containing said key
   153  // from the public key and the randomness from seed and writes the shared key
   154  // to ss and ciphertext to ct.
   155  //
   156  // Panics if ss, ct, or seed are not of length SharedKeySize, CiphertextSize
   157  // and EncapsulationSeedSize respectively.
   158  //
   159  // seed may be nil, in which case crypto/rand.Reader is used to generate one.
   160  func (pk *PublicKey) EncapsulateTo(ct []byte, ss []byte, seed []byte) {
   161  	if seed == nil {
   162  		seed = make([]byte, EncapsulationSeedSize)
   163  		if _, err := cryptoRand.Read(seed[:]); err != nil {
   164  			panic(err)
   165  		}
   166  	}
   167  	if len(seed) != EncapsulationSeedSize {
   168  		panic("seed must be of length EncapsulationSeedSize")
   169  	}
   170  	if len(ct) != CiphertextSize {
   171  		panic("ct must be of length CiphertextSize")
   172  	}
   173  	if len(ss) != SharedKeySize {
   174  		panic("ss must be of length SharedKeySize")
   175  	}
   176  
   177  	var G2out [2 * SharedKeySize]byte
   178  
   179  	var SpEpEpp [(paramN * paramNbar) + (paramN * paramNbar) + (paramNbar * paramNbar)]uint16
   180  	var byteSpEpEpp [2 * len(SpEpEpp)]byte
   181  	Sp := SpEpEpp[:paramN*paramNbar]
   182  	Ep := SpEpEpp[paramN*paramNbar : 2*paramN*paramNbar]
   183  	Epp := SpEpEpp[2*paramN*paramNbar:]
   184  
   185  	var Bp nbarByNU16
   186  
   187  	var V nbarByNbarU16
   188  	var C nbarByNbarU16
   189  
   190  	var A nByNU16
   191  
   192  	var hpk [pkHashSize]byte
   193  
   194  	var mu [messageSize]byte
   195  	copy(mu[:], seed[:messageSize])
   196  
   197  	// compute hpk = G_1(packed(pk))
   198  	shake128 := sha3.NewShake128()
   199  	var ppk [PublicKeySize]byte
   200  	pk.Pack(ppk[:])
   201  	_, _ = shake128.Write(ppk[:])
   202  	_, _ = shake128.Read(hpk[:])
   203  
   204  	// compute (seedSE || k) = G_2(hpk || mu)
   205  	shake128.Reset()
   206  	_, _ = shake128.Write(hpk[:])
   207  	_, _ = shake128.Write(mu[:])
   208  	_, _ = shake128.Read(G2out[:])
   209  
   210  	// Generate Sp, Ep, Epp, and A, and compute:
   211  	// Bp = Sp*A + Ep
   212  	// V = Sp*B + Epp
   213  	shake128.Reset()
   214  	_, _ = shake128.Write([]byte{0x96})
   215  	_, _ = shake128.Write(G2out[:SharedKeySize])
   216  	_, _ = shake128.Read(byteSpEpEpp[:])
   217  	for i := range SpEpEpp {
   218  		SpEpEpp[i] = uint16(byteSpEpEpp[i*2]) | (uint16(byteSpEpEpp[(i*2)+1]) << 8)
   219  	}
   220  	sample(SpEpEpp[:])
   221  
   222  	expandSeedIntoA(&A, &pk.seedA, &shake128)
   223  	mulAddSAPlusE(&Bp, Sp, &A, Ep)
   224  
   225  	mulAddSBPlusE(&V, Sp, &pk.matrixB, Epp)
   226  
   227  	// Encode mu, and compute C = V + enc(mu) (mod q)
   228  	encodeMessage(&C, &mu)
   229  	add(&C, &V, &C)
   230  
   231  	// Prepare the ciphertext
   232  	pack(ct[:matrixBpPackedSize], Bp[:])
   233  	pack(ct[matrixBpPackedSize:], C[:])
   234  
   235  	// Compute ss = F(ct||k)
   236  	shake128.Reset()
   237  	_, _ = shake128.Write(ct[:])
   238  	_, _ = shake128.Write(G2out[SharedKeySize:])
   239  	_, _ = shake128.Read(ss[:])
   240  }
   241  
   242  // DecapsulateTo computes the shared key that is encapsulated in ct
   243  // from the private key.
   244  //
   245  // Panics if ct or ss are not of length CiphertextSize and SharedKeySize
   246  // respectively.
   247  func (sk *PrivateKey) DecapsulateTo(ss, ct []byte) {
   248  	if len(ct) != CiphertextSize {
   249  		panic("ct must be of length CiphertextSize")
   250  	}
   251  	if len(ss) != SharedKeySize {
   252  		panic("ss must be of length SharedKeySize")
   253  	}
   254  
   255  	var Bp nbarByNU16
   256  	var C nbarByNbarU16
   257  
   258  	var W nbarByNbarU16
   259  	var CC nbarByNbarU16
   260  	var BBp nbarByNU16
   261  
   262  	var SpEpEpp [(paramN * paramNbar) + (paramN * paramNbar) + (paramNbar * paramNbar)]uint16
   263  	var byteSpEpEpp [2 * len(SpEpEpp)]byte
   264  	Sp := SpEpEpp[:paramN*paramNbar]
   265  	Ep := SpEpEpp[paramN*paramNbar : 2*paramN*paramNbar]
   266  	Epp := SpEpEpp[2*paramN*paramNbar:]
   267  
   268  	var A nByNU16
   269  
   270  	var muprime [messageSize]byte
   271  	var G2out [2 * SharedKeySize]byte
   272  
   273  	kprime := G2out[SharedKeySize:]
   274  
   275  	// Compute W = C - Bp*S (mod q), and decode the randomness mu
   276  	unpack(Bp[:], ct[0:matrixBpPackedSize])
   277  	unpack(C[:], ct[matrixBpPackedSize:])
   278  	mulBS(&W, &Bp, &sk.matrixS)
   279  	sub(&W, &C, &W)
   280  
   281  	decodeMessage(&muprime, &W)
   282  
   283  	// Generate (seedSE' || k') = G_2(hpk || mu')
   284  	shake128 := sha3.NewShake128()
   285  	_, _ = shake128.Write(sk.hpk[:])
   286  	_, _ = shake128.Write(muprime[:])
   287  	_, _ = shake128.Read(G2out[:])
   288  
   289  	// Generate Sp, Ep, Epp, A, and compute BBp = Sp*A + Ep.
   290  	shake128.Reset()
   291  	_, _ = shake128.Write([]byte{0x96})
   292  	_, _ = shake128.Write(G2out[:SharedKeySize])
   293  	_, _ = shake128.Read(byteSpEpEpp[:])
   294  	for i := range SpEpEpp {
   295  		SpEpEpp[i] = uint16(byteSpEpEpp[i*2]) | (uint16(byteSpEpEpp[(i*2)+1]) << 8)
   296  	}
   297  
   298  	sample(SpEpEpp[:])
   299  
   300  	expandSeedIntoA(&A, &sk.pk.seedA, &shake128)
   301  	mulAddSAPlusE(&BBp, Sp[:], &A, Ep[:])
   302  
   303  	// Reduce BBp modulo q
   304  	for i := range BBp {
   305  		BBp[i] = BBp[i] & logQMask
   306  	}
   307  
   308  	// compute W = Sp*B + Epp
   309  	mulAddSBPlusE(&W, Sp, &sk.pk.matrixB, Epp)
   310  
   311  	// Encode mu, and compute CC = W + enc(mu') (mod q)
   312  	encodeMessage(&CC, &muprime)
   313  	add(&CC, &W, &CC)
   314  
   315  	// Prepare input to F
   316  
   317  	// If (Bp == BBp & C == CC) then ss = F(ct || k'), else ss = F(ct || s)
   318  	// Needs to avoid branching on secret data as per:
   319  	//     Qian Guo, Thomas Johansson, Alexander Nilsson. A key-recovery timing attack on post-quantum
   320  	//     primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM. In CRYPTO 2020.
   321  	selector := ctCompareU16(Bp[:], BBp[:]) | ctCompareU16(C[:], CC[:])
   322  	// If (selector == 0) then load k' to do ss = F(ct || k'), else if (selector == 1) load s to do ss = F(ct || s)
   323  	subtle.ConstantTimeCopy(selector, kprime[:], sk.hashInputIfDecapsFail[:])
   324  
   325  	shake128.Reset()
   326  	_, _ = shake128.Write(ct[:])
   327  	_, _ = shake128.Write(kprime[:])
   328  	_, _ = shake128.Read(ss[:])
   329  }
   330  
   331  // Packs sk to buf.
   332  //
   333  // Panics if buf is not of size PrivateKeySize.
   334  func (sk *PrivateKey) Pack(buf []byte) {
   335  	if len(buf) != PrivateKeySize {
   336  		panic("buf must be of length PrivateKeySize")
   337  	}
   338  
   339  	copy(buf[:SharedKeySize], sk.hashInputIfDecapsFail[:])
   340  	buf = buf[SharedKeySize:]
   341  
   342  	sk.pk.Pack(buf[:PublicKeySize])
   343  	buf = buf[PublicKeySize:]
   344  
   345  	j := 0
   346  	for i := range sk.matrixS {
   347  		buf[j] = byte(sk.matrixS[i])
   348  		buf[j+1] = byte(sk.matrixS[i] >> 8)
   349  		j += 2
   350  	}
   351  	buf = buf[j:]
   352  
   353  	copy(buf[:], sk.hpk[:])
   354  }
   355  
   356  // Unpacks sk from buf.
   357  //
   358  // Panics if buf is not of size PrivateKeySize.
   359  func (sk *PrivateKey) Unpack(buf []byte) {
   360  	if len(buf) != PrivateKeySize {
   361  		panic("buf must be of length PrivateKeySize")
   362  	}
   363  
   364  	copy(sk.hashInputIfDecapsFail[:], buf[:SharedKeySize])
   365  	buf = buf[SharedKeySize:]
   366  
   367  	sk.pk = new(PublicKey)
   368  	sk.pk.Unpack(buf[:PublicKeySize])
   369  	buf = buf[PublicKeySize:]
   370  
   371  	for i := range sk.matrixS {
   372  		sk.matrixS[i] = uint16(buf[i*2]) | (uint16(buf[(i*2)+1]) << 8)
   373  	}
   374  	buf = buf[len(sk.matrixS)*2:]
   375  
   376  	copy(sk.hpk[:], buf[:])
   377  }
   378  
   379  // Packs pk to buf.
   380  //
   381  // Panics if buf is not of size PublicKeySize.
   382  func (pk *PublicKey) Pack(buf []byte) {
   383  	if len(buf) != PublicKeySize {
   384  		panic("buf must be of length PublicKeySize")
   385  	}
   386  
   387  	copy(buf[:seedASize], pk.seedA[:])
   388  	pack(buf[seedASize:], pk.matrixB[:])
   389  }
   390  
   391  // TODO: Unpacks pk from buf.
   392  //
   393  // Panics if buf is not of size PublicKeySize.
   394  func (pk *PublicKey) Unpack(buf []byte) {
   395  	if len(buf) != PublicKeySize {
   396  		panic("buf must be of length PublicKeySize")
   397  	}
   398  
   399  	copy(pk.seedA[:], buf[:seedASize])
   400  	unpack(pk.matrixB[:], buf[seedASize:])
   401  }
   402  
   403  // Boilerplate down below for the KEM scheme API.
   404  
   405  type scheme struct{}
   406  
   407  var sch kem.Scheme = &scheme{}
   408  
   409  // Scheme returns a KEM interface.
   410  func Scheme() kem.Scheme { return sch }
   411  
   412  func (scheme) Name() string                { return "FrodoKEM-640-SHAKE" }
   413  func (*scheme) PublicKeySize() int         { return PublicKeySize }
   414  func (*scheme) PrivateKeySize() int        { return PrivateKeySize }
   415  func (*scheme) SeedSize() int              { return KeySeedSize }
   416  func (*scheme) SharedKeySize() int         { return SharedKeySize }
   417  func (*scheme) CiphertextSize() int        { return CiphertextSize }
   418  func (*scheme) EncapsulationSeedSize() int { return EncapsulationSeedSize }
   419  
   420  func (sk *PrivateKey) Scheme() kem.Scheme { return sch }
   421  func (pk *PublicKey) Scheme() kem.Scheme  { return sch }
   422  
   423  func (sk *PrivateKey) MarshalBinary() ([]byte, error) {
   424  	var ret [PrivateKeySize]byte
   425  	sk.Pack(ret[:])
   426  	return ret[:], nil
   427  }
   428  
   429  func (sk *PrivateKey) Equal(other kem.PrivateKey) bool {
   430  	oth, ok := other.(*PrivateKey)
   431  	if !ok {
   432  		return false
   433  	}
   434  	if sk.pk == nil && oth.pk == nil {
   435  		return true
   436  	}
   437  	if sk.pk == nil || oth.pk == nil {
   438  		return false
   439  	}
   440  	return ctCompareU16(sk.matrixS[:], oth.matrixS[:]) == 0 &&
   441  		subtle.ConstantTimeCompare(sk.hashInputIfDecapsFail[:], oth.hashInputIfDecapsFail[:]) == 1 &&
   442  		sk.pk.Equal(oth.pk) &&
   443  		bytes.Equal(sk.hpk[:], oth.hpk[:])
   444  }
   445  
   446  func (pk *PublicKey) Equal(other kem.PublicKey) bool {
   447  	oth, ok := other.(*PublicKey)
   448  	if !ok {
   449  		return false
   450  	}
   451  	if pk == nil && oth == nil {
   452  		return true
   453  	}
   454  	if pk == nil || oth == nil {
   455  		return false
   456  	}
   457  
   458  	for i := range pk.matrixB {
   459  		if (pk.matrixB[i] & logQMask) != (oth.matrixB[i] & logQMask) {
   460  			return false
   461  		}
   462  	}
   463  	return bytes.Equal(pk.seedA[:], oth.seedA[:])
   464  }
   465  
   466  func (sk *PrivateKey) Public() kem.PublicKey {
   467  	return sk.pk
   468  }
   469  
   470  func (pk *PublicKey) MarshalBinary() ([]byte, error) {
   471  	var ret [PublicKeySize]byte
   472  	pk.Pack(ret[:])
   473  	return ret[:], nil
   474  }
   475  
   476  func (*scheme) GenerateKeyPair() (kem.PublicKey, kem.PrivateKey, error) {
   477  	return generateKeyPair(cryptoRand.Reader)
   478  }
   479  
   480  func (*scheme) DeriveKeyPair(seed []byte) (kem.PublicKey, kem.PrivateKey) {
   481  	if len(seed) != KeySeedSize {
   482  		panic(kem.ErrSeedSize)
   483  	}
   484  	return newKeyFromSeed(seed[:])
   485  }
   486  
   487  func (*scheme) Encapsulate(pk kem.PublicKey) (ct, ss []byte, err error) {
   488  	ct = make([]byte, CiphertextSize)
   489  	ss = make([]byte, SharedKeySize)
   490  
   491  	pub, ok := pk.(*PublicKey)
   492  	if !ok {
   493  		return nil, nil, kem.ErrTypeMismatch
   494  	}
   495  	pub.EncapsulateTo(ct, ss, nil)
   496  	return
   497  }
   498  
   499  func (*scheme) EncapsulateDeterministically(
   500  	pk kem.PublicKey, seed []byte,
   501  ) (ct, ss []byte, err error) {
   502  	if len(seed) != EncapsulationSeedSize {
   503  		return nil, nil, kem.ErrSeedSize
   504  	}
   505  
   506  	ct = make([]byte, CiphertextSize)
   507  	ss = make([]byte, SharedKeySize)
   508  
   509  	pub, ok := pk.(*PublicKey)
   510  	if !ok {
   511  		return nil, nil, kem.ErrTypeMismatch
   512  	}
   513  	pub.EncapsulateTo(ct, ss, seed)
   514  	return
   515  }
   516  
   517  func (*scheme) Decapsulate(sk kem.PrivateKey, ct []byte) ([]byte, error) {
   518  	if len(ct) != CiphertextSize {
   519  		return nil, kem.ErrCiphertextSize
   520  	}
   521  
   522  	priv, ok := sk.(*PrivateKey)
   523  	if !ok {
   524  		return nil, kem.ErrTypeMismatch
   525  	}
   526  	ss := make([]byte, SharedKeySize)
   527  	priv.DecapsulateTo(ss, ct)
   528  	return ss, nil
   529  }
   530  
   531  func (*scheme) UnmarshalBinaryPublicKey(buf []byte) (kem.PublicKey, error) {
   532  	if len(buf) != PublicKeySize {
   533  		return nil, kem.ErrPubKeySize
   534  	}
   535  	var ret PublicKey
   536  	ret.Unpack(buf)
   537  	return &ret, nil
   538  }
   539  
   540  func (*scheme) UnmarshalBinaryPrivateKey(buf []byte) (kem.PrivateKey, error) {
   541  	if len(buf) != PrivateKeySize {
   542  		return nil, kem.ErrPrivKeySize
   543  	}
   544  	var ret PrivateKey
   545  	ret.Unpack(buf)
   546  	return &ret, nil
   547  }
   548
View as plain text