Botan  2.19.1
Crypto and TLS for C++11
Public Types | Public Member Functions | List of all members
Botan::ZFEC Class Reference

#include <zfec.h>

Public Types

typedef std::function< void(size_t, const uint8_t[], size_t)> output_cb_t
 

Public Member Functions

void decode_shares (const std::map< size_t, const uint8_t * > &shares, size_t share_size, output_cb_t output_cb) const
 
void encode (const uint8_t input[], size_t size, output_cb_t output_cb) const
 
void encode_shares (const std::vector< const uint8_t * > &shares, size_t share_size, output_cb_t output_cb) const
 
size_t generated_shares () const
 
std::string provider () const
 
size_t recovery_threshold () const
 
 ZFEC (size_t K, size_t n)
 

Detailed Description

A forward error correction code compatible with the zfec library (https://github.com/tahoe-lafs/zfec)

This algorithm is not constant time and is likely succeptible to side channels. Do not use this class to encode information that should be kept secret. (If nothing else, because the first K shares are simply the original input!)

Definition at line 30 of file zfec.h.

Member Typedef Documentation

typedef std::function<void (size_t, const uint8_t[], size_t)> Botan::ZFEC::output_cb_t

Definition at line 33 of file zfec.h.

Constructor & Destructor Documentation

Botan::ZFEC::ZFEC ( size_t  K,
size_t  n 
)

FEC constructor

Parameters
Kthe number of shares needed for recovery
Nthe number of shares generated

Definition at line 405 of file zfec.cpp.

405  :
406  m_K(K), m_N(N), m_enc_matrix(N * K)
407  {
408  if(m_K == 0 || m_N == 0 || m_K > 256 || m_N > 256 || m_K > N)
409  throw Invalid_Argument("ZFEC: violated 1 <= K <= N <= 256");
410 
411  std::vector<uint8_t> temp_matrix(m_N * m_K);
412 
413  /*
414  * quick code to build systematic matrix: invert the top
415  * K*K Vandermonde matrix, multiply right the bottom n-K rows
416  * by the inverse, and construct the identity matrix at the top.
417  */
418  create_inverted_vdm(&temp_matrix[0], m_K);
419 
420  for(size_t i = m_K*m_K; i != temp_matrix.size(); ++i)
421  temp_matrix[i] = GF_EXP[((i / m_K) * (i % m_K)) % 255];
422 
423  /*
424  * the upper part of the encoding matrix is I
425  */
426  for(size_t i = 0; i != m_K; ++i)
427  m_enc_matrix[i*(m_K+1)] = 1;
428 
429  /*
430  * computes C = AB where A is n*K, B is K*m, C is n*m
431  */
432  for(size_t row = m_K; row != m_N; ++row)
433  {
434  for(size_t col = 0; col != m_K; ++col)
435  {
436  uint8_t acc = 0;
437  for(size_t i = 0; i != m_K; i++)
438  {
439  const uint8_t row_v = temp_matrix[row * m_K + i];
440  const uint8_t row_c = temp_matrix[col + m_K * i];
441  acc ^= GF_MUL_TABLE(row_v)[row_c];
442  }
443  m_enc_matrix[row * m_K + col] = acc;
444  }
445  }
446  }

Member Function Documentation

void Botan::ZFEC::decode_shares ( const std::map< size_t, const uint8_t * > &  shares,
size_t  share_size,
output_cb_t  output_cb 
) const
Parameters
sharesmap of share id to share contents
share_sizesize in bytes of each share
output_cbthe output callback

Definition at line 500 of file zfec.cpp.

References BOTAN_ASSERT_NOMSG.

504  {
505  /*
506  Todo:
507  If shares.size() < K:
508  signal decoding error for missing shares < K
509  emit existing shares < K
510  (ie, partial recovery if possible)
511  Assert share_size % K == 0
512  */
513 
514  if(shares.size() < m_K)
515  throw Decoding_Error("ZFEC: could not decode, less than K surviving shares");
516 
517  std::vector<uint8_t> decoding_matrix(m_K * m_K);
518  std::vector<size_t> indexes(m_K);
519  std::vector<const uint8_t*> sharesv(m_K);
520 
521  auto shares_b_iter = shares.begin();
522  auto shares_e_iter = shares.rbegin();
523 
524  bool missing_primary_share = false;
525 
526  for(size_t i = 0; i != m_K; ++i)
527  {
528  size_t share_id = 0;
529  const uint8_t* share_data = nullptr;
530 
531  if(shares_b_iter->first == i)
532  {
533  share_id = shares_b_iter->first;
534  share_data = shares_b_iter->second;
535  ++shares_b_iter;
536  }
537  else
538  {
539  // if share i not found, use the unused one closest to n
540  share_id = shares_e_iter->first;
541  share_data = shares_e_iter->second;
542  ++shares_e_iter;
543  missing_primary_share = true;
544  }
545 
546  if(share_id >= m_N)
547  throw Decoding_Error("ZFEC: invalid share id detected during decode");
548 
549  /*
550  This is a systematic code (encoding matrix includes K*K identity
551  matrix), so shares less than K are copies of the input data,
552  can output_cb directly. Also we know the encoding matrix in those rows
553  contains I, so we can set the single bit directly without copying
554  the entire row
555  */
556  if(share_id < m_K)
557  {
558  decoding_matrix[i*(m_K+1)] = 1;
559  output_cb(share_id, share_data, share_size);
560  }
561  else // will decode after inverting matrix
562  {
563  std::memcpy(&decoding_matrix[i*m_K], &m_enc_matrix[share_id*m_K], m_K);
564  }
565 
566  sharesv[i] = share_data;
567  indexes[i] = share_id;
568  }
569 
570  // If we had the original data shares then no need to perform
571  // a matrix inversion, return immediately.
572  if(!missing_primary_share)
573  {
574  for(size_t i = 0; i != indexes.size(); ++i)
575  {
576  BOTAN_ASSERT_NOMSG(indexes[i] < m_K);
577  }
578  return;
579  }
580 
581  invert_matrix(&decoding_matrix[0], m_K);
582 
583  for(size_t i = 0; i != indexes.size(); ++i)
584  {
585  if(indexes[i] >= m_K)
586  {
587  std::vector<uint8_t> buf(share_size);
588  for(size_t col = 0; col != m_K; ++col)
589  {
590  addmul(&buf[0], sharesv[col], decoding_matrix[i*m_K + col], share_size);
591  }
592  output_cb(i, &buf[0], share_size);
593  }
594  }
595  }
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
void Botan::ZFEC::encode ( const uint8_t  input[],
size_t  size,
output_cb_t  output_cb 
) const
Parameters
inputthe data to FEC
sizethe length in bytes of input
output_cbthe output callback

Definition at line 451 of file zfec.cpp.

References encode_shares().

455  {
456  if(size % m_K != 0)
457  throw Invalid_Argument("ZFEC::encode: input must be multiple of K uint8_ts");
458 
459  const size_t share_size = size / m_K;
460 
461  std::vector<const uint8_t*> shares;
462  for(size_t i = 0; i != m_K; ++i)
463  shares.push_back(input + i*share_size);
464 
465  this->encode_shares(shares, share_size, output_cb);
466  }
void encode_shares(const std::vector< const uint8_t * > &shares, size_t share_size, output_cb_t output_cb) const
Definition: zfec.cpp:468
void Botan::ZFEC::encode_shares ( const std::vector< const uint8_t * > &  shares,
size_t  share_size,
output_cb_t  output_cb 
) const
Parameters
sharesexactly K shares of data to FEC
share_sizethe length in bytes of each share
output_cbthe output callback

Definition at line 468 of file zfec.cpp.

References Botan::clear_mem().

Referenced by encode().

473  {
474  if(shares.size() != m_K)
475  throw Invalid_Argument("ZFEC::encode_shares must provide K shares");
476 
477  // The initial shares are just the original input shares
478  for(size_t i = 0; i != m_K; ++i)
479  output_cb(i, shares[i], share_size);
480 
481  std::vector<uint8_t> fec_buf(share_size);
482 
483  for(size_t i = m_K; i != m_N; ++i)
484  {
485  clear_mem(fec_buf.data(), fec_buf.size());
486 
487  for(size_t j = 0; j != m_K; ++j)
488  {
489  addmul(&fec_buf[0], shares[j],
490  m_enc_matrix[i*m_K+j], share_size);
491  }
492 
493  output_cb(i, &fec_buf[0], fec_buf.size());
494  }
495  }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
size_t Botan::ZFEC::generated_shares ( ) const
inline

Definition at line 43 of file zfec.h.

43 { return m_N; }
std::string Botan::ZFEC::provider ( ) const

Definition at line 597 of file zfec.cpp.

References Botan::CPUID::has_vperm().

598  {
599 #if defined(BOTAN_HAS_ZFEC_VPERM)
600  if(CPUID::has_vperm())
601  {
602  return "vperm";
603  }
604 #endif
605 
606 #if defined(BOTAN_HAS_ZFEC_SSE2)
607  if(CPUID::has_sse2())
608  {
609  return "sse2";
610  }
611 #endif
612 
613  return "base";
614  }
static bool has_vperm()
Definition: cpuid.h:362
size_t Botan::ZFEC::recovery_threshold ( ) const
inline

Definition at line 42 of file zfec.h.

42 { return m_K; }

The documentation for this class was generated from the following files: