// Copyright 2016 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/certificate_transparency/log_dns_client.h"

#include "base/big_endian.h"
#include "base/bind.h"
#include "base/format_macros.h"
#include "base/location.h"
#include "base/logging.h"
#include "base/metrics/histogram_functions.h"
#include "base/metrics/histogram_macros.h"
#include "base/stl_util.h"
#include "base/strings/strcat.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/string_util.h"
#include "base/strings/stringprintf.h"
#include "base/threading/thread_task_runner_handle.h"
#include "base/time/time.h"
#include "components/base32/base32.h"
#include "crypto/sha2.h"
#include "net/base/completion_once_callback.h"
#include "net/base/sys_addrinfo.h"
#include "net/cert/merkle_audit_proof.h"
#include "net/dns/dns_client.h"
#include "net/dns/dns_config.h"
#include "net/dns/dns_response.h"
#include "net/dns/dns_transaction.h"
#include "net/dns/dns_util.h"
#include "net/dns/public/dns_protocol.h"
#include "net/dns/record_parsed.h"
#include "net/dns/record_rdata.h"

namespace certificate_transparency {

namespace {

void LogQueryDuration(net::Error error, const base::TimeDelta& duration) {
  UMA_HISTOGRAM_MEDIUM_TIMES("Net.CertificateTransparency.DnsQueryDuration",
                             duration);

  if (error == net::OK) {
    UMA_HISTOGRAM_MEDIUM_TIMES(
        "Net.CertificateTransparency.DnsQueryDuration.Success", duration);
  }
}

void LogQueryResult(const std::string& name,
                    net::Error error,
                    const net::DnsResponse* response) {
  base::UmaHistogramSparse(
      base::StrCat({"Net.CertificateTransparency.DnsQuery", name, "Error"}),
      -error);

  if (response) {
    base::UmaHistogramSparse(
        base::StrCat({"Net.CertificateTransparency.DnsQuery", name, "Rcode"}),
        response->rcode());
  }
}

// Returns an EDNS option that disables the client subnet extension, as
// described in https://tools.ietf.org/html/rfc7871. This is to avoid the
// privacy issues caused by this extension being enabled in recursive resolvers
// used by this DNS client (see the "Privacy Note" in RFC7871).
net::OptRecordRdata::Opt OptToDisableClientSubnetExtension() {
  const uint16_t kClientSubnetExtensionCode = 8;
  // https://www.iana.org/assignments/address-family-numbers/address-family-numbers.xhtml
  const uint16_t kIanaAddressFamilyIpV4 = 1;

  char buf[4];
  base::BigEndianWriter writer(buf, base::size(buf));
  // family - address is empty so the value of this is irrelevant, so long as
  // it's valid (see https://tools.ietf.org/html/rfc7871#section-7.1.2).
  writer.WriteU16(kIanaAddressFamilyIpV4);
  // source prefix length - 0 to disable this extension.
  writer.WriteU8(0);
  // scope prefix length - must be 0 for queries.
  writer.WriteU8(0);
  // no address - don't want a client subnet in the query.

  return net::OptRecordRdata::Opt(kClientSubnetExtensionCode,
                                  base::StringPiece(buf, base::size(buf)));
}

// Parses the DNS response and extracts a single string from the TXT RDATA.
// If the response is malformed, not a TXT record, or contains any number of
// strings other than 1, this returns false and extracts nothing.
// Otherwise, it returns true and the extracted string is assigned to |*txt|.
bool ParseTxtResponse(const net::DnsResponse& response, std::string* txt) {
  DCHECK(txt);

  net::DnsRecordParser parser = response.Parser();
  // We don't care about the creation time, since we're going to throw
  // |parsed_record| away as soon as we've extracted the payload, so provide
  // the "null" time.
  auto parsed_record = net::RecordParsed::CreateFrom(&parser, base::Time());
  if (!parsed_record)
    return false;

  auto* txt_record = parsed_record->rdata<net::TxtRecordRdata>();
  if (!txt_record)
    return false;

  // The draft CT-over-DNS RFC says that there MUST be exactly one string in the
  // TXT record.
  if (txt_record->texts().size() != 1)
    return false;

  *txt = txt_record->texts().front();
  return true;
}

// Extracts a leaf index value from a DNS response's TXT RDATA.
// Returns true on success, false otherwise.
bool ParseLeafIndex(const net::DnsResponse& response, uint64_t* index) {
  DCHECK(index);

  std::string index_str;
  if (!ParseTxtResponse(response, &index_str))
    return false;

  return base::StringToUint64(index_str, index);
}

// Extracts audit proof nodes from a DNS response's TXT RDATA.
// Returns true on success, false otherwise.
// It will fail if there is not a whole number of nodes present > 0.
// There must only be one string in the TXT RDATA.
// The nodes will be appended to |proof->nodes|
bool ParseAuditPath(const net::DnsResponse& response,
                    net::ct::MerkleAuditProof* proof) {
  DCHECK(proof);

  std::string audit_path;
  if (!ParseTxtResponse(response, &audit_path))
    return false;
  // If empty or not a multiple of the node size, it is considered invalid.
  // It's important to consider empty audit paths as invalid, as otherwise an
  // infinite loop could occur if the server consistently returned empty
  // responses.
  if (audit_path.empty() || audit_path.size() % crypto::kSHA256Length != 0)
    return false;

  for (size_t i = 0; i < audit_path.size(); i += crypto::kSHA256Length) {
    proof->nodes.push_back(audit_path.substr(i, crypto::kSHA256Length));
  }

  return true;
}

}  // namespace

// Encapsulates the state machine required to get an audit proof from a Merkle
// leaf hash. This requires a DNS request to obtain the leaf index, then a
// series of DNS requests to get the nodes of the proof.
class AuditProofQueryImpl : public LogDnsClient::AuditProofQuery {
 public:
  // The API contract of LogDnsClient requires that callers make sure the
  // AuditProofQuery does not outlive LogDnsClient, so it's safe to leave
  // ownership of |dns_client| with LogDnsClient.
  AuditProofQueryImpl(net::DnsClient* dns_client,
                      net::URLRequestContext* url_request_context,
                      const std::string& domain_for_log,
                      const net::NetLogWithSource& net_log);

  ~AuditProofQueryImpl() override;

  // Begins the process of getting an audit proof for the CT log entry with a
  // leaf hash of |leaf_hash|. If |lookup_securely| is true, only secure DNS
  // lookups will be performed, otherwise only insecure DNS lookups will be
  // performed. The proof will be for a tree of size |tree_size|. If the proof
  // cannot be obtained synchronously, net::ERR_IO_PENDING will be returned and
  // |callback| will be invoked when the operation has completed asynchronously.
  // If the operation is cancelled (by deleting the AuditProofQueryImpl),
  // |cancellation_callback| will be invoked.
  net::Error Start(std::string leaf_hash,
                   bool lookup_securely,
                   uint64_t tree_size,
                   net::CompletionOnceCallback callback,
                   base::OnceClosure cancellation_callback);

  // Returns the proof that is being obtained by this query.
  // It is only guaranteed to be populated once either Start() returns net::OK
  // or the completion callback is invoked with net::OK.
  const net::ct::MerkleAuditProof& GetProof() const override;

 private:
  enum class State {
    NONE,
    REQUEST_LEAF_INDEX,
    REQUEST_LEAF_INDEX_COMPLETE,
    REQUEST_AUDIT_PROOF_NODES,
    REQUEST_AUDIT_PROOF_NODES_COMPLETE,
  };

  net::Error DoLoop(net::Error result);

  // When a DnsTransaction completes, store the response and resume the state
  // machine. It is safe to store a pointer to |response| because |transaction|
  // is kept alive in |current_dns_transaction_|.
  void OnDnsTransactionComplete(net::DnsTransaction* transaction,
                                int net_error,
                                const net::DnsResponse* response,
                                bool secure);

  // Requests the leaf index for the CT log entry with |leaf_hash_|.
  net::Error RequestLeafIndex();

  // Stores the received leaf index in |proof_->leaf_index|.
  // If successful, the audit proof nodes will be requested next.
  net::Error RequestLeafIndexComplete(net::Error result);

  // Requests the next batch of audit proof nodes from a CT log.
  // The index of the first node required is determined by looking at how many
  // nodes are already in |proof_->nodes|.
  // The CT log may return up to 7 nodes - this is the maximum allowed by the
  // CT-over-DNS draft RFC, as a TXT RDATA string can have a maximum length of
  // 255 bytes and each node is 32 bytes long (a SHA-256 hash).
  //
  // The performance of this could be improved by sending all of the expected
  // requests up front. Each response can contain a maximum of 7 audit path
  // nodes, so for an audit proof of size 20, it could send 3 queries (for nodes
  // 0-6, 7-13 and 14-19) immediately. Currently, it sends only the first and
  // then, based on the number of nodes received, sends the next query.
  // The complexity of the code would increase though, as it would need to
  // detect gaps in the audit proof caused by the server not responding with the
  // anticipated number of nodes. It would also undermine LogDnsClient's ability
  // to rate-limit DNS requests.
  net::Error RequestAuditProofNodes();

  // Appends the received audit proof nodes to |proof_->nodes|.
  // If any nodes are missing, another request will follow this one.
  net::Error RequestAuditProofNodesComplete(net::Error result);

  // Sends a TXT record request for the domain |qname|.
  // Returns true if the request could be started.
  // OnDnsTransactionComplete() will be invoked with the result of the request.
  bool StartDnsTransaction(const std::string& qname);

  // The next state that this query will enter.
  State next_state_;
  // The DNS domain of the CT log that is being queried.
  std::string domain_for_log_;
  // The Merkle leaf hash of the CT log entry an audit proof is required for.
  std::string leaf_hash_;
  // Whether the DNS request should be sent securely or insecurely.
  bool lookup_securely_;
  // The audit proof to populate.
  net::ct::MerkleAuditProof proof_;
  // The callback to invoke when the query is complete.
  net::CompletionOnceCallback callback_;
  // The callback to invoke when the query is cancelled.
  base::OnceClosure cancellation_callback_;
  // The DnsClient to use for sending DNS requests to the CT log.
  net::DnsClient* dns_client_;
  // The URLRequestContext to use for sending DoH requests to the CT log.
  net::URLRequestContext* url_request_context_;
  // The most recent DNS request. Null if no DNS requests have been made.
  std::unique_ptr<net::DnsTransaction> current_dns_transaction_;
  // The most recent DNS response. Only valid so long as the corresponding DNS
  // request is stored in |current_dns_transaction_|.
  const net::DnsResponse* last_dns_response_;
  // The NetLog that DNS transactions will log to.
  net::NetLogWithSource net_log_;
  // The time that Start() was last called. Used to measure query duration.
  base::TimeTicks start_time_;
  // Produces WeakPtrs to |this| for binding callbacks.
  base::WeakPtrFactory<AuditProofQueryImpl> weak_ptr_factory_;
};

AuditProofQueryImpl::AuditProofQueryImpl(
    net::DnsClient* dns_client,
    net::URLRequestContext* url_request_context,
    const std::string& domain_for_log,
    const net::NetLogWithSource& net_log)
    : next_state_(State::NONE),
      domain_for_log_(domain_for_log),
      dns_client_(dns_client),
      url_request_context_(url_request_context),
      last_dns_response_(nullptr),
      net_log_(net_log),
      weak_ptr_factory_(this) {
  DCHECK(dns_client_);
  DCHECK(!domain_for_log_.empty());
}

AuditProofQueryImpl::~AuditProofQueryImpl() {
  if (next_state_ != State::NONE)
    std::move(cancellation_callback_).Run();
}

// |leaf_hash| is not a const-ref to allow callers to std::move that string into
// the method, avoiding the need to make a copy.
net::Error AuditProofQueryImpl::Start(std::string leaf_hash,
                                      bool lookup_securely,
                                      uint64_t tree_size,
                                      net::CompletionOnceCallback callback,
                                      base::OnceClosure cancellation_callback) {
  // It should not already be in progress.
  DCHECK_EQ(State::NONE, next_state_);
  start_time_ = base::TimeTicks::Now();
  proof_.tree_size = tree_size;
  leaf_hash_ = std::move(leaf_hash);
  lookup_securely_ = lookup_securely;
  callback_ = std::move(callback);
  cancellation_callback_ = std::move(cancellation_callback);
  // The first step in the query is to request the leaf index corresponding to
  // |leaf_hash| from the CT log.
  next_state_ = State::REQUEST_LEAF_INDEX;
  // Begin the state machine.
  return DoLoop(net::OK);
}

const net::ct::MerkleAuditProof& AuditProofQueryImpl::GetProof() const {
  return proof_;
}

net::Error AuditProofQueryImpl::DoLoop(net::Error result) {
  CHECK_NE(State::NONE, next_state_);
  State state;
  do {
    state = next_state_;
    next_state_ = State::NONE;
    switch (state) {
      case State::REQUEST_LEAF_INDEX:
        result = RequestLeafIndex();
        break;
      case State::REQUEST_LEAF_INDEX_COMPLETE:
        result = RequestLeafIndexComplete(result);
        if (result == net::OK)
          LogQueryResult("LeafIndex", net::OK, last_dns_response_);
        break;
      case State::REQUEST_AUDIT_PROOF_NODES:
        result = RequestAuditProofNodes();
        break;
      case State::REQUEST_AUDIT_PROOF_NODES_COMPLETE:
        result = RequestAuditProofNodesComplete(result);
        break;
      case State::NONE:
        NOTREACHED();
        break;
    }
  } while (result != net::ERR_IO_PENDING && next_state_ != State::NONE);

  if (result != net::ERR_IO_PENDING) {
    // If the query is complete, log some metrics.
    LogQueryDuration(result, base::TimeTicks::Now() - start_time_);
    switch (state) {
      case State::REQUEST_LEAF_INDEX:
      case State::REQUEST_LEAF_INDEX_COMPLETE:
        // An error must have occurred if the query completed in this state.
        LogQueryResult("LeafIndex", result, last_dns_response_);
        break;
      case State::REQUEST_AUDIT_PROOF_NODES:
      case State::REQUEST_AUDIT_PROOF_NODES_COMPLETE:
        // The query may have completed successfully.
        LogQueryResult("AuditProof", result, last_dns_response_);
        break;
      case State::NONE:
        NOTREACHED();
        break;
    }
  }

  return result;
}

void AuditProofQueryImpl::OnDnsTransactionComplete(
    net::DnsTransaction* transaction,
    int net_error,
    const net::DnsResponse* response,
    bool secure) {
  DCHECK_EQ(current_dns_transaction_.get(), transaction);
  last_dns_response_ = response;
  net::Error result = DoLoop(static_cast<net::Error>(net_error));

  // If DoLoop() indicates that I/O is pending, don't invoke the completion
  // callback. OnDnsTransactionComplete() will be invoked again once the I/O
  // is complete, and can invoke the completion callback then if appropriate.
  if (result != net::ERR_IO_PENDING) {
    // The callback may delete this query (now that it has finished), so copy
    // |callback_| before running it so that it is not deleted along with the
    // query, mid-callback-execution (which would result in a crash).
    std::move(callback_).Run(result);
  }
}

net::Error AuditProofQueryImpl::RequestLeafIndex() {
  std::string encoded_leaf_hash = base32::Base32Encode(
      leaf_hash_, base32::Base32EncodePolicy::OMIT_PADDING);
  DCHECK_EQ(encoded_leaf_hash.size(), 52u);

  std::string qname = base::StringPrintf(
      "%s.hash.%s.", encoded_leaf_hash.c_str(), domain_for_log_.c_str());

  if (!StartDnsTransaction(qname)) {
    return net::ERR_NAME_RESOLUTION_FAILED;
  }

  next_state_ = State::REQUEST_LEAF_INDEX_COMPLETE;
  return net::ERR_IO_PENDING;
}

// Stores the received leaf index in |proof_->leaf_index|.
// If successful, the audit proof nodes will be requested next.
net::Error AuditProofQueryImpl::RequestLeafIndexComplete(net::Error result) {
  if (result != net::OK) {
    return result;
  }

  DCHECK(last_dns_response_);
  if (!ParseLeafIndex(*last_dns_response_, &proof_.leaf_index)) {
    return net::ERR_DNS_MALFORMED_RESPONSE;
  }

  // Reject leaf index if it is out-of-range.
  // This indicates either:
  // a) the wrong tree_size was provided.
  // b) the wrong leaf hash was provided.
  // c) there is a bug server-side.
  // The first two are more likely, so return ERR_INVALID_ARGUMENT.
  if (proof_.leaf_index >= proof_.tree_size) {
    return net::ERR_INVALID_ARGUMENT;
  }

  next_state_ = State::REQUEST_AUDIT_PROOF_NODES;
  return net::OK;
}

net::Error AuditProofQueryImpl::RequestAuditProofNodes() {
  // Test pre-conditions (should be guaranteed by DNS response validation).
  if (proof_.leaf_index >= proof_.tree_size ||
      proof_.nodes.size() >= net::ct::CalculateAuditPathLength(
                                 proof_.leaf_index, proof_.tree_size)) {
    return net::ERR_UNEXPECTED;
  }

  std::string qname = base::StringPrintf(
      "%zu.%" PRIu64 ".%" PRIu64 ".tree.%s.", proof_.nodes.size(),
      proof_.leaf_index, proof_.tree_size, domain_for_log_.c_str());

  if (!StartDnsTransaction(qname)) {
    return net::ERR_NAME_RESOLUTION_FAILED;
  }

  next_state_ = State::REQUEST_AUDIT_PROOF_NODES_COMPLETE;
  return net::ERR_IO_PENDING;
}

net::Error AuditProofQueryImpl::RequestAuditProofNodesComplete(
    net::Error result) {
  if (result != net::OK) {
    return result;
  }

  const uint64_t audit_path_length =
      net::ct::CalculateAuditPathLength(proof_.leaf_index, proof_.tree_size);

  // The calculated |audit_path_length| can't ever be greater than 64, so
  // deriving the amount of memory to reserve from the untrusted |leaf_index|
  // is safe.
  proof_.nodes.reserve(audit_path_length);

  DCHECK(last_dns_response_);
  if (!ParseAuditPath(*last_dns_response_, &proof_)) {
    return net::ERR_DNS_MALFORMED_RESPONSE;
  }

  // Keep requesting more proof nodes until all of them are received.
  if (proof_.nodes.size() < audit_path_length) {
    next_state_ = State::REQUEST_AUDIT_PROOF_NODES;
  }

  return net::OK;
}

bool AuditProofQueryImpl::StartDnsTransaction(const std::string& qname) {
  net::DnsTransactionFactory* factory = dns_client_->GetTransactionFactory();
  if (!factory) {
    return false;
  }

  last_dns_response_ = nullptr;
  DCHECK(url_request_context_);
  current_dns_transaction_ = factory->CreateTransaction(
      qname, net::dns_protocol::kTypeTXT,
      base::BindOnce(&AuditProofQueryImpl::OnDnsTransactionComplete,
                     weak_ptr_factory_.GetWeakPtr()),
      net_log_,
      lookup_securely_ ? net::SecureDnsMode::SECURE : net::SecureDnsMode::OFF,
      url_request_context_);

  current_dns_transaction_->Start();
  return true;
}

LogDnsClient::LogDnsClient(std::unique_ptr<net::DnsClient> dns_client,
                           net::URLRequestContext* url_request_context,
                           const net::NetLogWithSource& net_log,
                           size_t max_in_flight_queries)
    : dns_client_(std::move(dns_client)),
      url_request_context_(url_request_context),
      net_log_(net_log),
      in_flight_queries_(0),
      max_in_flight_queries_(max_in_flight_queries) {
  CHECK(dns_client_);
  net::NetworkChangeNotifier::AddDNSObserver(this);
  UpdateDnsConfig();
}

LogDnsClient::~LogDnsClient() {
  net::NetworkChangeNotifier::RemoveDNSObserver(this);
}

void LogDnsClient::OnDNSChanged() {
  UpdateDnsConfig();
}

void LogDnsClient::OnInitialDNSConfigRead() {
  UpdateDnsConfig();
}

void LogDnsClient::NotifyWhenNotThrottled(base::OnceClosure callback) {
  DCHECK(HasMaxQueriesInFlight());
  not_throttled_callbacks_.emplace_back(std::move(callback));
}

// |leaf_hash| is not a const-ref to allow callers to std::move that string into
// the method, avoiding LogDnsClient::AuditProofQuery having to make a copy.
net::Error LogDnsClient::QueryAuditProof(
    base::StringPiece domain_for_log,
    std::string leaf_hash,
    bool lookup_securely,
    uint64_t tree_size,
    std::unique_ptr<AuditProofQuery>* out_query,
    net::CompletionOnceCallback callback) {
  DCHECK(out_query);

  if (domain_for_log.empty() || leaf_hash.size() != crypto::kSHA256Length) {
    return net::ERR_INVALID_ARGUMENT;
  }

  if (HasMaxQueriesInFlight()) {
    return net::ERR_TEMPORARILY_THROTTLED;
  }

  auto* query = new AuditProofQueryImpl(dns_client_.get(), url_request_context_,
                                        domain_for_log.as_string(), net_log_);
  out_query->reset(query);

  ++in_flight_queries_;

  return query->Start(
      std::move(leaf_hash), lookup_securely, tree_size,
      base::BindOnce(&LogDnsClient::QueryAuditProofComplete,
                     base::Unretained(this), std::move(callback)),
      base::BindOnce(&LogDnsClient::QueryAuditProofCancelled,
                     base::Unretained(this)));
}

void LogDnsClient::QueryAuditProofComplete(
    net::CompletionOnceCallback completion_callback,
    int net_error) {
  --in_flight_queries_;

  // Move the "not throttled" callbacks to a local variable, just in case one of
  // the callbacks deletes this LogDnsClient.
  std::list<base::OnceClosure> not_throttled_callbacks =
      std::move(not_throttled_callbacks_);

  std::move(completion_callback).Run(net_error);

  // Notify interested parties that the next query will not be throttled.
  for (auto& callback : not_throttled_callbacks) {
    std::move(callback).Run();
  }
}

void LogDnsClient::QueryAuditProofCancelled() {
  --in_flight_queries_;

  // Move not_throttled_callbacks_ to a local variable, just in case one of the
  // callbacks deletes this LogDnsClient.
  std::list<base::OnceClosure> not_throttled_callbacks =
      std::move(not_throttled_callbacks_);

  // Notify interested parties that the next query will not be throttled.
  for (auto& callback : not_throttled_callbacks) {
    std::move(callback).Run();
  }
}

bool LogDnsClient::HasMaxQueriesInFlight() const {
  return max_in_flight_queries_ != 0 &&
         in_flight_queries_ >= max_in_flight_queries_;
}

void LogDnsClient::UpdateDnsConfig() {
  net::DnsConfig config;
  net::NetworkChangeNotifier::GetDnsConfig(&config);
  if (config.IsValid())
    dns_client_->SetConfig(config);

  net::DnsTransactionFactory* factory = dns_client_->GetTransactionFactory();
  if (factory) {
    factory->AddEDNSOption(OptToDisableClientSubnetExtension());
  }
}

}  // namespace certificate_transparency