Threat Alert CenterLearn More About Our Detection and Response Services
Most security experts are by now aware of the threat that the rise of quantum computing poses to modern cryptography. Shor’s quantum algorithm, in particular, provides a large theoretical speedup to the brute-forcing capabilities of attackers targeting many public-key cryptosystems such as RSA and ECDSA. But how much, exactly, is the impact in terms of security? What is the timeline we have to expect? Which algorithms are more vulnerable than others?
In this post I am going to deep-dive in quantum attack resource estimates for public-key cryptography based on recent advances on the topic. In particular, we will see the exact computational cost of running Shor’s algorithm to attack different keysizes for different public-key algorithms, we will put this in context with the current state of quantum computing, and we will see how RSA will be broken by June 25th 2027 (just kidding!)
First of all we need to quickly recap, from a purely classical standpoint, the difference between various computational hardness assumptions used in modern cryptosystems. This is actually a very complex topic. For the sake of simplicity, in this blog post we only take into account the following three problems:
Actually, taking into account these three problems in the context of quantum security is an oversimplification. In fact, in reality and unlike very often and wrongly claimed in popular literature, most existing cryptographic schemes are not directly based on the above assumptions. For example, the security of RSA is not based on IFP, but rather on a similar hardness assumption, called “RSA assumption”, that is known to be reducible to IFP, but the vice versa is not known. This means that “breaking RSA” is at most as difficult as solving the IFP, but it might be easier than that, just so far nobody figured out an easier way. The same happens for most schemes “based” on discrete logarithm problems, such as Diffie-Hellman key exchange or ECDSA elliptic-curve signatures. However, from a practical standpoint, most of the modern cryptanalytic efforts in breaking these schemes focus on solving the above math problems, so this is what is going to be relevant for us when looking at quantum attack resource estimates.
So, how large (again, from a non-quantum perspective) should, e.g., an RSA or ECDSA key be? It depends from two things:
For factorization and finite field discrete logarithm the situation is similar: the best known algorithm for solving these two problems in the cryptographic case (Number Field Sieve and Index Calculus Method, respectively) have a similar asymptotic subexponential complexity that can be roughly approximated as
![\mathcal{O}\left( 2^{9\sqrt[3]{n}}\right)](https://cdn.prod.website-files.com/67711be5796275bf61eaabfc/685cff0e76a70033d327b1f3_latex.png)
for
-bit moduli. This means that targeting
bits of security for cryptographic schemes such as RSA and DH requires pumping up the key size quite a lot: 2048 bit for 112 bit of security, 3072 bit for 128 bit of security, 7680 bit for 192 bit of security, etc.
For the ECDLP problem, instead, the best known general solving algorithm (Pollard’s Rho) has an exponential complexity of roughly
for
-bit curve fields. The lack of known subexponential attack algorithms is basically what made elliptic curve cryptography attractive so far, because the resulting key can have much smaller size for the same level of bit security, with corresponding increase in bandwidth and efficiency. This is summarized in the table below.
However, as we will see, this is also what makes elliptic curve cryptography more vulnerable to quantum computing.
Now we look at the quantum scenario, i.e., we consider a situation where a large scalable quantum computer has been built and is able to run complex quantum algorithms. It is well-known that Shor’s quantum algorithm can solve the integer factorization problem in polynomial time. Let’s dig a bit deeper in this claim.
First of all, Shor’s algorithm is actually composed of two parts: a purely quantum part (Quantum Fast Fourier Transform, or QFFT in short) and a purely classical pre- and post-processing phase. From a complexity standpoint, the QFFT has polynomial time complexity of roughly
for
-bit input integers. Given that the classical part has a similar complexity, we will only consider the quantum complexity as relevant.
For factoring
-bit integers, a quantum computer running Shor’s algorithm will clearly need at least
(logical) qubits of quantum memory to represent the integer, but it will also require additional working quantum registers that make the total qubit count increase. Given that the qubit count can be seen, as a first approximation, as a limiting resource for the attack, circuit versions capable of running the QFFT minimizing the number of required qubits have been proposed. The current state of the art of these circuits requires a number of qubits that is roughly double the bitsize of the input integer.
As in the classical case, again the situation for IFP and DLP is similar in the quantum scenario: Shor’s algorithm can be generalized to discrete logarithms, and the QFFT can be used to solve the DLP over
-bit moduli using roughly
logical qubits and with the same polynomial time complexity of roughly
.
The situation is slightly different in the case of elliptic curves. Again, the QFFT can be used to efficiently solve the ECDLP in roughly cubic time as above, but because of how the classical part of the algorithm needs to embed curve points representation into a larger group, this time the number of qubits required is roughly ten times the bitsize of the curve field!
Now, you might be tempted to say that the above implies that elliptic curve cryptography sounds more resilient to quantum attacks than RSA or DSA, because mounting an attack requires more qubits. But if you paid attention you can already see why it is exactly the opposite!
In fact, remember that elliptic curves keys are small because the best classical attacks are more inefficient. This difference disappears in the quantum scenario, as quantum attacks have all similar time complexity. And since RSA and discrete log cryptosystems already needed to use large keys in order to resist classical attacks, the required qubit count is actually larger for them! This is summarized in the table below.
As you can see, at the increase of the security parameter, the number of qubits necessary to attack RSA grows much faster than for an equivalent attack on elliptic curves of the same classical security level. We can almost say that classical attacks made RSA and related “more resilient” also to quantum attacks.
This should not be interpreted as saying that RSA is secure against quantum attacks: none of the schemes we are considering here are. However, so far it looks like EC-based cryptography is much more vulnerable than RSA to quantum attacks, and given the steady raise in the number of qubits available for quantum computation, it looks like elliptic curve cryptograhy will likely fall much earlier than other schemes.
Things get a bit more complex than that. Ultimately, we are interested in the question: “how much quantum resources we need to mount an attack against a certain scheme?” Answering this question will require us to dig a bit deeper.
We need to remember that a quantum computation is made of several “layers”:
Clearly, any improvements on any of these layers will yield an increase in the efficiency of quantum attacks, and a lower amount of quantum resources needed to mount the attack. Assessing the necessary amount of resources is therefore tricky, as this is a moving target. Regardless, something can be said about it, and a few recent works shed new light on the topic.
First of all one has to consider that the number of qubits necessary to mount the attack might not be the limiting factor. The estimates provided in the previous section of this blog post are lower bounds that take into account the minimum number of logical qubits required, but this is not an universally accepted measure of hard resources. In fact, there are better ones: If we consider the full implementation stack from the bottom layer of physical qubits up to the algorithmic layer, we see that certain common elementary quantum gates are more expensive than others. Pauli gates are usually “cheap”, in the sense that they are easy and fast to implement, while T gates (Toffoli) are extremely hard. They are so hard in fact that, as a first approximation, one can simply disregard every other quantum gate, and only count the number of T gates as a measure of the complexity of running a quantum algorithms. The “T count” complexity reflects exactly this: the higher the T count complexity of a quantum algorithm, the more difficult it is to build a quantum computer able to run it.
Given the above, quantum compilers usually allow to operate in a mode that produces a circuit representation that does not optimize the number of logical qubits, but rather the number of T gates. This usually has a side effect: a large increase in the number of physical qubits required (because converting from physical to logical requires T gates) and also an increase in the running time overall. It is also wasteful if a certain T gate is only used once on a certain qubit, while it could be better to reuse them as much as possible once they are implemented. For this reason, another very useful metric is the so-called “T depth” complexity, which takes into account the fact that a circuit can be described in “layers” where many T gates can be used in parallel on different qubits.
Building circuits that optimize the T-count or T-depth might end up using more logical layer than the strict minimum, but it would result in a more efficient attack overall, because it minimizes the real-world resources (time and cost of implementation). Recent works in quantum cryptanalysis adopt this approach, and new results have been published recently. The tables below show the state of the art in quantum attack resource estimates for two different scenarios: the current (realistic) case of base noise error of
in the underlying physical qubits (achieved by current state of the art superconducting qubits), or the more optimistic case of an error rate of
that most experts seems to agree it might achievable in the short-term future. Notice that the minimum number of logic qubits has increased compared to the previous table because, as mentioned before, recent results in quantum optimization aim at minimizing T-count and T-depth rather than circuit width. Moreover, the time necessary to mount an attack greatly depends on the failure rate of a single run of the underlying algorithm, which itself depends on the level of purity achieved in the error correction mechanism, which itself depends on the number of physical qubits used in the surface code. As it turns out, the ratio between number of physical qubits employed and time necessary to run the attack is pretty constant in each of the scenarios below. For this reason, a new measure of quantum resource has been introduced: megaqubit days. This is the number (expressed in millions) of physical qubits necessary to run the attack in 24 hours given a surface cycle (“quantum clock”) of 200 ns (5 MHz) and an error rate of
or
errors per measurement.
Notice the following, interesting fact. For “low” security parameters (e.g., RSA-3072 and ECDSA-256) attacking RSA is actually less expensive than attacking elliptic curve cryptography. This is a consequence of recent results in the optimization of Shor’s algorithm for factorization. However, as the security parameter increases, we see a steady increase of the quantum resources necessary for attacking RSA, while attacking elliptic curve cryptography becomes relatively easier.
Recent results in quantum attack resource estimates have started to shed light on how vulnerable, exactly, is conventional cryptography to the ever increasing performance of quantum computers. The traditional view that “elliptic curve cryptography is much more vulnerable to quantum computers than RSA and discrete log” still holds, sort of, but the cut-off point has been moved to roughly 160-bit of classical security, while for 128 bit of security the difference is not so relevant. This is a moving target, mainly given by recent optimization on Shor’s algorithm for attacking IFP and DLP, so the real cost of attacking ECDLP might be lower. Further results can surely change the current estimates. What is clear is that with a large enough number of physical qubits all these cryptosystems can be attacked in a matter of hours.
The situation for symmetric-key cryptography is radically different, but still recent advances in quantum resource estimates contributed to better frame the impact that quantum computers might have on the practical bit-security of primitives such as AES and SHA-3.
Intro
Unless you’re living under a rock, you might have read that last Tuesday the largest “crypto hack” in history targeted Cross-chain decentralized finance (DeFi) platform Poly Network, and allowed an undisclosed attacker to steal the equivalent of a whooping 610 million USD of crypto tokens.
The situation is in rapid development, and preliminary analysis of the attack started to circulate in the last hours. In this post, I am trying to explain what happened based on the existing available information.
The very basics
In this blog post I assume familiarity with the basic working of a permissionless decentralized ledger, and in particular with the concepts of blockchain and consensus, and related cryptocurrency token applications (for instance, Bitcoin), but I will recap anyway the most basic concepts.
In a nutshell, we can say that a “cryptocurrency token” is a virtual amount of “something” that is owned by someone. You claim possession of a token by publishing a “wallet address” (basically, a public verification key) and by “doing something” that makes the consensus protocol agree to bind the token to that address. Proof of possession of that token and the possibility of transferring the token to some other wallet is provided by a digital signature, which is generated by the wallet’s secret signing key. Issuing a “transaction” simply means embedding some metadata and a related valid signature in the blockchain, which authorizes transfer of funds from wallet A to wallet B. In a fully distributed ledger, the consensus mechanism makes it so that it is in the “best interest” of the participants to accept a valid signature within the blockchain.
Smart contracts
The next step is to realize the following: As explained above, issuing a cryptocurrency transaction is basically a process where multiple participants “agree” to change the state of a virtual ledger in the same way. And a ledger is nothing else than a replicated database with entries of the form “address: amount”. However, there is nothing special in this particular form of entries: nothing described so far forbids to apply the same process to change the state of a different kind of replicated database. What if we consider as our “database” the memory of a virtual machine?
This is where the idea of “smart contracts” came into play, initially adopted within the Ethereum application. In a nutshell, a smart contract is a piece of software that is designed to run on a distributed virtual machine. On traditional computers, software is “executed” by changing, step by step, the state of the computer’s internal memory according to a set of predefined rules. A smart contract works in a similar way: the initial internal state of the machine is embedded in the blockchain ledger by issuing a transaction (from a creator’s wallet) that contains a compiled (“compressed” and machine-readable) version of the code. The code is executed by changing the state of the blockchain, and the consensus protocol makes it so that it is always in the best interest of the participants to execute the code (that is, applying the rules that govern the state change to the next block) in a correct way. As in cryptocurrency transactions, the execution of a smart contract is authorized by a digital signature issued by the “owner” of the smart contract (usually, but not always, its creator), but must be validated by the consensus.
This brings up the important concept of ownership and interaction between contracts. How do smart contracts interact? In a typical code environment, you might have different subroutines calling different functions, often collected into libraries, and you need to manage input and output of these. Smart contracts work in the same way, but the difference is that, given the distributed nature of the computation, safeguards have to be put in place (and enforced by the consensus mechanism) to make sure that, for example, if contracts A and B both call a function F, F will return to each of them the right output, or that if you create and execute a smart contract, I cannot change arbitrarily its state since I’m not the owner.
In practice, smart contracts (or their running platforms) usually embed safeguards of the form “If the caller of this program is not authorized by a certain key, then abort”. The authorization does not always come in the form of a direct signature: a contract A might be issued specifying another contract B as its “owner”, and different permissions can be given to different sets of users.
Cross chain networks
There is already too many blockchains out there to keep track of them all. A common problem that arises in the cryptocurrency scenario is when you own a certain kind of token (say, Bitcoin) and you want to convert it to another one that uses a different kind of blockchain technology or consensus (say, Ripple). This usually involves swapping tokens at an exchange, with associated fees. In the smart contract landscape, you run into similar problems: what if you are running a smart contract on Ethereum but you want it to interact with another one, say, on Cardano?
Now, if you think about it, you can see a cryptocurrency exchange as a sort of contract: I give you X Bitcoin and you give me back Y Ripple. Analogously, centralized services can act as “cross-chain interpreters” by, let’s say, allowing a program A running on Ethereum to interact with another program B running on Cardano in the following way:
Services of this type are sometimes called “oracles” and, like exchanges, require a fee to operate. Also, like exchanges, they require the user to fully trust a single entity. However, the next observation is: since these nodes are basically running a contract or script, why don’t we decentralize that one as well as we do for smart contracts?
Enter the concept of “cross-chain network”, which is basically an additional abstraction layer on the concept of distributed virtual machine. A cross-chain network allows two different blockchains to “communicate with each other”. Or, to be more precise, allows users of a certain blockchain to perform operations on another blockchain in a distributed and autonomous way. However, exactly because they operate across different blockchains, these networks usually require their own “virtual blockchain” to run smart contracts that govern the communications rules within the underlying networks.
Poly Network is a cross-chain network that sits on top of different blockchains, including Bitcoin, Ethereum and Elrond. To overly simplify its architecture, Poly can be described by the following components:
It is common for cross-chain networks, including Poly, to store at any moment large amount of liquidity in their underlying wallets, because there are many users performing cross-chain operations at the same time. Therefore, it is crucial to properly secure the very privileged cross-chain smart contracts that administer these wallets. Unfortunately, this is exactly what did not happen here.
The hack
On August 10th, Poly Network reported that an undisclosed attacker hacked a smart contract of the network, transferring the equivalent of roughly 610 million USD (mainly in Ether, Binance Coin and USDC) and moving them to external wallet addresses.
According to cybersecurity firm SlowMist and security researcher Kelvin Fichter, the hack was made possible by a mismanagement of the access rights between two important Poly smart contract. The first one is EthCrossChainManager and the second one is EthCrossChainData.
Let’s first talk about EthCrossChainData. This is a very high privileged contract that is not supposed to be invoked by anyone within the network, except by its owners. The reason is that this contract is responsible for setting and managing a list of public keys of “authenticator nodes” (Keepers) that manage the wallets in the underlying liquidity chains. In other words, EthCrossChainData can decide who has the privilege of moving the large amount of funds contained within Poly’s Binance wallet, Ethereum wallet, etc. If an attacker could call the right function (putCurEpochConPubKeyBytes) within EthCrossChainData, there would be not even need to attack a Keeper’s secret key: the attacker could simply set their own public key to replace that of a Keeper, and then they would have the right to execute a high volume transaction within the Poly network to exfiltrate a large amount of funds to other wallets. Clearly not something you want to happen.
Now, about EthCrossChainManager. This is another high privilege contract that has the right to trigger messages from another chain to the Poly chain. Which means: anybody can call a cross-chain event by issuing a transaction on the source chain that invokes the verifyHeaderAndExecuteTx function within EthCrossChainManager, and specifying a target Poly contract to execute. However, because of its particular intended use, EthCrossChainManager would not call any function within the target contract, but only the one with a very specific “Solidity function ID”. Namely, it would only call a function whose 32-bit ID is computed this way:
In other words, the ID of the function called is computed as the 32-bit truncation of a 256-bit Keccak hash of the string _method and a suffix.
The attacker exploited two problems here.
The first one is, it turns out that EthCrossChainManager is an owner of EthCrossChainData, and can therefore execute privileged functions within this one! The second one is that the field _method in the code snippet above is actually user-defined, and can therefore be set at will. In particular, it is possible for the attacker to brute-force a _method field that hashes to a 32-bit value that is exactly the ID for putCurEpochConPubKeyBytes!
This is the attack in detail:
ethers.utils.id ('putCurEpochConPubKeyBytes(bytes)').slice(0, 10)'0x41973cd9' ethers.utils.id ('f1121318093(bytes,bytes,uint64)').slice(0, 10)'0x41973cd9' A total worth of over 610 million USD was stolen this way. That’s a lot.
Aftermath
Things are moving fast and it is difficult to keep track in real time of the evolving situation.
After the hack, the next reasonable step would have been for the attacker to transfer the stolen funds into the liquidity pool of an anonymous decentralized exchange like Curve. For this reason, Poly immediately issued a request for crypto miners and exchanges to “blacklist” the stolen funds, making them de facto unavailable to the attacker. This is in theory possible to do, but cumbersome for the exchanges for many reasons, and it is unclear whether all exchange platforms answered the plea.
However, administrators of the stablecoin Tether (who have greater control over their blockchain compared to other DeFi applications) managed to freeze the stolen Tether-USDC funds in time just 9 blocks before the attacker tried to launder them on the Curve liquidity pool. An anonymous user alerted the hacker by issuing an Ethereum transaction to the hacker’s address with the freeze warning message in the metadata, and the hacker rewarded this user with part of the stolen Ethereum. After that, the address of the hacker was flooded with transactions of hundreds of people begging for money.
Poly Network asked the hacker to return the funds. The security company Slowmist published findings on the alleged hacker, claiming that the hacker’s identity had been exposed and that the group had access to the hacker’s email and IP address. According to Slowmist, the hacker was able to take advantage of a relatively unknown crypto exchange in Asia and they claimed to have a lot of information about the attacker.
Whether this is true or not, the hacker started returning funds to Poly on Wednesday. By August 11th 15:00 UTC nearly half worth of tokens have been returned, and the hacker claims to be ready to return more in exchange for the unfreeze of the Tether tokens. A second message embedded in a transaction reads: “IT’S ALREADY A LEGEND TO WIN SO MUCH FORTUNE. IT WILL BE AN ETERNAL LEGEND TO SAVE THE WORLD. I MADE THE DECISION, NO MORE DAO”.
While this story develops, it is not superfluous to remind that “blockchain” is not synonymous with “security”. It is very important to audit the security of your applications, including smart contracts.
We continue our post-quantum series with this blog post that details the process behind adding quantum resistance to the WireGuard protocol and evaluating the performance of the resulting software.
WireGuard is a fast and secure open source virtual private network (VPN) solution that is using state-of-the-art cryptography. While being extremely fast, the WireGuard VPN secures your connection and protects your online privacy with several nice security features such as data security or identity-hiding.
The WireGuard protocol works in two steps, first a handshake is performed between client and server. During this handshake, both participants authenticate both to each other and at the same time securely exchange some key material. The derived key material is used to open a secure tunnel using symmetric key encryption and exchange the actual network data. When using this tunnel a client can then “hide” behind the server and obtain additional privacy from other parties while surfing the web.
The problem here is that the cryptography in use, as modern as it is, is not quantum resistant, thus threatened by the arrival of quantum computers.
As it relies on symmetric encryption, the tunnel part can be made quantum secure by “simply” doubling the key size. We thus put our main focus on the more complex challenge of adding quantum resistance to the WireGuard handshake.
There are already some works that propose post quantum handshakes for VPN. In the table below, we report the results of works published last year that add quantum resistance to respectively the OpenVPN protocol, or the WireGuard protocol. As we can see, the proposed quantum resistant handshake of WireGuard is much more practical than the one of OpenVPN. And this is why we chose to continue working with WireGuard specifically, and use these results as baseline.
Before we dive into the technical details, it’s important to just step back and think about what we want to achieve and what we want to evaluate. The performance of a VPN handshake has two dominant dimensions: the runtime and the bandwidth. Both are important but one can prevail according to the setting we are in. In some cases, a lower runtime is preferred either for convenience or to fit computationally-limited resources. On the opposite, some might require solutions where the bandwidth is the feature to minimize.
It’s important for every scenario to define the settings and constraints in order to propose the best tool that there is to maximize the performance. For instance, discarding the importance of bandwidth usage at the benefit of the runtime is prone to fire back as the network limitations may cause considerable delay, leading to a slow and heavy protocol.
With this in mind, the first thing that we do is to repeat the methodology of the prior PQ-WireGuard. We build our implementations on top of the Go mirror implementation of WireGuard.
The PQ-WireGuard handshake is built around an authenticated key exchange. In this case the authenticated key exchange follows the Fujioka construction –included below–, a recipe that combines two Key Encapsulation Mechanisms (KEM) to obtain the authentication, integrity and confidentiality properties. One of the KEM is working with static keys and is required to be CCA secure, and the second one is working with ephemeral keys, and is required to be only CPA secure. Only participants holding the correct private key can learn the internal view of the protocol and derive the correct key material, while the others can only at best guess at random.
We use plain Kyber as our KEM instances, with a security level 3 (Kyber768). Kyber is a really fast finalist that is built using a security-enhancing transform over a weakly-secure encryption scheme. We use our own open-source implementation, introduced in our previous blog post.
This simple approach yields results that are not very competitive on the bandwidth side, but promising when looking at the runtime, especially on the client side.
Performance of post-quantum handshakes.
We examine further our solution to try to find out “how fast can we go”?
To do such, we tweak the Kyber KEM instance working with ephemeral keys. We start by removing the Fujioka transform, and build our CPA-secure Kyber KEM directly on top of the encryption scheme. We also augment the compression of the ciphertexts. We can do that because in practice, a negligible decapsulation failure rate can be an overkill compared for example to the possibility of a packet drop.
These tweaks reduce the size of outputs, boost the performance, and actually increase the security, with arguments that can be borrowed from learning with rounding schemes. Because of potential attacks, we cannot apply this trick to the Kyber instance working with static keys. Indeed there exist attacks targeting the decapsulation failures that could lead to a secret key recovery, and of course we do not want that. The internals of the tweaked instance are detailed below.
Tweaked Kyber internals.
As a result, for security somewhat equal we obtain a protocol that offers improvement over the prior works regarding computational time while staying competitive regarding the bandwidth. Indeed, the handshake occurs every 2 minutes or so, the 2 extra IP packets being sent thus do not impact the practicality. As expected, the bigger improvement is on the client side, where we almost half the runtime compared to the prior PQ-WireGuard.
Performance of post-quantum handshakes.
Whereas the lower bound of one IP packet per message is reached for prior PQ-WireGuard handshake, we quickly come to the conclusion that there is no way, as aggressively as we tried, to fit our Kyber-based handshake into two IP packets only. Either the security level drops, or the failure rates drop below an acceptable rate. We identify the bottleneck in our case as being the size of the ciphertexts of the CCA-secure Kyber scheme.
We deviate from the original approach to try to now optimize the communication costs.
We study the use of the del Pino construction, a different authenticated key exchange recipe that replaces the KEM working with long term authenticating keys by a signature scheme.
We keep using our tweaked Kyber instance with ephemeral keys, and choose to work with Rainbow, a signature scheme that stands out because of its very small signature size. The relatively large public key size of rainbow is not a problem in our setup as after a one time transfer, only a hash can be used during the frequent handshakes. Hence this preprocessing is amortized pretty quickly.
Performance of post-quantum handshakes.
As you can see, we achieve a very light protocol. With this approach, saving of almost 2 thousand bytes –hence two IP packets — comes at the cost of some few milliseconds of computational overhead, a cost that is barely perceptible by the user.
The security properties of the original WireGuard protocol are maintained under the assumptions that the users public keys are not known to the attacker. We agree with the arguments of Hülsing et al. in Post-Quantum WireGuard and Appelbaum et al. in Tiny WireGuard tweak that conclude that such assumption is realistic. Then, as only a hash is used during the handshakes, any attacker such as eavesdroppers cannot threaten the deniability and anonymity properties.
Our quantum-resistant WireGuard fork including all the aforementioned PQ-WireGuard variants is publicly available at https://github.com/kudelskisecurity/pq-wireguard. Furthermore, knowing that quantum computers are currently at the stage of prototypes, we choose in our final product to use instances with a light security level, i.e., Kyber512, which offers security roughly equivalent to AES–128, and Rainbow-1. As result, our quantum-resistant WireGuard implementations achieve an even better performance, as reported on the table below.
Performance of the post-quantum handshakes included in our WireGuard fork.
When used correctly, a VPN is an useful tool whose security should be assured even after the advent of quantum computers. Towards that goal, we presented two performant quantum resistant WireGuard constructions. We show that there is still some improvement surface, especially when looking to optimize one dimension especially among bandwidth or runtime, while staying practical in the other one.
We agree that prior PQ-WireGuard looks like a very good compromise, but we are pleased to present protocols that show some improvements in different practical settings, and that provide experimental results that can be used as motivation to accelerate the transition towards post quantum alternatives.
If you want to use our PQ-WireGuard protocols, the tutorial is included in the README of our GitHub repository. For additional information, you can also watch the recording of our presentation at the NIST third post-quantum cryptography standardization conference.
As last word, we would like to mention that we plan to integrate recent optimizations and port our implementation to the Linux kernel space, hopefully to get even better runtimes. Stay tuned!
Today we are excited to release oramfs, a simple, flexible, Free Software ORAM implementation for Linux written in Rust. It is designed to support different ORAM schemes and encryption ciphers. It is storage- and cloud provider agnostic and supports any UNIX filesystem without requiring specific plugins or server-side support.
When looking at privacy of storage solutions, encryption alone is not sufficient to prevent access pattern leakage. Unlike traditional solutions such as LUKS or Bitlocker, an ORAM scheme prevents an attacker from knowing whether read or write operations are performed and which parts of the filesystem are accessed. This level of privacy is achieved by making extra access requests than necessary, shuffling the blocks composing the storage layer, and writing and re-encrypting data back and forth every time, even when just a read operation is performed. This obviously comes with a loss of performance, but brings additional security compared to other solutions.
With oramfs users can enjoy total privacy while storing their files on untrusted local or remote storage, such as a public cloud. Our solution is resizable, so there is no need to re-initialize a larger ORAM when space becomes a problem. With oramfs, a whole filesystem is encrypted and read/write access patterns are hidden from the remote server. Our initial release supports a simple implementation of Path ORAM, one of the first modern, tree-based ORAM schemes, but the design supports arbitrary schemes and we plan of releasing more optimized ones soon.
To setup the ORAM, two inputs are required: a public directory and a private directory.
The public directory can be any locally mounted directory, including remote volumes mounted as a local directory. This could be a remote FTP directory, or a remote cloud storage mounted locally. Just mount the remote storage (or use a local storage if you want) and you’re good to go. For example, Rclone supports mounting a variety of cloud storage providers as local directories.
The private directory is the local mount point for a virtual storage that is presented to the user after entering the right secret passphrase, and is used to access files stored in the ORAM. Any operation performed on the private directory has an impact on the public directory. And if that public directory is a mounted remote storage, then it is safely and transparently synchronized to the remote server whenever an operation is performed on the private directory.
In order to be fully storage agnostic, oramfs is file-based: the ORAM structure is split into blocks (or nodes of blocks) and every block or node is saved to the public directory as a separate file. FUSE is then used to recombine these files into a single virtual loop device that is eventually accessed through the ORAM scheme itself. All this is completely transparent for the user.
Let’s go through an example where we setup an ORAM that transparently synchronizes data to a remote FTP server. This would also work with any other remote storage supported by Rclone, such as SSH, Google Drive or S3.
We assume that a remote directory has already been mounted at the local mount point public/ and also an empty directory private/ has been created.
We initialize a new ORAM called myoram, by answering the interactive questions. This will automatically format the underlying filesystem with EXT4 but this option can be overridden if wished.
$ oramfs add myoram public/ private/
Please enter desired ORAM total size in bytes,
or press enter to use default [default: 16000000 (16 MB)]:
Adjusting ORAM size to closest valid value: 16711680 bytes
Please enter path to client data directory to use, or press enter to use default [default: /home/foobar/.config/oramfs/myoram]:
Please enter path to mountpoint directory to use, or press enter to use default [default: /tmp/oramfs_myoram]:
Successfully added ORAM myoram.Please enter path to mountpoint directory to use, or press enter to use default [default: /tmp/oramfs_myoram]:
Successfully added ORAM myoram.
Finally, we mount the ORAM (will prompt the user for the password) and write a file to it:
$ oramfs mount myoram
It looks like this ORAM is mounting for the first time. Initializing it first...
Please enter an encryption passphrase to secure your ORAM: ****
Please type it a second time to confirm: ****
Starting ORAM...
Running as a daemon...
Mounting filesystem to private directory...
Formatting EXT4 filesystem...
mke2fs 1.46.2 (28-Feb-2021)
Creating filesystem with 16320 1k blocks and 4080 inodes
Filesystem UUID: 7de4f86e-adb8-4587-bf68-814267ef5ab6
Superblock backups stored on blocks:
8193
Allocating group tables: done
Writing inode tables: done
Creating journal (1024 blocks): done
Writing superblocks and filesystem accounting information: done
Mounting directory...
[sudo] password for foobar:
Setting private directory owner...
[sudo] password for foobar:
Setup complete! ORAM filesystem mounted to private directory at: /home/foobar/git/oramfs/private
$ echo hello world > private/somefileWhen finished, we can unmount it:
$ oramfs umount myoramThat’s it! Files written/read to/from the private directory are encrypted and access patterns are hidden from the FTP server.
Head over to Github to get started with oramfs.
By the way, we will be presenting oramfs on Wednesday July 7th at 4:10pm CEST at Pass the SALT.
When Kudelski Security approaches a security assessment of a FinTech company such as Oxygen, we always aim to provide a full suite of coverage to ensure that the architecture, application, and operation of the environment is sound and free from known vulnerabilities or DeFI style attacks.
In the case of a DeFI ecosystem, there are always moving parts of dependencies, relationships, and workflows that may be dynamic. You may not always know the workflow, even if you know the components. In this manner, it is important to always understand the picture of the entire system, review the flow, understand the purpose and functionality and then view the system from the point of view as an attacker.
As a philosophy, a protocol such as Oxygen – in addition to providing the financial functions that it has been designed to provide – must protect its components from impact/liquidation even if one of the dependent components introduces a failure or economic scenario that is not intended.
While not every security risk can be uncovered by a single review, the artifacts that are created can be used as input for the organization to build security risk and operational controls into its system to better handle unintended system interactions. Whether it be economic or system level attacks, the security of the system takes review, continuous testing, analysis from experts in the form of pen testing or bug bounty, and review by legal and economic experts.
Within this lens, we are undertaking a series of assessments related to the Oxygen Protocol and supporting architecture and openly discussing the methodology to drive understanding further into the industry. We will conduct a series of reviews and audits of the Oxygen Protocol functionality and interfaces, as well as collaborating with Oxygen going forward to assess future enhancements, changes, or additions to Oxygen’s protocols.
As they state, beginning with prime brokerage, Oxygen intends to replicate a growing range of products offered by investment banks, helping to build finance without Wall Street. As a DeFi ecosystem, Oxygen intends to enable delivery of these services to individuals and institutions alike, democratizing access to sophisticated investment, risk management and liquidity solutions.
As a security provider, understanding the outcome desired by Oxygen drives our review criteria and also identifies which sorts of fraud, risk, and security controls that must be built into this sort of system. Traditional entities are built upon years of security learnings and audits, and any project intending to replicate this functionality should also deliver equivalent functional controls.
These controls deliver protections such as:
Security projects utilizing a STRIDE methodology along with appropriate control points and attack trees generally can understand and prioritize their risk surface, similar to how Oxygen is progressing.
As a protocol, Oxygen is built on the growing and liquid Serum ecosystem which leverages an on-chain orderbook to match borrowers and lenders to provide fair rates. And it is made possible by the massive throughput and ultra-low costs of the scalable Solana blockchain. Kudelski Security has previously performed assessments for Solana and has compiled a repository of knowledge which will be leveraged to better understand and review the Oxygen system.
In a follow-up article, we will discuss our process and outcomes from the review of the Oxygen ecosystem. Much can be learned from the attention on the Contracts Mechanism, Finance Logic, Yields, Borrowing, Lending and Leverage mechanism security controls and constraints, as well as other related funds safety considerations – such as whale attacks and collusion.
We will also discuss how “formal verification analyses” can confirm that formulas, cryptography and mathematics, etc. in the software faithfully implement the specified intent of the protocol.
Our final update will include the methodology of testing, which includes a discussion of the benefits of architecture review, dynamic testing of key financial risk scenarios such as edge situations, liquidity events, and more versus scripted testing or a pure static analysis.
More to come…
Concordium is a science-based proof-of-stake blockchain created with business applications in mind. It is the first blockchain with identification built into the protocol to meet regulatory requirements, while delivering a user-friendly platform that can handle smart contracts.
The Concordium Platform is designed to be fast, secure and cost-effective, which is why Concordium and Kudelski Security have been working together to perform threat modeling, code review, and “scenario based” assessment of the underlying code and logic of the Concordium software.
As documented in the White Paper, Concordium implements a Network Layer, Consensus Layer, and Identity Layer. These three layers interact with each other to process transactions and to execute the scalable/secure transactions.
At the beginning of the engagement, we first wanted to focus on the critical parts of the code which ensured that the foundation was solid, and that consensus and execution remained safe. We focused much of the security review on the following components and their interconnection.
During discussions with the core team, we quickly identified some key areas of overall concern
We ruled the following components out of scope for this first engagement
Following the review, we have come to these conclusions which we have presented to the project team as part of the report output
During the threat modeling exercise, we worked collaboratively with the Concordium team to identify the most important threats to the project. We used this information to guide the code review phase of the project.
During the code review, we found no critical or high-risk scenarios that put the tokens of the system at risk and we made a number of suggestions to improve overall documentation, code quality, and conformance to best practices.
Following the completed review, and during follow-on tests, scenarios were discovered in which unused network messages and test code could cause availability concerns on the network even though these errors would not cause a loss of funds. We completed a follow-on review, looking specifically at the network code and identified a few issues that the Concordium team fixed.
We look forward to continuing the effort with Concordium to bring trust into their ecosystem through diligent review of the critical components of their ecosystem
Heard about the quantum threat glooming on the horizon? Today, we dive into post-quantum, or quantum-resistant crypto, which is not to be mixed with quantum cryptography (see our previous blog entry on that), and unbox our post-quantum Go library.
The arrival of quantum computers threaten the security of traditional cryptographic algorithms. Shor’s, Grover’s and Brassard’s algorithms are few examples of tools that enable powerful quantum attacks on the public key cryptography as we know and use it. The hardness of some schemes such as RSA or Diffie-Hellman is not granted anymore, prompting us to find replacements that rely on alternative assumptions, namely post-quantum cryptography.
Lattice-based constructions make for the majority of post-quantum schemes. A lattice is a set with an order relation, meaning that every two elements have unique supremum and infimum. The most important lattice-based computational problem is the Shortest Vector Problem (SVP), which entails finding the shortest vector in a given lattice. The security of most of the lattice-based constructions can be reduced to the security of the SVP problem, which appears to be resistant to attacks by both classical and quantum computers.
The CRYSTALS algorithms are promising candidates for the post-quantum area, and are finalists of the NIST post-quantum cryptography standardization process. They stand out because of their great performance, the main drawback being their relatively large outputs size.
The first protocol of the CRYSTALS suite is Kyber, a Key Encapsulation Mechanism (KEM), that secures the exchange of key material over an insecure channel. It uses asymmetric encryption to transmit a short symmetric key. This symmetric key is then used to encrypt the longer messages. Briefly, Kyber is built using a security transformation that turns Regev’s weakly secure encryption scheme into a strongly secure one.
The second protocol is Dilithium, a Digital Signature Algorithm (DSA), that produces a signature on a message that is verifiable by anyone holding the public verification key associated to the secret signing key. Dilithium follows a Fiat-Shamir construction, sampling a mask and rejecting until the signature is binding yet hides the signing key.
The security of those protocols is parametrized by various factors such as the size of the lattice. Kyber and Dilithium can be instantiated to offer a light, recommended, or very high security level, and are respectively designated as Kyber512, Kyber768, and Kyber1024, or Dilithium2, Dilithium3, and Dilithium5.
A thorough cryptanalysis is necessary but not sufficient to guarantee the security of a library. The last decade has seen the number of publications about a new class of attacks arise (Meltdown, SPECTRE, Zombiland…). Side-channels attacks target the implementation of algorithmically secure crypto systems and can exploit information gained from the implementation itself.
Often overlooked, side-channel attacks can be used to weaken or break entirely the security of an infrastructure. Not paying enough attention to side-channel vulnerabilities can lead to devastating breaches, as we have seen with NSA’s TEMPEST system that could reconstruct the entirety of a computer’s screen by listening to its electromagnetic emissions, or more recently with the SPECTRE attacks, that can manipulate a process into revealing sensitive data, such as passwords, after monitoring the cache hits and misses timing. This is why we make it a priority to offer as much protection against said side-channel attacks as possible with our implementation.
The Go language has gained popularity amongst cryptographers because of its simplicity and security properties. Writing and maintaining Go code is easy and a great fit for projects of all scale, from proof-of-concepts to complete infrastructures.
In our library, we offer an implementation in Go of the CRYSTALS protocols. The open-source code is available in the crystals-go repository. While there are existing implementations that consist of a straightforward translation from the official implementations available in C to Go, we made the choice to deviate from the reference to provide additional security and performance properties. Correct behavior of our code is ensured and tested via known-answer tests provided by the CRYSTALS’s authors.
In this section, we provide hands-on examples on how to use our library. First, the crystal-go module can be installed via:
go get -u github.com/kudelskisecurity/crystals-goIn order to have a clear separation between the parameters and the algorithms, we define generic methods that work with all possible sets of parameters, and invoke them on an instance of Kyber or Dilithium that completely defines the parameters to be used. Hence, a user first has to define which level of security they want to work with by creating an instance of Kyber or Dilithium among Kyber512, Kyber768, Kyber1024 and Dilithium2, Dilithium3, Dilithium5:
k := NewKyber512() //Creates a Kyber instance with light security level
d := Dilithium3() //Creates a Dilithium instance with recommended security levelThe user can now generate a public and private key pair by calling:
pk, sk := k.KeyGen(seed)or
pk, sk := d.KeyGen(seed)Once the parameters are defined and the keys are generated, the core functionalities of Kyber and Dilithium can be called.
Kyber’s main functions are Encaps and Decaps. A typical flow of Kyber is:
//Select the parameters
k := NewKyber512()
//Generate the keys and openly disclose the public key.
pk, sk := k.KeyGen(seed)
//Generate a shared secret and a ciphertext. Similarly to the seed, the random
//coins used during the encapsulation can be given or deleguated to the method.
c, ss := k.Encaps(coins, pk)
//Send the ciphertext to the private key holder, which decapsulate it to recover
//the shared secret (ss = ss').
ss' := k.Decaps(c, sk)Similarly for Dilithium, the main methods Sign and Verify are typically used as follows:
d3 := Dilithium3() //Creates a Dilithium instance with recommended security level
pk, sk := d3.KeyGen()
msg := []byte("This is a message.")
sig := d3.Sign(sk, msg)
verified := d3.Verify(pk, sig, msg) //The boolean verified is true for honest runsA seed and coins of 32 bytes can be given as argument and allows for reproducibility for example, or is useful if the user does not trust the environment to generate good randomness and wants to use randomness from their own source.
They can be nil in which case the randomness will be generated during the key generation process using Go’s official crypto/rand library.
This section is not exhaustive of the features offered by our library and we refer to our README for a more complete description.
Our library stands out because of its security properties. Among the vulnerabilities reported on the original implementation, we integrate countermeasures for most of them, providing a library that is both theoretically and practically secure. We predict that new attacks will be published as the candidates are refined, and expect changes in the code to occur as the security of our library is treated as a continuous process.
We recall that side-channel attacks are high-risk threats and encourage users to prefer libraries with strong implementation security, such as our library, over implementations that lack these guarantees.
In order to provide an insight on the computation and communication costs of our library, we report in the following table the runtime in milliseconds and the outputs size in bytes of our implementation for a recommended security level.
Performance overview for a recommended security level
The relatively large outputs size can impact some applications but is never considered a bottleneck. Furthermore, we show in the following graphs that the performance of current classical security public-key and signature schemes (ECDSA and RSA-OAEP) can be excelled by our implementation. This difference can be explained by the very simple arithmetic the CRYSTALS suite relies on.
Our post-quantum library is easy to use, fast and secure. The practicality of our library should be used as motivation to integrate post-quantum alternatives in your infrastructures, to protect your data well into the foreseeable future without compromising on the performance.
At Kudelski Security, we perform quite a few security and cryptography reviews involving Rust code. Rust support in tooling has been lacking. We’ve developed some tools internally to assist in our reviews, but we were looking for a more general and mature framework that supports multiple languages. Semgrep is great great tool for performing static analysis and its support for multiple programming languages makes it valuable for developers and security professionals alike. Experimental support for Rust was recently added to Semgrep and we will see how to use it by going through a quick example, which will demonstrate some limitations. Then we’ll see how we improved this Rust support increasing usability for the scenarios we and many others find ourselves in everyday.
First we install Semgrep from PyPi:
$ pip install semgrepThen, we create a file named rules.yml with the following contents. This defines a very simple rule that matches those exact two lines defining a variable x and a variable y. We could of course define more complex rules, but this is not the point here:
rules:
- id: my-rule-id
patterns:
- pattern: |
let x = 0;
let y = x * 2;
message: "Found a match for my custom rule."
languages: [ rust ]
severity: WARNINGAfter that, we clone our codebase and run Semgrep on that directory using our custom rules. Semgrep then tells us which parts of the codebase match those rules.
$ git clone [email protected]:ing-bank/threshold-signatures.git
$ cd threshold-signatures
$ semgrep --config rules.yml .
running 1 rules...
semgrep error: invalid pattern
--> rules.yml:4
4 | - pattern: |
5 | let x = 0;
6 | let y = x * 2;
7 | message: "Found a match for my custom rule."
Pattern could not be parsed as a Rust semgrep patternBut this is not working!? Well, it appears that the two lines of Rust code in the semgrep pattern are not valid Rust code by themselves. If you try to compile a Rust source file containing only those two lines, it won’t work.
$ cat test.rs
let x = 0;
let y = x * 2;
$ rustc test.rs
error: expected item, found keyword `let`
--> test.rs:1:1
|
1 | let x = 0;
| ^^^ expected item
error: aborting due to previous errorIndeed, the Rust grammar is defined in a way that this should be wrapped in a function definition to be valid:
$ cat test.rs
fn main() {
let x = 0;
let y = x * 2;
}
$ rustc test.rs
warning: unused variable: `y`
--> test.rs:3:7
|
3 | let y = x * 2;
| ^ help: if this is intentional, prefix it with an underscore: `_y`
|
= note: `#[warn(unused_variables)]` on by default
warning: 1 warning emittedObviously, this produces a warning, but it now compiles.
To parse the pattern defined in our rule, semgrep uses tree-sitter, a parser generator, and more specifically, a modified version of the tree-sitter-rust grammar in the case of Rust source code. Similarly to the Rust compiler, this grammar won’t accept these two lines just by themselves. So we need to update the pattern in our rule:
rules:
- id: my-rule-id
patterns:
- pattern: |
fn $F(...) {
let x = 0;
let y = x * 2;
}
message: "Found a match for my custom rule."
languages: [ rust ]
severity: WARNINGNote that we used some special semgrep pattern syntax here: metavariables ($F) and the ellipsis operator (…). Indeed, Semgrep extends the tree-sitter-rust grammar to support additional language features only for semgrep patterns. This lets us match any function with any parameters without having to hardcode that for every possible case.
Now, if we run Semgrep again with our updated rule, we get some matches in our test.rs file:
$ semgrep --config rules.yml .
running 1 rules...
test.rs
severity:warning rule:my-rule-id: Found a match for my custom rule.
1:fn main() {
2: let x = 0;
3: let y = x * 2;
4:}
ran 1 rules on 20 files: 1 findings
2 files could not be analyzed; run with --verbose for details or run with --strict to exit non-This would be less painful if we could write only those two lines as the pattern for our rule. Additionally, the whole function is being printed out, but we only wanted to search for those two lines. For long functions, this makes it difficult to see which line matched.
Well, this is now possible thanks to a contribution we made to Semgrep:
We extended the tree-sitter-rust grammar to support a list of statements directly as a pattern and we updated the CST to AST mapping to make it work. So it is now possible to write rules directly containing a list of statements:
rules:
- id: my-rule-id
patterns:
- pattern: |
let x = 0;
let y = x * 2;
message: "Found a match for my custom rule."
languages: [ rust ]
severity: WARNINGSemgrep now accepts that pattern and only prints the lines we wanted to match:
$ semgrep --config rules.yml .
running 1 rules...
test.rs
severity:warning rule:my-rule-id: Found a match for my custom rule.
2: let x = 0;
3: let y = x * 2;
ran 1 rules on 20 files: 1 findings
2 files could not be analyzed; run with --verbose for details or run with --strict to exit non-zero if any file cannot be analyzedNote: Since these changes were recently merged, they will only appear in the next semgrep release. You will have to build from source to see them immediately.
We love being able to write rules more easily now and hope this will be helpful to others too. Our hope is that this expanded support leads to quicker identification of bugs and security issues in Rust code. Happy bug hunting.
In this post, we will talk specifically about the work we performed as part of our security assessment of the Multiplier.Finance environment. The public report provided to the Multiplier team will be published within the FAQ section of their web portal.
Executive Summary: There are no unresolved security findings present in the system following our review. There are zero (0) critical, high, or medium vulnerabilities in our final audit report.
The Multiplier.Finance environment is a multi-tier infrastructure within AWS, operated on Binance Smart Chain (BSC), and uses its own governance tokens (bMXX). Even though, they had completed an initial audit of their smart contracts, the Multiplier team wished to bring additional confidence to their community with a completed review of the entire infrastructure and deployment environment.
When Kudelski approaches an engagement such as one of the scope of this, we propose a multiple-phase review because security is always much larger than just a smart contract review. Security of an “App” or a “DAPP” or a “Site” is about the infrastructure, flows, contracts, wallets, and any other ingress and egress flows and control points that could impact the money flow. Even though the math under a blockchain is very solid at this point, contracts and infrastructure are not inherently secure, so it is the sign of a mature project to ask for a complete assessment of their work.
Initially, we performed a re-review of the Smart Contracts as it is always best practice to have multiple reviews of critical components, and our review of the Smart Contract code was the 2nd such review. We found no critical or high risk issues in the smart contracts, and all of our low/informational findings were related to dependencies or minor concerns with style or flow.
The code that we reviewed resides in a public repository at https://github.com/Multiplier-Finance/MCL-SmartContracts.
The reviews are based on the commit hash:
MCL-SmartContracts: cff17d6e07b51e7468a4aba72ae83b309b98d561
All third-party libraries were deemed out-of-scope for this review and are expected to work as designed. Based on the criticality of the dependency, we looked at the current state of the third-party libraries included when necessary.
Our general process for this review included:
Threat Model & Architecture Review
Code Review
Recommendations
We maintained a complete and consistent view across the known components and followed a systematic approach as we conducted the threat model workshop and code review. First threat actors of concern were identified and data flows between the system components were requested. Based upon the understanding of each component from documentation and the interviews, remote follow-up meetings were held with team members of Multiplier.Finance for clarification of any technical or functional details, followed by a code review.
In addition to infrastructure, the following scenarios were in scope for the Threat Model & Assessment:
Upon analysis of the infrastructure, contracts, and control points – we determined that the Multiplier team has handled all of these threat scenarios effectively.
As a result of our code review & assessment, we discovered 0 High, 0 Medium, 3 Low, and 15 Informational findings. The Multiplier team resolved all of these findings to our satisfaction.
We want to thank the Multiplier team for choosing Kudelski Security.
About Multiplier Finance
Multiplier.Finance operates a system known as “Multi-Chain Lend.” Multi-Chain (Lend) is an algorithmic money market system designed to bring secure and unique lending and borrowing opportunities like flash loans onto the Binance Smart Chain. The protocol designs are architected and forked based on Aave with revenue sharing components for liquidity providers and token holders that govern the protocol. bMXX, a BEP-20 token, will be the governance token of Multi-Chain (Lend).
ING (Dutch bank) recently released their own implementation of the popular Gennaro-Goldfeder’18 Threshold ECDSA signature scheme in the form of a library written in Rust. Kudelski Security audited their code, our report is available here. During the audit, we found a potentially serious problem in the protocol itself (not dependent on ING’s implementation, but rather on the need of a security assumption in the original protocol that is not given for granted in many real-world cases.) This problem might allow a single malicious attacker to delete or lock funds and blackmail all other peers.
Threshold signature schemes (TSS) have seen a growing interest and rapid adoption in the last few years, mainly driven by blockchain applications such as Bitcoin. A blockchain transaction (such as the transfer of funds, or the execution of a smart contract) in its basic form is created and verified by the network via a digital signature generated by a private signing key (usually held in a user’s wallet.) This presents a security challenge: anyone with access to the private signing key can issue an (irrevocable) transaction. Clearly an unacceptable risk for highly regulated environments such as large financial institutions, which cannot afford to lose billions of dollars with a single, irreversible transaction executed by a malicious hacker who manages to exfiltrate a high-value key.
TSSs solve this problem by splitting the generation of the signature between N different users, with the possibility of configuring a threshold parameter T such that any subset of T users (among the N authorized ones) is sufficient to generate the signature, but any subset of T-1 or less users is not. This reminds a bit of another similar cryptographic primitive, called “secret sharing schemes” (SSS) but it’s actually different: In a SSS, a subset of T among N users collaborate to have a leader reconstruct a secret (for example, a signing key.) But, after the reconstruction, the leader knows that secret and can further use it however they wish, even without requiring the collaboration of the other users, so it is again a security risk. In a TSS, instead, the signing key is never fully reconstructed! Each one of the T users interact in a complex multi-party computation (MPC) protocol by contributing with a partial signature. Those partial signatures are then recombined by a leader to obtain a single valid signature. The difference is that the leader cannot reuse the data collected to generate a different signature, so the scheme is highly interactive and requires different rounds of complex, interlocking encryption, signatures, and zero-knowledge subprotocols.
The appeal of TSS for many applications is that they are backward-compatible with already deployed signature schemes: the signature generated by a TSS is indistinguishable by a “normal” signature in respect to a certain public key, so at the end the verifying user does not care whether the signature was generated in a “standard” way or in a TSS way, because there is only one single public key to check against, and the verification algorithm is unmodified. So, for example, it is not necessary to modify the Bitcoin protocol to support a new type of signatures, it is just sufficient to add TSS support client-side.
Not all signature schemes are equivalent in respect to “TSS-ization” though. Certain schemes, such as BLS or Schnorr signatures, are much easier to implement in a TSS way. Others, such as ECDSA, are much more complex. It just happens by bad luck that ECDSA is the currently adopted standard in Bitcoin and many other important blockchains. Existing TSS schemes for ECDSA are quite difficult to analyse and implement and they are prone to issues, either in their design or code.
During our audit for ING we stumbled upon one of these issues. ING’s library implements GG18, one of the most popular TSS schemes for ECDSA. One of the features of GG18 is the “key resharing protocol”, which allows an old committee of peers to refresh the shares of the secret key across a new committee (for example, if it is necessary to add new members, or to remove some.) The key resharing protocol is a delicate procedure that has been covered by many recent attacks. One of these attacks, the “forget-and-forgive”, is described as:
The proposed mitigation is:
This mitigation is implemented correctly by ING. However, we found that such mitigation is insufficient – and might actually make things worse – if a robust broadcast channel is not available, by allowing a single malicious attacker to delete or lock funds and blackmail all other peers.
A robust broadcast channel is a reliable way of broadcasting messages in such a way that all parties receive the same broadcast message. This is easily achieved if a trusted third party relay is available, but for the general case of peer-to-peer networks, it is not always trivial. For example, the naive solution of sending a broadcast message as N distinct direct point-to-point connections is clearly not robust, because a malicious sender could transmit a message X to certain peers and a different message Y to other nodes.
This is exactly the scenario that enables a devastating attack in the GG18 resharing protocol. Let’s say a group of 4 peers (A, B, C, D) with threshold value 3 (any 3 of them is necessary and sufficient to sign) wants to add a fifth peer E to the committee (still with threshold value 3). So they start the resharing protocol, and in order to avoid the “forget-and-forgive” attack they conclude the protocol with the final round described in the mitigation above.
However, E is malicious. After the resharing protocol concludes, E crafts different messages for different peers instead of broadcasting a final “ACK”:
Now see what happens: A and B think that everything went fine, so they discard the secret key material (their “shares”) that was related to the old committee configuration, and migrate to the shares for the new committee configuration. C and D, however, follow the proposed mitigation to the “forget-and-forgive” attack: they assume that something went wrong and will not save the new shares to disk, falling back to the old shares. And now we have a problem: a single malicious adversary, E, has managed to “segment” the group of peers into two committees, one old and one new, where none of them has enough information to reconstruct the secret without E’s collaboration! So Eve can blackmail the committee, withholding all the funds associated to the wallet being shared.
Under the right circumstances, this attack can be devastating. It is important to notice that this has nothing to do with ING’s implementation, nor with a flaw in the security proof of GG18, but rather with the security model not taking into account real-world implementations of the communication channel. Countermeasures against these kind of attack can only be implemented at an application level, so developers have to be careful when adopting existing GG18 solutions.
We are grateful to ING for the trust they gave us, and found very stimulating working together with their tech team.
Proton Blockchain – “The Payment Blockchain” is a software blockchain developed by Metallicus, Inc., based on the foundation of EOSIO which identifies itself as having advantages over blockchain solutions due to its Speed, unique Identity ID, Signing system, and Fee structure.
During the initial phase of the project, we recognized that the main code base is comprised of a fork of the EOSIO block chain project with the tag v1.9.1.
This code was de-scoped from the assessment as we recognized that the EOSIO project is well used and therefore was essentially previously reviewed. The project did use the forked version in the Proton Chain repository as a reference when needed.
In this post, we will talk specifically about the work we performed as part of our security assessment for the Metallicus team. For a more in-depth overview of Proton and its roadmap, you can read about it on the Proton blog.
The source code for the project was supplied by Metallicus through the GitHub repository at https://github.com/ProtonProtocol and specifically under the proton.contracts project.
The assessment was conducted by the Kudelski Security Team, with the tests taking place in the 4th Quarter of 2020 and focused on the following objectives:
A separate engagement, also performed in the 4th Quarter of 2020 was a review of the Proton Swap tool, which is a tool allows users to swap an XPR based on the Ethereum blockchain to mainnet XPR – which opens all other functions of the Proton Blockchain.
The findings during the review were less than many of our other projects of similar size and complexity, with the findings being mostly initialization issues, arithmetic operational checks, resource allocation and code clarity on permission checks.
We believe that the reason for the rather low severity of the findings is due to the detailed threat modeling, discussion, and walkthroughs with the core development team. In addition, detailed security assessments have been performed on EOSIO and that also contributed to a lack of findings, but we recommended to the project team that they continue to monitor bug fixes on the EOSIO core and incorporate those updates and bug fixes.
In this code assessment, we performed the following tasks:
The review for this project was performed using manual methods and utilizing the experience of the reviewer. No dynamic testing was performed, only the use of custom-built scripts and tools were used to assist the reviewer during the testing.
Code Safety
We analyzed the provided code, checking for issues related to the following categories:
Cryptography
We analyzed the cryptographic primitives and components as well as their implementation. We checked in particular:
Technical Specification Matching
We analyzed the provided documentation and checked that the code matches the specification. We checked for things such as:
As a result of this assessment, we did not find any critical shortcomings in the reviewed components.
Metallicus quickly patched all the problems we identified and let us review their changes to confirm their effectiveness.
Notice that we did not find any evidence of malicious intent, flawed logic or potential backdoors in the codebase.
We would like to thank Metallicus, Inc. for trusting us, for their availability and the pleasant collaboration throughout the assessment!
This blog post is about benchmarking the IoT prototype we have been building for the FENTEC project, using functional encryption. For more information, please see the two previous blog posts we wrote on this topic:
The prototype is composed of three elements: a camera, a gateway, and a backend. This prototype is based on ffmpeg and is implemented as 3 bitstream filters, one for each element in the system.
The camera captures and encodes video in H.264 format. It extracts the motion vectors of the H.264-encoded stream and encrypts them using functional encryption thanks to the CiFEr library. Those encrypted motion vectors are then bundled as side data, alongside the AES encrypted video stream. This is possible because motion vectors are stored in H.264 Network Abstraction Layer (NAL) units of type H264_NAL_SEI and the image data of the video itself is stored in NAL units of type H264_NAL_SLICE and H264_NAL_IDR_SLICE. These different NAL units can therefore be encrypted differently without causing any problems. The SEI messages are additional messages that can carry any data format and must not be video-related. Therefore, we store the functionally encrypted motion vectors in these. The video image data is stored in the 2 other types of NAL units mentioned above. Symmetrically encrypting NAL units of that type is enough to make the video unreadable by anyone not possessing the encryption key.
The gateway uses the corresponding functional encryption key to evaluate whether there is motion or not within a group a video frames. For each group of frames, if there is motion, the gateway forwards the symmetrically encrypted group of frames to the backend. Thus, the amount of data transmitted over the wire is reduced to the interesting segments, where there is motion in the video. Since the video stream is encrypted, the gateway cannot determine anything about the image data inside the video, and therefore does not need to be trusted. The untrusted gateway can perform the computationally intensive motion detection on behalf of the potentially low-powered camera.
Unlike the gateway, the backend can decrypt the received AES encrypted video stream because it knows the symmetric encryption key. The decrypted video stream contains only frames of the original video where motion was detected by the gateway. The backend is able to play the video.
We measure how the number of motion vectors used affects the number of frames that can be processed per second on the camera side and on the gateway side. We also measure how turning on functional encryption of the motion vectors affects performance. In any given frame, there are a certain number of motion vectors. We do not need to use all of them but we are interested in knowing what is the performance impact of using a certain number of these.
We measure how the additional side-data size varies as the number of motion vectors used changes. Additionally, does functional encryption of the side-data have an impact on the output video sent to the gateway?
The gateway removes the segments in the video stream where no significant movement occurs. A segment is a group of pictures (GOP). We define a threshold maximum value for the sum of the motion vector norms and call it the GOP threshold. If the computed value exceeds the GOP threshold, the gateway considers that movement is detected. In that case, the segment is forwarded to the backend. Otherwise, it is removed. We measure the size of the stream received by the backend and compare it to the size of the original input video produced by the camera to see how much traffic can be spared.
The benchmarks were run on a single machine, running all three elements of the system (camera, gateway and backend). This machine is a five year old desktop computer with an Intel i7-6700k CPU clocked at 4.0 GHz, with 4 cores and 8 threads. It also has 32 GB of memory.
All measures were performed with a pre-recorded 1080p H.264 video at 30 frames per second as input for the camera.
Figure 1 shows the number of frames per second for a given number of motion vectors used, on the camera and on the gateway, and encrypted motion vectors.
We can see that the camera outputs more frames per second for smaller numbers of motion vectors (up to 95). Then, the gateway and the camera appear to be able to output similar FPS rates, for larger numbers of motion vectors.
The camera is still able to deliver a stable 30 frames per second with 40 motion vectors. The gateway drops below 30 frames per second if the number of motion vectors is greater than 13.
With a small, but large enough number of motion vectors of 3, the camera outputs 233 FPS and the gateway is able to output 67 FPS. Therefore, it would even be possible to process a 60 frame per second video in real-time without any slowdown, with encryption of the motion vectors.
The results of the same measures, but with motion vector encryption disabled are shown in Figure 2.
When motion vector encryption is disabled, the camera and gateway do not seem to be affected by the number of motion vectors and deliver a stable performance of 419 FPS on average.
Motion vectors compose the side-data sent alongside the video stream from the camera to the gateway. The overhead size added to the overall stream for a given number of motion vectors used is shown in Figure 3.
We see that for a small number of motion vectors (1 to 10), when encryption is disabled, the overhead size is roughly 10%, and in the 10%-20% range with encryption. This is still acceptable. However, as the number of motion vectors grow to greater numbers, such as 1500, the overhead without encryption is 41%, and 1431% with encryption. It is therefore suggested to use a small number of motion vectors to minimize the overhead. This is not a problem since motion detection can be performed properly with only 3 motion vectors. With 3 motion vectors, the overhead is only 13% with encryption, and 9% without encryption. Thus, encryption adds very little overhead with a small number of motion vectors.
It was empirically observed that, as soon as the backend system has started playing the gateway stream, there is no significant delay other than the one due to network latency. If the number of motion vectors is increased, it may happen that the camera or the gateway become unable to process the stream fast enough. Indeed, since the source video is 30 frames per second, if the gateway cannot process frames at that rate, then the backend system will receive frames slower than the video playback speed. When that happens, the video may play slower than expected. As previously shown in Figure 1 above, we have seen that the maximum value for the number of motion vectors, for which processing can happen at least at 30 frames per second, is 40 for the camera and 13 for the gateway. However, only 3 motion vectors are sufficient for proper movement detection. There is therefore plenty of room for processing videos with higher frame rates.
We used a 10MB video as input and measured the size of the output video sent to the backend with various values for the Group of Picture (GOP) threshold. The same measures were performed with 3, 6 and 9 motion vectors. The results are shown in Figure 4.
As expected, the greater the number of motion vectors used, the greater the GOP threshold is required for the output stream size to start dropping. Indeed, since the sum of the norms of the motion vectors for a GOP is compared to the GOP threshold to decide whether to forward that GOP to the backend, the result simply confirms that motion detection is performed.
The lines of the plot have another use, however. They clearly show the minimum GOP threshold that should be used so that movement is detected. For 3 motion vectors, the threshold should be set to at least 70. For 6 motion vectors, the threshold should be greater than 105. Finally, for 9 motion vectors, the GOP threshold should have a value greater than 125 for motion to be detected.
This also confirms that motion is properly detected with as little as 3 motion vectors.
Encryption of the motion vectors was successfully added to the prototype. We have shown that such encryption adds little overhead with small numbers of motion vectors and allows to stream a 30 fps 1080p video in real time. There is even room left for streaming up to 60 frames per second without slowdowns according to our measures.