text: // Copyright 2014 The Chromium Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  #include "components/rappor/byte_vector_utils.h"
  
  #include <string.h>
  #include <algorithm>
  #include <string>
  
  #include "base/check_op.h"
  #include "base/notreached.h"
  #include "base/rand_util.h"
  #include "base/strings/strcat.h"
  #include "base/strings/string_number_conversions.h"
  #include "crypto/random.h"
  
  namespace rappor {
  
  namespace {
  
  // Reinterpets a ByteVector as a StringPiece.
  base::StringPiece ByteVectorAsStringPiece(const ByteVector& lhs) {
    return base::StringPiece(reinterpret_cast<const char *>(&lhs[0]), lhs.size());
  }
  
  // Concatenates parameters together as a string.
  std::string Concat(const ByteVector& value, char c, base::StringPiece data) {
    return base::StrCat(
        {ByteVectorAsStringPiece(value), base::StringPiece(&c, 1), data});
  }
  
  // Performs the operation: K = HMAC(K, data)
  // The input "K" is passed by initializing |hmac| with it.
  // The output "K" is returned by initializing |result| with it.
  // Returns false on an error.
  bool HMAC_Rotate(const crypto::HMAC& hmac,
                   const std::string& data,
                   crypto::HMAC* result) {
    ByteVector key(hmac.DigestLength());
    if (!hmac.Sign(data, &key[0], key.size()))
      return false;
    return result->Init(ByteVectorAsStringPiece(key));
  }
  
  // Performs the operation: V = HMAC(K, V)
  // The input "K" is passed by initializing |hmac| with it.
  // "V" is read from and written to |value|.
  // Returns false on an error.
  bool HMAC_Rehash(const crypto::HMAC& hmac, ByteVector* value) {
    return hmac.Sign(ByteVectorAsStringPiece(*value),
                     &(*value)[0], value->size());
  }
  
  // Implements (Key, V) = HMAC_DRBG_Update(provided_data, Key, V)
  // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
  // "V" is read from and written to |value|.
  // The input "Key" is passed by initializing |hmac1| with it.
  // The output "Key" is returned by initializing |out_hmac| with it.
  // Returns false on an error.
  bool HMAC_DRBG_Update(base::StringPiece provided_data,
                        const crypto::HMAC& hmac1,
                        ByteVector* value,
                        crypto::HMAC* out_hmac) {
    // HMAC_DRBG Update Process
    crypto::HMAC temp_hmac(crypto::HMAC::SHA256);
    crypto::HMAC* hmac2 = provided_data.size() > 0 ? &temp_hmac : out_hmac;
    // 1. K = HMAC(K, V || 0x00 || provided_data)
    if (!HMAC_Rotate(hmac1, Concat(*value, 0x00, provided_data), hmac2))
      return false;
    // 2. V = HMAC(K, V)
    if (!HMAC_Rehash(*hmac2, value))
      return false;
    // 3. If (provided_data = Null), then return K and V.
    if (hmac2 == out_hmac)
      return true;
    // 4. K = HMAC(K, V || 0x01 || provided_data)
    if (!HMAC_Rotate(*hmac2, Concat(*value, 0x01, provided_data), out_hmac))
      return false;
    // 5. V = HMAC(K, V)
    return HMAC_Rehash(*out_hmac, value);
  }
  
  }  // namespace
  
  void Uint64ToByteVector(uint64_t value, size_t size, ByteVector* output) {
    DCHECK_LE(size, 8u);
    DCHECK_EQ(size, output->size());
    for (size_t i = 0; i < size; i++) {
      // Get the value of the i-th smallest byte and copy it to the byte vector.
      uint64_t shift = i * 8;
      uint64_t byte_mask = static_cast<uint64_t>(0xff) << shift;
      (*output)[i] = (value & byte_mask) >> shift;
    }
  }
  
  ByteVector* ByteVectorAnd(const ByteVector& lhs, ByteVector* rhs) {
    DCHECK_EQ(lhs.size(), rhs->size());
    for (size_t i = 0; i < lhs.size(); ++i) {
      (*rhs)[i] = lhs[i] & (*rhs)[i];
    }
    return rhs;
  }
  
  ByteVector* ByteVectorOr(const ByteVector& lhs, ByteVector* rhs) {
    DCHECK_EQ(lhs.size(), rhs->size());
    for (size_t i = 0; i < lhs.size(); ++i) {
      (*rhs)[i] = lhs[i] | (*rhs)[i];
    }
    return rhs;
  }
  
  ByteVector* ByteVectorMerge(const ByteVector& mask,
                              const ByteVector& lhs,
                              ByteVector* rhs) {
    DCHECK_EQ(lhs.size(), rhs->size());
    for (size_t i = 0; i < lhs.size(); ++i) {
      (*rhs)[i] = (lhs[i] & ~mask[i]) | ((*rhs)[i] & mask[i]);
    }
    return rhs;
  }
  
  int CountBits(const ByteVector& vector) {
    int bit_count = 0;
    for (size_t i = 0; i < vector.size(); ++i) {
      uint8_t byte = vector[i];
      for (int j = 0; j < 8 ; ++j) {
        if (byte & (1 << j))
          bit_count++;
      }
    }
    return bit_count;
  }
  
  ByteVectorGenerator::ByteVectorGenerator(size_t byte_count)
      : byte_count_(byte_count) {}
  
  ByteVectorGenerator::~ByteVectorGenerator() {}
  
  ByteVector ByteVectorGenerator::GetRandomByteVector() {
    ByteVector bytes(byte_count_);
    crypto::RandBytes(&bytes[0], bytes.size());
    return bytes;
  }
  
  ByteVector ByteVectorGenerator::GetWeightedRandomByteVector(
      Probability probability) {
    switch (probability) {
      case PROBABILITY_100:
        return ByteVector(byte_count_, 0xff);
      case PROBABILITY_75: {
        ByteVector bytes = GetRandomByteVector();
        return *ByteVectorOr(GetRandomByteVector(), &bytes);
      }
      case PROBABILITY_50:
        return GetRandomByteVector();
      case PROBABILITY_25: {
        ByteVector bytes = GetRandomByteVector();
        return *ByteVectorAnd(GetRandomByteVector(), &bytes);
      }
      case PROBABILITY_0:
        return ByteVector(byte_count_);
    }
    NOTREACHED();
    return ByteVector(byte_count_);
  }
  
  HmacByteVectorGenerator::HmacByteVectorGenerator(
      size_t byte_count,
      const std::string& entropy_input,
      base::StringPiece personalization_string)
      : ByteVectorGenerator(byte_count),
        hmac_(crypto::HMAC::SHA256),
        value_(hmac_.DigestLength(), 0x01),
        generated_bytes_(0) {
    // HMAC_DRBG Instantiate Process
    // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
    // 1. seed_material = entropy_input + nonce + personalization_string
    // Note: We are using the 8.6.7 interpretation, where the entropy_input and
    // nonce are acquired at the same time from the same source.
    DCHECK_EQ(kEntropyInputSize, entropy_input.size());
    std::string seed_material =
        base::StrCat({entropy_input, personalization_string});
    // 2. Key = 0x00 00...00
    crypto::HMAC hmac1(crypto::HMAC::SHA256);
    if (!hmac1.Init(std::string(hmac_.DigestLength(), 0x00)))
      NOTREACHED();
    // 3. V = 0x01 01...01
    // (value_ in initializer list)
  
    // 4. (Key, V) = HMAC_DRBG_Update(seed_material, Key, V)
    if (!HMAC_DRBG_Update(seed_material, hmac1, &value_, &hmac_))
      NOTREACHED();
  }
  
  HmacByteVectorGenerator::~HmacByteVectorGenerator() {}
  
  HmacByteVectorGenerator::HmacByteVectorGenerator(
      const HmacByteVectorGenerator& prev_request)
      : ByteVectorGenerator(prev_request.byte_count()),
        hmac_(crypto::HMAC::SHA256),
        value_(prev_request.value_),
        generated_bytes_(0) {
    if (!HMAC_DRBG_Update("", prev_request.hmac_, &value_, &hmac_))
      NOTREACHED();
  }
  
  // HMAC_DRBG requires entropy input to be security_strength bits long,
  // and nonce to be at least 1/2 security_strength bits long.  We
  // generate them both as a single "extra strong" entropy input.
  // max_security_strength for SHA256 is 256 bits.
  // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
  const size_t HmacByteVectorGenerator::kEntropyInputSize = (256 / 8) * 3 / 2;
  
  // static
  std::string HmacByteVectorGenerator::GenerateEntropyInput() {
    return base::RandBytesAsString(kEntropyInputSize);
  }
  
  ByteVector HmacByteVectorGenerator::GetRandomByteVector() {
    // Streams bytes from HMAC_DRBG_Generate
    // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
    const size_t digest_length = hmac_.DigestLength();
    DCHECK_EQ(value_.size(), digest_length);
    ByteVector bytes(byte_count());
    uint8_t* data = &bytes[0];
    size_t bytes_to_go = byte_count();
    while (bytes_to_go > 0) {
      size_t requested_byte_in_digest = generated_bytes_ % digest_length;
      if (requested_byte_in_digest == 0) {
        // Do step 4.1 of the HMAC_DRBG Generate Process for more bits.
        // V = HMAC(Key, V)
        if (!HMAC_Rehash(hmac_, &value_))
          NOTREACHED();
      }
      size_t n = std::min(bytes_to_go,
                          digest_length - requested_byte_in_digest);
      memcpy(data, &value_[requested_byte_in_digest], n);
      data += n;
      bytes_to_go -= n;
      generated_bytes_ += n;
      // Check max_number_of_bits_per_request from 10.1 Table 2
      // max_number_of_bits_per_request == 2^19 bits == 2^16 bytes
      DCHECK_LT(generated_bytes_, 1U << 16);
    }
    return bytes;
  }
  
  }  // namespace rappor
  