Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
executable file 838 lines (786 sloc) 26.3 KB
<?php
declare(strict_types=1);
namespace Airship\Engine;
use Airship\Alerts\Continuum\{
ChannelSignatureFailed,
CouldNotUpdate,
PeerSignatureFailed
};
use Airship\Alerts\Hail\SignatureFailed;
use Airship\Engine\{
Bolt\Supplier as SupplierBolt,
Bolt\Log as LogBolt
};
use Airship\Engine\Continuum\{
API,
Channel,
Log
};
use Airship\Engine\Keyggdrasil\{
Peer,
TreeUpdate
};
use GuzzleHttp\Exception\TransferException;
use ParagonIE\ConstantTime\Base64UrlSafe;
use ParagonIE\Halite\{
Asymmetric\Crypto as AsymmetricCrypto,
Structure\MerkleTree,
Structure\Node
};
use Psr\Log\LogLevel;
/**
* Class Keygdrassil
*
* (Yggdrasil = "world tree")
*
* This synchronizes our public keys for each channel with the rest of the
* network, taking care to verify that a random subset of trusted peers sees
* the same keys. We also keep the checksums and version identifiers of all
* extensions in the Merkle tree.
*
* @package Airship\Engine\Continuum
*/
class Keyggdrasil
{
use SupplierBolt;
use LogBolt;
/**
* @var Database
*/
protected $db;
/**
* @var Log
*/
protected static $continuumLogger;
/**
* @var Hail
*/
protected $hail;
/**
* @var array<string, \Airship\Engine\Continuum\Supplier>
*/
protected $supplierCache = [];
/**
* @var array<mixed, Channel>
*/
protected $channelCache = [];
/**
* Keyggdrasil constructor.
*
* @param Hail|null $hail
* @param Database $db
* @param array $channels
*/
public function __construct(
Hail $hail = null,
Database $db = null,
array $channels = []
) {
$config = State::instance();
if (empty($hail)) {
$hail = $config->hail;
}
$this->hail = $hail;
if (empty($db)) {
$db = \Airship\get_database();
}
$this->db = $db;
foreach ($channels as $ch => $config) {
$this->channelCache[$ch] = new Channel($this, $ch, $config);
}
if (!self::$continuumLogger) {
self::$continuumLogger = new Log($this->db, 'keyggdrasil');
}
}
/**
* Does this peer notary see the same Merkle root?
*
* @param Peer $peer
* @param string $expectedRoot
* @return bool
* @throws CouldNotUpdate
* @throws PeerSignatureFailed
*/
protected function checkWithPeer(Peer $peer, string $expectedRoot): bool
{
foreach ($peer->getAllURLs('/verify') as $url) {
// Challenge nonce:
$challenge = Base64UrlSafe::encode(\random_bytes(33));
// Peer's response:
$response = $this->hail->postJSON($url, ['challenge' => $challenge]);
if ($response['status'] !== 'OK') {
$this->log(
'Upstream error.',
LogLevel::EMERGENCY,
[
'response' => $response
]
);
return false;
}
// Decode then verify signature
$message = (string) Base64UrlSafe::decode($response['response']);
$signature = $response['signature'];
$isValid = AsymmetricCrypto::verify(
$message,
$peer->getPublicKey(),
$signature
);
if (!$isValid) {
$this->log(
'Invalid digital signature (i.e. it was signed with an incorrect key).',
LogLevel::EMERGENCY
);
throw new PeerSignatureFailed(
'Invalid digital signature (i.e. it was signed with an incorrect key).'
);
}
// Make sure our challenge was signed.
$decoded = \json_decode($message, true);
if (!\hash_equals($challenge, $decoded['challenge'])) {
$this->log(
'Challenge-response authentication failed.',
LogLevel::EMERGENCY
);
throw new CouldNotUpdate(
\__('Challenge-response authentication failed.')
);
}
// Make sure this was a recent signature (it *should* be).
// The earliest timestamp we will accept from a peer:
$min = (new \DateTime('now'))
->sub(new \DateInterval('P01D'));
// The timestamp the server provided:
$time = new \DateTime($decoded['timestamp']);
if ($time < $min) {
throw new CouldNotUpdate(
\__(
'Timestamp %s is far too old.', 'default',
$decoded['timestamp']
)
);
}
// Return TRUE if it matches the expected root.
// Return FALSE if it matches.
return \hash_equals(
$expectedRoot,
$decoded['root']
);
}
// When all else fails, throw a TransferException
throw new TransferException();
}
/**
* Launch the update process.
*
* This updates our keys for each channel.
*
* @return void
*/
public function doUpdate(): void
{
if (empty($this->channelCache)) {
return;
}
foreach ($this->channelCache as $chan) {
$this->updateChannel($chan);
}
}
/**
* Fetch all of the updates from the remote server.
*
* @param Channel $chan
* @param string $url
* @param string $root Which Merkle root are we starting at?
* @return TreeUpdate[]
* @throws \TypeError
*/
protected function fetchTreeUpdates(
Channel $chan,
string $url,
string $root
): array {
try {
return $this->parseTreeUpdateResponse(
$chan,
$this->hail->getSignedJSON(
$url . API::get('fetch_keys') . '/' . $root,
$chan->getPublicKey()
)
);
} catch (SignatureFailed $ex) {
$state = State::instance();
if (!($state->logger instanceof Ledger)) {
throw new \TypeError(
\trk('errors.type.wrong_class', Ledger::class)
);
}
$state->logger->alert(
'Signature failed!',
\Airship\throwableToArray($ex)
);
}
return [];
}
/**
* Given a TreeUpdate, return an array formatted for logging.
*
* @param TreeUpdate $up
* @return array
*/
protected function getLogData(TreeUpdate $up): array
{
return [
'is' => [
'core' =>
$up->isAirshipUpdate(),
'package' =>
$up->isPackageUpdate(),
'newKey' =>
$up->isCreateKey(),
'revoke' =>
$up->isRevokeKey()
],
'merkleRoot' =>
$up->getRoot(),
'type' =>
$up->isPackageUpdate() || $up->isAirshipUpdate()
? $up->getPackageType()
: $up->getKeyType(),
'supplier' =>
$up->getSupplierName(),
'name' =>
$up->getPackageName(),
'data' =>
$up->getNodeData()
];
}
/**
* Get the tree of existing Merkle roots.
*
* @param Channel $chan
* @return MerkleTree
*/
protected function getMerkleTree(Channel $chan): MerkleTree
{
$nodeList = [];
$nodes = $this->db->run(
'SELECT
data
FROM
airship_tree_updates
WHERE
channel = ?
ORDER BY
treeupdateid ASC
',
(string) $chan->getName()
);
foreach ($nodes as $node) {
$nodeList []= new Node($node['data']);
}
return (new MerkleTree(...$nodeList))
->setHashSize(
\SODIUM_CRYPTO_GENERICHASH_BYTES_MAX
)
->setPersonalizationString(
\AIRSHIP_BLAKE2B_PERSONALIZATION
);
}
/**
* We're storing a new public key for this supplier.
*
* @param Channel $chan
* @param TreeUpdate $update
* @return void
*/
protected function insertKey(Channel $chan, TreeUpdate $update): void
{
$supplier = $update->getSupplier();
$name = $supplier->getName();
$file = ROOT . '/config/supplier_keys/' . $name . '.json';
$supplierData = \Airship\loadJSON($file);
$supplierData['signing_keys'][] = [
'type' => $update->getKeyType(),
'public_key' => $update->getPublicKeyString()
];
\Airship\saveJSON($file, $supplierData);
\clearstatcache();
// Flush the channel's supplier cache
$chan->getSupplier($name, true);
}
/**
* Interpret the TreeUpdate objects from the API response. OR verify the signature
* of the "no updates" message to prevent a DoS.
*
* Dear future security auditors: This is important.
*
* @param Channel $chan
* @param array $response
* @return TreeUpdate[]
* @throws ChannelSignatureFailed
* @throws CouldNotUpdate
*/
protected function parseTreeUpdateResponse(
Channel $chan,
array $response
): array {
if (!empty($response['no_updates'])) {
// The "no updates" message should be authenticated.
$signatureVerified = AsymmetricCrypto::verify(
$response['no_updates'],
$chan->getPublicKey(),
(string) Base64UrlSafe::decode($response['signature']),
true
);
if (!$signatureVerified) {
throw new ChannelSignatureFailed();
}
$datetime = new \DateTime($response['no_updates']);
// One day ago:
$stale = (new \DateTime('now'))
->sub(new \DateInterval('P01D'));
if ($datetime < $stale) {
throw new CouldNotUpdate(
\__('Stale response.')
);
}
// We got nothing to do:
return [];
}
// We were given updates. Let's validate them!
$TreeUpdateArray = [];
foreach ($response['updates'] as $update) {
$data = (string) Base64UrlSafe::decode($update['data']);
$sig = $update['signature'];
$signatureVerified = AsymmetricCrypto::verify(
$data,
$chan->getPublicKey(),
$sig
);
if (!$signatureVerified) {
// Invalid signature
throw new ChannelSignatureFailed();
}
$decoded = \json_decode($data, true);
if (!\is_array($decoded)) {
throw new CouldNotUpdate('JSON error -- did not get an array');
}
// Now that we know it was signed by the channel, time to update
$TreeUpdateArray[] = new TreeUpdate($chan, $decoded);
}
// Sort by ID
\uasort(
$TreeUpdateArray,
function (TreeUpdate $a, TreeUpdate $b): int
{
return (int) ($a->getChannelId() <=> $b->getChannelId());
}
);
return $TreeUpdateArray;
}
/**
* Insert/delete entries in supplier_keys, while updating the database.
*
* Dear future security auditors: This is important.
*
* @param Channel $chan
* @param array<int, TreeUpdate> $updates
* @return bool
*/
protected function processTreeUpdates(
Channel $chan,
TreeUpdate ...$updates
): bool {
$this->db->beginTransaction();
foreach ($updates as $update) {
// Insert the new node in the database:
$treeUpdateID = (int) $this->db->insertGet(
'airship_tree_updates',
[
'channel' => $chan->getName(),
'channelupdateid' => $update->getChannelId(),
'data' => $update->getNodeJSON(),
'merkleroot' => $update->getRoot()
],
'treeupdateid'
);
// Update the JSON files separately:
if ($update->isCreateKey()) {
$this->insertKey($chan, $update);
self::$continuumLogger->store(
LogLevel::INFO,
'New public key',
[
'action' => 'KEYGGDRASIL',
'supplier' => $update->getSupplierName(),
'publicKey' => $update->getPublicKeyString(),
'merkleRoot' => $update->getRoot(),
'data' => $this->getLogData($update)
]
);
} elseif ($update->isRevokeKey()) {
$this->revokeKey($chan, $update);
self::$continuumLogger->store(
LogLevel::INFO,
'Public key revoked',
[
'action' => 'KEYGGDRASIL',
'supplier' => $update->getSupplierName(),
'publicKey' => $update->getPublicKeyString(),
'merkleRoot' => $update->getRoot(),
'data' => $this->getLogData($update)
]
);
} else {
$this->updatePackageQueue($update, $treeUpdateID);
self::$continuumLogger->store(
LogLevel::INFO,
'New package metadata',
[
'action' => 'KEYGGDRASIL',
'supplier' => $update->getSupplierName(),
'merkleRoot' => $update->getRoot(),
'data' => $this->getLogData($update)
]
);
}
}
return $this->db->commit();
}
/**
* We're storing a new public key for this supplier.
*
* @param Channel $chan
* @param TreeUpdate $update
* @return void
*/
protected function revokeKey(Channel $chan, TreeUpdate $update)
{
$supplier = $update->getSupplier();
$name = $supplier->getName();
$file = ROOT . '/config/supplier_keys/' . $name . '.json';
$supplierData = \Airship\loadJSON($file);
foreach ($supplierData['signing_keys'] as $id => $skey) {
if (\hash_equals($skey['public_key'], $update->getPublicKeyString())) {
// Remove this key
unset($supplierData['signing_keys'][$id]);
break;
}
}
\Airship\saveJSON($file, $supplierData);
\clearstatcache();
// Flush the channel's supplier cache
$chan->getSupplier($name, true);
}
/**
* Update a particular channel.
*
* 1. Identify a working URL for the channel.
* 2. Query server for updates.
* 3. For each update:
* 1. Verify that our trusted notaries see the same update.
* (Ed25519 signature of challenge nonce || Merkle root)
* 2. Add/remove the supplier's key.
*
* @param Channel $chan
* @return void
*/
protected function updateChannel(Channel $chan): void
{
// The original Merkle Tree (and root) from the last-known-good state.
$originalTree = $this->getMerkleTree($chan);
$originalRoot = $originalTree->getRoot();
foreach ($chan->getAllURLs() as $url) {
try {
/**
* Fetch all the alleged updates from the server, which are to
* be treated with severe skepticism. The updates we see here
* are, at least, authenticated by the server API's signing key
* which means we're commmunicating with the correct channel.
*
* @var TreeUpdate[]
*/
$updates = $this->fetchTreeUpdates(
$chan,
$url,
$originalRoot
);
if (empty($updates)) {
// Nothing to do.
return;
}
/**
* We'll keep retrying until we're in a good state or we have
* no more candidate updates left to add to our tree.
*/
while (!empty($updates)) {
$merkleTree = $originalTree->getExpandedTree();
// Verify these updates with our Peers.
try {
if ($this->verifyResponseWithPeers(
$chan,
$merkleTree,
...$updates
)) {
// Apply these updates:
$this->processTreeUpdates($chan, ...$updates);
return;
}
// If we're here, verification failed
} catch (CouldNotUpdate $ex) {
/**
* Something bad happened. Possibilities:
*
* 1. One of our peers disagreed with the Merkle root
* that we saw, so we aborted for safety.
* 2. Too many network failures occurred, so we aborted
* to prevent a DoS to create a false consensus.
*
* Log the details, then the loop will continue.
*/
$this->log(
$ex->getMessage(),
LogLevel::ALERT,
\Airship\throwableToArray($ex)
);
$subsequent = [];
foreach ($updates as $up) {
if ($up instanceof TreeUpdate) {
$subsequent[] = $this->getLogData($up);
}
}
self::$continuumLogger->store(
LogLevel::ALERT,
$ex->getMessage(),
[
'action' => 'KEYGGDRASIL',
'baseRoot' => $originalRoot,
'subsequent' => $subsequent
]
);
}
// If verification fails, pop off the last update and try again
\array_pop($updates);
}
// Received a successful API response.
return;
} catch (ChannelSignatureFailed $ex) {
/**
* We can't even trust the channel's API response. An error
* occurred. We aborte entirely at this step.
*
* This may mean a MITM attacker with a valid CA certificate.
* This may mean a server-side error.
*
* Log and abort; don't try to automate any decisions based
* on a strange network state.
*/
$this->log(
'Invalid Channel Signature for ' . $chan->getName(),
LogLevel::ALERT,
\Airship\throwableToArray($ex)
);
self::$continuumLogger->store(
LogLevel::ALERT,
'Invalid Channel Signature for ' . $chan->getName(),
[
'action' => 'KEYGGDRASIL'
]
);
} catch (TransferException $ex) {
/**
* Typical network error. Maybe an HTTP 5xx response code?
*
* Either way: log and abort.
*/
$this->log(
'Channel update error',
LogLevel::NOTICE,
\Airship\throwableToArray($ex)
);
}
}
// IF we get HERE, we've run out of updates to try.
$this->log('Channel update concluded with no changes', LogLevel::ALERT);
}
/**
* We're storing metadata about a package in the database.
*
* @param TreeUpdate $update
* @param int $treeUpdateID
* @return void
*/
protected function updatePackageQueue(TreeUpdate $update, int $treeUpdateID): void
{
$packageId = $this->db->cell(
'SELECT
packageid
FROM
airship_package_cache
WHERE
packagetype = ?
AND supplier = ?
AND name = ?
',
$update->getPackageType(),
$update->getSupplierName(),
$update->getPackageName()
);
if (empty($packageId)) {
$packageId = $this->db->insertGet(
'airship_package_cache',
[
'packagetype' =>
$update->getPackageType(),
'supplier' =>
$update->getSupplierName(),
'name' =>
$update->getPackageName()
],
'packageid'
);
}
$data = $update->getNodeData();
$this->db->insert(
'airship_package_versions',
[
'package' =>
$packageId,
'version' =>
$data['version'],
'checksum' =>
$data['checksum'],
'commithash' =>
$data['commit'] ?? null,
'date_released' =>
$data['date_released'],
'treeupdateid' =>
$treeUpdateID
]
);
}
/**
* Return true if the Merkle roots match.
*
* Dear future security auditors: This is important.
*
* This employs challenge-response authentication:
* @ref https://github.com/paragonie/airship/issues/13
*
* @param Channel $channel
* @param MerkleTree $originalTree
* @param array<int, TreeUpdate> $updates
* @return bool
* @throws CouldNotUpdate
*/
protected function verifyResponseWithPeers(
Channel $channel,
MerkleTree $originalTree,
TreeUpdate ...$updates
): bool {
$state = State::instance();
$nodes = $this->updatesToNodes($updates);
$tree = $originalTree->getExpandedTree(...$nodes);
$maxUpdateIndex = \count($updates) - 1;
$expectedRoot = $updates[$maxUpdateIndex]->getRoot();
if (!\hash_equals($tree->getRoot(), $expectedRoot)) {
// Calculated root did not match.
self::$continuumLogger->store(
LogLevel::EMERGENCY,
'Calculated Merkle root did not match the update.',
[
$tree->getRoot(),
$expectedRoot
]
);
throw new CouldNotUpdate(
\__('Calculated Merkle root did not match the update.')
);
}
if ($state->universal['auto-update']['ignore-peer-verification']) {
// The user has expressed no interest in verification
return true;
}
$peers = $channel->getPeerList();
$numPeers = \count($peers);
/**
* These numbers are negotiable in future versions.
*
* If P is the set of trusted peer notaries (where ||P|| is the number
* of trusted peer notaries):
*
* 1. At least 1 must return 'success'.
* 2. At least ln(||P||) must return 'success'.
* 3. At most e * ln(||P||) can timeout.
* 4. If any peer disagrees with what we see, our
* result is discarded as invalid.
*
* The most harm a malicious peer can do is DoS if they
* are selected.
*/
$minSuccess = $channel->getAppropriatePeerSize();
$maxFailure = (int) \min(
\floor($minSuccess * M_E),
$numPeers - 1
);
if ($maxFailure < 1) {
$maxFailure = 1;
}
\Airship\secure_shuffle($peers);
$success = $networkError = 0;
/**
* If any peers give a different answer, we're under attack.
* If too many peers don't respond, assume they're being DDoS'd.
* If enough peers respond in absolute agreement, we're good.
*/
for ($i = 0; $i < $numPeers; ++$i) {
try {
if (!$this->checkWithPeer($peers[$i], $tree->getRoot())) {
// Merkle root mismatch? Abort.
return false;
}
++$success;
} catch (TransferException $ex) {
self::$continuumLogger->store(
LogLevel::EMERGENCY,
'A transfer exception occurred',
\Airship\throwableToArray($ex)
);
++$networkError;
}
if ($success >= $minSuccess) {
// We have enough good responses.
return true;
} elseif ($networkError >= $maxFailure) {
// We can't give a confident response here.
return false;
}
}
self::$continuumLogger->store(
LogLevel::EMERGENCY,
'We ran out of peers.',
[
$numPeers,
$minSuccess,
$maxFailure
]
);
// Fail closed:
return false;
}
/**
* Get a bunch of nodes for inclusion in the Merkle tree.
*
* @param TreeUpdate[] $updates
* @return Node[]
*/
protected function updatesToNodes(array $updates): array
{
$return = [];
foreach ($updates as $up) {
$return []= new Node($up->getNodeJSON());
}
return $return;
}
}
You can’t perform that action at this time.